Представление заданного числа в виде всевозможных сумм - C (СИ)

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

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

в программе подразумевается рекурсия,но в моем случае функция должна возвращать 2 значения,значит,надо писать структуры(которые мы еще не проходили) и с массивом работать нельзя. не могли бы вы мне подсказать алгоритм (возможно,моя реализация невозможна с помощью функции) вот мой код
#include <stdio.h>
#include <cstdlib>
#include <math.h>
 
int main()
{
    int n,t=0, k = 0,l=0;
    scanf_s("%d", &n);
 
    do
    {
        n = n - 1;
        k = k + 1;
        printf("%d",k);
        printf("+%d\n", n);
    } while (n > 0);
    if (k > 1)
    {
        do
        {
            k = k - 2;
            l = l + 1;
            if (k < 0) {
                break;
            }
            printf("1+%d", l);
            printf("+%d\n", k);
        } while (k > 0);
    }
    system("pause");
 
}

Решение задачи: «Представление заданного числа в виде всевозможных сумм»

textual
Листинг программы
#include <stdio.h>
#include <string.h>
#include <locale.h>
 
#define MAX_INT_LENGTH 12
 
void printAllSums(const int);
void decomposition(const int, const int, const char *);
int min(const int, const int);
 
int main(int argc, char *argv[])
{
    setlocale(LC_ALL, "RU");
 
    int x;
    printf("Введите число: ");
    scanf("%d", &x);
    printAllSums(x);
 
    return 0;
}
 
void printAllSums(const int x){
    decomposition(x, x, "");
}
 
void decomposition(const int n, const int m, const char str[]){
    if(!n){
        printf("%s\n", str);
        return;
    }
 
    for(int i=min(n, m); i >= 1; i--){
        char number[MAX_INT_LENGTH];
        sprintf(number, "%d", i);
 
        char newStr[strlen(str) + strlen(number) + 2];
        strcpy(newStr, str);
        strcat(newStr, " ");
        strcat(newStr, number);
 
        decomposition(n-i, i, newStr);
    }
}
 
int min(const int n, const int m){
    return n < m ? n : m;
}

Объяснение кода листинга программы

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

  1. В функции main устанавливается локальная настройка для вывода на русском языке.
  2. Пользователю предлагается ввести число.
  3. Число сохраняется в переменной x.
  4. Вызывается функция printAllSums с аргументом x.
  5. В функции printAllSums вызывается функция decomposition с аргументами x, x и пустой строкой ```` (в дальнейшем она будет дополняться числами).
  6. В функции decomposition используется рекурсивный подход для генерации всех возможных комбинаций чисел.
  7. Если число n равно 0, то текущая комбинация чисел печатается на экране.
  8. Если число n больше 0, то для каждого числа i от min(n, m) до 1 (включительно) создается новая строка number, которая содержит это число.
  9. Создается новая строка newStr, которая содержит исходную строку str, дополненную числом number, разделенными пробелом.
  10. Строка newStr передается в функцию decomposition с аргументами n-i, i и newStr.
  11. В функции min сравниваются числа n и m, и возвращается меньшее из них.
  12. Этот процесс повторяется для всех чисел i от min(n, m) до 1.
  13. Когда число n становится равным 0, текущая комбинация чисел печатается на экране.
  14. В функции main программа завершается после вывода всех комбинаций чисел.

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

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