Русский
Русский
English
Статистика
Реклама

Рекурсивный алгоритм представления Цекендорфа

Приветики-омлетики

Спасибо добрым участникам Хабра, за то, что пригласили писать посты и получать на них фидбек.

Сегодня я бы хотел освятить тему представления чисел с помощью ряда Фибоначи и разумеется написать простенькое 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)enddef main(target,result)  temporary = le_fib(target, [1,1])  result << temporary  return result if target - temporary <= 0  main(target - temporary, result)endpp main(gets.to_i,[])

Функция le_fib - рекурсивно ищет ряд Фибоначи с пределом, на то, что бы следующее число не было больше чем входное число target. Здесь важно, что нас не интересует ряд Фибоначи целиком, нам важно лишь его окончание.

Функция main - рекурсивно ищет масcив, числа которого есть числами Фибоначе, и которые бы в сумме давали нам входное число.

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

Пример работы для 20 случайных чисел до 1000

Оценка времени работы в зависимости от величины ряда (входного числа)

Как видим время работы даже на числах до 10^9 очень позитивное.

А общий обьем кода в 17 строк говорит о том что обе задачи выполнены успешно.

Статья про интерес, всегда в рукаве нужно иметь пару задач с числами Фибоначе, иначе какой из тебя программист :-)

Источник: habr.com
К списку статей
Опубликовано: 31.12.2020 00:22:22
0

Сейчас читают

Комментариев (0)
Имя
Электронная почта

Алгоритмы

Математика

Алгоритм

Математическая задача

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru