Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Задача на квадратную матрицу http://www.cyberforum.ru/cpp-beginners/thread29901.html
Дана целочисленная квадратная матрица. Определить: 1) Сумму элементов в тех столбцах, которые не содержат отрицательных элементов; 2) Минимум среди сумм модулей элементов диагоналей,...
C++ С указателями. Поменять местами строку матрицы, содержащую минимальные элементы и строку матрицы содержащей последний чётный элемент Нужен полный текст программы, заранее благодарен http://www.cyberforum.ru/cpp-beginners/thread29871.html
C++ С использованием указателя. Даны два одномерных массива целых чисел А и В, сформировать массив С, содержащий элементы массива А , присутствующий в массиве В в нескольких экземплярах.
(Элементы массива С не должны повторяться) Нужен полный текст программы, заранее благодарен
Дана целочисленная квадратная матрица, найти количество строк с нечётной суммой элементов. C++
Нужен полный текст программы, заранее благодарен
C++ двумерный массив http://www.cyberforum.ru/cpp-beginners/thread29853.html
Дан целочисленный массив A. Заменить все элементы массива с максимальным значением на сумму цифр минимального элемента. написал, не работает! посмотрите пожалуйста где ошибки? #include...
C++ Множественное наследование Возник вопрос по теме множественное наследование. Вот скажем у нас определены классы: class Animal{ public: int GetAge(){return Age;} public: int Age; }; подробнее

Показать сообщение отдельно
Alexiski
Любитель давать советы
340 / 132 / 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
1
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru