C++で「n」を奇数の整数の合計として表現する方法を数える

例

入力

n=6

出力

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

説明

The ways in which we can express ‘n’ as sum of odd integers −
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

説明

The some of the ways in which we can express ‘n’ as sum of odd integers:
1. 1+1+1+1+1+1+1+1+1
2. 3+3+3
3. 5+3+1
4. 7+1+1
5. ….and other such combinations

以下のプログラムで使用されるアプローチは次のとおりです −

このアプローチでは、n-1番目とn-2番目の数値である以前の数値からの奇数の整数の合計として数値を表す方法を確認します。ウェイはway（n-1）+ Ways（n-2）になります。

• 入力として整数nを取ります。

• 関数odd_ways（int n）は数値を受け取り、「n」を奇数の整数の合計として表現する方法の数を返します。

• 長さn+1の配列arrを取り、奇数の整数の合計として数値を表すためのカウント方法を格納します。

• 番号0の場合、そのような方法はないので、arr[0]を0に設定します。

• 1番の場合、方法は1つしかないため、arr[1]を1に設定します。

• 残りの数値については、2からnの間のiに対してarr [i-1] +arr[i-2]を使用してarr[i]を設定できます。

• 最後に、nが奇数の整数の合計として表される方法の数についてarr[n]があります。

• 結果としてarr[n]を返します。

例

#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