1

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

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

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

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

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

4
  • Вам не к нам. а на маткод. И погуглите «линейные Диофантовы уравнения».
    – VladD
    28 сен 2014 в 15:04
  • Всем огромное спасибо за помощь! Решил 2мя способами: N1: перебор def McNuggets(n): """ n is an int Returns True if some integer combination of 6, 9 and 20 equals n Otherwise returns False. """ # Your Code Here for c in range(10): for b in range(10): for a in range(10): if n==6*a+9*b+20*c: return True return False 28 сен 2014 в 18:35
  • n2: рекурсия def McNuggets(n): if (n==0): return True else: if ( n<0 ): return False else: if ( McNuggets(n-6) or McNuggets(n-9) or McNuggets(n-20) )==True : return True else: return False 28 сен 2014 в 18:38
  • 3
    Я голосую за закрытие этого вопроса как не соответствующего теме, потому что это - математическая задача, а не вопрос программирования. 28 окт 2015 в 8:05

2 ответа 2

1

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

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

0
0

В конечном счете задача сводится к решению уравнения с тремя неизвестными. Вот, что мы имеем:

6a + 9b + 20c = N

Если упростить, то:

3(2a + 3b) + 20c = N
3(2a + 3b) = N - 20c
2a + 3b = (N-20c) / 3;

Далее ищем такое целое значение "c", чтобы (N - 20c) было числом, кратным тройке. Допустим, нашли (либо 0).
Нашли "с" и теперь получившееся значение (N-20c)/3 заменим, скажем, на "K":

2a + 3b = K
2a = K - 3b
a = (K-3b)/2

Теперь ищем такое целое значение переменной "b", чтобы (K-3b) было четным числом (кратным двойке). Получаем значение "b" и "a".

Надеюсь, общая идея понятна, потому как лично я не уверен, что описанный в этом виде алгоритм будет работать. Можем, например, найти такое "c", что число вроде бы получится кратным трем, но не таким, чтобы дальше и "a", и "b" состыковались с ним.

0

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.