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

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

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

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

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

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

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

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

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

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

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

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

А где сама рекурсивная функция?)
0
Kuzia domovenok
2316 / 2067 / 478
Регистрация: 25.03.2012
Сообщений: 7,366
Записей в блоге: 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 / 0
Регистрация: 17.12.2011
Сообщений: 26
23.04.2012, 15:06  [ТС] 7
Так она мне и нужна
0
Kuzia domovenok
2316 / 2067 / 478
Регистрация: 25.03.2012
Сообщений: 7,366
Записей в блоге: 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 / 0
Регистрация: 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

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

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

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


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

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

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