|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
28.02.2019, 13:42 | #1 |
Пользователь
Регистрация: 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. |
28.02.2019, 13:56 | #2 |
Пользователь
Регистрация: 07.11.2017
Сообщений: 42
|
№ 1 2 3 4 5 6 7 8
а 1 100 101 1001 10000 10001 10100 10101 |
28.02.2019, 14:02 | #3 |
Старожил
Регистрация: 15.02.2010
Сообщений: 15,709
|
Это за ряд во втором посте?
По задаче: начните с простого варианта - ищете максимальное непревосходящее число Фибоначчи и ставите 1 в его номер, дальше из числа вычитаете это найденное и повторяете пока не 0. |
28.02.2019, 14:04 | #4 |
Пользователь
Регистрация: 07.11.2017
Сообщений: 42
|
|
28.02.2019, 14:15 | #5 | |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
классная задача.
Мне потребовалось XX минут чтения википедии, чтобы просто понять условие задачи (что такое за последовательность 1 10 100 101 1000 1001 1010 ... ) читал это Теорема Цекендорфа Фибоначчиева система счисления ну и собственно, я бы просто написал перевод числа в ФСС Цитата:
|
|
28.02.2019, 14:21 | #6 |
Старожил
Регистрация: 15.02.2010
Сообщений: 15,709
|
Та ладно, простое ж условие на системы исчисления.
|
28.02.2019, 14:30 | #7 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
|
01.03.2019, 12:36 | #8 |
Пользователь
Регистрация: 07.11.2017
Сообщений: 42
|
Спасибо всем за помощь. Задача оказалась для меня непростой. Перечитал ВИКИ. Но всё равно потребовалось пол дня для осмысления условия задачи. Ещё пол дня читал что такое жадный алгоритм. В конце при помощи сети все таки получилось.
|
05.10.2020, 17:25 | #9 |
Пользователь
Регистрация: 16.05.2020
Сообщений: 57
|
На PascalABC.NET
Код:
Код:
Последний раз редактировалось canadamoscow; 05.10.2020 в 18:54. |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Найти сумму цифр заданного натурального числа | 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 |