Форум программистов, компьютерный форум, киберфорум
Наши страницы
C для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/4: Рейтинг темы: голосов - 4, средняя оценка - 5.00
CVB
99 / 90 / 53
Регистрация: 22.03.2011
Сообщений: 226
1

Задача на перебор с возвратами. Из последовательности выбрать последовательность.

27.11.2011, 12:15. Просмотров 662. Ответов 1
Метки нет (Все метки)

Написать программу (на чистой Си):

Даны натуральные числа m, a1, …, an. В последовательности a1, …, an выбрать последовательность ai1, ai2, …, aik (0≤i1 < i2 < …<ik ≤ n) такую, что ai1+…+ aik=m. Если такую последовательность выбрать невозможно, то следует об этом сообщить.

C
1
2
3
//Например:
m=5, n=3
a[0]=1, a[1]=2, a[0]=3
C
1
2
//Результат:
2,3//так как 2+3=5, и оно равно заданной m.
На картинке задача с нормальными индексами. Спасибо на перед. Очень прошу помочь.
0
Миниатюры
Задача на перебор с возвратами. Из последовательности выбрать последовательность.  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.11.2011, 12:15
Ответы с готовыми решениями:

Выбрать из введенной последовательности нулевые значения, и составить последовательность из их номеров
Добрый вечер, у меня проблема в написании программы, кто поможет с кодом? ...

Задача с циклом For. Выбрать из последовательности числа не меньше заданного
Составить программу с циклом for. (Заранее спасибо!)

Задача на перебор вариантов. Задача Л.Эйлера. Про чиновника
Задача Л.Эйлера. Некий чиновник купил лошадей и быков на сумму 1770 талеров. За...

Дана последовательность чисел ai. Построить новую последовательность, содержащую все простые числа исходной последовательности.
procedure TForm1.Button1Click(Sender: TObject); begin...

Вводится последовательность целых чисел,0 –конец последовательности. Определить, содержит ли последовательность хотя бы три отрицательных четных числа
Составить алгоритм решения задачи и написать программу на языке С++. В ...

1
Net_Wanderer
235 / 208 / 29
Регистрация: 08.06.2011
Сообщений: 467
27.11.2011, 22:04 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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <stdio.h>
 
#define N  9
 
enum { NOT_FOUND, FOUND };
 
int buf[N];
int bufp = 0;
int sum;
 
int process_term(int pos, int val, int *arr, int size);
 
int main()
{
    /*
     * There is a one trick: the sequence is preceded by zero,
     * fake-element, which are the other terms are processed by.
     * Maximum depth of recursion is the number of elements
         * in the sequence.
     */
    int arr[N] = {0, 1, 1, 3, 8, 2, 6, 5, 7};
    int val = 9;
    int i;
    
    printf("Sequence:");
    for (i = 1; i < N; i++)
        printf(" %d", arr[i]);
    printf("\nSum: %d\n", val);
 
    if (process_term(0, val, arr, N) == FOUND) {
        printf("Found:");
        for (i = 1; i < bufp; i++)
            printf(" %d", buf[i]);
        putchar('\n');
    } else
        printf("Not found!\n");
    return 0;
}
 
int process_term(int pos, int val, int *arr, int size)
{
    int prev_sum, prev_bufp;
 
    buf[bufp++] = arr[pos];
    sum += arr[pos];
 
    if (sum != val && pos == size-1)
        return NOT_FOUND;
 
    if (sum > val) 
        return NOT_FOUND;
    else if (sum < val) {
        for (pos += 1; pos < size; pos++) {
            prev_sum  = sum;
            prev_bufp = bufp;
 
            if (process_term(pos, val, arr, size) == FOUND)
                return FOUND;
 
            sum  = prev_sum;
            bufp = prev_bufp;
        }
        return NOT_FOUND;
    } else
        return FOUND;
}
пример работы
Sequence: 1 1 3 8 2 6 5 7
Sum: 9
Found: 1 1 2 5
Press any key to continue . . .
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.11.2011, 22:04

Дано число и две последовательности. Образовать последовательность, состоящую из элементов 1-й последовательности, которых нет во 2-й
Здравствуйте! Дано число M и две последовательности А1,...,АM и В1,...,ВM....

Дано число и две последовательности. Образовать последовательность, состоящую из элементов 1-й последовательности, которых нет во 2-й
Дано число M и две последовательности А1,...,АM и B1,...,BM. Образовать...

безопасное размещение ферзей методом поиска с возвратами
Помогите пожалуйста!!! Написать и отладить, используя средства Delphi,...


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

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

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