用 C++ 表示 N 為 1、3 和 4 的和的不同方法的計數

給定一個正數 N 作為輸入。目標是找到我們可以用僅 1、3 和 4 的和來表示 N 的方法的數量。例如，如果 N 是 4，則它可以表示為 1+1+1+1、3+1、1+3、4，因此方法的數量為 4。

讓我們透過例子來理解。

例如

輸入 -  N=5

輸出 - 用 1、3 和 4 的和表示 N 的不同方法的計數為：6

說明 - 5 可以表示為

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

輸入 - N=6

輸出 - 用 1、3 和 4 的和表示 N 的不同方法的計數為：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

以下程式中使用的方法如下

在這種方法中，我們將使用動態規劃方法來計算我們可以用 1、3 和 4 的和來表示 N 的方法的數量。取陣列 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 並返回用 1、3 和 4 的和表示 N 的不同方法的數量。
  • 取陣列 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

更新於： 2021年1月29日

699 次瀏覽

開啟你的 職業生涯

完成課程獲得認證

開始學習
廣告