國際象棋棋盤是8*8的，假如有一種牌佔兩個格子，兩個格子一黑一白，那麼把32塊這樣的牌填滿棋盤有多少填法？

11-26

我猜在題主問的時候，沒有意識到這個問題的複雜性。1*2的骨牌覆蓋m*n的棋盤問題是非常有意思的一個數學問題和ACM問題。在下不才，試著把這個問題講解一下。首先從最簡單的問題開始：

1.用1*2的骨牌覆蓋1*n的棋盤，有幾種方法？

顯然，當n為偶數時有一種方法，當n為奇數時無法覆蓋。

2.用1*2的骨牌覆蓋2*n的棋盤，有幾種方法？

易知當n=1時，只有一种放法；當n=2時，有兩种放法。
當n&>2時，設方法數為f（n）。我們考慮最右端的情況：
（1）豎著放一個

這種情況的方法數和在2*（n-1）的棋盤上覆蓋是一樣的；
（2）橫著放兩個

這種情況的方法數和在2*（n-2）的棋盤上覆蓋是一樣的。
綜上，我們得到遞推式

$f(n)=f(n-2)+f(n-1)$

其中 $n>2$ 。

如果設 $f(0)=1$ ,這個數列就是斐波那契數列，可以通過對角矩陣推導其通項公式，這裡我介紹一種程序設計中常用的方法：快速冪。
/*快速冪簡介
當我們計算 $3^{100}$ 的時候，一次一次的去乘無疑是非常低效的。注意到 $3^{100}=(3^{64}) imes (3^{32}) imes (3^4)$
,而 $3^2=3 imes 3,3^4=(3^2) imes (3^2)$ ，如此往後，因此我們可以構造一個數表，把3的2、4、8、16……次冪計算出來，然後把需要的乘起來。
程序是這麼寫的：

double qpow(double a,int n) { double ans = 1.0; while(n) { if(n1) ans *= a; a *= a; n = n/2; } return ans; }

能夠這樣做的原因是數的乘法符合結合律，而矩陣的乘法同樣符合結合律，因此我們可以用同樣的思想進行矩陣乘法，把其中的ans初始化為單位矩陣，乘法變成矩陣乘法就行了，代碼略。
*/
斐波那契數列的遞推式可以寫成矩陣的形式：

由結合律，得：

按照快速冪計算即可。
3.用1*2的骨牌覆蓋3*n的棋盤，有幾種方法？
我們設方法數為f(n)，為了研究方便，設缺了一個角的3*n棋盤覆蓋數為g(n)。顯然當n為奇數時f(n)=0,當n為偶數時g(n)=0。下面分析問題的不同情況。
（1）最右端兩列為橫著的3個骨牌

這樣就和在3*（n-2）的棋盤上覆蓋的方法數相同，為f(n-2)；
（2）最右端為上邊一塊橫的加下邊一塊豎的

這種情況就相當於白色的缺角棋盤的方法數，為g(n-1);
（3）最右端為上邊一塊豎的加下邊一塊橫的
由對稱性，答案還是g（n-1)；
所以遞推公式為
$f(n)=f(n-2)+2g(n-1)$

那麼 $g(n)$ 如何計算呢？還是分類討論。對於一個缺角棋盤，缺角的方向有兩種情況：
（1）放著3個橫著的

（圖扯了……囧）這種情況和 $3 imes (n-2)$ 的缺角棋盤方法數相同，即 $g(n-2)$ ;
（2）把那一列填了

情況數和 $3 imes (n-1)$ 的正常棋盤一樣，方法數為 $f(n-1)$ .我們得到遞推式 $g(n)=f(n-1)+g(n-2)$ 結合上一個遞推式 $f(n)=f(n-2)+2g(n-1)$ ，聯立得到 $f(n)$ 的遞推式：
$f(n)=4f(n-2)-4f(n-4)$ .
又容易知道 $f(0)=1,f(1)=f(3)=0,f(2)=3$ ,所以利用快速冪同樣容易求得n很大時的結果，這裡

4.用 $1 imes 2$ 的骨牌覆蓋 $4 imes n$ 的棋盤，有幾種方法？
這裡不再贅述推導過程了，大致說一下思路。
首先設方法數為 $f(n)$ ,再設 $4 imes n$ 的如下兩種缺角方式的方法數分別是 $g(n)$ 和 $h(n)$ .

（這個是 $g(n)$ )

(這個是 $h(n)$ )
遞推公式為
$f(n)=f(n-1)+2h(n-1)+f(n-2)g(n)=f(n-1)+g(n-2)$
$h(n)=f(n-1)+h(n-1)$
整理得到 $f(n)$ 的遞推式：
$f(n)=f(n-1)+5f(n-2)+f(n-3)-f(n-4)$
又易得
$f(0)=1,f(1)=1,f(2)=5,f(3)=8$ .
建立矩陣的遞推關係，可以用快速冪求解n很大時的值，遞推關係為：

5.用 $1 imes 2$ 的骨牌覆蓋 $m imes n$ 的棋盤，有多少種方法？其中 $mnleq 100$ 。

前面扯了一堆沒用的，終於該題主的問題了。這裡要用到一種叫做「輪廓線動態規劃」的演算法，這種演算法的適用條件為棋盤比較窄，操作複雜的情況。最近知乎上有一個問題比較火，就是什麼是動態規劃（dp），題主可以先看一看。什麼是動態規劃？動態規劃的意義是什麼？ - 演算法
輪廓線動態規劃就是把輪廓線作為狀態的一部分，用整數去存儲輪廓線的形狀（這也叫狀態壓縮），由於這樣做的複雜度為指數級，因此僅僅適用於小範圍數據。
我們從上到下、從左到右的把棋盤分為若干個階段，每個階段就有 $2^m$ 個節點，其中每個節點用一個m表示，m二進位的對應位數字表示節點狀態。1表示覆蓋，0表示未覆蓋。決策是「以目前的格子為右下角，如何放置骨牌？有3種決策，如下圖：

（1）不放。因為當 $k_4=0$ 時沒有有效地後續狀態，只有其為1時才可以轉移到 $k_3k_2k_1k_10$ .
（2）往上放。只有 $k_4=0$ 且i不是最上邊一行時，轉移到 $k_3k_2k_1k_11$ ，
（3）往左放。只有 $k_4=0$ 且j不是最左邊一行時，轉移到 $k_3k_2k_111$ 。
其時間複雜度為 $O(2^m imes mn)$ ,我們把各行編號0-n，各列編號0-m，初始狀態是 $dp[0][2^m-1]=1$ ,答案是 $dp[cur][2^m-1]$ .具體的程序設計方法就不講了，直接上代碼：

#include& #include& #include& using namespace std; int n, m, cur;


const int maxn = 15;

long long d[2][1&<&
我隨便打了一些數據，下圖是結果。其中題主要求的棋盤方法數為12988816.


6.任意情況的公式？
上邊的推導過程越來越繁瑣，大家都在尋找一個對於任意的棋盤可以直接套用的公式。幸運的是這個公式是存在的，在wiki的Domino tiling詞條下有這麼一個公式，對於任意的m，n都可以直接來算：

注意這個公式只能計算行和列都是偶數的情況，裡邊的m和n分別是行數和列數的一半。這個問題就說到這裡，水平有限，有錯誤或疑問歡迎討論。


這本書的第一題目.
@王希回答很多,
但是系統的學習還是看書吧..
  推薦閱讀：


TAG:數學 | 編程 | 趣味數學 |