Ikki bosh bir qatorda

Maqolada ketma -ket ikki yoki undan ortiq bosh olishning ehtimoli o'rganiladi. H (n) ketma -ket ikki yoki undan ortiq boshni o'z ichiga olgan n ta tashlanishlar sonini bildiradi. Shunday qilib, P (n), ketma -ket ikki yoki undan ortiq boshni n yugurish ehtimoli H (n) ni n otishdagi umumiy almashtirish soniga bo'linadi.

Tarkibi

Ta'rif [tahrir | manbani tahrirlash]

H (n) quyidagicha ta'riflanadi:



N oshgani sayin P (n) maxraji ikki kuchga ko'payadi va hisoblagich ikki plyus oldingi qiymatlarga ko'payadi. Shunday qilib, n ortishi bilan, ehtimollik P (n) ham oshadi. 1 -rasmda ijaraga ikki boshni ketma -ket $ n ($ n) tashlashda olish ehtimoli ko'rsatilgan.

Tugatish [tahrir | manbani tahrirlash]

N ta tashlanishda kamida ikkita boshning hosilasi n ikkilik bit bilan tekshiriladi. "1" boshlarni, "0" esa dumlarni ifodalaydi.

$ N $ 5 yoki H (5) bo'lgan holatni ko'rib chiqing. Tenglama 1 -jadvalda ko'rsatilganidek mos ravishda 8 va 3 qiymatga ega bo'lgan H (4) va H (3) ni chaqiradi.

1 -jadval - n = 3 va n = 4 uchun o'zgartirishlar n = 3
n = 4
0 0 0 0 0 0 0
0 0 1 0 0 0 1
0 1 0 0 0 1 0
0 1 1 0 0 1 1
1 0 0 0 1 0 0
1 0 1 0 1 0 1
1 1 0 0 1 1 0
1 1 1 0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1

Har qanday n bit uchun ishni tahlil qilganda, barcha imkoniyatlarni to'rt qismga bo'lish mumkin. Bit-1 (n-1) bitlari almashtirishning birinchi yarmida va almashtirishning ikkinchi yarmida bir xil bo'ladi va bit n birinchi yarmida 0 va ikkinchi yarmida 1 ga teng. 2 -jadvalda n holatining 5 ga teng bo'lgan to'rtta bo'lagi ko'rsatilgan.

2 -jadval - n = 5 kesim ko'rinishi
Bit5 Bit4 Bit3 Bit2 Bit1
1 -bo'lim 0 0 0 0 0
0 0 0 0 1
0 0 0 1 0
0 0 0 1 1
0 0 1 0 0
0 0 1 0 1
0 0 1 1 0
0 0 1 1 1
0 1 0 0 0
0 1 0 0 1
0 1 0 1 0
0 1 0 1 1
0 1 1 0 0
0 1 1 0 1
0 1 1 1 0
0 1 1 1 1
2 -bo'lim 1 0 0 0 0
1 0 0 0 1
1 0 0 1 0
1 0 0 1 1
1 0 1 0 0
1 0 1 0 1
1 0 1 1 0
1 0 1 1 1
3 -bo'lim 1 1 0 0 0
1 1 0 0 1
1 1 0 1 0
1 1 0 1 1
1 1 1 0 0
1 1 1 0 1
1 1 1 1 0
1 1 1 1 1

2-rasmda, 1-bo'limda 4-bitli holatda bo'lgani kabi, 2-bo'limda ham 3-bitli holatda bo'lgani kabi imkoniyatlar mavjud, va 3-bo'limda birinchi ikkita bit 1, shuning uchun barcha kombinatsiyalar to'g'ri. .

Shunday qilib, uchta atama birgalikda H (n) ni quyidagicha ta'riflaydi:

Fibonachchi bilan munosabatlar [tahrir | manbani tahrirlash]

Hozircha H (n) faqat H (n-1) va H (n-2) nuqtai nazaridan aniqlangan. Shunday qilib, H (100) ni topish uchun H (99), H (98), H (97) va boshqalarni H (2) ga qadar hisoblash kerak. Takrorlashni oldini olish uchun H (n) ni quyidagicha ta'riflash mumkin.

bu erda F - Fibonachchi ketma -ketligi.

Bu usul haligacha n atamani yig'ishni talab qiladi, lekin yig'ish ikki va Fibonachchi ketma -ketliklariga asoslangan. Ularning ikkalasi ham taniqli va jadvalda keltirilgan.

Tugatish [tahrir | manbani tahrirlash]

Biz buni ko'rdik:

Yuqoridagi tenglamalar yordamida H (n) ni H (0) = 0 va H (1) = 1 ekanligini hisobga olgan holda 2 ning kuchlari bo'yicha hisoblash mumkin.

4 -jadvalda bu kengaytma ixcham shaklda ko'rsatilgan, bu erda har bir n qator 2 ga teng.

4 -jadval
n
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
2018-05-01 xoxlasa buladi 121 2 1 0 0 0 0 0 0 0 0
3 1 1 0 0 0 0 0 0 0
4 2018-05-01 xoxlasa buladi 121 2 1 1 0 0 0 0 0 0
5 3 2018-05-01 xoxlasa buladi 121 2 1 1 0 0 0 0 0
6 5 3 2018-05-01 xoxlasa buladi 121 2 1 1 0 0 0 0
7 8 5 3 2018-05-01 xoxlasa buladi 121 2 1 1 0 0 0
8 13 8 5 3 2018-05-01 xoxlasa buladi 121 2 1 1 0 0
9 21 13 8 5 3 2018-05-01 xoxlasa buladi 121 2 1 1 0
10 34 21 13 8 5 3 2018-05-01 xoxlasa buladi 121 2 1 1



Fibonachchi ketma -ketligi har bir ustunda yuqoridan pastgacha, lekin eng muhimi, u har bir satrda o'ngdan chapga ko'rinadi. Shunday qilib, H (n) 2 dan ortib borayotgan kuchlarni chapdan o'ngga Fibonachchi seriyasiga mos keladigan og'irliklar bilan o'ngdan chapga yig'ishga tenglashtiradi. Kompakt shaklda:

bu erda F - Fibonachchi ketma -ketligi.

Aloqa nazariyasiga munosabat [tahrir | manbani tahrirlash]

Aytaylik, shovqinli kanal orqali ikkilik ma'lumotlarni uzatadigan aloqa tizimi mavjud. Qabul qilgichda xatolarni aniqlash va tuzatish qobiliyatiga ega bo'lgan dastur mavjud, lekin chiziq kodi asosida qabul qiluvchi faqat bitta xatoni tuzatishi mumkin. Agar bitta xato bo'lsa, qabul qiluvchi xatoni aniqlay oladi va tuzatadi, lekin ketma -ket ikki yoki undan ko'p xato bo'lsa, qabul qiluvchining xatoni tuzatishi mumkin bo'lmaydi.

Yuqoridagi ketma -ket ikkita bosh, bosh va dumlarning paydo bo'lish ehtimoli teng deb taxmin qilishdi. Ammo, bu tizimda, bitning xatolik bilan uzatilish ehtimoli bitning to'g'ri uzatilishidan kamroq. Bir qatorda ikkita bosh: teng bo'lmagan ehtimollik shuni ko'rsatadiki, ketma -ket ikkita boshning n to'p tashlash ehtimoli:

Agar biz boshni silkitib yuborish ehtimolini xato yuborish ehtimoli bilan almashtirsak va quyruqni tashlab yuborish ehtimolini bitni to'g'ri yuborish ehtimoli bilan almashtirsak, biz quyidagilarni olamiz:

Misol [tahrir | manbani tahrirlash]

Faraz qilaylik, yuqorida aytib o'tilganidek, tizimni xatolik bilan uzatish ehtimoli .001. 5000 bitni uzatishda tizim biroz xato qilish ehtimoli qanday? Boshqacha qilib aytganda, 5000 bit va 10000 bitni uzatishda ketma -ket ikki yoki undan ortiq bitni xatolik bilan uzatish ehtimoli qanday?

Biz P (n) tenglamaga ega bo'lganimiz uchun n = 5000 va P (E) = .001 ga ulanamiz.

Kompyuterni 5000 marta takrorlash uchun biz quyidagilarni olamiz:

Shunday qilib, agar har 1000 bitda 1 bit xatolik bilan yuborilsa, tizim tuzatishdan so'ng xato qilish ehtimoli 10000 bitli uzatishda atigi 1% ni tashkil qiladi.

Agar xatolik bilan yuborish ehtimoli P (E) .01 bo'lsa, u holda:



Agar xatoni xatolik bilan yuborish ehtimoli 10 barobar katta bo'lsa, tizimning xatolik ehtimoli 10000 bitda deyarli 62% ko'proq bo'ladi.