Как то в прошлом
Я написал статью о рекурсивном алгоритме Цекендорфа : пост
Пример кода
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ив, числа которого есть числами Фибоначчи, и которые бы в сумме давали нам входное число.
Хотя по правде говоря в комментах предложили более изящное решение :
Один цикл и делов
n, F = 100, [1, 2]
while F[-1] < n do
F << F[-2] + F[-1]
end
F.reverse.each do |f|
if f <= n
n -= f
print f
print '+' if n > 0
end
end
На практике я буду применять именно второй алгоритм так как он менее перегружен лишними действиями.
Постановка задачи куда мы будем "впихивать этот алгоритм"
Есть некий набор продуктов, условно говоря :
[ Курица, томаты, лаваш, грибы ].
Эти продукты имеют ценность, как себестоимость так и ценность для конечного пользователя.
К примеру градацию можно произвести такую
[ курица > томаты > грибы > лаваш ] .
Задача состоит в том что бы генерировать такой набор продуктов, который имел бы по крайней мере 1 "Low cost", и 1 "High cost" продукт.
#Update : Так как многие не могли осознать в чём состоит задача, я немного более подробно опишу её.
Пользователь должен в конечнем счете получить шаурму, набор продуктов из холодильника как промежуточный этап этого действия.
Набор продуктов из холодильника должен происходит постепенно, не больше 1 предмета за раз и когда все продукты кончатся, холодильник вновь заполняется.
Заполнять холодильник желательно таким способом, который бы включал как можно больше дешевых продуктов (Low cost) и как можно меньше High cost, но они должны точно быть, и быть должны разные, так как существует процедура обмена 2 дорогих продуктов на 1 любой другой.
А нужно это потому что холодильником будут пользоватса сразу несколько пользователей, соответствено продукты одни на всех, и что бы как-то наградить самого быстрого пользователся - ему дается возможность взять дорогой продукт и в последствии его поменять.
Кроме того курица заслужено дорогой продукт, но по прежднему важный ингридиент, и что бы его получить нужно "постараться".
Остальные ингредиенты не являются мусором. Иногда пользователю будет попадатся спец-заказ где вместо курицы - говядина, а, к примеру, вместо огурца - яблоко.
Вот тут то я хочу приспособить этот алгоритм (Цекендорфа).
Главная идея в том что бы создать хэш (структура данных в Ruby) где ключ это число Фиббоначи, а значение собственно имя продукта.
Задача есть, теперь перейдем к решению.
Для начала анализируем сам алгоритм
Запустим его в цикле от x до y и посчитаем количество вхождений каждого числа.
[1,100] [1,1000] Как видим на малых Y вероятность того что число будет использовано в последовательности - равномерно распределенно так как верхняя граница чисел Фибоначчи постоянно растёт пропорционально к текущему числу в итерации.
Что мы с этого получили - чем больше входное число, тем выше вероятность получения одного и того же граничнего числа последовательности Фибоначчи.
Значит нам нужен отрезок с более равномерным распределением. Уменьшаем Y[1,143] Видим пик на крайних числах 1 и 89. Что собственно отвечает постановке задачи, но при этом мы не теряем случайное равномерное выпадение "Middle cost" продуктов.
Предлагаю остановится на 3 варианте где x = 1 и y = 143.
Реализация
Программы куда будем прописывать алгоритм Цекендорфа, выглядят так :
Модуль-перечень продуктов (для возможной тематичности)
Collector, который загружает перечень продуктов и составляет Hash (где ключ -> число Фибоначчи, значение -> название продукта)
Такую струтуру я использую для возможной тематичности продуктов, достаточно просто создать новый перечень продуктов и передать в autoloader название новой тематики, что бы времено ввести новые продукты в оборот.
К слову говоря, всё это я делаю для Telegram бота , который создан по гайду описаном в другом посте.
Итак, написав небольшой парсер, на выходе получаем такой результат
Небольшой парсер
@fib = [1,2,3,5,8,13,21,34,55,89]
def collect_the_items
food_hash = Hash.new
(0..9).each do |iterator|
food_hash[@fib[iterator]] = FOOD.first[iterator]
end
puts food_hash.map{|key,value| "#{key} - #{value}"}
end
![](https://habrastorage.org/getpro/habr/upload_files/a93/e0e/e02/a93e0ee028a0b0d05be5af93503da38c.png)
Следующим шагом, слегка изменим алгоритм представления Цекендорфа :
Алгоритм
def get_sequence(limit)
result = [] n, fib = limit, [1, 2]
while fib[-1] < n do
fib << fib[-2] + fib[-1] end
fib.reverse.each do |f| if f <= n
n -= f
result << f
end
end
result
end
Я собираюсь использовать готовую последовательность и пройдя по ней - просто вывести все продукты по ключам.
Код функции
def generate_food
food_array = Collector.collect_the_items
food = []
rarity = rand(1..143)
get_sequence(rarity).each do |key|
food << food_array[key]
end
food
end
Похоже всё готово к тесту, проведу 6 тестовых прогонов, результаты будут в виде ответа от телеграмм бота.
Немного украшу сообщение от бота. Поскольку это никак не отражается на задаче - я не буду описывать этот шаг.
Результаты теста
![](https://habrastorage.org/getpro/habr/upload_files/180/e1f/135/180e1f135f05d9575171206d8c92656a.png)
![](https://habrastorage.org/getpro/habr/upload_files/0a9/7c5/f2e/0a97c5f2ea80c18fa6a40e6e2bfca6ab.png)
примечание :
Low cost : туалетка
Mid cost : мешок с долларом
High cost : магический шар
Результат
Применения алгоритма представления Цекендорфа меня полностью удовлетворяет. То есть - выполняет поставленную перед ним задачу.
Один из первых комментов под статьей на которой основано это практическое приминение, как раз таки и ставил перед мной вопрос : "а действительно, где это применить можно?". Как видим, вот для таких задач данный алгоритм вполне можно использовать.
И я не говорю о том что это единственный правильный вариант составления списка продуктов для моего бота, но он действительно вполне потян и работает.