Събиране във фибоначиева бройна система



Дата22.07.2016
Размер14.59 Kb.
Събиране във фибоначиева бройна система (5 сек на тест)

Числата на Фибоначи се задават по следния начин:



F0=0, F1=1, Fn=Fn-1+Fn-2, за n>1.

В бройна система, с основа числата на Фибоначи, всяко цяло положително число има единствено представяне във вида: N=Fk1+Fk2+…+Fkr, където Fki – са числа на Фибоначи, а



k1 >> k2 >>>> kr >> 0. ( i >> j , ако i j+2).

Цяло неотрицателно число може да се запише с 0 и 1-ци: N=(bmbm-1b2)F, където bi = 1, ако Fi влиза в предсавянето и 0, в противен случай.

Пример: 1000000 = 832040 + 121393 + 46368 + 144 + 55 =F30 + F26 + F24 + F12 + F10

или (1000000)10=(10001010000000000010100000000)F.

Тази бройна система наподобява двоичното представяне, с изключение на това, че в нея никога не се получават две последователни единици.

При прибавяне на единица във ФБС има два случая:



  • ако младшият разряд е 0, той се заменя с 1

  • ако младшите разряди са 01 те се заменят с 10 (тъй като F3=F2+1). След което трябва да заменим цифрите 011 с 100 (тъй като Fn=Fn-1+Fn-2), дотогава, докато в редицата от цифри има две последователни единици.

Напишете програма за събиране на две числа във ФБС.

Вход: Във входният файл, по едно на ред, са записани две неотрицателни цели числа, във ФБС,. Броя на разрядите в числата може да бъде различен и да не превишава 1000.

Изход: Сумата, записана във ФБС.


Пример

INPUT.TXT: OUTPUT.TXT



1010 10010

100


База данных защищена авторским правом ©obuch.info 2016
отнасят до администрацията

    Начална страница