Я написал статью о рекурсивном алгоритме Цекендорфа : пост
Пример кода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” продукт.
Вот тут то я хочу присбособить этот алгоритм (Цекендорфа).
Главная идея в том что бы создать хэш (структура данных в Ruby) где ключ это число фиббоначи, а значение собственно имя продукта.
Задача есть, теперь перейдем к решению.
Запустим его в цикле от x до y и посчитаем количество вхождений каждого числа.
Как видим на малых Y вероятность того что число будет использовано в последовательности – равномерно распределенно так как верхняя граница чисел Фибоначчи постоянно растёт пропорционально к текущему числу в итерации.
Что мы с этого получили – чем больше входное число, тем выше вероятность получения одного и того же граничнего числа последовательности Фибоначчи.
Значит нам нужен отрезок с более равномерным распределением. Уменьшаем Y
Видим пик на крайних числах 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
Следующим шагом, слегка изменим алгоритм представления Цекендорфа :
Алгоритм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 тестовых прогонов, результаты будут в виде ответа от телеграмм бота.
Немного украшу сообщение от бота. Поскольку это никак не отражается на задаче – я не буду описывать этот шаг.
примечание :
Low cost : ?
Mid cost : ?
High cost : ?
Применения алгоритма представления Цекендорфа меня полностью удовлетворяет. Тоесть – выполняет поставленную перед ним задачу.
Один из первых комментов под статьей на которой основано это практическое приминение, как раз таки и ставил перед мной вопрос : “а действительно, где это применить можно?”. Как видим, вот для таких задач данный алгоритм вполне можно использовать.
И я не говорю о том что это единственный правильный вариант составления списка продуктов для моего бота, но он действительно вполне потян и работает.
VK объявляет о приобретении 40% компании Intickets.ru (Интикетс). Это облачный сервис для контроля и управления продажей билетов на мероприятия. Сумма…
OpenAI готовится запустить собственную поисковую систему на базе ChatGPT. Информацию об этом публикуют западные издания. Ожидается, что новый поисковик может…
Центр управления связью общего пользования (ЦМУ ССОП) Роскомнадзора рекомендовал компаниям из реестра провайдеров ограничить доступ поисковых ботов к информации на российских сайтах.…
Apple возобновила переговоры с OpenAI о возможности внедрения ИИ-технологий в iOS 18, на основе данной операционной системы будут работать новые…
Конкурсный управляющий российской «дочки» Google подготовил 23 иска к участникам рекламного рынка. Общая сумма исков составляет 16 млрд рублей –…
Google завершил обновление основного алгоритма March 2024 Core Update. Раскатка обновлений была завершена 19 апреля, но сообщил об этом поисковик…