行测笔试：图解错位排列

作者丨道哥

来源丨爱码有道（ID：aimayoudao）

今天，我们来聊一个非常有意思的问题：错位排列。无论是高考、行测笔试还是程序员笔试，都是常考的问题，具体如下：

在武侠中，有n对夫妻，现在要进行男女之前的两两比武，为避免误伤，要求夫妻之间不允许直接比武，求比武的方法数。

根据题目要求，张无忌不能和赵敏比武，郭靖不能和黄蓉比武，宋青书不能和周芷若比武。这就是错位排列的模型，接下来我们逐步分析下。

1对夫妻的比武

如果只有1对夫妻，比如张无忌和赵敏，显然他们不能比武，所以比武的方法数为0：

2对夫妻的比武

如果有2对夫妻，很显然，他们的比武安排的方法数是1，只有唯一的办法，如下：

3对夫妻的比武

如果有3对夫妻，可以按照如下图所示的2种安排方法进行比武，显然，方法数为2：

n对夫妻的比武

接下来，我们看更一般的情况，假设有n对夫妻，对应的错位比武方法数为F(n),  显然有：

n的值	F(n)的值
n = 1	0
n = 2	1
n = 3	2
n > 3	?

假设有n对夫妻，我们来一起分析下。对于张无忌而言，假设他选择黄蓉，此时，郭靖要么选择赵敏，要么不选择赵敏。我们先考虑郭靖选择赵敏的情况，如下：

可以看到，前面的2对夫妻配对好了，后面还有n-2对夫妻，他们只要完成错位比武就行。显然，问题的规模缩小了。剩下的n-2对夫妻的错位比武的方法数为F(n-2).

接着看另外一种情况，假设张无忌选择黄蓉后，郭靖不选择赵敏，那么情况如下：

为了更好地理解这种情况，我来调整一下位置，如下：

现在的问题变成了：郭靖不能选择赵敏，宋青书不能选择周芷若，段誉不能选择王语嫣，这不就是规模为n-1的错位比武问题吗？是的，方法数为F(n-1).

综上所述：

• 当张无忌选择黄蓉，郭靖选择赵敏时，整体的错位比武方法数为F(n-2)
  

• 当张无忌选择黄蓉，而郭靖不选择赵敏时，整体的错位比武方法数为F(n-1)

也就是说，当张无忌选择黄蓉时，整体的错位比武方法数为：

F(n-2) + F(n-1)

显然，张无忌除了选择黄蓉外，还可以选择周芷若或者王语嫣，总之，张无忌可选的方法数为n-1,  所以，整体的错位比武方法数F(n)为：

(n-1)*(F(n-2) + F(n-1))

故有：

n的值	F(n)的值
n = 1	0
n = 2	1
n = 3	2
n > 3	(n-1)*(F(n-2) + F(n-1))

当n = 3时，上述递推关系依然成立，故整理后得到：

n的值	F(n)的值
n = 1	0
n = 2	1
n > 2	(n-1)*(F(n-2) + F(n-1))

编程实现

在一些笔试面试的时候，只要掌握了递推算法，就能很快求出具体的值。既然弄清了算法，那么对应的编程就很简单了，如下：

#include <iostream>
using namespace std;

int solution(int n)
{
  if(n <= 1)
  {
    return 0;
  }
  
  if(n == 2)
  {
    return 1;
  }
  
  return (n - 1) * (solution(n - 2) + solution(n - 1));
}

int main()
{
   for(int n = 1; n < 10; n++)
   {
       cout << solution(n) << endl;
   }
  
   return 0;
}

结果：

0

1

2

9

44

265

1854

14833

133496

错位排列很有意思，也是经常涉及到的考点，关键还是在于思路。我们也会一步一个脚印，争取每篇文章讲清讲透一件事，也希望大家阅读后有所收获，心情愉快。

你好，我是道哥，CSDN前30名，曾混迹于BAT大厂。公众号讲解计算机基础、网络、数据结构、算法、C++、Java、Golang等多方面的编程知识。欢迎点击如下名片关注道哥，感谢点赞和在看支持哦。

点分享

点点赞

点在看