Генератор последовательности обобщенных @ -чисел фибоначчи с произвольными начальными условиями Советский патент 1989 года по МПК G06F1/02 

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

Целью изобретения является расширение области применения за счет выделения последовательности четных р-чисел Фибоначчио

На чертеже представлена функциональная схема генератора для случая .

Генератор содержит счетные ячейки 1.1-1.3, каждая из которых содержит триггер 2, первый и второй элементы И 3 и 4, элемент 5 и реверсивный счетчик 6, регистры 7.1- 7.3, сумматор 8, блок 9 управления, коммутатор 10 и информационные 11, дополнительные информационные 12 и установочный 13 входы генератора, инэтом номер первого четного числа п0, 3, а число, на которое осуществляют пересчет номера первого четного числа, равно трем Таким образом, имеем следующие четные числа ряда 1 чисел Фибоначчи: 2,8,34,144 и т.д соответствующие номерам 3,6,9,12 и т.д. (3, , , и

0 т.д.) (табл.1).

, , 2ри-1 7, При этом номера первых трех четных членов следующие: п., , n 7, а число на которое осуществляют пересчет но15 меров первых трех четных чисел, равно семи. Таким образом, имеем следующие четные числа ряда 2-чисел Фибоначчи: 2,4,6,28,,406,872,1278 и т.д. соответствующие номерам 4,6,7,11,13,

20 14,18,20,2) и т.д. (4,6,7; , , , , , и т.д.) (табл.1)о

, , 2р+1-1 15, При этом номера первых семи четных членов сле30

формационные 14 и дополнительные ин- 25 дующие: п 5, , поэ 10, , формационные 15 выходы генератора. , , . Таким обра- Генератор функционирует следующим образом.

В предлагаемом генераторе используется закономерность чередования четных и нечетных чисел последовательности. Номера четных чисел после довательности определяются на основа- „нии следующего выражения

n n0j + (2P+1 - 1) хК где n - номера первых 2. четных чисел последовательности

(,2,0.o,2p-1);

К - натуральное число.

35

П05

зом, имеем следующие четные числа ряда 3-чисел Фибоначчи: 2,4,10,14,26, 36,50,250,476,1252 и т.д„, соответствующие номерам 5,7,10,11,13,14,15,20, 22,25,26,28,29,30 и т.д. (5,7,10,11, 3,14,15; , , 10+15 25, 11+15 26, 13+15 28, 14+15 29. 15+15 30 и т.д.).

Последовательности для - 3 представлены в табл.К

Допустим, что , а . На основании рекуррентного соотношения (1) имегм последовательность 2-чисел Фибоначчи, приведенную в табл.2.

Поясним выделение четных чисел последовательности обобщенных чисел Фибоначчи, при , , , когда на основании рекуррентного соотношения

О при

(i) NO при i 0; (1) N04(i-l)+No4(i-l-p)

при i О, при Nft - начальное условие;

р - произвольное натуральное

число;

Cp(i) - i-e число Фибоначчи, имеем три числовые последовательности, приведенные в табл„1. Для простоты показаны последовательности с начальным условием, равным единице, что не изменяет сути излагаемого.

, 2Р -1 1, 2 - 3. При

этом номер первого четного числа п0, 3, а число, на которое осуществляют пересчет номера первого четного числа, равно трем Таким образом, имеем следующие четные числа ряда 1 чисел Фибоначчи: 2,8,34,144 и т.д соответствующие номерам 3,6,9,12 и т.д. (3, , , и

0 т.д.) (табл.1).

, , 2ри-1 7, При этом номера первых трех четных членов следующие: п., , n 7, а число на которое осуществляют пересчет номеров первых трех четных чисел, равно семи. Таким образом, имеем следующие четные числа ряда 2-чисел Фибоначчи: 2,4,6,28,,406,872,1278 и т.д. соответствующие номерам 4,6,7,11,13,

0 14,18,20,2) и т.д. (4,6,7; , , , , , и т.д.) (табл.1)о

, , 2р+1-1 15, При этом номера первых семи четных членов сле0

5 дующие: п 5, , поэ 10, , , , . Таким обра-

5

0

5

0

5

П05

зом, имеем следующие четные числа ряда 3-чисел Фибоначчи: 2,4,10,14,26, 36,50,250,476,1252 и т.д„, соответствующие номерам 5,7,10,11,13,14,15,20, 22,25,26,28,29,30 и т.д. (5,7,10,11, 3,14,15; , , 10+15 25, 11+15 26, 13+15 28, 14+15 29. 15+15 30 и т.д.).

Последовательности для - 3 представлены в табл.К

Допустим, что , а . На основании рекуррентного соотношения (1) имегм последовательность 2-чисел Фибоначчи, приведенную в табл.2.

В начальный момент по входу 1 Г в первый регистр 7.1 вводится начальное условие - число . При этом остальные регистры 7.2 и 7.3 содержат нули, В каждый счетчик 6.1 - 6.3 по входам 12.1-12.3 устройства сигналом с входа 13 вводятся величины, соответствующие номерам первых трех (2 - 1 3) четных членов последовательности. Так, в счетчик 6. вводится число 4, в счетчик 6,2 - число 6, а в счетчик 6.3 - число 7. Одновременно сигнал по входу 13 приводит триггеры 2.1-2,3 в исходное нулевое состояние по их R-входам. Тактовые сигналы с выхода блока 9 управления поступают одновременно на первые входы всех элементов И 3 и 4. Так как триггеры 2,1-2.3 находятся в нулевом состоянии, то сигнал Лог.1 с их инверсных выходов, поступающий на второй вход соответствующих элементов И 4, разрешает прохождение тактовых сигналов на вход обратного счета соответствующих им реверсивных счетчиков 6. Таким образом, реверсив- ные счетчики 1 в исходный момент находятся в режиме вычитания,

При поступлении тактовых сигналов содержимое реверсивных счетчиков 1 уменьшается на единицу. При этом в каждом такте производится суммирование содержимого регистров 7.1 и 7.3, после чего результат суммирования принимается регистром 7.1, а содер- жимое регистра 7.1 переписывается в регистр 7.2, предыдущее содержимое которого принимается регистром 7.3, Таким образом, в каждом такте на выходе регистра 7.1 (выходе 14) появля ются результаты суммирования в предыдущем такте, соответствующие очередному числу в последовательности обобщенных чисел Фибоначчи, согласно рекуррентному соотношению (1) (табл.2). Процесс уменьшения содержимого реверсивных счетчиков 6 происходит до их переполнения. Так как в реверсивный счетчик 6,1 было записано число 4, то он переполняется первым. Сигнал переполнения этого счетчика (Лог.О) с его первого выхода переполнения поступает на первый вход элемента И-КЕ 5.1, и поэтому на выходе элемента И-НЕ 5.1 появляется сигнал Лог.1, Который поступает на управляющий вход коммутатора 10, и число с выхода регистра 7.1, соответствующее номеру 4, поступает на выход 15 генератора. Как видно из табл.2, это число ц(4) 10 есть четное число. Таким образом, выделяется первый четный член последовательности 2-чисел Фибоначчи, Одновременно сигнал переполнения ровер- сивного счетчика 6/1 поступает на S-вход триггера 2„1 и устанавливает его в единичное состояниес Сигнал Лог.1 с его прямого выхода поступает на второй вход элемента И 3.1 и после этого тактовые сигналы с выхода блока 9 управления начинают поступать на вход прямого счета реверсивного счетчика 6.1, который переходит в режим суммирования с,

По переполнению реверсивного счетчика 6с 1 через каждый 1 7 тактовых сигналов сигнал с второго выхода переполнения поступает на второй вход элемента И-НЕ 5.1, и на выходе последнего появляется сигнал Лог.1 который разрешает прохождение на выход 15 устройства числа, появившегося в данном такте на выходе регистра 7,1 Шестым тактовым сигналом переполняется реверсивный счетчик 6.2„ Сигнал переполнения (Лог.О) с его первого выхода переполнения поступает на первый вход элемента И-НЕ 5.2. Сигнал Лог,1 с его выхода, поступая на управляющий вход коммутатора 10, разрешает прохождение на выход 15 уст-т ройства числа, выработанного регистром 7,1 и соответствующего номеру 6„

Как видно из табл.2, это число есть четное ср(6)20« Таким образом, выделяется второй четный член после- доват.ельности 2-числа Фибоначчи Одновременно сигнал переполнения реверсивного счетчика 6.2 поступает на S-вход триггера 2.2 и устанавливает его в единичное состояние. Сигнал Лог.1 с его прямого выхода поступает на второй вход элемента И Зс2, и после этого тактовые сигналы начинают поступать на вход прямого счета реверсивного счетчика 602, который переходит в режим суммирования. Реверсивный счетчик 6,2 в этом режиме также начинает суммирование тактовых сигналов блока 9 управления

По переполнению реверсивного счетчика 6.2, которое происходит через каждые 2 Pt1 - 1 7 тактовых сигналов сигнал с второго выхода переполнения поступает на второй вход элемента И-НЕ , а с его выхода - на управляющий вход коммутатора 10, и разрешает прохождение очередного четного числа из последовательности, выработанного регистром 7.1 в данном такте. Таким образом, обеспечивается выделение четных членов последовательности обобщенных чисел Фибоначчи с номерами 6,13,20 и т.д. Как видно из Табл.2, этим номерам соответствуют следующие четные числа ср(6)20, Ц(13)300 и т.д.

В седьмом такте переполняется реверсивный счетчик 6.3 и сигнал переполнения с его первого выхода переполнения поступает на первый вход

элемента И-НЕ 5.3. Сигнал Лог. его выхода поступает на управляющий вход коммутатора 10, тем самым разрешает прохождение очередного четного числа последовательности обобщенных 2-чисел Фибоначчи на выход 15 генератора, номер которого соответствует данному седьмому такту. Как видно из табл,2, это число q(7)30 есть четное число. Таким образом, выделяется третье, т.е. четное (2 -1) число последовательности обобщенных 2-чисел Фибоначчи, Одновременно сигнал передимость, может быть введено новое начальное условие по входу 12 для формирования и выделения четных чисел следующей последовательности обобщенных 2-чисел Фибоначчи.

Формула изобретения

Генератор последовательности обобщенных р-чисел Фибоначчи с произ- вольными начальными условиями ло . авт,св. №662926, о т л и ч а ю щ и й- с я тем, что, с целью расширения об

Изобретение относится к вычислительной технике и может быть использовано при построении устройств контроля чисел, представленных в кодах Фибоначчи. Целью изобретения является расширение области применения за счет выделения последовательности четных р=чисел Фибоначчи. Генератор содержит счетные ячейки 1,1-1,3, каждая из которых содержит триггер 2, первый 3 и второй 4 элементы И, элемент И-НЕ 5 и реверсивный счетчик 6, регистры 7,1 и 7,3, сумматор 8, блок 9 управления, коммутатор 10, информационные 11, дополнительные информационные 12 и установочный 13 входы генератора, информационные 14 и дополнительные информационные 15 выходы генератора,1 ил., 2 табл.

полнения с первого выхода переполне- 15 ласти применения за счет выделения

последовательности четных р-чисел Фибоначчи, в него введены коммутатор и 2 -3 счетных ячеек, каждая из которых содержит реверсивный счетчик, триг- 20 гер элементы И и элементы И-НЕ, выход первого элемента И счетной ячейки подключен к суммирующему входу реверсивного счетчика, первый выход которого1 соединен с первым входом элережим суммирования и в дальнейшем на- 5 мента И-НЕ и S-входом триггера, вто- чинает суммирование тактовых сигна- рой выход реверсивного счетчика соеди- лов. По переполнению реверсивного йен с вторым входом элемента И-НЕ, счетчика 6.3 через каждые 2рн прямой и инверсный выходы триггера тактовых сигналов сигнал с второго соединены с первыми входами соответ- выхода переполнения поступает на уп- 30 ственно первого и второго элементов равляющий вход коммутатора 10 и раз- И, выход второго элемента И соединен

с вычитающим входом реверсивного счетчика, вторые входы элементов И всех счетных ячеек объединены и подключе- 35 ны к первому выходу блока управления, С-входы реверсивных счетчиков и R- входы триггеров всех счетных ячеек объединены и являются установочным входом генератора, информационные 40 входы реверсивных счетчиков счетных; ячеек , являются соответствующими дополнительными информационными вхония реверсивного счетчика 6.3 поступает на S-вход триггера 2.3 и устанавливает его в единичное состояние.

Сигнал Лог.1 с прямого выхода триггера 2.3 поступает на второй вход элемента И 3.3 и в дальнейшем тактовые сигналы поступают на вход прямого счета реверсивного счетчика 6.3. Этот счетчик также переходитв

решает прохождение очередного числа на выход 15 в данном такте. Таким образом, обеспечивается выделение четных членов последовательности обобщенных 2-чисел Фибоначчи с номерами 7,14,21 и-т.д. Как видно из табл.2, этим номерам соответствуют следующие четные числа: ср(7)30, cf(14)440 и т.д. Таким образом, на выходе генератора (табл.2) выделяются все четные числа последовательности обобщенных 2-чисел Фибоначчи: 10,дами генератора, выходы элементов 20,30,140,300,440,2030 и т.д., соот-И-НЕ счетных ячеек объединены и под- ветствующие номерам 4,6,7; 11,13,14;45 ключены к управляющему входу комму- 18,20,21 и т.д. татора, информационные входы которого Следует отметить, что по сигналуподключены к соответствующим информа- переполнения с второго выхода пере-ционным выходам первого регистра, выполнения реверсивного счетчика 6,3ходы являются дополнительными инфор- в генератор, если в этом есть необхо- 50 мационными выходами генератора.

,1- -t1-.,-.-,

inLiLl l Mlbl ll Ill

I I

I I

I 2 3 4 6 9 Э 19 28 I I 2 3 4 5 7 10 14

Таблица 1

13

4

15

(6

П J18 19 20 J2I J22 J23| 24J25

41 60 88 179 1в9 271 406 595 872 1278

19 26 36 50 69 95 131 181 250 345 476 657 907

ГI 2 з 4 5 I 6 1 7 8 9 lO ll l2 l3 JI4 l5 J l 6 17 Ј 18

2 5 5 5 10 15 20 30 45 65 95 140 205 300 440 645 945 1385 2030

Таблица 2