Как решить задачу о быках, коровах и телятах на Haskell?

Question

[Koljasiko]

Бык стоит 10 рублей, корова - 5 рублей, телёнок - 0.5 рублей. Необходимо на 100 рублей купить 100 голов скота. Мне стало интересно, как такую задачу решить в Haskell? В императивных языках задача решается через вложенные циклы, но в Haskell их нет. Сколько ни пытался, решить задачу не смог.

Answer 1

[Александр Скуснов]

Один из вариантов (простенький, но не оптимальный) такой:

Prelude> [(bull, cow, calf) | bull<-[1..10], cow<-[1..20],calf<-[1..200], bull + cow + calf == 100, 10*bull + 5*cow +calf/2 == 100]
[(1.0,9.0,90.0)]

Answer 2

[mayton2019]

Эта задача похожа на поиск в глубину DFS и на задачу об укладке рюказака.

Как решить ее на Хаскеле - я пока не знаю. Надо думать. Особенно в части поиска
оптимальности и вообще доказательства того что решение существует.

Доказательство - важно если вы представите что цены на коров - иррациональные числа на пример.

Answer 3

[wiz]

Это жадный алгоритм. Сортировка + свёртка решат для любого количества любых цен.

Есть ещё чуть более весёлый вариант когда количество доступных для покупки позиций ограничено.