Задача для Python

Рейтинг: 1Ответов: 1Опубликовано: 28.09.2014

Всем доброго времени суток!

Есть следующая задача:

Мак Дональдс продает жаренную курицу порциями по 6, 9, и 20 кусков. Возможно купить точно 15 кусков (если купить порцию из 6 и 9 кусков). Но точно 16 купить нельзя, поскольку ни одно сочетание сумм положительных значений 6, 9, и 20 не дадут в результате 16.

Задача написать фунцию, которая посчитает для любого числа n, возможно или нет купить точно n кусков курицы: 6a + 9b + 20c = n ////
a, b, c могут быть натуральными числами или 0.

С программированием проблем нет, а вот с математической точки зрения я понятия не имею, как к этому подойти. За любую идею, как это считать, буду очень признателен!!!!!

python математика
Источник: Stack Overflow на русском

Ответы

▲ 1Принят

Проще всего решить тупым перебором. Очевидно, что максимально возможное значение a равно N/6. Максимально возможное значение b = N/9. И так далее. Вот и делаем три вложенных цикла.

Это, конечно, самый наивный способ. Самый изящный, пожалуй, через рекурсию. Задаемся неким a (из приемлемого диапазона), задача сводится к более простой - всего N-a порций, которые надо разделить на две группы, по b и c порций. Чувствуете, куда я клоню? Python хоть и не Лисп, но такое вполне сможет, я думаю.