www.wikidata.uk-ua.nina.az

Система числення Фібоначчі змішана система числення для цілих чисел на основі чисел Фібоначчі F 2 1 F 2 1 F 3 2 displays

Система числення Фібоначчі

Система числення Фібоначчі — змішана система числення для цілих чисел на основі чисел Фібоначчі , , , , і т. д.

Число Запис

у СЧФ

код

Фібоначчі

0 0……0
F2=1 1 11
F3=2 10 011
F4=3 100 0011
4 101 1011
F5=5 1000 00011
6 1001 10011
7 1010 01011
F6=8 10000 000011
…
Fn − 1   101010… …0101011  
Fn 10……00 00……011
Fn + 1 10……01 10……011

Подання натуральних чисел

Будь-яке невід'ємне ціле число можна єдиним чином подати послідовністю бітів () так що , причому послідовність містить лише скінченне число одиниць, і не має пар сусідніх одиниць: . За винятком останньої властивості, дане подання аналогічне двійковій системі числення .

Обґрунтування

В основі лежить теорема Цекендорфа: будь-яке невід'ємне ціле число можна єдиним чином подати у вигляді суми деякого набору чисел Фібоначчі з індексами більшими від одиниці, який не містить пар сусідніх чисел Фібоначчі.

Доведення існування легко провести за індукцією. Будь-яке ціле число потрапить у проміжок між двома сусідніми числами Фібоначчі, тобто для деякого виконується нерівність: . Таким чином, , де , Так що розкладання числа вже не буде містити доданка .

Використання

Юпана

Юпана

Припускають, що деякі різновиди юпани (абака інків) використовували систему числення Фібоначчі, щоб мінімізувати необхідне для обчислень число зерен.

У теорії інформації

На основі системи числення Фібоначчі будується код (кодування) Фібоначчі — універсальний код[ru] для натуральних чисел (1,   2,   3 …), який використовує послідовності бітів. Оскільки комбінація   11 заборонена в системі числення Фібоначчі, її можна використовувати як маркер кінця запису.

Для складання коду Фібоначчі за записом числа в системі числення Фібоначчі слід переписати цифри у зворотному порядку (так, що старша одиниця виявляється останнім символом) і приписати в кінці ще раз   1 (див. таблицю). Тобто, кодова послідовність має вигляд:

де n — номер найстаршого розряду з одиницею.

Арифметика

Додавання чисел у позиційних системах числення виконується з використанням переносу, що дозволяє усувати наслідки переповнення розряду. Наприклад, у двійковій системі: 01 + 01 = 02 = 10.

У системі числення Фібоначчі ситуація складніша:

  • По-перше, вага старших розрядів не є кратною вазі розряду, з якого виконується перенесення. При додаванні двох одиниць в одному розряді потрібне перенесення не тільки вліво, але й управо: 0200 = 1001. При перенесенні у відсутні розряди ε1 і ε0 слід пам'ятати, що F1=1=F2 і F0=0.
  • По-друге, потрібно позбавлятися від сусідніх одиниць: 011 = 100. Правило для розкриття двійок є наслідком цієї рівності: 0200 = 0100 + 0011 = 0111 = 1001.

Узагальнення на дійсні числа

Число Подання
через степінь  
1       1
2      10,01
3     100,01
4     101,01
5    1000,1001
6    1010,0001
7   10000,0001
8   10001,0001
9   10010,0101
10   10100,0101
11   10101,0101
12 100000,101001
13 100010,001001
14 100100,001001

Схоже влаштована позиційна система числення з ірраціональною основою, рівною золотому перетину .

Будь-яке дійсне число з відрізка допускає розкладання в ряд через від'ємні степені золотого перетину:

де має ту ж властивість відсутності сусідніх одиниць. Коефіцієнти знаходяться послідовним порівнянням з  — золотим перетином відрізка , відніманням (якщо ) і множенням на . З цього неважко бачити, що будь-яке невід'ємне дійсне число допускає розкладання:

де N таке, що . Зрозуміло, слід вважати, що для всіх .

Ці формули повністю аналогічні формулам для звичайних позиційних систем з цілими основами. Виявляється, що будь-яке невід'ємне ціле число (і, більш загально, кожен невід'ємний елемент кільця ) має подання лише зі скінченною кількістю одиниць, тобто у вигляді скінченної суми неповторюваних степенів золотого перетину.

Аналогія між числами Фібоначчі і степенями золотого перетину заснована на однаковій формі тотожностей:

які дозволяють усунення сусідніх одиниць. Прямого зв'язку між поданням натуральних чисел в системі золотого перетину і в системі Фібоначчі немає.

Правила додавання аналогічні показаним вище з тією поправкою, що перенесення в бік молодших розрядів поширюється без обмеження. У даній системі числення можна виконувати й множення.

Множення Фібоначчі

Для цілих чисел і можна визначити «множення»

аналогічне множенню чисел у двійковій системі числення.

Зрозуміло, що дана операція не є справжнім множенням чисел, і виражається формулою:

де  — ціла частина,  — золотий перетин .

Ця операція має асоціативність, що вперше зауважив Дональд Кнут. Слід зазначити, що інше «множення» відрізняється лише зсувом на два розряди, вже не є асоціативним.

Примітки

  1. . Архів оригіналу за 6 травня 2017. Процитовано 15 грудня 2019. 
  2. Antonio Aimi, Nicolino De Pasquale. . Процитовано 12 грудня 2009. 
  3. Система числення на основі золотого перетину[en]
  4. послідовність A101330 з Онлайн енциклопедії послідовностей цілих чисел, OEIS(англ.), Теорема Цекендорфа
  5. Notes on the Fibonacci circle and arroba products(англ.)
  6. D. E. Knuth.  // Applied Mathematics Letters. — 1988. — Т. 1, № 1. — С. 57—60. — DOI:10.1016/0893-9659(88)90176-0.

Література

  • Воробьёв Н. Н. Числа Фибоначчи. — Наука, 1978. — Т. 39. — (Популярные лекции по математике)(рос.)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Sistema chislennya Fibonachchi zmishana sistema chislennya dlya cilih chisel na osnovi chisel Fibonachchi F 2 1 F 2 1 F 3 2 displaystyle F 3 2 F 4 3 displaystyle F 4 3 F 5 5 displaystyle F 5 5 F 6 8 displaystyle F 6 8 i t d Chislo Zapis u SChF kod Fibonachchi0 0 0F2 1 1 11F3 2 10 011F4 3 100 00114 101 1011F5 5 1000 000116 1001 100117 1010 01011F6 8 10000 000011 Fn 1 101010 0101011 Fn 10 00 00 011Fn 1 10 01 10 011Zmist 1 Podannya naturalnih chisel 1 1 Obgruntuvannya 1 2 Vikoristannya 1 2 1 Yupana 1 2 2 U teoriyi informaciyi 1 3 Arifmetika 2 Uzagalnennya na dijsni chisla 3 Mnozhennya Fibonachchi 4 Primitki 5 LiteraturaPodannya naturalnih chisel RedaguvatiBud yake nevid yemne cile chislo a a mozhna yedinim chinom podati poslidovnistyu bitiv e k e 4 e 3 e 2 displaystyle dots varepsilon k dots varepsilon 4 varepsilon 3 varepsilon 2 e k 0 1 displaystyle varepsilon k in 0 1 tak sho a k e k F k displaystyle a sum k varepsilon k F k prichomu poslidovnist e k displaystyle varepsilon k mistit lishe skinchenne chislo odinic i ne maye par susidnih odinic k 2 e k 1 e k 1 0 displaystyle forall k geq 2 varepsilon k 1 Rightarrow varepsilon k 1 0 Za vinyatkom ostannoyi vlastivosti dane podannya analogichne dvijkovij sistemi chislennya Obgruntuvannya Redaguvati V osnovi lezhit teorema Cekendorfa 1 bud yake nevid yemne cile chislo mozhna yedinim chinom podati u viglyadi sumi deyakogo naboru chisel Fibonachchi z indeksami bilshimi vid odinici yakij ne mistit par susidnih chisel Fibonachchi Dovedennya isnuvannya legko provesti za indukciyeyu Bud yake cile chislo a 1 displaystyle a geq 1 potrapit u promizhok mizh dvoma susidnimi chislami Fibonachchi tobto dlya deyakogo n 2 displaystyle n geq 2 vikonuyetsya nerivnist F n a lt F n 1 displaystyle F n leq a lt F n 1 Takim chinom a F n a displaystyle a F n a de a a F n lt F n 1 displaystyle a a F n lt F n 1 Tak sho rozkladannya chisla a displaystyle a vzhe ne bude mistiti dodanka F n 1 displaystyle F n 1 Vikoristannya Redaguvati Yupana Redaguvati YupanaPripuskayut sho deyaki riznovidi yupani abaka inkiv vikoristovuvali sistemu chislennya Fibonachchi shob minimizuvati neobhidne dlya obchislen chislo zeren 2 U teoriyi informaciyi Redaguvati Na osnovi sistemi chislennya Fibonachchi buduyetsya kod koduvannya Fibonachchi universalnij kod ru dlya naturalnih chisel 1 2 3 yakij vikoristovuye poslidovnosti bitiv Oskilki kombinaciya 11 zaboronena v sistemi chislennya Fibonachchi yiyi mozhna vikoristovuvati yak marker kincya zapisu Dlya skladannya kodu Fibonachchi za zapisom chisla v sistemi chislennya Fibonachchi slid perepisati cifri u zvorotnomu poryadku tak sho starsha odinicya viyavlyayetsya ostannim simvolom i pripisati v kinci she raz 1 div tablicyu Tobto kodova poslidovnist maye viglyad e2e3 en1 de n nomer najstarshogo rozryadu z odiniceyu Arifmetika Redaguvati Dodavannya chisel u pozicijnih sistemah chislennya vikonuyetsya z vikoristannyam perenosu sho dozvolyaye usuvati naslidki perepovnennya rozryadu Napriklad u dvijkovij sistemi 01 01 02 10 U sistemi chislennya Fibonachchi situaciya skladnisha Po pershe vaga starshih rozryadiv ne ye kratnoyu vazi rozryadu z yakogo vikonuyetsya perenesennya Pri dodavanni dvoh odinic v odnomu rozryadi potribne perenesennya ne tilki vlivo ale j upravo 02 00 1001 Pri perenesenni u vidsutni rozryadi e1 i e0 slid pam yatati sho F1 1 F2 i F0 0 Po druge potribno pozbavlyatisya vid susidnih odinic 011 100 Pravilo dlya rozkrittya dvijok ye naslidkom ciyeyi rivnosti 02 00 0100 0011 011 1 1001 Uzagalnennya na dijsni chisla RedaguvatiChislo Podannya cherez stepin f varphi 1 12 10 013 100 014 101 015 1000 10016 1010 00017 10000 00018 10001 00019 10010 010110 10100 010111 10101 010112 100000 10100113 100010 00100114 100100 001001Shozhe vlashtovana pozicijna sistema chislennya z irracionalnoyu osnovoyu rivnoyu zolotomu peretinu f 1 5 2 displaystyle varphi 1 sqrt 5 2 Bud yake dijsne chislo x x z vidrizka 0 1 0 1 dopuskaye rozkladannya v ryad cherez vid yemni stepeni zolotogo peretinu x k 1 e k f k e k 0 1 displaystyle x sum k 1 infty varepsilon k varphi k qquad varepsilon k in 0 1 de e k displaystyle left varepsilon k right maye tu zh vlastivist vidsutnosti susidnih odinic Koeficiyenti znahodyatsya poslidovnim porivnyannyam x x z f 1 displaystyle varphi 1 zolotim peretinom vidrizka 0 1 0 1 vidnimannyam f 1 displaystyle varphi 1 yaksho e k 1 displaystyle varepsilon k 1 i mnozhennyam na f varphi Z cogo nevazhko bachiti sho bud yake nevid yemne dijsne chislo dopuskaye rozkladannya a k N 1 e k f k displaystyle a sum k N 1 infty varepsilon k varphi k de N take sho a lt f N displaystyle a lt varphi N Zrozumilo slid vvazhati sho e k 0 displaystyle varepsilon k 0 dlya vsih k N displaystyle k geqslant N Ci formuli povnistyu analogichni formulam dlya zvichajnih pozicijnih sistem z cilimi osnovami Viyavlyayetsya sho bud yake nevid yemne cile chislo i bilsh zagalno kozhen nevid yemnij element kilcya Z f Z displaystyle mathbb Z varphi mathbb Z maye podannya lishe zi skinchennoyu kilkistyu odinic tobto u viglyadi skinchennoyi sumi nepovtoryuvanih stepeniv zolotogo peretinu 3 Analogiya mizh chislami Fibonachchi i stepenyami zolotogo peretinu zasnovana na odnakovij formi totozhnostej F k F k 1 F k 2 displaystyle F k F k 1 F k 2 f k f k 1 f k 2 displaystyle varphi k varphi k 1 varphi k 2 yaki dozvolyayut usunennya susidnih odinic Pryamogo zv yazku mizh podannyam naturalnih chisel v sistemi zolotogo peretinu i v sistemi Fibonachchi nemaye Pravila dodavannya analogichni pokazanim vishe z tiyeyu popravkoyu sho perenesennya v bik molodshih rozryadiv poshiryuyetsya bez obmezhennya U danij sistemi chislennya mozhna vikonuvati j mnozhennya Mnozhennya Fibonachchi RedaguvatiDlya cilih chisel a k e k F k displaystyle a sum k varepsilon k F k i b l z l F l displaystyle b sum l zeta l F l mozhna viznachiti mnozhennya 4 a b k l e k z l F k l displaystyle a circ b sum k l varepsilon k zeta l F k l analogichne mnozhennyu chisel u dvijkovij sistemi chislennya Zrozumilo sho dana operaciya ne ye spravzhnim mnozhennyam chisel i virazhayetsya formuloyu 5 a b 3 a b a b 1 f 2 b a 1 f 2 displaystyle a circ b 3ab a lfloor b 1 varphi 2 rfloor b lfloor a 1 varphi 2 rfloor de displaystyle lfloor cdot rfloor cila chastina f 1 5 2 displaystyle varphi frac 1 sqrt 5 2 zolotij peretin Cya operaciya maye asociativnist sho vpershe zauvazhiv Donald Knut 6 Slid zaznachiti sho inshe mnozhennya k l e k z l F k l 2 displaystyle sum k l varepsilon k zeta l F k l 2 vidriznyayetsya lishe zsuvom na dva rozryadi vzhe ne ye asociativnim Primitki Redaguvati Eduard Cekendorf Arhiv originalu za 6 travnya 2017 Procitovano 15 grudnya 2019 Antonio Aimi Nicolino De Pasquale Andean Calculators Procitovano 12 grudnya 2009 Sistema chislennya na osnovi zolotogo peretinu en poslidovnist A101330 z Onlajn enciklopediyi poslidovnostej cilih chisel OEIS angl Teorema Cekendorfa Notes on the Fibonacci circle and arroba products angl D E Knuth Applied Mathematics Letters 1988 T 1 1 S 57 60 DOI 10 1016 0893 9659 88 90176 0 Literatura RedaguvatiVorobyov N N Chisla Fibonachchi Nauka 1978 T 39 Populyarnye lekcii po matematike ros Sistema schisleniya Fibonachchi realizaciya na C 2014 Arhivovano z dzherela 16 zhovtnya 2014 ros Otrimano z https uk wikipedia org w index php title Sistema chislennya Fibonachchi amp oldid 37308166