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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 5.00
Blade
0 / 0 / 0
Регистрация: 30.11.2008
Сообщений: 13
#1

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

13.04.2009, 20:54. Просмотров 1373. Ответов 3
Метки нет (Все метки)

есть вот такая програмка:
Код
#include <stdio.h>
#include <conio.h>

int a[100],cnt=0,N,K;

void fun(long S, int tek)
{
 if(tek==N)
  {
   if(S==K) cnt++;
   return;
  }

for(int i=0; S+a[tek]*i<=K; i++)
 {
  fun(S+a[tek]*i, tek+1);
 }
}


void main()
{
int i;

clrscr();
printf("Vvedite hislo elementov: ");
scanf("%d",&N);
for(i=0;i<N;i++)
 {
  printf("Vvedite a[%d]: ",i+1);
  scanf("%d",&a[i]);
 }
printf("\nVvedite symmy: ");
scanf("%d",&K);
printf("\n------------------\n");
fun(0,0);
printf("Kolichestvo variantov = %d\n",cnt);

getch();
}
Обьясните как работает рекурсия?

Смысл задачи:
Задано количество элементов n.Каждый элемент-монета(a1-an),разного достоинства которое задает пользователь.Вводится сумма k.Нужно вывести количесво вариантов выдачи этой суммы данными монетами. Т.е. количество решиний уравнения a1x1+...+anxn=k.
Задача работает, но как обьяснить что она делает в функции?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.04.2009, 20:54     Обьясните как работает рекурсия в данной задаче
Посмотрите здесь:
C++ Обьясните как работает рекурсия
Обьясните, как работает цикл C++
обьясните пожалуйта как работает программа C++
Обьясните что происходит в данной функцие C++
Обьясните понятие как работает Операция языка C++
метод гауса..обьясните как работает программа C++
Функция C++ в php или обьясните по подробнее как она работает C++
C++ Тема: Циклы, функции. Написать программу по данной задаче
C++ Тема: Циклы, строковый тип. Написать программу по данной задаче
C++ Как работает рекурсия?
Не понимаю как работает рекурсия C++
Объясните как работает рекурсия C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Alexiski
Любитель давать советы
339 / 131 / 2
Регистрация: 12.01.2009
Сообщений: 511
13.04.2009, 23:32     Обьясните как работает рекурсия в данной задаче #2
Она довольно тупо работает. Перебирает все варианты сложения 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
Blade
0 / 0 / 0
Регистрация: 30.11.2008
Сообщений: 13
18.04.2009, 22:44  [ТС]     Обьясните как работает рекурсия в данной задаче #3
А вот как в этой проге сделать вывод вариантов?
Например даны монеты 5 и 10. Сумма 15.
Нужно чтоб выводило:
3 монеты достоинтсвом 5 и 0 монет достоинтсвом 10
1 монет достоинством 5 и 1 монет достоинством 10
Evg
Эксперт CАвтор FAQ
17528 / 5766 / 368
Регистрация: 30.03.2009
Сообщений: 15,854
Записей в блоге: 26
18.04.2009, 23:45     Обьясните как работает рекурсия в данной задаче #4
Цитата Сообщение от Blade Посмотреть сообщение
А вот как в этой проге сделать вывод вариантов?
Например даны монеты 5 и 10. Сумма 15.
Нужно чтоб выводило:
3 монеты достоинтсвом 5 и 0 монет достоинтсвом 10
1 монет достоинством 5 и 1 монет достоинством 10
Судя по всему, после строки "if(S==K) cnt++;" надо распечатать первые N элементов массива a
Yandex
Объявления
18.04.2009, 23:45     Обьясните как работает рекурсия в данной задаче
Ответ Создать тему
Опции темы

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