Генератор последовательности обобщенных @ -чисел фибоначчи с произвольными начальными условиями

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИМ

РЕСПУБЛИК

Ш4 .G 06 F 1 02

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМ .Ф СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (61) 662926 (21) 4139364/24-24 (22) 09,10.86 (46) 23.04.89. Бюл. ¹ 15 (71) Научно-производственное объединение космических исследований АЗССР (72) Я.А.Мамедов, Ф.А,Мамедов и И.З.Животовский (53) 681.3(088.8) (56) Авторское свидетельство СССР № 662926, кл. G 06 F 1/02, 1976. (54) ГЕНЕРАТОР ПОСЛЕДОВАТЕЛЬНОСТИ

ОБОБЩЕННЫХ р-ЧИСЕЛ ФИБОНАЧЧИ С ПРОИЗВОЛЬНЬКИ НАЧАЛЬНЫМИ УСЛОВИЯМИ (57) Изобретение относится к вычислительной технике и может быть ис/к

„„SU„„1474627 А 2 пользовано при построении устройств . контроля чисел, представленных в ко дах Фибоначчи. Целью изобретения является расширение области применения за счет выделения последовательности четных р-чисел Фибоначчи. Генератор содержит счетные ячейки 1,11.3, каждая из которых содержит триггер 2, первый 3 и второй 4 элементы

И, элемент И-НЕ 5 и реверсивный счетчик 6 регистры 7.1 и 7.3, сумматор

8, блок 9 управления, .коммутатор 10, информационные 11, дополнительные информационные 12 и установочный 13 входы генератора, информационные 14 и дополнительные информационные 15 выходы генератора. 1 ил., 2 табл.

1474627

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

Фибоначчи, и является усовершенствованием генератора по авт.св.

М 662926.

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

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

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

Генератор функционирует следующим образом.

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

n = n" + (2"- I)xK о

p- i где n — номера первых 2 четных о) чисел последовательности (1=1,2, о ооу2 );

К вЂ” натуральное число, Поясним выделение четных чисел по" следовательности.обобщенных чисел Фибоначчи, при p=1, р=2, р=Зр когда основании рекуррентного соотношения

0 при i 0; (i) N npu i =О; (I)

И,су(i-l)+N, ср (i-1 р) при i> О, при N — начальное условие; р — произвольное натуральное число; (р() — i-e число Фибоначчи, имеем три числовые последовательности, приведенные в табл.1. Для простоты показаны последовательности с начальным условием, равным единице, что не изменяет сути излагаемого, . р=1, 2 -1 l, 2 — 1 =3, При

P p+t этом номер первого четного числа и„ =3, а число, на которое осуществлявт пересчет номера первого четного числа, равно трем. Таким образом, имеем следующие четные числа ряда

1-чисел Фибоначчи: 2,8,34,!44 и т.д. соответствующие номерам 3,6,9,12 и т„д. (3, 3+3=6, 6+3 †-9, 9+3=12 и т.д.) (табл.!). р=2, 2 -1=3, 2 †1. При этом номера первых трех четных членов следующие: п„=4, и =6, и =7, а число на которое осуществляют пересчет ноIS меров первых трех четных чисел, равно семи. Таким образом, имеем следующие четные числа ряда 2-чисел Фибоначчи:

2,4,6, 28,60 88,406,872,1278 и т.д, соответствующие номерам 4,6,7,11,13, 20 14, 18, 20, 2! и т,д. (4,6,7; 4+7=11, 6+7=13, 7+7=14, 11+7=18, 13+7=20, l4+7=2! и т.д.) (табл.l). р=3, 2 -1=7, 2 †1=. При этом номера первых семи четных членов следующие: и =5, по = l » no3 =10, и =1 1, и =13, и =!4, по, =15. Таким образом, имеем следующие четные числа ряда 3-чисел Фибоначчи: 2,4,10,14,26, 36,50,250,476,1252 и т.д., соответст30 вующие номерам 5,7,10,!1,13,!4,15,20, . 22,25,26,28,29,30 и т.д. (5,7,10,11, !

3,14,15; 5+15=20, 7+15=22, 10+15=25, 11+15=26, 13+15=28, 14+15=29. 15+15=

=30 и т.д.).

Последовательности для p=l — 3 представлены в табл.), Допустим, что !! =5, а р=2. На основании рекуррентного соотношения (1) щ имеем последовательность 2-чисел Фибаначчи, приведенную в табл.2.

В начальный момент по входу 1Г в первый регистр 7. 1 вводится начальное условие — число N,=5. При этом остальные регистры 7.2 и 7,3 содержат нули, В каждый счетчик 6.1 — 6,3 по входам 12.1-12.3 устройства сигналом с входа 13 вводятся величины, соответствующие номерам первых трех ,(2 — =3) четных членов последоваP тельности. Так, в счетчик 6. вводится число 4, в счетчик 6.2 — число 6, . а в счетчик 6.3 — число 7, Одновременно сигнал по входу 13 приводит триггеры 2,1-2.3 в исходное нулевое состояние по их К-входам. Тактовые сигналы с выхода блока 9 управления поступают одновременно иа первые вхо1474627 ды всех элементов Vi 3 и 4. Так как триггеры 2,1-2.3 находятся в нулевом состоянии, то сигнал "Лог.1" с их инверсных выходов, поступающий на второй вход соответствующих элементов И 4, разрешает прохождение тактовых сигналов на вход обратного счета соответствующих им реверсивных счетчиков 6. Таким образом, реверсив- !0 ные счетчики 1 в исходный момент находятся в режиме вычитания.

При поступлении тактовых сигна- лов содержимое реверсивных счетчиков

1 уменьшается на единицу. При этом в каждом такте производится суммирование содержимого регистров 7.1 и 7.3, после чего результат суммирования принимается регистром 7.1, а содержимое регистра 7.1 переписывается в регистр 7.2, предыдущее содержимое которого принимается регистром 7,3, Таким. образом, в каждом такте на выходе регистра 7.1 (выходе 14) появля-25 ются результаты суммирования в предыдущем такте, соответствующие очередному числу в последовательности обобщенных чисел Фибоначчи, согласно рекуррентному соотношению (1) (табл,2).

Процесс уменьшения содержимого реверсивных счетчиков 6 происходит до их переполнения. Так как в реверсивный счетчик 6,1 было записано число 4, то он переполняется первым. Сигнал переполнения этого счетчика ("Лог.О") с его первого выхода переполнения поступает на первый вход элемента И-БЕ

5.1, и поэтому на выходе элемента

И-НЕ 5.1 появляется сигнал "Лог,!"

40 который поступает на управляющий вход коммутатора 10, и число с выхода регистра 7.1, соответствующее номеру 4, поступает на выход 15 генератора. Как видно из табл.2, это число q(4)=10

45 есть четное число. Таким образом, выделяется первый четный член последовательности 2-чисел Фибоначчи„ Одновременно сигнал переполнения р".зер-. сивного счетчика 6. 1 поступает на

S-вход трит гера 2.1 и устанавливает

его в единичное состояние. Сигнал

"Лог.1" с его прямого выхода поступает на второй вход элемента И 3.1 и после этого тактовые сигналы с вы55 хода блока 9 управления начинают поступать на вход прямого счета реверсивного счетчика 6.1, который переходит B режим суммирования, По переполнению реверсивного счетчика 6,.1 через каждый 2 — 1 = 7 тактовых сигналов сигнал с второго выхода переполнения поступает на второй вход элемента И-НЕ 5.1, и на выходе последнего появляется сигнал "Лог,!" который разрешает прохождение на выход 15 устройства числа, появившегося в данном такте на выходе регистра 7,1.

Шестым тактовым сигналом переполняется реверсивный счетчик 6.2. Сигнал переполнения ("Лог.О") с его первого выхода переполнения поступает на первый вход элемента И-НЕ 5,2. Сигнал

"Лог,1" с его выхода, поступая на управляющий вход коммутатора 10, разрешает прохождение на выход 15 уст ройства числа, выработанного регистром 7.1 и соответствующего номеру б.

Как видно из табл.2, это число есть четное с (6)=20. Таким образом, выделяется второй четный член последовательности 2-числа Фибоначчи, Одновременно сигнал переполнения реверсивного счетчика 6.2 поступает на

S-вход триггера 2,2 и устанавливает его в единичное состояние. Сигнал

"Лог.1 с его прямого выхода поступает на второй вход элемента И 3.2, и после этого тактовые сигналы начинают поступать на вход прямого счета реверсивного счетчика 6.2, который переходит в режим суммирования. Реверсивный счетчик 6,2 в этом режиме также начинает суммирование тактовых сигналов блока 9 управления„

По переполнению реверсивного счетчика 6.2, которое происходит через

Pt1 кажцые 2 — 1 =7 тактовых сигналов сигнал с второго выхода переполнения поступает на второй вход элемента

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

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

74627 т 33 8 ц н ц а . I/172 ) 3 !4 Цб! 1$8$9JIOQII 12 !3 14 1 314 12$19fl9j20$21 !22 (PPJ 24 !23

I 2 3 4 6 9 13 19 28 41 60 88 179 189 27) 406 395 872 1278

1 2 3 4 3 7 10 14 )9 26 36 30 69 %3 13! IB) 23!) 343 476 637 907! I,)

2 l

3 I 1

5 .14 элемента И-НЕ 5.3, Сигнал "Лог.1 с

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

2-чисел Фибоначчи на выход 15 генератора, номер которого соответствует данному седьмому такту. Как видно из табл .2, это число 17(7)=30 есть четное число. Таким образом, выделяется третье, т.е. четное (2 — 1) число поP следовательности обобщенных 2-чисел

Фибоначчи. Одновременно сигнал переполнения с первого выхода переполне" ния реверсивного счетчика 6.3 поступает на S-вход триггера 2.3 и устанавливает его в единичное состояние.

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

6 ° 3. Этот счетчик также переходит в режим суммирования и в дальнейшем начинает суммирование тактовых сигналов. По переполнению реверсивного

Рн счетчика 6.3 через каждые 2 -1=7 тактовых сигналов сигнал с второго выхода переполнения поступает на управляющий вход коммутатора 10 и разрешает прохождение очередного чис ла на выход 15 в данном такте. Таким образом, обеспечивается выделение четных членов последовательности обобщенных 2-чисел Фибоначчи с номерами 7,14,21 и. т.д. Как видно из табл.2, этим номерам соответствуют следующие четные числа: ч (7)=30, q(14)=440 и т.д. Таким образом, на выходе генератора (табл.2) выдаляются все четные числа последовательности обобщенных 2-чисел Фибоначчи: 10, 20,30,140,300,440,2030 и т,д., соответствующие номерам 4,6,7; 11,13,14;

18,20,21 и т.д.

Следует отметить, что по сигналу переполнения с второго выхода переполнения реверсивного счетчика 6.3 в генератор, если в этом есть необходимость, может быть введено новое начальное условие по входу 12 для формирования и выделения четных чисел

5 следующей последова тельнос ти обобщен- ных 2-чисел Фибоначчи.

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

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

2 -1 счетных ячеек, каждая из которых

Р содержит реверсивный счетчик, триг20 гер элементы И и элементы И-НЕ, выход первого элемента И счетной ячейки подключен к суммирующему входу реверсивного счетчика, первый выход которого соединен с первым входом элемента И-НЕ и S-входом триггера, вто-. .рой выход реверсивного счетчика соединен с вторым входом элемента И вЂ” НЕ, прямой и инверсный выходы триггера соединены с первыми входами соответ30 ственно первого и второго элементов

И, выход второго элемента И соединен с вычитающим входом реверсивного счетчика, вторые входы элементов И всех счетных ячеек объединены и подклю23е-ны к первому выходу блока управления, С-входы реверсивных счетчиков и Квходы триггеров всех счетных ячеек объединены и являются установочным входом генератора, информационные

40 входы реверсивных счетчиков счетных ячеек;,.являются соответствующими дополнительными информационными входами генератора, выходы элементов

И-НЕ счетных ячеек объединены и под45 ключены к управляющему входу коммутатора, информационные входы которого подключены к соответствующим информационным выходам первого регистра, выходы являются дополнительными инфоря мационными выходами генератора.

1474627

7 8 9

Таблица 2

10 11 12 13 14 15 16 17 18

Составитель О.Неплохов

Редактор В,Данко Техред .А.Кравчук Корректор Э.Лончакова

Заказ 1894/46 Тираж 667 Бодписно е

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Иосква, Ж-35, Раужская наб., д. 4/5

Производственно-издательский комбинат "Патент", г.ужгород, ул. Гагарина,101

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