recursion - 再帰の実装

Question

整数kを合計として表すことができるさまざまな方法の数を見つけるための再帰的な方法。ここで、各オペランドはn未満の整数です...アルゴリズムを手伝ってください。この問題の再帰的な解決策を考えることはできません

Answer 1

基本的に、私の最初のアイデアは次のとおりです。

int numberOfWays(int x)
{
    if(x <= 1)
        return 0;
    if(x == 2)
        return 1;
    // else:
    int res = 0;
    int i;
    for(i = 1; i <= x / 2; i++)
        res += numberOfWays(x - i);
    return res;
}

私はそれにいくつかのテストと考えを与えるつもりですが、それだけです。

たぶん、いくつかの説明の言葉...

明らかに、整数の和 < 1 として 1 を書く方法はなく、整数 < 2 の和として 2 を書く方法は 1 つしかありません: 2 = 1 + 1.

そこから、物事は面白くなります。すべての整数 x > 2 は (x-1) + 1 として記述できます。再帰しているため、方法の数が得られます。(x-1) は整数 < (x-1) の合計として記述できます。の上。最終的に (xn) = 2 に到達し、1 が返されます。

そこから上に戻って、見つけた数を表す方法の数を合計すると、ほら :)