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

[kim-im]

Здравствуйте. Прошу вашей помощи для решения задачи (взята с e-olimp, номер 8702):
Любое натуральное число единственным способом можно представить в виде суммы некоторого набора чисел Фибоначчи — это утверждение лежит в основе системы счисления Фибоначчи.

Найти n-й член последовательности чисел: 1 10 100 101 1000 1001 1010 10000 10001 10010 10100 10101 …
Например: для 7 вывести 1010.
Нашел в сети информацию, чтобы хоть понять как формировать этот ряд чисел. Что-то похожее есть о задачи Цзяньшицзы. В ней есть таблица для формирования чисел данного ряда.
Что такое числа Фибоначчи тоже знаю, но прошу что-бы хоть намекнули с чего начать писать программу.
Спасибо за помощь.

[kim-im]

№ 1 2 3 4 5 6 7 8
а 1 100 101 1001 10000 10001 10100 10101

[p51x]

Это за ряд во втором посте?

По задаче: начните с простого варианта - ищете максимальное непревосходящее число Фибоначчи и ставите 1 в его номер, дальше из числа вычитаете это найденное и повторяете пока не 0.

[kim-im]

Сообщение от p51x

Это за ряд во втором посте?

Так, хотел таблицу напечатать!!!

[Serge_Bliznykov]

классная задача.
Мне потребовалось XX минут чтения википедии, чтобы просто понять условие задачи (что такое за последовательность 1 10 100 101 1000 1001 1010 ... )
читал это

Теорема Цекендорфа

Фибоначчиева система счисления

ну и собственно, я бы просто написал перевод числа в ФСС

Для любого заданного натурального числа его цекендорфово представление находится при помощи жадного алгоритма, когда на каждом этапе выбирается наибольшее возможное число Фибоначчи.

[p51x]

Та ладно, простое ж условие на системы исчисления.

[Serge_Bliznykov]

Сообщение от p51x

Та ладно, простое ж условие на системы исчисления.

для кого-то простое. лично для меня - условие оказалось не простым.
(теперь, конечно, всё понятно, но, боюсь, что без википедии, я бы так и не смог понять, что это за последовательность такая )

[kim-im]

Сообщение от Serge_Bliznykov

классная задача.

ну и собственно, я бы просто написал перевод числа в ФСС

Спасибо всем за помощь. Задача оказалась для меня непростой. Перечитал ВИКИ. Но всё равно потребовалось пол дня для осмысления условия задачи. Ещё пол дня читал что такое жадный алгоритм. В конце при помощи сети все таки получилось.

[canadamoscow]

На PascalABC.NET

begin
 var n := Readinteger('n =');
 var f := SeqWhile(1,1, (a,b) -> a + b, fib -> fib <= n).toArray; //ряд Фибоначчи от 1 до числа<=n
 var s:='1'+'0' * (f.High - 1); //крайний левый разряд ('наибольший  вес') равен 1, остальные пока нули
 n -= f.Last; //вычитаем из n число соответствующее крайнему левому разряду
 while n > 0 do begin
   var j := f.FindLastIndex(t-> t <= n); //находим индекс наибольшего числа из ряда Фиб. в составе n
   s[f.High + 1 - j] := '1'; //в разряде соответствующем индексу устанавливаем 1
   n -= f[j]; //вычитаем из n число соответствующее установленному разряду
 end;
 write(s,'(fib)');
end.

Или так:

begin
 var n := Readinteger('n =');
 var f := SeqWhile(1,1, (a,b) -> a + b, fib -> fib <= n).toArray; //ряд Фибоначчи от 1 до числа<=n
 For var j := f.High downto 1 do //пробегаемся по всем разрядам числа в ФСС от большего к меньшему
   if n >= f[j] then //если n, или остаток от n >= числу в разряде j, то
     begin Write(1); n -= f[j] end //выводим 1 и уменьшам n на число соответствующее этому разряду
   else write(0); //иначе 0
 '(fib)'.Println;
end.