Решение задачи Система счисления Фибоначчи с Acmp
Без пояснения   Просмотров: 288
Числа Фибоначчи F1, F2, … определяются начальными значениями и соотношением:
F1=1; F2=2; Fn=Fn-1+Fn-2.
Рассмотрим систему счисления с двумя цифрами 0 и 1, в которой, в отличие от двоичной системы, весами являются не степени двойки 1, 2, 4, 8, 16, …, а числа Фибоначчи 1, 2, 3, 5, 8, 13, …. В этой системе счисления каждое положительное целое число единственном способом представляется в виде строки из нулей и единиц, которая начинается с 1 и в которой нет двух единиц, стоящих рядом.
Требуется написать программу, которая по двум заданным строкам, представляющим числа A и B в системе счисления Фибоначчи, находила строку, представляющую число A+B также в этой системе счисления.
Например, исходные строки 10101 и 100 представляют числа 1*8+0*5+1*3+0*2+1*1=8+3+1=12 и 1*3+0*2+0*1=3. Ответом является строка 100010, представляющая число 1*13+0*8+0*5+0*3+1*2+0*1=13+2=15=12+3.
F1=1; F2=2; Fn=Fn-1+Fn-2.
Рассмотрим систему счисления с двумя цифрами 0 и 1, в которой, в отличие от двоичной системы, весами являются не степени двойки 1, 2, 4, 8, 16, …, а числа Фибоначчи 1, 2, 3, 5, 8, 13, …. В этой системе счисления каждое положительное целое число единственном способом представляется в виде строки из нулей и единиц, которая начинается с 1 и в которой нет двух единиц, стоящих рядом.
Требуется написать программу, которая по двум заданным строкам, представляющим числа A и B в системе счисления Фибоначчи, находила строку, представляющую число A+B также в этой системе счисления.
Например, исходные строки 10101 и 100 представляют числа 1*8+0*5+1*3+0*2+1*1=8+3+1=12 и 1*3+0*2+0*1=3. Ответом является строка 100010, представляющая число 1*13+0*8+0*5+0*3+1*2+0*1=13+2=15=12+3.