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

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

Войти
Регистрация
Восстановить пароль
 
Killspamers
0 / 0 / 0
Регистрация: 17.12.2011
Сообщений: 26
#1

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

22.04.2012, 18:38. Просмотров 593. Ответов 8
Метки нет (Все метки)

Всем привет! Нужна помощь с программкой. Можете пожалуйста обьяснить, с чего начинать?

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

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

Рекурсивная функция - C++
Выручайте! Очень нада сдать, сам не знаю как сделать. Описать рекурсивную функцию Combin2(N, K) целого типа, находящую C(N, K) — число...

рекурсивная функция - C++
написал программу вот такую как ее оформить в виде рекурсивной функции . эта программа проверяет на палиндром строку от i до j ...

Рекурсивная функция - C++
Задача

Рекурсивная функция - C++
Составить прогруамму для вычисления , где , для вычисления n!!, использовать рекурсивную типизированную функцию.

Рекурсивная функция - C++
Здраствуйте, пытаюсь написать лабу для нахождения пути в лабиринте, выбрал волновой алгоритм Ли. Для начала хочу просто заполнить...

рекурсивная функция - C++
Требуется разработать рекурсивную функцию, возвращающую значение для вычисления n-го члена последовательности b1=5, bn+1=bn/n2+n+1 ...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,925
Записей в блоге: 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
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,925
Записей в блоге: 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
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,925
Записей в блоге: 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
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,925
Записей в блоге: 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;
}
сколько уже решений у этой задачи?
Killspamers
0 / 0 / 0
Регистрация: 17.12.2011
Сообщений: 26
23.04.2012, 15:21  [ТС] #9
Вот спасибище, то что нужно
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.04.2012, 15:21
Привет! Вот еще темы с ответами:

Рекурсивная функция С++ - C++
Написать рекурсивную функцию (+ саму программу), которая подсчитывает сумму элементов одномерного массива.

Рекурсивная функция - C++
С клавиатуры вводится массив из 20 элементов. Заменить все отрицательные элементы суммой чётных! int x,h; void input(int i){ ...

Рекурсивная функция C++ - C++
Сосчитать f(y)=3y+5, yk - входное данное.

Рекурсивная функция! - C++
Разработать рекурсивную функцию, возвращающую значение , для вычисления n-го члена последовательности b1 =5, bn+1=bn/(n2+n+1). Не знаю...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
23.04.2012, 15:21
Ответ Создать тему
Опции темы

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