Java 中的 Rencontres 数

我们有两个数字。第一个数字是一个整数，用 n 表示，第二个数字是一个非负数，小于或等于 n，用 k 表示。任务是找出给定数字 n 和 k 的所有错排（disarrangements）的总数，使得只有 k 个元素处于其原始位置。换句话说，我们需要找到错排的总数。总的

示例 1

输入： int n = 3, int k = 0

输出 2

解释： k 的值为 0。这意味着没有数字需要处于其原始位置。错排是 {2, 3, 1} 和 {3, 1, 2}。

示例 2

输入： int n = 3, k = 1

输出 3

解释： k 的值为 1。因此，只有一个数字应该处于其原始位置。因此，我们得到的错排是
是 {2, 1, 3}, {1, 3, 2}, 和 {3, 2, 1}。

方法：使用递推关系
在数学中，重数 D(n, k) 表示部分错排的总数。递推关系如下：

D(n, k) = ⁿC_k x D(n - k, 0)，当 k = 0 时，关系可以表示为：

D(n, 0) = (n - 1) * (D(n - 1, 0) + D(n - 2, 0))
基础情况如下：

D(0, 0) = 1, D(0, 1) = 0, 和 D(1, 0) = 0

因此，
对于 n = 1, k = 1，我们得到：
D(1, 1) = ¹C₁ x D(1 - 1, 0) = 1 x D(0, 0) = 1 x 1 = 1

对于 n = 2, k = 1，我们得到：
D(2, 1) = ²C₁ x D(2 - 1, 0) = 2 x D(1, 0) = 2 x 0 = 0

对于 n = 3, k = 1，我们得到：
D(3, 1) = ³C₁ x D(3 - 1, 0) = 3 x D(2, 0)

现在，我们需要找到 D(2, 0) 的值，可以通过另一个递推关系找到。
D(n, 0) = (n - 1) x (D(n - 1, 0) + D(n - 2, 0))

D(2, 0) = (2 - 1) x (D(2 - 1, 0) + D(2 - 2, 0)) = 1 x (D(1, 0) + D (0, 0)) = 1 x (0 + 1) = 1 x 1 = 1

因此，我们得到：

D(3, 1) = 3 x D(2, 0) = 3 x 1 = 3

现在，让我们实现上述关系。

文件名： RencontresNumberRec.java

输出

For the value of n = 7 and k = 2, the total number of derangements are: 924
For the value of n = 3 and k = 1, the total number of derangements are: 3
For the value of n = 1 and k = 1, the total number of derangements are: 1

复杂度分析： 程序的时间复杂度为 O(n x k)，其中 n 和 k 表示输入整数。由于递归栈，程序的空间复杂度也为 O(n x k)。

方法：使用动态规划

在此方法中，我们将首先将问题分解为更小的子问题，然后解决这些子问题。我们将解决方案存储在一个二维数组中，然后使用它来找到给定问题的解决方案。

文件名： RencontresNumDP.java

输出

For the value of n = 7 and k = 2, the total number of derangements are: 924
For the value of n = 3 and k = 1, the total number of derangements are: 3
For the value of n = 1 and k = 1, the total number of derangements are: 1

复杂度分析：程序的 time complexity 和 space complexity 与上一个程序相同。