Форум программистов, компьютерный форум, киберфорум
Наши страницы
C для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.50/4: Рейтинг темы: голосов - 4, средняя оценка - 4.50
Fibbo
0 / 0 / 0
Регистрация: 14.11.2013
Сообщений: 4
1

Не мог бы кто-нибудь объяснить рекурсию? (не простую как в примерах с факториалом)

14.11.2013, 11:06. Просмотров 739. Ответов 3
Метки нет (Все метки)

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

Код на С я потерял, а в разделе питона нет подраздела для новичков, так что напишу на питоне, разницы все равно почти нет:

Python
1
2
def McNuggets(n):
    return n >= 0 and (n == 0 or n % 6 == 0 or n % 9 == 0 or n % 20 == 0 or McNuggets(n - 6) or McNuggets(n - 9) or McNuggets(n - 20))
Вот какую задачу этот код призван решать:

McDonald’s sells Chicken McNuggets in packages of 6, 9 or 20 McNuggets. Thus, it is possible, for example, to buy exactly 15 McNuggets (with one package of 6 and a second package of 9), but it is not possible to buy exactly 16 McNuggets, since no non- negative integer combination of 6's, 9's and 20's add up to 16. To determine if it is possible to buy exactly n McNuggets, one has to find non-negative integer values of a, b, and c such that

6a + 9b + 20c = n

Write a function, called McNuggets that takes one argument, n, and returns True if it is possible to buy a combination of 6, 9 and 20 pack units such that the total number of McNuggets equals n, and otherwise returns False.


Это задача из курса EDx(может кто знает). Я ее так и не решил, но вообще нашел вот такой вот код. Код работает правильно, с ним проблем нет. Проблема в том что я никак не могу понять как тут работает рекурсия. Может кто-нибудь объяснить пошагово либо дать ссылку куда следует, либо если для таких функций есть какое-то особенное название - дать это название. Спасибо.


На всякий случай:
Как работает
C
1
2
3
int factorial(int x) { 
    return !x ? 1 : x * factorial(x - 1);
}
я понимаю.
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.11.2013, 11:06
Ответы с готовыми решениями:

не мог бы кто нибудь объяснить ошибку с темплейтами
Добрый день, (или вечер) не мог бы кто нибудь помочь разобраться с ошибкой с темплейтами в...

Кто-нибудь может объяснить как это работает?
Именно создание списка не понятно main :: IO() main = do let fib = 0 : 1 : n <-...

Может кто нибудь объяснить на любом примере как сделать данное задание?
Спроектировать сеть и построить её модель в Cisco Packet Tracer. Сеть должна включать в себя 4 под...

Не мог бы кто-нибудь дать пособия для 1 курса с++
Не мог бы кто-нибудь помочь дать материал по программированию С++ для первого курса.

Кто нибудь может объяснить?
Посмотрите на глю! Кэто как?

3
gng
897 / 617 / 195
Регистрация: 08.09.2013
Сообщений: 1,663
14.11.2013, 12:20 2
На Си поленились перевести?
C
1
2
3
4
int mcn(int n) {
  return (n>=0) && (!(n%6) || !(n%9) || !(n%20)
          || mcn(n-6) || mcn(n-9) || mcn(n-20));
}
И на русский язык тоже?

Смысл простой. Если само число не делится ни на 6, ни на 9, ни на 20, то проверяем это же для чисел n-6, n-9 и n-20. Математика простая. Если аргумент меньше нуля - выход с false.
0
Fibbo
0 / 0 / 0
Регистрация: 14.11.2013
Сообщений: 4
14.11.2013, 15:21  [ТС] 3
Так, вроде бы разобрался. Правильно ли я понимаю происходящее в функции:

mcn(int 35)
!35%6 , 9, 20, поэтому:
mcn(int 35 - 6 = 29)
!29%6 , 9, 20, поэтому:
mcn(int 29 - 6 = 23)
!23%6 , 9, 20, поэтому:
mcn(int 23 - 6 = 17)
!17%6 , 9, 20, поэтому:
mcn(int 17 - 6 = 11)
!11%6 , 9, 20, поэтому:
mcn(int 11 - 6 = 5)
!5%6 , 9, 20, поэтому:
mcn(int 5 - 6 = -1)
Но -1 < 0, так что возвращаемся к предыдущему возвращенному значению и начинаем отнимать 9:
mcn(int 5 - 9 = -4)
Опять отрицательное значение. возвращаемся еще на ступень назад по, так сказать, ветке отнимания шестерки:
mcn(int 11 - 9 = 2)
...

И так пока не придем к ступени когда была отнята только одна шестерка, не отнимем от 29 девятку и не получим число делимое на 20.
Правильно, или это как-то по-другому работает?

Добавлено через 23 минуты
Перевод задачи:

МакДональдс продают Куриные Наггетсы в коробках по 6, 9 и 20 штук. Так что возможно например купить именно 15 наггетсов (1 коробка по 6 штук и 1 по 9), но невозможно купить именно 16, так как нет таких комбинаций чисел 6, 9, и 20 которые в сумме давали бы 16. Для того чтобы узнать можно ли купить n число наггетсов нужно найти положительные целые значения чисел a, b и с при которых

6a + 9b + 20c = n

Напишите функцию, которая принимает один аргумент - n и возвращает True если возможно купить такую комбинацию 6ти, 9ти и 20ти штучных коробок общее число наггетсов в которых равняется n, иначе функция возвращает False
0
gng
897 / 617 / 195
Регистрация: 08.09.2013
Сообщений: 1,663
14.11.2013, 17:51 4
Цитата Сообщение от Fibbo Посмотреть сообщение
И так пока не придем к ступени когда была отнята только одна шестерка, не отнимем от 29 девятку и не получим число делимое на 20.
Правильно, или это как-то по-другому работает?
Правильно.
1
14.11.2013, 17:51
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.11.2013, 17:51

Может кто нибудь объяснить асинхронность?
Здравствуйте, как я не пытался понять, что на самом деле происходит при асинхронном вызове, так и...

БОМБА это кто нибудь может объяснить?
Взгляните на статичтику http://www.liveinternet.ru/stat/ru/searches.html Гугля обогнал рамблер...

может кто нибудь объяснить что это за цифры
дана программа может кто нибудь объяснить что это за цифры s:5:3 program proga7; uses crt; var...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.