1

Не понимаю способа решения данной задачи. Помогите, прошу, натолкните на путь истинный.

Однажды мама попросила Петю сходить в магазин и купить ровно n фруктов. Придя в магазин он увидел, что может купить яблоки, бананы, апельсины и айву. Но он не может купить произвольное количество каждого вида фруктов:

  • Бананы продаются гроздьями по 5 бананов в каждой, поэтому их количество должно быть кратно пяти.
  • Петя и его сестра одинаково сильно любят яблоки, поэтому количество яблок должно быть чётным.
  • Апельсинов в магазине осталось всего 4 штуки.
  • Петя не очень любит айву, поэтому не будет покупать больше одной.

Посчитайте, сколько всего различных способов купить n фруктов есть у Пети. Входные данные: Единственная строка содержит одно целое число n(1⩽n⩽109) — количество фруктов. Результат Нужно вывести одно число — количество способов купить n фруктов.

9
  • 1
    Минусаторам: тут совсем не нужно решать задачу за автора. Объясните алгоритм на псевдокоде, этого будет вполне достаточно.
    – Nick Volynkin
    27 сен 2017 в 14:52
  • Андрей, вас же устроит просто объяснение алгоритма решения?
    – Nick Volynkin
    27 сен 2017 в 14:53
  • @NickVolynkin, Конечно устроит. Буду рад его увидеть! 27 сен 2017 в 14:54
  • 1
    Похоже на эту задачу ru.stackoverflow.com/questions/581668/581750 только предположить что во входном массиве лежит несколько раз по минимальному количеству фруктов каждого вида, только 1 т.е. айву только 1 раз. и конечно массива никакого делать не надо а укладывать по мере необходимости. И видимо начинать с минимальной корзины, где сразу лежит каждый вид по 1 разу, если задача купить все виды обязательно (в условиях этого вроде как не сказано, но возможно подразумевается)
    – Mike
    27 сен 2017 в 15:33
  • @АндрейСухой отлично, тогда чуток поменяю метки.
    – Nick Volynkin
    27 сен 2017 в 15:52

1 ответ 1

1

Вообще, мы здесь имеем дело с т.н. сочетаниями с повторениями. Количество сочетаний с повторениями вычисляется по следующей формуле:

С n по k с повторениями

Для 109 это будет 227920 сочетаний. Число не астрономическое, можно перебирать их все и считать те, которые отвечают условиям задачи. Но делать этого мы всё-таки не будем.

Мы разделим задачу на ряд мелких. Для этого нам понадобятся 4 вложенных цикла со счётчиком. Выглядит это примерно так:

s = 0  # количество возможных сочетаний

for x in range(0,2):  # x - количество айвы
    if (n-x) < 4 : max_o = n - x  # проверим, сколько апельсинов поместится в нашу покупку 
    else: max_o = 4 
    for o in range(0,max_o+1):  # o - количество апельсинов
        for a in range(0,n-x-o+1,2):  # a - количество яблок. Счётчик прибавляет по 2 яблока за шаг!
            if (n-x-o-a) % 5 == 0: s += 1 # Мы выполнили три условия.
                                          # Но делится ли оставшееся место на 5 (кратность количества бананов)? 
                                          # Если да, то мы выполнили все условия и можем засчитать это сочетание.  

Разумеется, порядок вложенности циклов можно изменять как угодно. Главное - сохранять суть алгоритма: 3 условия выполняем, 1 проверяем.

2
  • Раз вы уж формулу привели, может вы хоть скажете, почему при данных условиях задачи количество сочетаний получается всегда на 1 больше требуемого количества фруктов и вся программа сводится к print(n+1) ?
    – Mike
    28 сен 2017 в 11:30
  • Насчёт n+1 нужно немного подумать. Я не запускал код, поэтому не заметил. Спасибо. 28 сен 2017 в 12:28

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

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