算法之错排

问题简述

原问题:十本不同的书放在书架上。现重新摆放,使每本书都不在原来放的位置。有几种摆法?

把这个问题推广一下,就是错排问题: n个有序的元素应有 n!种不同的排列。如若一个排列式的所有的元素都不在原来的位置上,则称这个排列为错排。

解答过程

当有 n 个元素的时候,为了使元素编号与位置编号各不对应(错排),我们就从第 n 个元素开始排序,将其放置非n号位置的n-1的位置上,其他元素以此类推。主要过程如下:

我们假设 n 个元素的错排个数为 M(n)。

  1. 把 n 号元素随机放到一个位置上,则有 n-1 种方法。(先假设放到位置k上)
  2. 现在我们放编号为 k 的元素(即第一步我们放的位置上的对应的正确元素),这时就会出现两种方法:第一、将其放到 n 号位置上,则剩下的元素的排法为 M(n-2);第二、不将其放到 n 号位置上,则对于这 n-1 个元素就有 M(n-1) 中排法;

综上,我们可以得出这样一个递推公式: M(n) = (n-1) * [M(n-1) + M(n-2)]

算法

现在我们有了递推公式了,那么我们在具体实现的时候应该怎么做呢?

方法一:递推

对于有递推公式的,我们完全可以使用递推算法来实现。

首先我们来考虑递推的基本情况(即递推触底情况):

  1. 当 n = 1 的时候,是不可能出现错排的(即 M(1) = 0 );
  2. 当 n = 2 的时候,此时可能出现错排,其错排情况有且仅有一种(即 M(2) = 1);
  3. 当 n >= 3 的时候,就要考虑我们上述的 [解答过程] (#solveProcess)了;

具体代码如下:

1
2
3
4
5
6
7
8
9
10
11
double solveLS1(int n) {
int sum = 0;
if (n == 1) {
return 0;
}else if (n == 2) {
return 1;
}else {
sum += (n-1) * (solveLS1(n-1) + solveLS1(n-2));
}
return sum;
}

方法二:迭代

其基本情况依旧参照 递推法 中的,具体情况如下:

1
2
3
4
5
6
7
8
9
10
11
#define Nkeys 14

// 为了使数组序号与元素个数相对应,我们这个将0号位置的值设置为0;
// 这样下标为n的元素值就表示为了 M(n);
double ls[Nkeys] = {0, 0, 1};

void solveLS() {
for (int i = 3; i < 14; i++) {
ls[i] = (i - 1) * (ls[i -1] + ls[i - 2]);
}
}
文章目录
  1. 问题简述
  2. 解答过程
  3. 算法
    1. 方法一:递推
    2. 方法二:迭代
|