Реализовать рекурсивную функцию, которая вычисляет число представлений своего натурального параметра. (с++)

Question

Вот полностью поставленная задача : Реализовать функцию, которая вычисляет число представлений своего натурального параметра в виде суммы натуральных слагаемых, порядок которых является существенным, то есть суммы 2 + 1 и 1 + 2 считаются различными. Есть код, который выводит все представления заданного числа в консоль, нужна помощь именно с рекурсивной функцией подсчета этих представлений. Заранее спасибо!

 #include<iostream>
#include <algorithm>
using namespace std;

int a[100];

void dec(int n, int k, int i);
int count_comp(int left);
int main() {
    setlocale(LC_ALL,"Rus");
    int number;
    cout << "Input:";
    cin >> number;
    for (int i = 0; i <= number; i++) {
        a[i] = 0;
    }
    cout << "Result:" << endl;
    dec(number, number, 0);
    return 0;
}
void dec(int n, int k, int i)
{
   
    if (n < 0) return;
    if (n == 0) {

        int j;
        for (j = 0; j < i; j++) {
            next_permutation(a, a + i);
            for (int h = 0; h < i; h++)
            {
                cout << a[h] << " ";
              
            }
            cout << endl;
        }
    }
    else
    {
        if (n - k >= 0)
        {
            a[i] = k;
            dec(n - k, k, i + 1);
           
        }

        if (k - 1 > 0) {
            dec(n, k - 1, i);
           
        }
    }
    return;
}

Answer 1

Ну хорошо, c учётом представления n=n:

int numallpartitions(int n) {
    if (n == 1)
        return 1;
    return 2 * numallpartitions(n-1);
}

без учёта:

    if (n == 0)
        return 0;
     return 1 + 2 * numallpartitions(n-1);

(Ещё короче будет с тернарным оператором

  return (n==0) ? 0: 1 + 2 * numallpartitions(n-1); //всё тело функции

Проверяем:

Почему так? Между n единицами числа можно поставить n-1 разделителей. Каждая расстановка разделителей даёт группировку единиц в набор чисел, а всего их 2^(n-1).

Answer 2

unsigned long long dec(int N)
{
    if (N == 1) return 1;
    else
    {
        unsigned long long s = 1;
        for(int i = 1; i < N; ++i) s += dec(N-i);
        return s;
    }
}

Если само число не учитывать — то минус 1.

Но еще проще возвести 2 в нужную степень, если не ошибаюсь :)

БЛОГ НА HUSL

Реализовать рекурсивную функцию, которая вычисляет число представлений своего натурального параметра. (с++)

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