使用 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 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始
广告