Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Delphi программирование > Паскаль, Turbo Pascal, PascalABC.NET
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 28.02.2019, 13:42   #1
kim-im
Пользователь
 
Регистрация: 07.11.2017
Сообщений: 42
По умолчанию Для любого заданного натурального числа его цекендорфово представление находится при помощи жадного алгоритма, когда на каждом этапе выбирается наибольшее возможное число Фибоначчи

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

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

Последний раз редактировалось kim-im; 28.02.2019 в 13:45.
kim-im вне форума Ответить с цитированием
Старый 28.02.2019, 13:56   #2
kim-im
Пользователь
 
Регистрация: 07.11.2017
Сообщений: 42
По умолчанию

№ 1 2 3 4 5 6 7 8
а 1 100 101 1001 10000 10001 10100 10101
kim-im вне форума Ответить с цитированием
Старый 28.02.2019, 14:02   #3
p51x
Старожил
 
Регистрация: 15.02.2010
Сообщений: 15,695
По умолчанию

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

По задаче: начните с простого варианта - ищете максимальное непревосходящее число Фибоначчи и ставите 1 в его номер, дальше из числа вычитаете это найденное и повторяете пока не 0.
p51x вне форума Ответить с цитированием
Старый 28.02.2019, 14:04   #4
kim-im
Пользователь
 
Регистрация: 07.11.2017
Сообщений: 42
По умолчанию

Цитата:
Сообщение от p51x Посмотреть сообщение
Это за ряд во втором посте?
Так, хотел таблицу напечатать!!!
kim-im вне форума Ответить с цитированием
Старый 28.02.2019, 14:15   #5
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

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

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

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

ну и собственно, я бы просто написал перевод числа в ФСС
Цитата:
Для любого заданного натурального числа его цекендорфово представление находится при помощи жадного алгоритма, когда на каждом этапе выбирается наибольшее возможное число Фибоначчи.
Serge_Bliznykov вне форума Ответить с цитированием
Старый 28.02.2019, 14:21   #6
p51x
Старожил
 
Регистрация: 15.02.2010
Сообщений: 15,695
По умолчанию

Та ладно, простое ж условие на системы исчисления.
p51x вне форума Ответить с цитированием
Старый 28.02.2019, 14:30   #7
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

Цитата:
Сообщение от p51x Посмотреть сообщение
Та ладно, простое ж условие на системы исчисления.
для кого-то простое. лично для меня - условие оказалось не простым.
(теперь, конечно, всё понятно, но, боюсь, что без википедии, я бы так и не смог понять, что это за последовательность такая )
Serge_Bliznykov вне форума Ответить с цитированием
Старый 01.03.2019, 12:36   #8
kim-im
Пользователь
 
Регистрация: 07.11.2017
Сообщений: 42
По умолчанию

Цитата:
Сообщение от Serge_Bliznykov Посмотреть сообщение
классная задача.

ну и собственно, я бы просто написал перевод числа в ФСС
Спасибо всем за помощь. Задача оказалась для меня непростой. Перечитал ВИКИ. Но всё равно потребовалось пол дня для осмысления условия задачи. Ещё пол дня читал что такое жадный алгоритм. В конце при помощи сети все таки получилось.
kim-im вне форума Ответить с цитированием
Старый 05.10.2020, 17:25   #9
canadamoscow
Пользователь
 
Аватар для canadamoscow
 
Регистрация: 16.05.2020
Сообщений: 57
По умолчанию

На 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.

Последний раз редактировалось canadamoscow; 05.10.2020 в 18:54.
canadamoscow вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Найти сумму цифр заданного натурального числа ZigaBr0 Паскаль, Turbo Pascal, PascalABC.NET 3 29.08.2016 16:09
Перевод из натурального десятичного числа в двоичное представление(string) Berserk0 Помощь студентам 3 17.06.2011 00:52
найти сумму цифр заданного натурального числа dima.m Microsoft Office Excel 6 06.12.2010 11:30
вывод на экран наибольшего делителя натурального числа N, меньше заданного натурального M Fatality Помощь студентам 2 03.12.2008 23:27