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

рекурсивная функция - C++

Восстановить пароль Регистрация
 
Killspamers
0 / 0 / 0
Регистрация: 17.12.2011
Сообщений: 26
22.04.2012, 18:38     рекурсивная функция #1
Всем привет! Нужна помощь с программкой. Можете пожалуйста обьяснить, с чего начинать?

Дана последовательность из ста целых чисел. Найти такой набор чисел (не обязательно подряд идущих), чтобы их сумма была равна 100.

Тоесть я как понимаю нужно создать функцию которая будет просматривать массив с числами и складывать их, если они меньше ста? Ещё как их вывести на экран не понимаю: их их до прохождения функции записывать в массив надо или как?) Заранее спасибо.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.04.2012, 18:38     рекурсивная функция
Посмотрите здесь:

C++ Рекурсивная функция!
C++ Рекурсивная функция
Рекурсивная функция C++
Рекурсивная функция C++
C++ рекурсивная функция
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
22.04.2012, 19:40     рекурсивная функция #2
вот тут точно попробуй динамическое программирование.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <stdio.h>
#include <stdlib.h>
void Way(int* , int* , int , int );
///////////////////////////////////////////
int solve(int* p, int N, int target=100){
int i, j;
int **a=(int**)malloc(N*sizeof(int*));
a[0]=(int*)calloc(N*target*sizeof(int));
for (i=0; i<N; i++) a[i]=a[0]+i*target;
////////////////////////////////////////////
 
for(i=1; i<N; i++)
for(j=0; j<target; j++)
if (j-p[i]>=0) a[i-1][j]=max(a[i-1][j], a[i-1][j-p[i]]+p[i]);
else a[i][j]=a[i-1][j];
 
////////////////////////////////////////////
Way(p, a, );
////////////////////////////////////////////
free(a[0]);
free(a);
 
}
 
///////////////////////////////////////
void Way(int* p, int* a, int i, int j){
if ((i==0)&&(a[i][j]==0)) return;
if (i==1){
  Way(i, j-P[i]);
  printf("%d ", p[i]);
}
else{
  if (a[i][j]!=a[i-1][j]){
    Way(i, j-P[i]);
    printf("%d ", p[i]);
   }
   else way(i-1, j);
}
 
}
Killspamers
0 / 0 / 0
Регистрация: 17.12.2011
Сообщений: 26
23.04.2012, 05:33  [ТС]     рекурсивная функция #3
Спасибо конечно,но не понятно что такое malloc, calloc, free(a[0]). Слишком сложно для меня)
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
23.04.2012, 14:43     рекурсивная функция #4
Ну то что я использовал динамические массивы, без этого можно обойтись. Ведь у тебя заранее известно, что символов сто штук!
Есть ещё менее оптимальный вариант, который будет перебирать все 2 в сотой степени вариантов сумм чисел.

Это порядка 10000000000000000000000000000000 операций сравнения и сложения

Я не люблю неоптимальные варианты, но всё равно решил сделать его как альтернативу предыдущему решению.
Это несколько не тривиальный алгоритм в отличие от десятков о помощи со школьными заданиями тем в этом разделе.
Но раз тебе задали именно нахождение комбинации, дающей в сумме 100, думаю вы уже прошли многое по оптимизации алгоритмов перебора.
Эта программа читает 100 чисел из файла input.txt, который необходимо создать в папке с программой, и записать в него 100 чисел.
Если требуются пояснения - пиши.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <stdio.h>
#include <string.h>
int main(){
  int data[100];
  getdata(data);
  int dgts[100];
  int arws[100];
  int i, j, sum, run, target;
  FILE* in=fopen("input.txt", "r");
  for (i=0; i<100; i++) 
    fscanf(in, "%d", &(data[i]));
  printf("\nread numbers are:\n");
  for (i=0; i<10; i++){
    for(j=0; j<10; j++)
      printf("%d", a[i][j]);
    printf("\n");
  }
  printf("Enter expected sum:");
  scanf("%d", &target);
  memset(dgts, 0, 100*sizeof(int));
  memset(arws, 1, 100*sizeof(int));
  sum=0;
  run=1;
  while(run){
    i=0;
    while((dgts[i]+arws[i])!=0){arws[i]^=1; i++;}
    if (dgts[i]==0){
      dgts[i]=1;
      sum+=data[i];
    }
    else{
      dgts[i]=0;
      sum-=data[i];
    }
    if (sum==target){
      for(i=0; i<100; i++)
        if (dgts[i])printf("%d+", data[i]);
      printf("=%d", target);
      run=0;
    }
  } 
  fclose(in);
  return 0;
}
Добавлено через 16 минут
Ой, ошибка! Условие в цикле (строка 26) должно быть другое.
C++
1
while((dgts[i]+arws[i])!=1){arws[i]^=1; i++;}
Killspamers
0 / 0 / 0
Регистрация: 17.12.2011
Сообщений: 26
23.04.2012, 14:50  [ТС]     рекурсивная функция #5
Не компилится =( (Visual C++ 2008)
error C3861: getdata: идентификатор не найден (5 строка)
error C2065: a: необъявленный идентификатор (15 строка)

А где сама рекурсивная функция?)
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
23.04.2012, 14:59     рекурсивная функция #6
Ну да, я не в студии писал, а прям на форуме. забыл getdata убрать
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <stdio.h>
#include <string.h>
int main(){
  int data[100];
  int dgts[100];
  int arws[100];
  int i, j, sum, run, target;
  FILE* in=fopen("input.txt", "r");
  for (i=0; i<100; i++) 
    fscanf(in, "%d", &(data[i]));
  printf("\nread numbers are:\n");
  for (i=0; i<10; i++){
    for(j=0; j<10; j++)
      printf("%d", data[i*10+j]);
    printf("\n");
  }
  printf("Enter expected sum:");
  scanf("%d", &target);
  memset(dgts, 0, 100*sizeof(int));
  memset(arws, 1, 100*sizeof(int));
  sum=0;
  run=1;
  while(run){
    i=0;
    while((dgts[i]+arws[i])!=0){arws[i]^=1; i++;}
    if (dgts[i]==0){
      dgts[i]=1;
      sum+=data[i];
    }
    else{
      dgts[i]=0;
      sum-=data[i];
    }
    if (sum==target){
      for(i=0; i<100; i++)
        if (dgts[i])printf("%d+", data[i]);
      printf("=%d", target);
      run=0;
    }
  } 
  fclose(in);
  return 0;
}
рекурсии нет
Killspamers
0 / 0 / 0
Регистрация: 17.12.2011
Сообщений: 26
23.04.2012, 15:06  [ТС]     рекурсивная функция #7
Так она мне и нужна
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
23.04.2012, 15:20     рекурсивная функция #8
хорошо, вот вариант рекурсивной функции
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <stdio.h>
int data[100];
 
int solve(int id, int sum){
 if (sum==target){
   return 1;
 }
 
 if (sum<target){
   res=solve(id+1, sum+data[id]);
   if (res==1) {
       printf("%d ", data[id]); 
       return 1;
       }
   res=solve(id+1, sum);
   if (res==1)
       return 1;
 }
 return -1;
}
int main(){
  int data[100];
  int i, j, target;
  FILE* in=fopen("input.txt", "r");
  for (i=0; i<100; i++) 
    fscanf(in, "%d", &(data[i]));
  printf("\nread numbers are:\n");
  for (i=0; i<10; i++){
    for(j=0; j<10; j++)
      printf("%d", a[i][j]);
    printf("\n");
  }
  printf("Enter expected sum:");
  scanf("%d", &target);
  solve(0,0);
  fclose(in);
  return 0;
}
сколько уже решений у этой задачи?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.04.2012, 15:21     рекурсивная функция
Еще ссылки по теме:

Рекурсивная функция C++
Рекурсивная функция C++
Рекурсивная функция C++

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

Или воспользуйтесь поиском по форуму:
Killspamers
0 / 0 / 0
Регистрация: 17.12.2011
Сообщений: 26
23.04.2012, 15:21  [ТС]     рекурсивная функция #9
Вот спасибище, то что нужно
Yandex
Объявления
23.04.2012, 15:21     рекурсивная функция
Ответ Создать тему
Опции темы

Текущее время: 03:08. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru