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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИРЕСПУБЛИК 09) 01) 1)4 С 06 Р 1 ОПИСА И АВТОРСК СВИДЕТЕЛЬСТ юл. У 15 зводстве х исследФ.А,Ма ий ) ное объедиваний АЗССРедов тво СССР 1976,ЕЛЬНОСТИ ЧЧИ С ПРООВИЯМИ я к вычисбыть ис ОСУДАРСТБЕННЫИ КОМИТЕТ О ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР(56) Авторское свидетель В 662926, кл. С 06 Р 1/О (54) ГЕНЕРАТОР ПОСЛЕДОВА ОБОБЩЕННЫХ р-ЧИСЕЛ ФИБОНА ИЗВОЛЬНЬКИ НАЧАЛЬНЫМИ УС (57) Изобретение относит лительной технике и може БРЕТЕНИЯ пользовано при построении устроиствконтроля чисел, представленных в кодах Фибоначчи, Целью изобретения является расширение области применения за счет выделения последовательности четных р-чисел Фибоначчи. Генератор содержит счетные ячейки 1,11.3, каждая из которых содержит триггер 2, первый 3 и второй 4 элементыИ, элемент И-НЕ 5 и реверсивный счетчик 6 регистры 7,1 и 7.3, сумматор8, блок 9 управления, коммутатор 10,информационные 11, дополнительныеинформационные 12 и установочный 13входы генератора, информационные 14и дополнительные информационные 15выходы генератора. 1 ил., 2 табл.Изобретение относится к вычислительной технике, может быть использовано при построении устройств контроля чисел, представленных в кодахФибоначчи, и является усовершенствованием генератора по авт.св,М 662926.Целью изобретения является расширение области применения за счетвыделения последовательности четныхр-чисел Фибоначчи.На чертеже представлена функциональная схема генератора для случаяр=2.Генератор содержит счетные ячейки 1.1-1.3, каждая из которых содержит триггер 2, первый и второй элементы И 3 и 4, элемент И-НЕ 5 и ревеусивный счетчик б, регистры 7,.17.3, сумматоР 8, блок 9 управления,коммутатор 10 и информационные 11,дополнительные информационные 12 иустановочный 13 входы генератора, информационные 14 и дополнительные информационные 15 выходы генератора.Генератор функционирует следующимобразом.В предлагаемом генераторе используется закономерность чередованиячетных и нечетных чисел последовательности. Номера четных чисел после.довательности определяются на основании следующего выраженияп=п" + (2 Р"-1)хКоР-где и - номера первых 2 четныхочисел последовательностиПоясним выделение четных чисел по" следовательности.обобщенных чисел Фибоначчи,при р=1, р=2, р=3, когда на основании рекуррентного соотношения0 при 1 0; (1) Ю, при 1 =0; (1) И,(-1)+Ы. Р(-1-р)приО, при Б - начальное условие; р - произвольное натуральноечисло;(р(1) - х-е число Фибоначчи, имеем три числовые последовательности, приведенные в табл,1, Для простоты показаны последовательности с начальным условием, равным еди" нице, что не изменяет сути излагаемого рщ 2 -11, 2 -=3, ПриР Р+Ф этом номер первого четного числаи =3, а число, на которое осуществлявт пересчет номера первого четного числа, равно трем. Таким образом,имеем следующие четные числа ряда1-чисел Фибоначчи: 2834144 и т,д,соответствующие номерам 3,6,9,12 итд, (3, 3+3=6, 6+39, 9+3=12 иО т,д ) (табл1р=2, 2 -1=3, 2 Р в 1, При этомномера первых трех четных членовследующие: п=4, и =б, и =7, а числона которое осуществляют пересчет но 15 меров первых трех четных чисел, равносеми. Таким образом, имеем следующиечетные числа ряда 2-чисел Фибоначчи:2,4,6,28,60 88,406,872,1278 и т,д,соответствующие номерам 4,6,7,11,13,20 14,18,202 и т,д, (4,6,7; 4+7=11,6+=13, 7+7=14, 11+7=18, 13+7=20,14+7=21 и т,д,) (табл.1).Р=З, 2 -1=7, .2 Р-1=15. При этомномера первых семи четных членов следующие: пщ =5 по 2 =7 поз =10 п 0, =1и =13, п 06 =14, и., =15. Таким образом, имеем следующие четные числаряда 3-чисел Фибоначчи: 2,4,10,14,26,36,50,250,476,1252 и т.д., соответст 30 вующие номерам 5,7,10,11,13,14,15,20,=30 и т,д.).35 Последовательности для р=1 - 3представлены в табл.,Допустим, что Н =5, а р=2. На основании рекуррентного соотношения (1) щ имеем последовательность 2-чисел Фибаначчи, приведенную в табл,2.В начальный момент по входу 1 Г в первый регистр 7,1 вводится начальное условие - число Ю,=5. При этом остальные регистры 7.2 и 7,3 содержат нули, В каждый счетчик 6,1 - 6,3 по входам 12,1-12,3 устройства сигналом с входа 13 вводятся величины, соответствующие номерам первых трех ,(2 -=3) четных членов последоваРтельности. Так, в счетчик 6, вводится число 4, в счетчик 6.2 - число б, . а в счетчик 6,3 - число 7, Одновременно сигнал по входу 13 приводит триггеры 2,1-2.3 в исходное нулевое состояние по их К-входам, Тактовыесигналы с выхода блока 9 управления поступают одновременно иа первые вхо 1474627ды всех элементов И 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,то он переполняется первым. Сигналпереполнения этого счетчика("Лог.0") 35с его первого выхода переполнения поступает на первый вход элемента И-БЕ5.1, и поэтому на выходе элементаИ-НЕ 5.1 появляется сигнал "Лог,1",40который поступает на управляющий входкоммутатора 10, и число с выхода регистра 7,1, соответствующее номеру 4,поступает на выход 15 генератора. Каквидно из табл,2, это число (4)=1045есть четное число, Таким образом, выделяется первый четный член последовательности 2-чисел Фибоначчи Одновременно сигнал переполнения ревер-,сивного счетчика 6.1 поступает наЯ-вход триггера 2.1 и устанавливаетего в единичное состояние, Сигнал"Лог.1" с его прямого выхода поступает на второй вход элемента И 3.1и после этого тактовые сигналы с вы 55хода блока 9 управления начинают поступать на вход прямого счета реверсивного счетчика 6.1, который переходит в режим суммирования,По переполнению реверсивного счетчика 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 поступает на Б-вход триггера 2,2 и устанавливает его в единичное состояние, Сигнал "Лог.1" с его прямого выхода поступает на второй вход элемента И 3,2, и после этого тактовые сигналы начинают поступать на вход прямого счета реверсивного счетчика 6,2, который переходит н режим суммирования, Реверсивный счетчик 6,2 в этом режиме также начинает суммирование тактовых сигналов блока 9 управленияПо переполнению реверсивного счетчика 6,2, которое происходит черезРФ 1кажцые 2 - 1 =7 тактовых сигналов сигнал с второго выхода переполненияпоступает на второй вход элементаИ-НЕ 5,2, а с его выхода - на управляющий вход коммутатора 10, и разрешает прохождение очередного четногочисла из последовательности, выработанного регистром 7,1 н данном такте, Таким образом, обеспечиваетсявыделение четных членов последовательности обобщенных чисел Фибоначчи сномерами 6,13,20 и т,д. Как видно изтабл.2, этим номерам соответствуютследующие четные числа р(б)=20,ч"(13)=300 и т,д,В седьмом такте переполняется реверсинный счетчик 6.3 и сигнал переполнения с его первого выхода переполнения поступает на первый вход. 911 )23 ) 4 (5 411 Е 91 10 11 12 13 14 15 Т 14 13 119 191021 22 123 24 252 3 4 6 9 13 19 28 41 бО 88 179 189 27 406595 872 127812 3 4 57 10 14 79 26 36 50 69 %5 3 8 258 345 476 657 9071,21 3 1 1 б ,14 элемента И-НЕ 5.3, Сигнал "Лог,1 с его выхода поступает на управляющий вход коммутатора 10, тем самым разрешает прохождение очередного четного числа последовательйости обобщенных 2-чисел Фибоначчи на выход 15 генератора, номер которого соответствует данному седьмому такту. Как видно из табл .2, это число 1.7(7)=30 есть четное число, Таким образом, выделяется третье, т,е. четное (2 - 1) число последовательности обобщенных 2-чисел Фибоначчи. Одновременно сигнал переполнения с первого выхода переполне" ния реверсивного счетчика 6,3 поступает на Б-вход триггера 2.3 и устанавливает его в единичное состояние.Сигнал "Лог.1" с прямого выхода триггера 2.3 поступает на второй вход элемента И 3.3 и в дальнейшем тактовые сигналы поступают на вход прямого счета реверсивного счетчика 63. Этот счетчик также переходит в режим суммирования и в дальнейшем начинает суммирование тактовых сигналов. По переполнению реверсивногоРн счетчика 6,3 через каждые 2 -1=7 тактовых сигналов сигнал с второго выхода переполнения поступает на управляющий вход коммутатора 1 О и разрешает прохождение очередного числа на выход 15 в данном такте. Таким образом, обеспечивается выделение четных членов последовательности обобщенных 2-чисел Фибоначчи с номерами ,14,21 и. т.д, Как видно из табл.2, этим номерам соответствуют следующие четные числа: (7)=30, 1(14)=440 и т,д. Таким образом, на выходе генератора (табл,2) выдаляются все четные числа последовательности обобщенных 2-чисел Фибоначчи: 1 О, 20,30,140,300,440,2030 и т,д., соответствующие номерам 4,6,7; 11,13,14;18,20,21 и т.д.Следует отметить, что по сигналу переполнения с второго выхода переполнения реверсивного счетчика 6.3 в генератор, если в этом есть необходимость 9 может быть введено новоеначальное условие по входу 12 дляформирования и выделения четных чисел5следующей последовательности обобщен-ных 2-чисел Фибоначчи. Формула изобретения Генератор последовательности обобщенных р-чисел Фибоначчи с произ-вольными начальными условиями по;авт,св. 119 662926, о т л и ч а ю щ и йс я тем, что, с целью расширения об ласти применения за счет выделенияпоследовательности четных р-чисел Фибоначчи, в него введены коммутатори2 -1 счетных ячеек, каждая из которыхсодержит реверсивный счетчик, триг гер элементы И и элементы И-НЕ, выход первого элемента И счетной ячейки подключен к суммирующему входу реверсивного счетчика, первый выход которого соединен с первым входом эле мента И-НЕ и Я-входом триггера, вто.рой выход реверсивного счетчика соединен с вторым входом элемента И-НЕ,прямой и инверсный выходы триггерасоединены с первыми входами соответ ственно первого и второго элементовИ, выход второго элемента И соединенс вычитающим входом реверсивного счетчика, вторые входы элементов И всехсчетных ячеек объединены и подклю 23 е-ны к первому выходу блока управления,С-входы реверсивных счетчиков и Квходы триггеров всех счетных ячеекобъединены и являются установочнымвходом генератора, информационные 40 входы реверсивных счетчиков счетныхячеек;,.являются соответствующимидополнительными информационными входами генератора, выходы элементовИ-НЕ счетных ячеек объединены и под ключены к управляющему входу коммутатора, информационные входы которогоподключены к соответствующим информационным выходам первого регистра, выходы являются дополнительными инфор мационными выходами генератора,1474627 р 1 2 3 4 5 6 7 8 9 Таблица 210 11 12 13 14 15 16 17 18 ЪСоставитель О.НеплоховРедактор В,Данко Техред А.Кравчук Корректор Э.ЛончаковаЗаказ 1894/46 Тираж 667 ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Иосква, Ж, Рауаская наб., д. 4/5 Производственно-издательский комбинат "Патент", г.ужгород, ул. Гагарина,101 2 5 5 5 10 15 20 30 45 65 95 140 205 300 440 645 945 1385 2030