將N表示為K個非零整數的不同方式

問題「將N表示為K個非零整數的不同方式」在許多現實世界的用例中都有應用。

密碼學 - 在密碼學中，使用將一個數字N編碼為K個非零整數總和的概念來設計特定的加密方法。

將一個整數N表示為K個非零整數的和可能會出現在最佳化方法的不同最佳化問題的子問題中。

機器學習− 在機器學習中，可以透過使用將整數N表示為K個非零整數總和的問題來建立描述資料點分佈的特徵向量。

Explanation

的中文翻譯為：

解釋

現在讓我們解碼這個問題。

假設我們有兩個正整數N和K，我們需要找出K個非零整數，它們的和等於N。例如，如果N=10且K=3，我們需要找出三個非零整數，它們的和等於10。在這種情況下可能的解有−

1 + 4 + 5
2 + 3 + 5
2 + 4 + 4

請注意，在這些解中，我們有K=3個非零整數，它們相加等於N=10。

解決這個問題有不同的方法，讓我們討論每一種方法。

遞迴方法

使用遞迴方法的逐步演算法，找出用K個非零整數表示N的不同方式。

• 在主函數中輸入N和K的值。

• 建立函數 f(N, K)，它傳回N可以表示為K個非零整數的總方式數。

• 如果K = 1，當N超過0時回傳1，否則回傳0。 （基本情況）。

• 如果 N == 0 或 K > N，則回傳 0。 (基本情況)。

• 建立一個變數 count 來儲存結果。

• 將變數count的值設定為0。

• 從1到min(N-K 1, N-1)對於每個整數I

• #遞迴計算 f (N-i, K-1)。

• 將結果加入計數中。

• 傳回計數。

Example

上述演算法的實作

#include <iostream>
using namespace std;

int f(int N, int K) {
   if (K == 1) {
      return (N > 0) ? 1 : 0; // base case
   }
   if (N <= 0 || K > N) {
      return 0; // base case
   }
   int count = 0;
   for (int i = 1; i <= min(N-K+1, N-1); i++) {
      count += f(N-i, K-1);
   }
   return count;
}

int main() {
   int N = 5, K = 2;
   
   int ways = f(N, K);
   cout << "Number of ways to represent " << N << " as the sum of " << K << " non-zero integers: " << ways << endl;
   return 0;
}

輸出

Number of ways to represent 5 as the sum of 2 non-zero integers: 4

複雜性

時間複雜度: O(N ^ K).

#空間複雜度: O(K)

二項式係數公式

星星和條紋組合方法可以用來得到一個正整數N可以表示為K個非零整數總和的方式的公式。

想像一排N顆星（*），它們代表給定整數的N個分區單元。可以使用K-1個垂直線（|）將星星排成K個段，代表分區的K個非零整數。

以將10分成3個非零整數為例。下面的星號和橫槓可以用來表示這個過程 −

* * | * * * | * * * * *

這個插圖的第一部分描繪了數字2，第二部分描繪了數字3，第三部分描繪了數字5。

在N顆星星的一行中排列K-1個條的方式數量等於用K個非零整數表示N的方式數。為了計算這個數量，我們使用公式：$\mathrm{C(N\: \:K\:-\:1,\:K\:-\:1)}$。

根據二項式係數公式 $\mathrm{C(n,k)\:=\:n!\:/(k!*(n-k)!)}$。

但在我們的情況下，我們需要排除包含0的可能性。為了排除包含0作為其中一個加數的分割，我們可以使用下列方法−

• 從N中減去1得到N-1。

• 將N-1分成K-1個非負整數。

• 將步驟2所得到的K-1個非負整數都加1，得到K個非零整數，它們的和為N。

這種方法有效的原因是每個加數的最小可能值是1（因為我們希望是非零整數），所以我們從N中減去1，以確保有足夠的單位可以分配給K個加數。

因此，我們得到公式：ways = C(N-1, K-1)

假設我們要找出用4個非零整數表示6的方式的數量。我們可以使用先前推導出的公式，即 −

C(N-1, K-1) = C(6-1, 4-1) = C(5, 3) = 10

這告訴我們將6分成4個非零整數有10種方法。

他們是 −

• 1 1 1 3

• 1 1 2 2

• 1 1 3 1

• 1 2 1 2

• 1 2 2 1

• 1 3 1 1

• 2 1 1 2

• 2 1 2 1

• 2 2 1 1

• 3 1 1 1

方法

讓我們討論實現上述方法的逐步演算法 -

• 在主函數中輸入N和K的值。

• 使用上述公式計算方法的數量。

• 列印出變數 ways 的值。

現在讓我們來寫一些程式碼。

範例

使用二項式係數方法的程式碼實作

#include <iostream>
using namespace std;

int binomial(int n, int k) {
   int res = 1;
   if (k > n - k) {
      k = n - k;
   }
   for (int i = 0; i < k; ++i) {
      res *= (n - i);
      res /= (i + 1);
   }
   return res;
}

int main() {
   int N = 7, K = 2;
   
   int ways = binomial(N - 1, K - 1);
   cout << "Number of ways to represent " << N << " as the sum of " << K << " non-zero integers: " << ways << endl;
   return 0;
}

輸出

Number of ways to represent 7 as the sum of 2 non-zero integers: 6

複雜性

時間複雜度: O( K).

空間複雜度: O(1)

結論

在這篇文章中，我們嘗試解釋了一種找出將N表示為K個非零整數總和的方法。我希望這篇文章能幫助你更理解這個概念。

以上是將N表示為K個非零整數的不同方式的詳細內容。更多資訊請關注PHP中文網其他相關文章！