Задача на перебор с возвратами. Из последовательности выбрать последовательность. - 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; }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д