Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Killspamers
0 / 0 / 2
Регистрация: 17.12.2011
Сообщений: 26
#1

Рекурсия: найти в последовательности такой набор чисел, сумма которых равна 100 - C++

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

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

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

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

В последовательности целых чисел найти пары, сумма которых равна заданному числу
Дана последовательность целых чисел а1, а2,..., аn. Указать пары чисел ai, aj,...

Найти все целые числа из промежутка от 100 до 300, у которых сумма делителей равна k
Найти все целые числа из промежутка от 100 до 300, у которых сумма делителей...

Не правильно работает... Программа должна найти непрерывные участки, на которых сумма элементов равна 100
Не правильно работает... Помогите исправить... Программа должна найти...

Рекурсия: найти подпоследовательность подряд идущих элементов последовательности, сумма которых минимальна
В данной последовательности чисел найти подпоследовательность подряд идущих...

Найти количество чисел в интервале [A, B], у которых сумма цифр равна 8 или 12
Помогите, плиз. Написать программу, которая находит сумму цифр числа и с ее...

Найти количество N-значных чисел, у которых сумма цифр равна их произведению
Найти количество N- значных чисел , у которых сумма цифр равна их произведению...

8
Kuzia domovenok
2210 / 1979 / 442
Регистрация: 25.03.2012
Сообщений: 6,947
Записей в блоге: 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);
}
 
}
1
Killspamers
0 / 0 / 2
Регистрация: 17.12.2011
Сообщений: 26
23.04.2012, 05:33  [ТС] #3
Спасибо конечно,но не понятно что такое malloc, calloc, free(a[0]). Слишком сложно для меня)
0
Kuzia domovenok
2210 / 1979 / 442
Регистрация: 25.03.2012
Сообщений: 6,947
Записей в блоге: 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++;}
1
Killspamers
0 / 0 / 2
Регистрация: 17.12.2011
Сообщений: 26
23.04.2012, 14:50  [ТС] #5
Не компилится =( (Visual C++ 2008)
error C3861: getdata: идентификатор не найден (5 строка)
error C2065: a: необъявленный идентификатор (15 строка)

А где сама рекурсивная функция?)
0
Kuzia domovenok
2210 / 1979 / 442
Регистрация: 25.03.2012
Сообщений: 6,947
Записей в блоге: 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;
}
рекурсии нет
1
Killspamers
0 / 0 / 2
Регистрация: 17.12.2011
Сообщений: 26
23.04.2012, 15:06  [ТС] #7
Так она мне и нужна
0
Kuzia domovenok
2210 / 1979 / 442
Регистрация: 25.03.2012
Сообщений: 6,947
Записей в блоге: 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;
}
сколько уже решений у этой задачи?
1
Killspamers
0 / 0 / 2
Регистрация: 17.12.2011
Сообщений: 26
23.04.2012, 15:21  [ТС] #9
Вот спасибище, то что нужно
0
23.04.2012, 15:21
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.04.2012, 15:21
Привет! Вот еще темы с решениями:

Найти первые 120 натуральных чисел, сумма цифр которых равна 10
Люди помогите пожалуйста! Для зачета не хватает одной проги на Си. Не могу...

Найти количество простых чисел, сумма цифр которых равна натуральному числу
В одномерном массиве, состоящем из N натуральных чисел найти количество простых...

Найти среди всех трёхзначных целых чисел те, у которых сумма цифр равна N
Народ я ешё новичёк в СИ! а препод злой задал задачку решить! плиз помогите...

Найти количество N-значных чисел, у которых сумма цифр равна их произведению (оптимизировать код)
Здравствуйте! Снова приходится просить помощи уважаемых знатоков. Сам в...


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

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

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