Фибоначчи шифр – Находим N’е число Фибоначчи тремя способами за приемлемое время: основы динамического программирования

Код Фибоначчи Википедия

Фибоначчиева система счисления — смешанная система счисления для целых чисел на основе чисел Фибоначчи F2=1, F3=2, F4=3, F5=5, F6=8 и т. д.

Число Запись
в
Код
Фибоначчи
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

Представление натуральных чисел

Любое неотрицательное целое число a{\displaystyle a} можно единственным образом представить последовательностью битов …εk…ε4ε3ε2 (εk∈{0,1}{\displaystyle \varepsilon _{k}\in \{0,1\}}) так, что a=∑kεkFk{\displaystyle a=\sum _{k}\varepsilon _{k}F_{k}}, причём последовательность {εk} содержит лишь конечное число единиц, и не имеет пар соседних единиц: ∀k≥2:(εk=1)⇒(εk+1=0){\displaystyle \forall k\geq 2:(\varepsilon _{k}=1)\Rightarrow (\varepsilon _{k+1}=0)}. За исключением последнего свойства, данное представление аналогично двоичной системе счисления.

Обоснование

В основе лежит теорема Цекендорфа[1] — любое неотрицательное целое число единственным образом представимо в виде суммы некоторого набора чисел Фибоначчи с индексами больше единицы, не содержащего пар соседних чисел Фибоначчи.

Доказательство существования легко провести по индукции. Любое целое число a≥1{\displaystyle a\geq 1} попадёт в промежуток между двумя соседними числами Фибоначчи, то есть для некоторого n≥2{\displaystyle n\geq 2} верно неравенство: Fn≤a<Fn+1{\displaystyle F_{n}\leq a<F_{n+1}}. Таким образом, a=Fn+a′{\displaystyle a=F_{n}+a’}, где a′=a−Fn < Fn−1{\displaystyle a’=a-F_{n}\ <\ F_{n-1}}, так что разложение числа a′{\displaystyle a’} уже не будет содержать слагаемого Fn−1{\displaystyle F_{n-1}}.

Использование

Юпана

Предполагают, что некоторые разновидности юпаны (абака инков) использовали фибоначчиеву систему счисления, чтобы минимизировать необходимое для вычислений число зёрен

[2].

В теории информации

На основе фибоначчиевой системы счисления строится код (кодирование) Фибоначчи — универсальный код для натуральных чисел (1, 2, 3…), использующий последовательности битов. Поскольку комбинация 11 запрещена в фибоначчиевой системе счисления, её можно использовать как маркер конца записи.

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

ε2ε3…εn1,

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

Арифметика

Сложение чисел в позиционных системах счисления выполняется с использованием переноса, позволяющего устранять последствия переполнения разряда. Например, в двоичной системе: 01 + 01 = 02 = 10.

В фибоначчиевой системе счисления дело обстоит сложнее:

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

Обобщение на вещественные числа

Число Представление
через степени φ{\displaystyle \varphi }
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

Похожее устройство имеет позиционная система счисления с иррациональным основанием, равным золотому сечению φ=(1+5)/2{\displaystyle \varphi =(1+{\sqrt {5}})/2}.

Любое вещественное число x из отрезка [0,1] допускает разложение в ряд через отрицательные степени золотого сечения:

x=∑k=−1−∞εkφk,εk∈{0,1}{\displaystyle x=\sum _{k=-1}^{-\infty }\varepsilon _{k}\varphi ^{k},\qquad \varepsilon _{k}\in \{0,1\}}

где {εk}{\displaystyle \left\{\varepsilon _{k}\right\}} обладает тем же свойством отсутствия соседних единиц. Коэффициенты находятся последовательным сравнением x с φ−1{\displaystyle \varphi ^{-1}} — золотым сечением отрезка [0,1], вычитанием φ−1{\displaystyle \varphi ^{-1}} (если εk=1{\displaystyle \varepsilon _{k}=1}) и умножением на φ{\displaystyle \varphi }. Из этого нетрудно видеть, что любое неотрицательное вещественное число допускает разложение:

a=∑k=N−1−∞εkφk,{\displaystyle a=\sum _{k=N-1}^{-\infty }\varepsilon _{k}\varphi ^{k}\,,}

где N таково, что a<φN{\displaystyle a<\varphi ^{N}}. Разумеется, следует считать, что εk=0{\displaystyle \varepsilon _{k}=0} для всех k⩾N{\displaystyle k\geqslant N}.

Эти формулы полностью аналогичны формулам для обычных позиционных систем с целыми основаниями. Оказывается, что любое неотрицательное целое число (и, более общо, всякий неотрицательный элемент кольца Z+φZ{\displaystyle {\mathbb {Z} }+\varphi {\mathbb {Z} }}) имеет представление лишь с конечным количеством единиц, то есть в виде конечной суммы неповторяющихся степеней золотого сечения.[3]

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

Fk=Fk−1+Fk−2{\displaystyle F_{k}=F_{k-1}+F_{k-2}}
φk=φk−1+φk−2{\displaystyle \varphi ^{k}=\varphi ^{k-1}+\varphi ^{k-2}}

позволяющих устранение соседних единиц. Прямой связи между представлением натуральных чисел в системе золотого сечения и в фибоначчиевой не имеется.

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

Фибоначчиево умножение

Для целых чисел a=∑kεkFk {\displaystyle a=\sum _{k}\varepsilon _{k}F_{k}\ } и b=∑lζlFl {\displaystyle b=\sum _{l}\zeta _{l}F_{l}\ } можно определить «умножение»[4]

a∘b=∑k,lεkζlFk+l,{\displaystyle a\circ b=\sum _{k,l}\varepsilon _{k}\zeta _{l}F_{k+l},}

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

Разумеется, данная операция не является настоящим умножением чисел, и выражается формулой:[5]

a∘b=3ab−a⌊(b+1)φ−2⌋−b⌊(a+1)φ−2⌋,{\displaystyle a\circ b=3ab-a\lfloor (b+1)\varphi ^{-2}\rfloor -b\lfloor (a+1)\varphi ^{-2}\rfloor ,}

где ⌊⋅⌋{\displaystyle \lfloor \cdot \rfloor } — целая часть, φ=1+52{\displaystyle \varphi ={\frac {1+{\sqrt {5}}}{2}}} — золотое сечение.

Эта операция обладает ассоциативностью, на что впервые обратил внимание Дональд Кнут[6]. Следует отметить, что другое «произведение» ∑k,lεkζlFk+l−2,{\displaystyle \sum _{k,l}\varepsilon _{k}\zeta _{l}F_{k+l-2},} отличающееся лишь сдвигом на два разряда, уже не является ассоциативным.

Примечания

Литература

Код Фибоначчи Вики

Фибоначчиева система счисления — смешанная система счисления для целых чисел на основе чисел Фибоначчи F2=1, F3=2, F4=3, F5=5, F6=8 и т. д.

Число Запись
в
Код
Фибоначчи
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

Представление натуральных чисел[ | код]

Любое неотрицательное целое число a{\displaystyle a} можно единственным образом представить последовательностью битов …εk…ε4ε3ε2 (εk∈{0,1}{\displaystyle \varepsilon _{k}\in \{0,1\}}) так, что a=∑kεkFk{\displaystyle a=\sum _{k}\varepsilon _{k}F_{k}}, причём последовательность {εk} содержит лишь конечное число единиц, и не имеет пар соседних единиц: ∀k≥2:(εk=1)⇒(εk+1=0){\displaystyle \forall k\geq 2:(\varepsilon _{k}=1)\Rightarrow (\varepsilon _{k+1}=0)}. За исключением последнего свойства, данное представление аналогично двоичной системе счисления.

Обоснование[ | код]

В основе лежит теорема Цекендорфа[1] — любое неотрицательное целое число единственным образом представимо в виде суммы некоторого набора чисел Фибоначчи с индексами больше единицы, не содержащего пар соседних чисел Фибоначчи.

Доказательство существования легко провести по индукции. Любое целое число a≥1{\displaystyle a\geq 1} попадёт в промежуток между двумя соседними числами Фибоначчи, то есть для некоторого n≥2{\displaystyle n\geq 2} верно неравенство: Fn≤a<Fn+1{\displaystyle F_{n}\leq a<F_{n+1}}. Таким образом, a=Fn+a′{\displaystyle a=F_{n}+a’}, где a′=a−Fn < Fn−1{\displaystyle a’=a-F_{n}\ <\ F_{n-1}}, так что разложение числа a′{\displaystyle a’} уже не будет содержать слагаемого Fn−1{\displaystyle F_{n-1}}.

Использование[ | код]

Юпана[ | код]

Предполагают, что некоторые разновидности юпаны (абака инков) использовали фибоначчиеву систему счисления, чтобы минимизировать необходимое для вычислений число зёрен[2].

В теории информации[ | код]

На основе фибоначчиевой системы счисления строится код (кодирование) Фибоначчи — универсальный код для натуральных чисел (1, 2, 3…), использующий последовательности битов. Поскольку комбинация 11 запрещена в фибоначчиевой системе счисления, её можно использовать как маркер конца записи.

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

ε2ε3…εn1,

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

Арифметика[ | код]

Сложение чисел в позиционных системах счисления выполняется с использованием переноса, позволяющего устранять последствия переполнения разряда. Например, в двоичной системе: 01 + 01 = 02 = 10.

В фибоначчиевой системе счисления дело обстоит сложнее:

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

Обобщение на вещественные числа[ | код]

Число Представление
через степени φ{\displaystyle \varphi }
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

Похожее устройство имеет позиционная система счисления с иррациональным основанием, равным золотому сечению φ=(1+5)/2{\displaystyle \varphi =(1+{\sqrt {5}})/2}.

Любое вещественное число x из отрезка [0,1] допускает разложение в ряд через отрицательные степени золотого сечения:

x=∑k=−1−∞εkφk,εk∈{0,1}{\displaystyle x=\sum _{k=-1}^{-\infty }\varepsilon _{k}\varphi ^{k},\qquad \varepsilon _{k}\in \{0,1\}}

где {εk}{\displaystyle \left\{\varepsilon _{k}\right\}} обладает тем же свойством отсутствия соседних единиц. Коэффициенты находятся последовательным сравнением x с φ−1{\displaystyle \varphi ^{-1}} — золотым сечением отрезка [0,1], вычитанием φ−1{\displaystyle \varphi ^{-1}} (если εk=1{\displaystyle \varepsilon _{k}=1}) и умножением на φ{\displaystyle \varphi }. Из этого нетрудно видеть, что любое неотрицательное вещественное число допускает разложение:

a=∑k=N−1−∞εkφk,{\displaystyle a=\sum _{k=N-1}^{-\infty }\varepsilon _{k}\varphi ^{k}\,,}

где N таково, что a<φN{\displaystyle a<\varphi ^{N}}. Разумеется, следует считать, что εk=0{\displaystyle \varepsilon _{k}=0} для всех k⩾N{\displaystyle k\geqslant N}.

Эти формулы полностью аналогичны формулам для обычных позиционных систем с целыми основаниями. Оказывается, что любое неотрицательное целое число (и, более общо, всякий неотрицательный элемент кольца Z+φZ{\displaystyle {\mathbb {Z} }+\varphi {\mathbb {Z} }}) имеет представление лишь с конечным количеством единиц, то есть в виде конечной суммы неповторяющихся степеней золотого сечения.[3]

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

Fk=Fk−1+Fk−2{\displaystyle F_{k}=F_{k-1}+F_{k-2}}
φk=φk−1+φk−2{\displaystyle \varphi ^{k}=\varphi ^{k-1}+\varphi ^{k-2}}

позволяющих устранение соседних единиц. Прямой связи между представлением натуральных чисел в системе золотого сечения и в фибоначчиевой не имеется.

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

Фибоначчиево умножение[ | код]

Для целых чисел a=∑kεkFk {\displaystyle a=\sum _{k}\varepsilon _{k}F_{k}\ } и b=∑lζlFl {\displaystyle b=\sum _{l}\zeta _{l}F_{l}\ } можно определить «умножение»[4]

a∘b=∑k,lεkζlFk+l,{\displaystyle a\circ b=\sum _{k,l}\varepsilon _{k}\zeta _{l}F_{k+l},}

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

Разумеется, данная операция не является настоящим умножением чисел, и выражается формулой:[5]

a∘b=3ab−a⌊(b+1)φ−2⌋−b⌊(a+1)φ−2⌋,{\displaystyle a\circ b=3ab-a\lfloor (b+1)\varphi ^{-2}\rfloor -b\lfloor (a+1)\varphi ^{-2}\rfloor ,}

где ⌊⋅⌋{\displaystyle \lfloor \cdot \rfloor } — целая часть, φ=1+52{\displaystyle \varphi ={\frac {1+{\sqrt {5}}}{2}}} — золотое сечение.

Эта операция обладает ассоциативностью, на что впервые обратил внимание Дональд Кнут[6]. Следует отметить, что другое «произведение» ∑k,lεkζlFk+l−2,{\displaystyle \sum _{k,l}\varepsilon _{k}\zeta _{l}F_{k+l-2},} отличающееся лишь сдвигом на два разряда, уже не является ассоциативным.

Примечания[ | код]

Литература[ | код]

ПОСЛЕДОВАТЕЛЬНОСТЬ ФИБОНАЧЧИ. Взламывая код да Винчи

ПОСЛЕДОВАТЕЛЬНОСТЬ ФИБОНАЧЧИ

В самом начале книги «Код да Винчи», там, где говорится об обнаружении тела Жака Соньера, написано, что на полу галереи были начертаны цифры. Софи Невё, внучка убитого, узнает последовательность чисел и приходит к выводу, что это зашифрованное послание, которое оставил для нее перед смертью дед. После того как в ее руки попадает ключ от банковского сейфа, Невё понимает: чтобы добраться до его содержимого, необходимо знать номер банковского счета. А чтобы отгадать зашифрованный номер, цифры должны быть размещены в порядке увеличения.

Созданная математиком Леонардо Фибоначчи и названная в его честь последовательность представляет собой бесконечный ряд чисел. Начинается она так: 1, 1, 2, 3, 5, 8, 13… и каждое новое число является суммой двух предыдущих. Например: 1 + 1 = 2; 1 + 2 = 3; 2 + 3 = 5; 3 + 5 = 8; 5 + 8 = 13 и так далее. Для любой величины, превышающей в этой последовательности число 3, соотношение между двумя последовательными числами равно 1:1,618. Это и есть знаменитое золотое сечение.

Последовательность Фибоначчи имеет массу примеров в природе. Например, подсолнечник имеет 21 спираль на своей головке в одном направлении и 34 — в другом. Это и есть последовательные числа Фибоначчи. Внешняя сторона сосновой шишки имеет спирали, проходящие по часовой стрелке и против нее. Соотношение числа этих спиралей являет собой вышеназванную последовательность. В элегантных завитках раковины головоногого моллюска наутилуса соотношение диаметра каждого витка спирали к следующему составляет 1:1,618.

Фибоначчи родился в итальянском городе Пиза в 1170 году. Образование получил в Северной Африке в Буджии, ныне Беджайя, на территории современного Алжира. На родину, в Пизу, он вернулся примерно в 1200 году. Фибоначчи предположительно обучался у арабских математиков и испытал огромное влияние с их стороны. Он написал множество трактатов на темы математики и сделал ряд важных открытий в этой науке. Это способствовало росту его популярности во всей Италии и привлекло к Фибоначчи внимание тогдашнего императора Священной Римской империи Фридриха II, который пригласил его к своему двору, в ту пору находившемуся в Пизе. Умер Фибоначчи в 1250 году.

См. также: Золотое сечение, Золотой прямоугольник.

Поделитесь на страничке

Следующая глава >

Куб Фибоначчи — Википедия

Ку́бы Фибона́ччи, или фибоначчиевы сети, — это семейство неориентированных графов с богатыми рекурсивными свойствами, возникшее в теории чисел. Математически эти кубы похожи на графы гиперкуба, но с числом вершин, равным числу Фибоначчи. Кубы Фибоначчи впервые явно определил в своей статье Сюй[1] в контексте взаимосвязей топологий для связи систем параллельных вычислений или распределённых систем. Они применяются также в химической теории графов[en].

Куб Фибоначчи можно определить в терминах кодов Фибоначчи и расстояния Хэмминга, независимых множеств вершин в путях, или через дистрибутивные решётки[en].

Кубы Фибоначчи (нарисованные красным цветом) как подграфы гиперкубов Куб Фибоначчи порядка 6

Подобно графу гиперкуба, вершины куба Фибоначчи порядка n можно пометить битовыми строками длины n таким образом, что две вершины смежны, если их метки отличаются одним битом. Однако в кубе Фибоначчи разрешены только метки, которые (как битовые строки) не имеют двух единиц подряд. Имеется Fn+2{\displaystyle F_{n+2}} возможных меток, где Fn обозначает n-е число Фибоначчи, а потому имеется Fn+2{\displaystyle F_{n+2}} вершин в кубе Фибоначчи порядка n.

Узлам таких сетей могут быть назначены последовательные целые числа от 0 до Fn+2−1{\displaystyle F_{n+2}-1}. Битовые строки, соответствующие этим числам, задаются их представлениями Цекендорфа[2].

Куб Фибоначчи порядка n является симплектическим графом[en] дополнения графа пути с n вершинами[3]. То есть, каждая вершина куба Фибоначчи представляет клику в дополнении пути или, эквивалентно, в независимом множестве в самом пути. Две вершины куба Фибоначчи смежны, если клики или независимые множества, которые они представляют, отличаются удалением или добавлением одного элемента. Поэтому, подобно другим симплексным графам, кубы Фибоначчи являются медианными графами и, более обще, частичными кубами[4][5]. Медиана любых трёх вершин куба Фибоначчи может быть найдена путём вычисления побитовой мажоритарной функции трёх меток. Если каждая их трёх меток не имеет двух последовательных битов 1, то это верно и для их мажоритарного значения.

Куб Фибоначчи является также графом дистрибутивной решётки[en], которая может быть получена через теорему Биркгофа[en] из «забора[en]», частично упорядоченного множества, определённого чередующейся последовательностью отношений a<b>c<d>e<f>…{\displaystyle a<b>c<d>e<f>\dots }[6]. Имеется также альтернативное описание на языке тории графов той же решётки: независимые множества любого двудольного графа могут быть даны в определённом порядке, в котором одно независимое множество меньше другого, если они получаются путём удаления элементов из одной доли и добавления элементов в другую долю. С этим порядком независимые множества образуют дистрибутивную решётку

[7], а применение данного построения к графу-пути приводит к ассоциации решётки с кубом Фибоначчи.

Куб Фибоначчи порядка n можно разбить на куб Фибоначчи порядка n−1{\displaystyle n-1} (разметка узлов начинается с бита, имеющего значение 0) и куб Фибоначчи порядка n−2{\displaystyle n-2} (узлы начинаются с бита значением 1)[8].

Любой куб Фибоначчи имеет гамильтонов путь. Конкретнее, существует путь, который обходит разбиение, описанное выше — он посещает узлы сначала с 0, а потом с 1 в двух непрерывных подпоследовательностях. В этих двух подпоследовательностях путь может быть построен рекурсивно по тому же правилу, соединяя две подпоследовательности концами, на которых второй бит имеет значение 0. Тогда, например, в кубе Фибоначчи порядка 4 последовательностью, построенной таким образом, будет (0100—0101—0001—0000—0010)—(1010—1000—1001), где скобки показывают подпоследовательности двух подграфов. Кубы Фибоначчи с чётным числом узлов, большим двух, имеют гамильтонов цикл

[9].

Мунарини и Сальви[10] изучали радиус и число независимости кубов Фибоначчи. Поскольку эти графы двудольные и имеют гамильтоновы пути, их максимальные независимые множества имеют число вершин, которое равно половине вершин всего графа, округлённое до ближайшего целого[11]. Диаметр куба Фибоначчи порядка n равен n, а его радиус равен n/2 (снова, округлённый до ближайшего целого)[12].

Тараненко и Весель[13] показали, что можно проверить, является ли граф кубом Фибоначчи за время, близкое к его размеру.

Сюй[1], а также Сюй, Пейдж и Лью[14] предложили использовать кубы Фибоначчи в качестве сетевой топологии в системах параллельных вычислений. Как коммуникационная сеть куб Фибоначчи имеет полезные свойства, подобные свойствам гиперкуба — число инцидентных рёбер на одну вершину не более

n/2, и диаметр сети не превосходит n, оба значения пропорциональны логарифму числа вершин, а возможность разбить сеть на меньшие подсети того же типа позволяет расщепить многие задачи параллельных вычислений[9]. Кубы Фибоначчи поддерживают также эффективные протоколы для маршрутизации и широковещания в системах распределённых вычислений[1][15].

Клавжар и Жигерт применили кубы Фибоначчи в химической теории графов[en] как описание семейства совершенных паросочетаний некоторых молекулярных графов[16]. Для молекулярной структуры, описываемой планарным графом G резонансным графом (или графом Z-преобразований) графа G является граф, вершины которого описывают совершенные паросочетания графа G, а рёбра которого соединяют пары совершенных паросочетаний, симметрическая разность которых является внутренней гранью графа G. Полициклические ароматические углеводороды могут быть описаны как подграфы шестиугольной мозаики плоскости, а резонансные графы описывают возможные структуры с двойными связями этих молекул. Как показали Клавжар и Жигерт

[16], углеводороды, образованные цепочками шестиугольников, соединённых ребро к ребру без трёх смежных шестиугольников на прямой, имеют резонансные графы, которые в точности являются графами Фибоначчи. Более обще, Чжан, Оу и Яо описали класс планарных двудольных графов, которые имеют кубы Фибоначчи в качестве графов резонанса[17][3].

Обобщённые кубы Фибоначчи предложили Сюй и Чжан[18], базируясь на числах Фибоначчи k-го порядка, которые позднее Сюй, Чжан и Дас, основываясь на более общих видах линейных рекурсий, расширили на класс сетей, названных линейными рекурсивными сетями[19]. Ву модифицировал кубы Фибоначчи второго порядка, основываясь на иных начальных условиях[20]. Другой связанный граф — куб Люка, с количеством вершин, равным числу Люка, определённый из куба Фибоначчи путём запрещения бита значением 1 как в первой, так и последней позициях каждой битовой строки. Дедо, Торри и Салви использовали свойства раскраски как кубов Фибоначчи, так и кубов Люка

[21].

  1. 1 2 3 Hsu, 1993.
  2. ↑ Klavžar, 2011, с. 3—4.
  3. 1 2 Klavžar, 2011, с. 3.
  4. ↑ Klavžar, 2005.
  5. ↑ Klavžar, 2011, с. Theorem 5.1.
  6. ↑ Ганснер (Gansner 1982) говорит как о «хорошо известном факте», что эта решётка имеет число элементов, равное числу Фибоначчи, а Стэнли (Stanley 1986) переносит этот факт в упражнения. См. также Höft & Höft, 1985, Beck, 1990 и Salvi & Salvi, 2008.
  7. ↑ Propp, 1997.
  8. ↑ Klavžar, 2011, с. 4—5.
  9. 1 2 Cong, Zheng, Sharma, 1993.
  10. ↑ Munarini, Salvi, 2002.
  11. ↑ Klavžar, 2011, с. 6.
  12. ↑ Klavžar, 2011, с. 9.
  13. ↑ Taranenko, Vesel, 2007.
  14. ↑ Hsu, Page, Liu, 1993.
  15. ↑ Stojmenovic, 1998.
  16. 1 2 Klavžar, Žigert, 2005.
  17. ↑ Zhang, Ou, Yao, 2009.
  18. ↑ Hsu, Chung, 1993.
  19. ↑ Hsu, Chung, Das, 1997.
  20. ↑ Wu, 1997.
  21. ↑ Dedó, Torri, Salvi, 2002.
  • István Beck. Partial orders and the Fibonacci numbers // Fibonacci Quarterly. — 1990. — Т. 28, вып. 2. — С. 172–174.
  • Cong B., Zheng S. Q., Sharma S. On simulations of linear arrays, rings and 2D meshes on Fibonacci cube networks // Proc. 7th Int. Parallel Processing Symposium. — 1993. — С. 748–751. — DOI:10.1109/IPPS.1993.262788.
  • Ernesto Dedó, Damiano Torri, Norma Zagaglia Salvi. The observability of the Fibonacci and the Lucas cubes // Discrete Mathematics. — 2002. — Т. 255, вып. 1–3. — С. 55–63. — DOI:10.1016/S0012-365X(01)00387-9.
  • Emden R. Gansner. On the lattice of order ideals of an up-down poset // Discrete Mathematics. — 1982. — Т. 39, вып. 2. — С. 113–122. — DOI:10.1016/0012-365X(82)90134-0.
  • Hartmut Höft, Margret Höft. A Fibonacci sequence of distributive lattices // Fibonacci Quarterly. — 1985. — Т. 23, вып. 3. — С. 232–237.
  • Hsu W.-J. Fibonacci cubes: a new interconnection topology // IEEE Transactions on Parallel and Distributed Systems. — 1993. — Т. 4, вып. 1. — С. 3–12. — DOI:10.1109/71.205649.
  • Hsu W.-J., Chung M. J. Generalized Fibonacci cubes // 1993 International Conference on Parallel Processing — ICPP’93. — 1993. — Т. 1. — С. 299–302. — DOI:10.1109/ICPP.1993.95.
  • Hsu W.-J., Page C. V., Liu J.-S. Fibonacci cubes: a class of self-similar graphs // Fibonacci Quarterly. — 1993. — Т. 31, вып. 1. — С. 65–72.
  • Hsu W.-J., Chung M. J., Das A. Linear recursive networks and their applications in distributed systems // IEEE Transactions on Parallel and Distributed Systems. — 1997. — Т. 8, вып. 7. — С. 673–680. — DOI:10.1109/71.598343.
  • Sandi Klavžar. On median nature and enumerative properties of Fibonacci-like cubes // Discrete Mathematics. — 2005. — Т. 299, вып. 1–3. — С. 145–153. — DOI:10.1016/j.disc.2004.02.023.
  • Sandi Klavžar. Structure of Fibonacci cubes: a survey // IMFM Preprint Series. — Ljubljana, Slovenia: Institute of Mathematics, Physics and Mechanics, 2011. — Т. 49, вып. 1150.
  • Sandi Klavžar, Petra Žigert. Fibonacci cubes are the resonance graphs of Fibonaccenes // Fibonacci Quarterly. — 2005. — Т. 43, вып. 3. — С. 269–276. Архивировано 8 февраля 2007 года..
  • Emanuele Munarini, Norma Zagaglia Salvi. Structural and enumerative properties of the Fibonacci cubes // Discrete Mathematics. — 2002. — Т. 255, вып. 1–3. — С. 317–324. — DOI:10.1016/S0012-365X(01)00407-1.
  • James Propp. Generating random elements of finite distributive lattices // Electronic Journal of Combinatorics. — 1997. — Т. 4, вып. 2. — С. R15. — arXiv:math.CO/9801066.
  • Rodolfo Salvi, Norma Zagaglia Salvi. Alternating unimodal sequences of Whitney numbers // Ars Combinatoria. — 2008. — Т. 87. — С. 105–117.
  • Richard P. Stanley. Enumerative Combinatorics. — Wadsworth, Inc., 1986. Упражнение 3.23a, страница 157
  • Ivan Stojmenovic. Optimal deadlock-free routing and broadcasting on Fibonacci cube networks // Utilitas Mathematica. — 1998. — Т. 53. — С. 159–166. Архивировано 25 июля 2011 года..
  • Taranenko A., Vesel A. Fast recognition of Fibonacci cubes // Algorithmica. — 2007. — Т. 49, вып. 2. — С. 81–93. — DOI:10.1007/s00453-007-9026-5.
  • Jie Wu. Extended Fibonacci cubes // IEEE Transactions on Parallel and Distributed Systems. — 1997. — Т. 8, вып. 12. — С. 1203–1210. — DOI:10.1109/71.640012.
  • Heping Zhang, Lifeng Ou, Haiyuan Yao. Fibonacci-like cubes as Z-transformation graphs // Discrete Mathematics. — 2009. — Т. 309, вып. 6. — С. 1284–1293. — DOI:10.1016/j.disc.2008.01.053.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *