Создать функцию расклада числа N на k слагаемых

Question

Доброго времени суток форумчанам))

Задача нынче стоит следующая: Разработать функцию, которая определяет и выводит на экран все возможные разложения заданного натурального числа N (10 <= N <= 1000) на k (1 <= k <= 5) различных ненулевых слагаемых. С клавиатуры ввести целое число, принадлежащее указанному диапазону. Используя разработанную функцию, предоставить возможные варианты разложения введенного числа на заданное количество слагаемых. Подсказка: в функции целесообразно воспользоваться циклом перебора возможных слагаемых.

#include <stdio.h>

int a[50];
int c = 0, k;

void get_numbers (int pos, int n) {
     int i;
     for (i = 1; i < n; i++) {
          a[pos] = i;
          get_numbers(pos+1, n-i);
     }

     if (pos == k-1) {
          for (i = 0; i <= pos-1; i++)
          printf("%d + ", a[i]);
          printf("%d\n", n);
          c++; 
     }
  }

int main(void) {
int num;
printf("num = ");
scanf_s("%d", &num);
if (num < 10 || num > 1000) {
    printf("Incorrect enter of 'N'");
    return 1;
}

printf("k = ");
scanf_s("%d", &k);
if (k < 1 || k > 5) {
    printf("Incorrect enter of 'k'");
    return 1;
}

printf("-----------------------\n");
get_numbers(0, num);
printf("-----------------------\n");
printf("c = %d\n", c);
return 0;
}

Вывод результатов:

num = 25
k = 2
-----------------------
1 + 24
2 + 23
3 + 22
4 + 21
5 + 20
6 + 19
7 + 18
8 + 17
9 + 16
10 + 15
11 + 14
12 + 13
"13 + 12
14 + 11
15 + 10
16 + 9
17 + 8
18 + 7
19 + 6
20 + 5
21 + 4
22 + 3
23 + 2
24 + 1"
-----------------------
c = 24

Есть идеи как сделать так, чтобы выделенного кавычками не было. Потому что из-за этого(но это не точно), начиная с num = 30, программа очень долго думает и долго не выводит результат.

Я сделал вариант который не "отзеркаливает" то, что уже было сверху. НО там не используется рекурсия, а по условию нужно именно с рекурсией((

Answer 1

Чтобы не печатать варианты которые отличаются только порядком слагаемых нужно порождать только суммы в которых слагаемые строго возрастают. Заодно это удовлетворит требованию различности: "на k (1 <= k <= 5) различных ненулевых слагаемых".

Код будет вроде такого (показаны только изменённые строки):

...
void get_numbers (int pos, int n, int m) {
...
     for (i = m; i < n; i++) {
...
          get_numbers(pos+1, n-i, i+1);
...
     if (pos == k-1 && n >= m) {
...
get_numbers(0, num, 1);
...

Получившийся код работает медленно. Чтобы его ускорить надо перестать делать бесполезные рекурсивные вызовы. Самая маленькая сумма в вызове get_numbers(pos, n, m) равна m + (m + 1) + (m + 2) + ... + (m + k - pos - 1). В сумме k - pos слагаемых. Эта сумма равна (k - pos) * (m + m + k - pos - 1) / 2. Рекурсивный вызов бесполезен если

(k - pos) * (m + m + k - pos - 1) / 2 > n

Вторая причина медлительности - печать:

...
1 + 34 + 51 + 284 + 630
1 + 34 + 51 + 285 + 629
1 + 34 + 51 + 286 + 628
1 + 34 + 51 + 287 + 627
...

Начала строк повторяются. Но мы снова и снова преобразуем одни и те же числа в строки.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void print_sums(int n, int k, int m, char *head, char *tail) {
    if (k == 1) {
        printf("%s%d\n", head, n);
    } else {
        // k * (2 * i + k - 1) <= 2 * n 
        // i <= (2 * n / k - k + 1) / 2
        const int m2 = (2 * n / k - k + 1) / 2;
        for (int i = m; i <= m2; ++i) {
            sprintf(tail, "%d + ", i);
            print_sums(n - i, k - 1, i + 1, head, tail + strlen(tail));
        }
    }
}

int main() {
    int n;
    int k;
    if (scanf("%d%d", &n, &k) != 2) {
        return 1;
    }
    char *expr = malloc(k * 30);
    if (expr == NULL) {
        return 1;
    }
    print_sums(n, k, 1, expr, expr);
}

$ gcc -std=c11 -pedantic -Wall -Wextra -Werror -O3 terms.c

$ echo 20 5 | ./a.out 
1 + 2 + 3 + 4 + 10
1 + 2 + 3 + 5 + 9
1 + 2 + 3 + 6 + 8
1 + 2 + 4 + 5 + 8
1 + 2 + 4 + 6 + 7
1 + 3 + 4 + 5 + 7
2 + 3 + 4 + 5 + 6

$ time echo 1000 5 | ./a.out | wc -l
336912737

real  1m11.511s
user  1m15.584s
sys   0m4.788s

Answer 2

Если не ошибся, то вот так можно:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

void doit(int N, int k, int m, int * sol, int K)
{
    if (k == 0 && N == 0)
    {
        for(int i = 0; i < K; ++i)
        {
            printf("%d%c", sol[i], (i == K-1) ? '\n' : '+');

        }
    }
    else if (N < 0 || m > N || k < 0) return;
    else
    {
        for(int i = m; i <= N; ++i)
        {
            sol[K-k] = i;
            doit(N-i,k-1,i+1,sol,K);
        }
    }
}

int main(int argc, const char * argv[])
{
    int N, k;
    scanf("%d %d",&N,&k);

    int * sol = malloc(sizeof(int)*k);
    doit(N,k,1,sol,k);

}

Рассматриваем все разделения числа N на k чисел, причем минимальное первое значение - m (так мы, во-первых, делаем все слагаемые разными, а во-вторых, избегаем дублей типа 12+13 и 13+12).

БЛОГ НА HUSL

Создать функцию расклада числа N на k слагаемых

Ответы (2 шт):