[Алгоритмы, Математика] Рекурсивный алгоритм представления Цекендорфа
Автор
Сообщение
news_bot ®
Стаж: 6 лет 9 месяцев
Сообщений: 27286
Спасибо добрым участникам Хабра, за то, что пригласили писать посты и получать на них фидбек.Сегодня я бы хотел осветить тему представления чисел с помощью ряда Фибоначи и разумеется написать простенькое REST API c использованием Mongo DB алгоритм с помощью языка Ruby, который бы по заданому числу N возвращал его представление. Часть 1 : представление ЦекендорфаКак гласит статья из Википедии :
Теорема Цекендорфа гласит, что всякое натуральное число можно единственным образом представить в виде суммы одного или нескольких различных чисел Фибоначчи так, чтобы в этом представлении не оказалось двух соседних чисел из последовательности Фибоначчи.
100 = 89 + 8 + 3.
Я думаю, понимая что такое числа Фибоначи, не составит труда понять в чём заключенна данная теорема.Цели которые должны быть достигнуты :
- скорость работы
- максимальная простота кода
Как язык програмирования я буду использовать Ruby, почему? Потому что Ruby - это
Лучший друг программиста.
Сначала теоретически нужно найти закономерность по которой и будет написан алгоритм.Выписав все числа Фибоначи которые меньше заданого, на листочек (школа), я обнаружил, что выгодней всего для такой суммы брать самое последнее число, но при условии что оно меньше чем наше искомое число.
Пример:
N = 51
F = 1 , 1 , 2 , 3 , 5 , 8 , 13, 21, 34.
Берём число 34, соседнее с ним число (21) можно сразу пропустить, ибо их сумма будет заведомо больше нашего входного числа N, ибо числа Фибоначи мы ищем пока они не превысят входное, ведь зачем нам числа больше входного :-).
Но каким образом лучше всего посчитать сумму, простым перебором мы точно не добьемся первого условия : скорость работы .
Сложным алгоритмом - откажемся от второго : максимальная простота кода.
И тогда появилась идея: а что если отнимать от N последнее число в ряду Фибоначи, и искать новый ряд где эта разница будет лимитом, и рекурсивно продолжать это действия пока разница не станет <= 0.
Пример:
N = 51
F = 1 , 1 , 2 , 3 , 5 , 8 , 13, 21, 34.
ans = [34]
N = 51 - 34 = 17
F = 1 , 1 , 2 , 3 , 5 , 8 , 13.
ans = [34 , 13]
N = 17 - 13 = 4
F = 1 , 1 , 2 , 3.
ans = [34 , 13 , 3]
N = 4 - 3 = 1
F = 1
ans = [34 , 13 , 3, 1]Сразу попробую записать в код :
def le_fib(limit, fib)
theoretical = fib[fib.count - 1] + fib[fib.count - 2]
return fib.last if theoretical > limit
fib << theoretical
le_fib(limit, fib)
end
def main(target,result)
temporary = le_fib(target, [1,1])
result << temporary
return result if target - temporary <= 0
main(target - temporary, result)
end
pp main(gets.to_i,[])
Функция le_fib - рекурсивно ищет ряд Фибоначи с пределом, на то, что бы следующее число не было больше чем входное число target. Здесь важно, что нас не интересует ряд Фибоначи целиком, нам важно лишь его окончание.Функция main - рекурсивно ищет масcив, числа которого есть числами Фибоначе, и которые бы в сумме давали нам входное число.Но, что бы убедится что алгоритм работает правильно, следует сказать что в теории никакие два числа рядом не могут оказатся одинаковые, ведь последовательность убывает, и на каждом следующей итерации нам недоступно число с предидущего этапа, ведь она заведомо больше.Пример работы для 20 случайных чисел до 1000 
Оценка времени работы в зависимости от величины ряда (входного числа)
Как видим время работы даже на числах до 10^9 очень позитивное.А общий обьем кода в 17 строк говорит о том что обе задачи выполнены успешно.Статья про интерес, всегда в рукаве нужно иметь пару задач с числами Фибоначе, иначе какой из тебя программист :-)
===========
Источник:
habr.com
===========
Похожие новости:
- [Занимательные задачки, Программирование, Алгоритмы, Компиляторы] Чемпионат по выполнению теста Кнута
- [Программирование, Алгоритмы, Компиляторы, Софт] О реализации точного представления чисел или «где хранить деньги?»
- [Математика, Научно-популярное] Изучающий математику студент расширяет рубежи теории графов (перевод)
- [Терминология IT, Учебный процесс в IT, Образование за рубежом, Карьера в IT-индустрии] Наше ИТ и их Computer Science
- [Open source, Алгоритмы, Lua, Параллельное программирование] Такие важные короткоживущие данные
- [Алгоритмы, Обработка изображений, Машинное обучение] Эксперимент в распознавании рукописных текстов на кириллице. Часть 2
- [Алгоритмы, Облачные вычисления, Интернет-маркетинг, Управление e-commerce, Искусственный интеллект] Розничная цена: с головы или довериться алгоритмам
- [Ненормальное программирование, Разработка игр, Алгоритмы] Трассировка лучей в Notepad.exe со скоростью 30 кадров в секунду (перевод)
- [Алгоритмы, Криптовалюты] Алгоритм Ethash
- [Информационная безопасность, Криптография, Алгоритмы] Симметричный алгоритм блочного шифрования Advanced Encryption Standart
Теги для поиска: #_algoritmy (Алгоритмы), #_matematika (Математика), #_algoritm (алгоритм), #_matematicheskaja_zadacha (математическая задача), #_algoritmy (
Алгоритмы
), #_matematika (
Математика
)
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 10:44
Часовой пояс: UTC + 5
| Автор | Сообщение |
|---|---|
|
news_bot ®
Стаж: 6 лет 9 месяцев |
|
|
Спасибо добрым участникам Хабра, за то, что пригласили писать посты и получать на них фидбек.Сегодня я бы хотел осветить тему представления чисел с помощью ряда Фибоначи и разумеется написать простенькое REST API c использованием Mongo DB алгоритм с помощью языка Ruby, который бы по заданому числу N возвращал его представление. Часть 1 : представление ЦекендорфаКак гласит статья из Википедии : Теорема Цекендорфа гласит, что всякое натуральное число можно единственным образом представить в виде суммы одного или нескольких различных чисел Фибоначчи так, чтобы в этом представлении не оказалось двух соседних чисел из последовательности Фибоначчи.
100 = 89 + 8 + 3.
Лучший друг программиста.
Пример: N = 51 F = 1 , 1 , 2 , 3 , 5 , 8 , 13, 21, 34. Берём число 34, соседнее с ним число (21) можно сразу пропустить, ибо их сумма будет заведомо больше нашего входного числа N, ибо числа Фибоначи мы ищем пока они не превысят входное, ведь зачем нам числа больше входного :-). Но каким образом лучше всего посчитать сумму, простым перебором мы точно не добьемся первого условия : скорость работы . Сложным алгоритмом - откажемся от второго : максимальная простота кода. И тогда появилась идея: а что если отнимать от N последнее число в ряду Фибоначи, и искать новый ряд где эта разница будет лимитом, и рекурсивно продолжать это действия пока разница не станет <= 0. Пример: N = 51 F = 1 , 1 , 2 , 3 , 5 , 8 , 13, 21, 34. ans = [34] N = 51 - 34 = 17 F = 1 , 1 , 2 , 3 , 5 , 8 , 13. ans = [34 , 13] N = 17 - 13 = 4 F = 1 , 1 , 2 , 3. ans = [34 , 13 , 3] N = 4 - 3 = 1 F = 1 ans = [34 , 13 , 3, 1]Сразу попробую записать в код : def le_fib(limit, fib)
theoretical = fib[fib.count - 1] + fib[fib.count - 2] return fib.last if theoretical > limit fib << theoretical le_fib(limit, fib) end def main(target,result) temporary = le_fib(target, [1,1]) result << temporary return result if target - temporary <= 0 main(target - temporary, result) end pp main(gets.to_i,[])  Оценка времени работы в зависимости от величины ряда (входного числа)  Как видим время работы даже на числах до 10^9 очень позитивное.А общий обьем кода в 17 строк говорит о том что обе задачи выполнены успешно.Статья про интерес, всегда в рукаве нужно иметь пару задач с числами Фибоначе, иначе какой из тебя программист :-) =========== Источник: habr.com =========== Похожие новости:
Алгоритмы ), #_matematika ( Математика ) |
|
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 10:44
Часовой пояс: UTC + 5