Задача 4.
Числа Фибоначчи U[1], U[2], ... определяются начальными значениями U[1]=1, U[2]=2 и соотношением
U[N+1] = U[N] + U[N-1].
Рассмотрим систему счисления с двумя цифрами 0 и 1, в которой, в отличие от двоичной системы весами являются не степени двойки 1,2,4,8,16,..., а числа Фибоначчи 1,2,3,5,8,13,.... В этой системе счисления каждое положительное целое число единственным образом представляется в виде строки нулей и единиц, которая начинается с 1 и в которой нет двух единиц, стоящих рядом.
Даны две строки, представляющие числа A и B. Найти строку, представляющую число A+B.
Пример. Исходные строки '10101' и '100' представляют числа 8+3+1=12 и 3. Ответом является строка '100010', представляющая строку 13+2=15=12+3.
Примечание. Строки могут быть столь длинны, что числа A и B превысят максимально допустимое в вашем компьютере целое число.
|
Решение задачи 4.
Воспользуйтесь тем, что
U[1] + U[1] = U[2], (1)
U[i] + U[i] = U[i] + U[i-1] + U[i-2] = U[1+1] + U[i-2], (2)
U[i] + U[i-1] = U[i+1]. (3)
Суммируем числа A и B поразрядно, используя приведенные выше правила, начиная со старших разрядов. После применения любого из правил опять начинаем просмотр числа со старших разрядов.
Проведем суммирование чисел '10101' и '100' из задачи.
10101
+ 100
10 Первые два разряда просто сносятся,
+ 1001 затем применяем правило (2),
+ 01 и добавляем последние два разряда
+ 00 чисел A и B
11001 Для двух первых разрядов применяем правило (3)
+ 01
+ 00
100001
+ 01 Правило (1)
+ 00
100010
|
