使用 C++ 計算重遇數（計數部分錯排）

給定兩個整數 N 和 k，我們需要計算 k 個點固定在其位置的錯排數。給定 k 的約束條件在 0 到 n 之間，因為當有 n 個點時，固定點的數量不能超過 n。

int N=4, k=2;
res = solve(N, k);


請注意，k 上至少條件不成立。必須精確且嚴格地有 k 個點在其原始索引上。這是一個數學問題。我們不解釋數學的證明和解釋，作為計算機科學專業的學生，我們可以使用數學家形成的結果。結果是，𝑹𝒆𝒄𝒐𝒏𝒕𝒓𝒆𝒔(𝒏, 𝒌) = 𝒏𝑪𝒌 ∗ 𝑹𝒆𝒄𝒐𝒏𝒕𝒓𝒆𝒔(𝒏− 𝒌, 𝟎)

讓我們來看一些輸入/輸出場景

假設 N 個點作為輸入，其中沒有分配固定點。獲得的結果值將是所有點的組合 -

Input: N = 4, k = 0
Result: 9

使用任何四個座標點，在沒有任何固定點的情況下，我們可以獲得 9 種不同的組合。

假設 N 個點作為輸入，其中所有點都已固定。獲得的結果值將是所有點的組合 -

Input: N = 4, k = 4
Result: 1

如果所有點都固定，則只獲得一個結果組合。

演算法

該演算法的基本思想源於各種軸上座標點的排列和組合的思想。因此，它用於識別在一張圖上繪製一組點的幾種方式。

  • 將點數和固定點數作為方法的輸入。

  • 我們應用組合公式來查詢不同的組合

  • 如果沒有輸入，程式返回 1。

  • 如果沒有固定點和一個座標，程式返回 0。

  • 如果沒有固定點，程式將遞迴呼叫以查詢所有組合，同時更改所有座標的位置。

  • 如果有固定點，則應用組合公式

示例

例如，讓我們考慮 N=3，k=1；因此，只有一個點必須在其原始索引上。

如果給定的點是 {1,3,2}、{3,2,1}、{2,1,3}，以下是用 C++ 編寫的實現重遇數的程式，其中我們計算指定固定點的排列數 -

#include <iostream>
using namespace std;
int nCr(int n, int r) {
   if (r==0 || r==n)
      return 1;
   return nCr(n-1, r-1) + nCr(n-1, r);
}
int solve(int N, int k) {
   if (N==0 && k==0)
      return 1;
   if (N==1 && k==0)
      return 0;
   if (k==0)
      return (N-1) * (solve(N-1, 0) + solve(N-2, 0));
   return nCr(N, k) * solve(N-k, 0);
}
int main() {
   int N=3, k=1;
   cout << solve(N, k);
   return 0;
}

輸出

3

結論

我們使用先前結果使用 DP 儲存最後一個值以進行更快的處理。此外，為了找到 nCr，我們可以使用一種最佳化的方法。

更新於: 2022年8月10日

213 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始
廣告