C ++でNを1、3、4の合計として表現するさまざまな方法の数

入力として正の数Nが与えられます。目標は、Nを1、3、4の合計としてのみ表現できる方法の数を見つけることです。たとえば、Nが4の場合、1 + 1 + 1 + 1、3 + 1、1 + 3、4として表すことができるため、ウェイの数は4になります。

例を挙げて理解しましょう。

例

入力- N =5

出力- Nを1、3、および4の合計として表すさまざまな方法の数は次のとおりです。6

説明- 5は次のように表すことができます：

• 1 + 1 + 1 + 1 + 1
• 1 + 3 + 1
• 3 + 1 + 1
• 1 + 1 + 3
• 4 + 1
• 1 + 4

入力- N =6

出力- Nを1、3、および4の合計として表すさまざまな方法の数は次のとおりです。9

説明- 9は次のように表すことができます：

• 1 + 1 + 1 + 1 + 1 + 1
• 3 + 1 + 1 + 1
• 1 + 3 + 1 + 1
• 1 + 1 + 3 + 1
• 1 + 1 + 1 + 3
• 3 + 3
• 4 + 1 + 1
• 1 + 4 + 1
• 1 + 1 + 4

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

このアプローチでは、動的計画法を使用して、Nを1、3、4の合計として表すことができる方法の数を数えます。配列arr [i]を取ります。ここで、iは数を表し、arr[i]はそれを表す方法です。合計として。

基本ケースは

arr [0] =0（まさか）

arr [1] =1（一方向のみ、1）

arr [2] =1（一方向のみ、1 + 1）

arr [3] =2（1 + 1 + 1、3）

これで、他の4、5…iなどの数字はarr [i-1] + arr [i-3] +arr[i-4]のようになります。

• 正の数Nを入力として使用します。
• 関数Expres_sum（int N）はNを取り、Nを1、3、および4の合計として表すさまざまな方法の数を返します。
• 配列arr[N+ 1]を使用して、ウェイの数を保存します。
• 基本ケースarr[0]=1、arr [1] =1、arr [2]=1およびarr[3]=2を初期化します。
• i=4からi<=Nまでの残りの値をトラバースします。
• テイクアウトarr[i]は、arr [i-1] + arr [i-3] +arr[i-4]の合計です。
• forループの最後に結果としてarr[N]を返します。

例

#include <bits/stdc++.h>
using namespace std;
int Expres_sum(int N) {
   int arr[N + 1];
   arr[0] = 1;
   arr[1] = 1;
   arr[2] = 1;
   arr[3] = 2;
   for (int i = 4; i <= N; i++) {
      arr[i] = arr[i - 1] + arr[i - 3] + arr[i - 4];
   }
   return arr[N];
}
int main() {
   int N = 5;
   cout << "Count of different ways to express N as the sum of 1, 3 and 4 are: " << Expres_sum(N);
   return 0;
}

上記のコードを実行すると、次の出力が生成されます-

出力

Count of different ways to express N as the sum of 1, 3 and 4 are: 6