[Ruby, Программирование, Алгоритмы, Математика] Практическое применение алгоритма для представления Цекендорфа

Ответить на тему

Автор

Сообщение

news_bot ^®

Стаж: 6 лет 9 месяцев
Сообщений: 27286

news_bot ^® написал(а)
06-Янв-2021 01:31

Цитировать

Как то в прошлом Я написал статью о рекурсивном алгоритме Цекендорфа : пост Пример кода

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 и посчитаем количество вхождений каждого числа.

[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

Следующим шагом, слегка изменим алгоритм представления Цекендорфа :Алгоритм

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 : ?Результат Применения алгоритма представления Цекендорфа меня полностью удовлетворяет. Тоесть - выполняет поставленную перед ним задачу. Один из первых комментов под статьей на которой основано это практическое приминение, как раз таки и ставил перед мной вопрос : "а действительно, где это применить можно?". Как видим, вот для таких задач данный алгоритм вполне можно использовать.И я не говорю о том что это единственный правильный вариант составления списка продуктов для моего бота, но он действительно вполне потян и работает.
===========
Источник:
habr.com
===========
Похожие новости:

Теги для поиска: #_ruby, #_programmirovanie (Программирование), #_algoritmy (Алгоритмы), #_matematika (Математика), #_algoritm (алгоритм), #_prakticheskoe_primenenie (практическое применение), #_tsekendorf (Цекендорф), #_ruby, #_telegram, #_ruby, #_programmirovanie (
Программирование
), #_algoritmy (
Алгоритмы
), #_matematika (
Математика
)

Профиль ЛС

Ответить на тему

Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы

Текущее время: 22-Ноя 20:49
Часовой пояс: UTC + 5