C++で整数nを奇数の和として表現する方法の数を求める

整数 n が入力として与えられたとき、「n を奇数の和として表現できる方法が何通りあるか」を求めるのがこの問題の目的です。例えば n = 3 の場合、「1+1+1」と「3」の2通りの表現方法があるため、答えは2となります。

入力例と出力例

入力

n=6

出力

Count of ways to express 'n' as sum of odd integers are: 8

解説

n = 6 を奇数の和で表現すると、以下の8通りがあります。

1. 1+1+1+1+1+1
2. 3+1+1+1
3. 1+3+1+1
4. 1+1+3+1
5. 1+1+1+3
6. 3+3
7. 1+5
8. 5+1

入力

n=9

出力

Count of ways to express 'n' as sum of odd integers are: 34

解説

n = 9 を奇数の和で表現する方法の一例は次のとおりです。

1. 1+1+1+1+1+1+1+1+1
2. 3+3+3
3. 5+3+1
4. 7+1+1
5. …その他の組み合わせも含め、合計34通り

アプローチの考え方

このプログラムでは、動的計画法（DP）の考え方を使います。ある数 n の表現方法の数は、直前の2つの数である「n−1 の表現方法の数」と「n−2 の表現方法の数」の和で求められるという性質を利用します。つまり、ways(n) = ways(n−1) + ways(n−2) という漸化式が成り立ちます。

• 整数 n を入力として受け取ります。
• 関数 odd_ways(int n) は、n を奇数の和として表現する方法の数を返します。
• 長さ n+1 の配列 arr を用意し、各数値についての表現方法の数を格納します。
• 0 を奇数の和で表す方法はないため、arr[0] = 0 とします。
• 1 の場合は「1」の1通りしかないため、arr[1] = 1 とします。
• i が 2 から n までの範囲で、arr[i] = arr[i−1] + arr[i−2] を順に計算していきます。
• 最終的に arr[n] に、n を奇数の和として表現する方法の総数が格納されます。
• arr[n] を結果として返します。

C++での実装例

#include<iostream>
using namespace std;
int odd_ways(int n){
    int arr[n+1];
    arr[0] = 0;
    arr[1] = 1;
    for(int i = 2; i <= n; i++){
        arr[i] = arr[i-1] + arr[i-2];
    }
    return arr[n];
}
int main(){
    int n = 6;
    cout<<"Count of ways to express 'n' as sum of odd integers are: "<<odd_ways(n);
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

Count of ways to express 'n' as sum of odd integers are: 8

まとめ

このように、フィボナッチ数列と同じ漸化式を利用することで、n を奇数の和として表現する方法の数を効率よく求められます。計算量は O(n) であり、再帰を使わず配列に結果を保存しながら処理を進めるため、大きな n に対しても高速に動作します。