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

Узнай цену своей работы

Формулировка задачи:

Написать программу (на чистой Си): Даны натуральные числа m, a1, …, an. В последовательности a1, …, an выбрать последовательность ai1, ai2, …, aik (0≤i1 < i2 < …<ik ≤ n) такую, что ai1+…+ aik=m. Если такую последовательность выбрать невозможно, то следует об этом сообщить.
//Например:
m=5, n=3
a[0]=1, a[1]=2, a[0]=3
//Результат:
2,3//так как 2+3=5, и оно равно заданной m.
На картинке задача с нормальными индексами. Спасибо на перед. Очень прошу помочь.

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

textual
Листинг программы
#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;
}

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

9   голосов , оценка 3.778 из 5
Похожие ответы