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

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

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

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

13.04.2009, 20:54. Просмотров 1391. Ответов 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.
Задача работает, но как обьяснить что она делает в функции?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.04.2009, 20:54
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Обьясните как работает рекурсия в данной задаче (C++):

Обьясните как работает рекурсия - C++
#include &lt;iostream&gt; using namespace std; int Multiply(int, int); int main() { int number; int exponent; cout&lt;&lt;&quot;Enter...

Обьясните, как работает цикл - C++
#include &lt;iostream&gt; #include &lt;string&gt; using namespace std; int main() { int j = 0; string str,str1; cout&lt;&lt;&quot;Enter str &quot;;...

обьясните пожалуйта как работает программа - C++
#include &lt;sstream&gt; #include &lt;iostream&gt; int main() { std::stringstream ss; long int u, count = 0; std::cout &lt;&lt;&quot;Vvedite celoe...

Обьясните что происходит в данной функцие - C++
Объясните неучу, очень интерестно что происходит в if ((....)) do { std::cout &lt;&lt; &quot;Введите число: &quot;; std::cin &gt;&gt; num; ...

Обьясните понятие как работает Операция языка - C++
Простите пожалуста, если я не видел аналогичной темы. Вот Операции сдвига ( « и » ) применяются к целочисленным операндам....

метод гауса..обьясните как работает программа - C++
ipMatr(); for(opMatr(),k=0;k&lt;=n;k++) //прямой ход метода Гаусса; {for(aa=fabs(a),i=k,j=k+1;j&lt;=n;j++)//поиск макс....

3
Alexiski
Любитель давать советы
340 / 132 / 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
1
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
0
Evg
Эксперт CАвтор FAQ
18449 / 6499 / 454
Регистрация: 30.03.2009
Сообщений: 18,129
Записей в блоге: 29
18.04.2009, 23:45 #4
Цитата Сообщение от Blade Посмотреть сообщение
А вот как в этой проге сделать вывод вариантов?
Например даны монеты 5 и 10. Сумма 15.
Нужно чтоб выводило:
3 монеты достоинтсвом 5 и 0 монет достоинтсвом 10
1 монет достоинством 5 и 1 монет достоинством 10
Судя по всему, после строки "if(S==K) cnt++;" надо распечатать первые N элементов массива a
0
18.04.2009, 23:45
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.04.2009, 23:45
Привет! Вот еще темы с ответами:

Функция C++ в php или обьясните по подробнее как она работает - C++
typedef std::basic_ostringstream&lt;Char&gt; OStringStream; std::string ByteArrayToHexStr(uint8 const* bytes, uint32 arrayLen) { ...

Тема: Циклы, функции. Написать программу по данной задаче - C++
:help: Задача решается без использования массивов и строк. Последовательно вводится некоторое количество целых чисел. Определить...

Тема: Циклы, строковый тип. Написать программу по данной задаче - C++
:help: В строке записан текст, в котором слова разделены знаками препинания (пробел : , - ; ), в конце предложения стоит точка, ? или...

Как работает рекурсия? - C++
Ребята! Вот дошёл до темы рекурсия, и вроде тему из школы роходили, но смотрю на программу, и что-то не могу понять вот эту строку: ...


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

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

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