Форум программистов, компьютерный форум CyberForum.ru

Обьясните как работает рекурсия в данной задаче - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Код Хаффмана http://www.cyberforum.ru/cpp-beginners/thread29799.html
Люди подскажите, что это за зверь? и как его реализовать на с?
C++ Проверьте себя. А хорошо ли вы знакомы со switch'ом? В первую очередь смысл задачи не в том, что же там напечатается, а в том, что многие увидят несколько непривычный для себя код, который на первый взгляд даже покажется синтаксически ошибочным. А потому просьба к специалистам - не спешите сразу писать решение или пояснения - кому-то может оказаться интересным подумать над задачей. По этим же соображениям пропускаю отступы #include <stdio.h> ... http://www.cyberforum.ru/cpp-beginners/thread29774.html
C++ Massey-Omura
Люди добрые! Помогите кто чем может в написании прграммы, выполняющей этот алгоритм на С (желательно)...
C++ Case клавиш
Подскажите пожалуйста, как мне узнать какие case у клавиш: w, a, s, d и пробела. Заранее спасибо.
C++ Здраствуйте мои будущие колеги http://www.cyberforum.ru/cpp-beginners/thread29672.html
я не могу решить эту задачу помогите, если не трудно: Ребенок нарисовал кружки, и некоторые из них соединил отрезками. Кружки он пометил целыми числами от 1 до N, а на каждом отрезке поставил стрелочку. Затем он приписал каждому кружочку вес в виде некоторого целого числа и определил начальный и конечный кружочки. Из первого он должен выйти, а во второй попасть. Ребенок решил для себя набрать...
C++ Окно с активной областью? Написал прогу на С++,рисует в окошке фигуры,работа с классами,перегрузкой операций и так далее...(не суть как важно)....возникли проблемы...надо как то привязать область случайной генерации координат фигур и размерами окна...кажется через RectClient чтоли...чтобы за пределы окна не выходило....помогите кто в курсе плиз.... Добавлено через 15 минут 4 секунды Работа c MFC приложениями..... подробнее

Показать сообщение отдельно
Alexiski
Любитель давать советы
 Аватар для Alexiski
338 / 130 / 2
Регистрация: 12.01.2009
Сообщений: 511
13.04.2009, 23:32     Обьясните как работает рекурсия в данной задаче
Она довольно тупо работает. Перебирает все варианты сложения N чисел.

Смысл такой: первый аргумент - это накопленная сумма, второй - количество обработанных монет (или номер "текущей" монеты).
Мы последовательно входим в рекурсию, по однму виду монет на каждом шаге и параллельно наращиваем сумму. Когда обработаны все N монет, проверяем, если сумма равна К, то увеличиваем счетчик на 1. При возврате на предыдущий уровень рекурсии увеличиваем число "текущих" монет на 1 - и продолжаем перебор.

Проще разобрать на небольшом примере. Пусть массив 1, 2, 3 и надо набрать 4.
Последовательность вызовов будет такая:
Код
fun(0,0) 
   fun(0,1) - берем 0 монет по "1"
     fun(0,2) - берем 0 монет по "2"
        fun(0,3) - берем 0 монет по "3" - неудача
        fun(3,3) - берем 1 монет по "3" - неудача
     fun(2,2) - берем 1 монет по "2"
        fun(2,3) - берем 0 монет по "3" - неудача
     fun(4,2) - берем 2 монет по "2"
        fun(4,3) - берем 0 монет по "3" - успех, cnt=1    
   fun(1,1) - берем 1 монет по "1"
     fun(1,2) - берем 0 монет по "2"
        fun(1,3) - берем 0 монет по "3" - неудача
        fun(4,3) - берем 1 монет по "3" - успех, cnt=2
     fun(3,2) - берем 1 монет по "2"
        fun(3,3) - берем 0 монет по "3" - неудача
   fun(2,1) - берем 2 монет по "1"
     fun(2,2) - берем 0 монет по "2"
        fun(2,3) - берем 0 монет по "3" - неудача
     fun(4,2) - берем 1 монет по "2"
        fun(4,3) - берем 0 монет по "3" - успех, cnt=3
   fun(3,1) - берем 3 монет по "1"
     fun(3,2) - берем 0 монет по "2"
        fun(3,3) - берем 0 монет по "3" - неудача
   fun(4,1) - берем 4 монет по "1"
     fun(4,2) - берем 0 монет по "2"
        fun(4,3) - берем 0 монет по "3" - успех, cnt=4
 
Текущее время: 21:50. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru