行測筆試：圖解錯位排列

大家好，我是道哥。

今天，我們來聊一個非常有意思的問題：錯位排列。無論是高考、行測筆試還是程序員筆試，都是常考的問題，具體如下：

在武俠中，有 n 對夫妻，現在要進行男女之前的兩兩比武，爲避免誤傷，要求夫妻之間不允許直接比武，求比武的方法數。

根據題目要求，張無忌不能和趙敏比武，郭靖不能和黃蓉比武，宋青書不能和周芷若比武。這就是錯位排列的模型，接下來我們逐步分析下。

1 對夫妻的比武

如果只有 1 對夫妻，比如張無忌和趙敏，顯然他們不能比武，所以比武的方法數爲 0：

2 對夫妻的比武

如果有 2 對夫妻，很顯然，他們的比武安排的方法數是 1，只有唯一的辦法，如下：

3 對夫妻的比武

如果有 3 對夫妻，可以按照如下圖所示的 2 種安排方法進行比武，顯然，方法數爲 2：

n 對夫妻的比武

接下來，我們看更一般的情況，假設有 n 對夫妻，對應的錯位比武方法數爲 F(n),  顯然有：

gjKykp

假設有 n 對夫妻，我們來一起分析下。對於張無忌而言，假設他選擇黃蓉，此時，郭靖要麼選擇趙敏，要麼不選擇趙敏。我們先考慮郭靖選擇趙敏的情況，如下：

可以看到，前面的 2 對夫妻配對好了，後面還有 n-2 對夫妻，他們只要完成錯位比武就行。顯然，問題的規模縮小了。剩下的 n-2 對夫妻的錯位比武的方法數爲 F(n-2).

接着看另外一種情況，假設張無忌選擇黃蓉後，郭靖不選擇趙敏，那麼情況如下：

爲了更好地理解這種情況，我來調整一下位置，如下：

現在的問題變成了：郭靖不能選擇趙敏，宋青書不能選擇周芷若，段譽不能選擇王語嫣，這不就是規模爲 n-1 的錯位比武問題嗎？是的，方法數爲 F(n-1).

綜上所述：

也就是說，當張無忌選擇黃蓉時，整體的錯位比武方法數爲：

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

顯然，張無忌除了選擇黃蓉外，還可以選擇周芷若或者王語嫣，總之，張無忌可選的方法數爲 n-1,  所以，整體的錯位比武方法數 F(n) 爲：

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

故有：

Xef3ru

當 n = 3 時，上述遞推關係依然成立，故整理後得到：

4h7eyi

編程實現

在一些筆試面試的時候，只要掌握了遞推算法，就能很快求出具體的值。既然弄清了算法，那麼對應的編程就很簡單了，如下：

#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 等多方面的編程知識。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/dyU8X5TPFBenFs3GsgGtyg

猜你喜歡