「組合數學」隔離區
本題是組合數學中的卡特蘭數問題,此處給出了用分治思想推出卡特蘭數遞推公式的分析思路.
我們先來看一下這題的題面.
題面
題目描述
西安發生新冠疫情了。不少人進了隔離區。
隔離區是一個凸多邊形，為了隔離人員的安全，我們需要用木板將隔離區分隔開。為了隔板的穩定，隔板兩邊分別與凸多邊形的頂點相接，當然隔板不能被其他隔板斷開。
凸多邊形是5的情況，有上面5種劃分方案。
現在知道頂點個數，你知道有多少種隔離方案,使得每個區域是三角形？
輸入
一個整數n (3<=n<=20)
輸出
一個整數,即方案數
樣例輸入
5
樣例輸出
5
題目分析與常見錯誤思路
顯然,這是一道卡特蘭數的問題,如果你知道什麼是卡特蘭數,那麼直接帶卡特蘭數的遞推公式即可解決該問題.
那如果我不知道什麼是卡特蘭數,或者沒想到這題是卡特蘭數的問題,又如何解決呢?別急,我們慢慢分析.
就先從n=3的情況開始分析吧.首先很顯然,n=3的多邊形就是三角形,而對於一個三角形,它劃分成三角形的方案數就是1,因為它本身就已經是一個三角形了,無需劃分.
那麼n=4呢?這個時候的圖形是個四邊形,簡單分析可以知道,沿著兩條對角線分別可以把它分成兩個三角形,所以這時的劃分方案就是2,如下圖:
那麼n=5呢?好像這次沒有之前那麼直觀了,不過好在這種情況題面上已經直接給出了:
相信有不少同學經過對上圖的仔細觀察,再加上自己對多邊形劃分的理解,發現5邊形的劃分方式就是分別選擇5個頂點中的一個,然後向不相鄰的頂點連線,所以是5種方案.於是他們由此認為,n邊形的劃分方案也是遵循這個規律的.(你還別說,我第一次做類似的題目的時候,我也是這麼想的).
實際上,如果把這種思路提交上去,得到的結果只會是WA.
今天又是陪伴WA的一天呢
其實,我們只要繼續對6邊形的劃分稍加分析,就會找到上述思路的規律的反例,比如下圖這種6邊形的劃分法,顯然是不滿足這個規律的:
正確思路
那正確的規律是什麼捏?別急,我們先回到5邊形的劃分中,我們仔細找找有什麼潛在的規律.
顯然,對於每種劃分情況,總會存在一個三角形,它總有至少一邊是在原本的正五邊形上的,而且這個規律是可以推廣到n邊形的.(不信?那如果沒有三角形的邊在n邊形上,那是不是所有三角形都跑到圖形裡面去啦?這樣就不是在進行三角形劃分了鴨!嚴格的數學證明這裡就略了 才不是我不會證)
所以,我們可以在這個五邊形的5條邊中任意選擇1條邊作為劃分出來的那個三角形的一條邊.由於我們只看劃分的方案,邊的長度是無關緊要的,所以這個五邊形旋轉72°(360°/5)後和原本的圖形可以看成和原本的圖形是一個圖形(對n邊形自然也成立,即可以直接把條件看成正n邊形,因為只需要劃分方案數,顯然這與這個凸n邊形長啥樣無關),因此,無論我們選哪條邊,本質上都是選了同一條邊,所以這裡隨便選1條來分析即可.
現在有了一條邊了,距離組成三角形還差一個點.所以我們在剩下來的3個點中可以任意選擇一個點,根據分類加法原理,只需要把選擇每個點的情況所算出來的方案數都加起來,就是最終的答案了.
我們先來看取如下點的情況:
此時三角形選擇完畢後,剩下的左右兩邊是兩個三角形,顯然已經完成了劃分.
接下來看取另一個點的情況:
此時三角形選擇完畢後,剩下的右邊已經沒有圖形了,而左邊是一個四邊形.誒,怎麼是四邊形,四邊形怎麼辦呢?
別急,我問你,如果我直接給你一個四邊形,我要你劃分成三角形,你會劃分嗎?顯然是可以直接完成的,前面也已經討論過了,是兩種劃分方式.
而在這裡,是不是也是同樣的?我們只需要對這個四邊形繼續求劃分方案,是不是就可以啦?也就是,在這裡,我們通過選一條邊和一個點劃分出一個三角形,來將問題的規模從原本的5降低到了4.
還有一個點的選取情況與上面類似,最後也是兩種劃分方式,這裡就略過了.根據上述分析,我們可以成功求得5邊形的劃分方式是5.
我們再來看看在六邊形中能否做到同樣的事情,我們先選擇這一個點來分解:
此時上面是一個三角形,下面是一個四邊形,我們確實也成功地把問題分小了.接下來只要對下面的四邊形計算有幾種劃分方案即可,而上面已經討論過了兩次了,這裡不多贅述了.
那如果我們選擇這一個點呢?
顯然,此時問題也一樣變小了,上面已經沒有圖形了,而下面是一個5邊形.啊咧,5邊形怎麼辦捏?別急,前面規模降低到4邊形的時候是不是接著對4邊形進行劃分鴨?那這裡我們自然可以一樣對這個5邊形繼續劃分,怎麼劃分捏?前面不是剛剛分析過五邊形的劃分方法嘛.我們可以接著選一條邊,然後通過選點繼續降低規模求解.
分析到這裡,此題的思路基本已經有了.我們先固定n邊形的一條邊,然後依次選擇剩下的各個點,這樣劃分後剩下的圖形的邊數就會變小,然後對每一個分小後的部分進行同樣的操作,即繼續進行固定邊、選點來分小,直到問題規模變成可以直接求解的3邊形或4邊形.根據分步乘法原理,此時只需要把劃分出來的左右兩個多邊形的劃分方法數相乘,就是當前選擇的這個點的劃分方法數啦!然後再根據分類加法原理,把每個點的劃分方法數加起來,就是最後的答案啦!
不過這裡有個小小的問題,前面的分析中有出現過選擇一個點後,一邊已經沒有圖形的情況.為了和上面統一,我們希望這種情況也可以使用分步乘法原理.為此,我們人為規定此時的劃分方法數為1(此時可以看成”2邊形”,所以也就是人為規定”2邊形”的劃分方法數是1),這樣就沒有問題啦!
上述這種思路是一種叫做分而治之,即分治,的思想的應用.我們將大規模問題不斷分解成小規模問題,即減小問題的規模,然後再對每一個小規模問題進行同樣的操作,分成更小規模的問題,即進一步減小問題的規模,如此下去,直到問題被分成小到可以直接解決的規模為止.然後我們便可從這些已經解決的小問題逐步推回,最終解決大問題.快速排序就是典型的分治思想的例子,通過對數組中的每一段進行小放左、大放右的排序,最終完成對整個數組的排序.
Nothing is particularly hard if you divide it into small jobs.
如果你能把要做的事情化整為零,就沒有什麼事會特別困難。
——Henry Ford(亨利·福特)
程式碼編寫
好了,思路找到了,接下來就來寫程式碼吧!
在分治思想中,我們對每個劃分出來的小問題執行的操作和對原本的大問題執行的操作是一樣的,這非常符合遞歸的特點,所以我們可以用遞歸來解決此問題.
我們先寫一個函數,用來計算劃分數目,局部參考程式碼如下:
int f(int n)
{
}
顯然,遞歸的基準線條件就是3邊形和”2邊形”的情況(4邊形可以通過3邊形和”2邊形”算出來,所以無需列入基準線條件.當然,如果你想這麼干也可以),此時無需繼續遞歸,可以直接返回值,局部參考程式碼如下:
// 基準線條件,3邊形只有一種劃分方式,"2邊形"為了統一,人為規定有一種劃分方式,此時可以直接返回,結束遞歸,開始逐步返回值計算結果
if(n == 3 || n == 2)
{
return 1;
}
接下來就是分治的核心程式碼了,由於有多種分法,所以我們需要寫一個循環來分別計算每一種分法的結果數目,然後求和,這個和即為結果.
那這個循環怎麼寫呢?我們觀察一下從最近的點開始選點時的規律:
我們可以發現,右側的多邊形從”2邊形”一直變化到n-1邊形,而左側的多邊形從n-1邊形一直變化到”2邊形”,所以我們可以寫一個for循環,將一側多邊形的邊數作為循環變數即可.
局部參考程式碼如下:
int res = 0; // 累加器
for(int i = 3;i < n;i++) // 選點,從最近開始選,一側會從"2邊形"逐步變成n - 1邊形
{
// 此處應寫 res += 當前情況的結果數目
}
return res;
那如何計算結果數目捏?如前所述,我們使用分治思想,對劃分出來的兩個部分繼續進行同樣的操作,即進行遞歸.然後根據分步乘法計數原理,乘起來就是這種情況的結果數目.
這裡可能有些朋友對一側邊數為i時另一側的邊數怎麼求感到困惑.當一側是i邊形時,它會用掉多邊形的i – 1條邊(去掉的那1條是中間的那個三角形上的).此時再去掉中間三角形用掉的多邊形上的那1條邊,還剩n – (i – 1) – 1,也就是n – i條邊.再加上中間三角形上的1條邊,那麼另一側的多邊形就是n – i + 1條邊啦!
如果還是看不出來,也可以直接利用臨界條件找規律,然後用數學歸納法簡單證明下即可.
局部參考程式碼如下:
res += f(i) * f(n - i + 1); // 對兩個部分進行同樣的操作,不斷把問題分小,直到可以解決
其實,此時我們推出來的這個式子就是卡特蘭數的一種遞推公式,但我們在這裡並沒有運用任何和卡特蘭數有關的知識,就已經直接推導出這個遞推公式了,怎麼樣,思維的力量是不是非常強大?(其實卡特蘭數就是從這些問題中抽象出來的一個數列,和斐波那契數列一樣)
這樣這個問題就解決了,這個函數的完整參考程式碼如下:
int f(int n)
{
// 基準線條件,3邊形只有一種劃分方式,"2邊形"為了統一,人為規定有一種劃分方式,此時可以直接返回,結束遞歸
if (n == 3 || n == 2)
{
return 1;
}
int res = 0; // 累加器
for (int i = 2; i < n; i++) // 選點,從最近開始選,一側會從"2邊形"逐步變成n - 1邊形
{
res += f(i) * f(n - i + 1); // 對兩個部分進行同樣的操作,不斷把問題分小
}
return res;
}
剪枝
由於目前oj的提交通道已經關閉,我不清楚上述的程式碼是否會導致TLE(時間超限),但是顯然(如果你顯不出來也沒關係,接著看就好了),上述的程式碼實際的運行效率會很慢.因為當我們求f(n)的時候,我們求遍了f(2)到f(n-1),而當我們求f(n-1)的時候,我們再次求遍了f(2)到f(n-2),這裡有數量非常可怕的重複運算.
和對求斐波那契數列中出現的重複計算的處理方法一樣,我們也可以通過記憶化搜索的方式來優化掉重複的計算(這種操作稱為對遞歸樹進行剪枝).我們引入一個數組,當我們計算出f(i)(2<=i<=n)的時候,我們就把它存在數組下標為i的位置上.當我們下一次用到這個f(i)時,我們就直接從數組中將它取出,不用再繼續遞歸下去算了.這樣的一步簡單的優化可以大大提高演算法的效率.
參考程式碼如下:
int dp[21]; // 下標0-20,其中0,1,2,3其實是不存數據的.
int f(int n)
{
// 基準線條件,3邊形只有一種劃分方式,"2邊形"為了統一,人為規定有一種劃分方式,此時可以直接返回,結束遞歸
if (n == 3 || n == 2)
{
return 1;
}
if (dp[n] != 0) // 當前項已經計算過,直接從數組中取出,不再繼續遞歸
{
return dp[n];
}
// 此時直接把dp[n]當做累加器即可
for (int i = 2; i < n; i++) // 選點,從最近開始選,一側會從"2邊形"逐步變成n - 1邊形
{
dp[n] += f(i) * f(n - i + 1); // 對兩個部分進行同樣的操作,不斷把問題分小
}
return dp[n];
}
參考程式碼
下面給出我自己做這道題時候的完整程式碼:
#include <stdio.h>
int dp[21]; // 0-20,其中0,1是不存數據的.
int f(int n)
{
// 基準線條件,3邊形只有一種劃分方式,"2邊形"為了統一人為規定有一種劃分方式,此時可以直接返回,結束遞歸
if (n == 3 || n == 2)
{
return 1;
}
if (dp[n] != 0) // 當前項已經計算過,直接從數組中取出,不再繼續遞歸
{
return dp[n];
}
// 此時直接把dp[n]當做累加器即可
for (int i = 2; i < n; i++) // 選點,從最近開始選,一側會從"2邊形"逐步變成n - 1邊形
{
dp[n] += f(i) * f(n - i + 1); // 對兩個部分進行同樣的操作,不斷把問題分小
}
return dp[n];
}
int main()
{
int n;
scanf("%d", &n);
printf("%d\n", f(n));
}
提高
就如開頭所說的那樣,此題其實是一道卡特蘭數的問題.在xcpc勸退樹中,卡特蘭數被歸入基礎中(同樣被歸入基礎里的還有貪心、二分等基礎演算法),所以對於acmer來說,卡特蘭數還是要好好掌握的.
關於卡特蘭數的介紹,這裡直接引用維基百科:
卡塔蘭數是組合數學中一個常在各種計數問題中出現的數列。以比利時的數學家歐仁·查理·卡特蘭命名。歷史上，清朝數學家明安圖在其《割圜密率捷法》中最先發明這種計數方式，遠遠早於卡塔蘭。
卡塔蘭數的一般項公式為:
此外,還具有如下兩種遞推公式:
組合數學中有非常多的組合結構可以用卡塔蘭數來計數.比如合法括弧組合 二叉樹構成方案 不越過對角線的單調路徑 凸多邊形劃分三角形 進出棧的置換 不交叉劃分 填充階梯狀圖形 標準楊氏矩陣數量等.
本題就屬於凸多邊形劃分三角形的典型問題.
關於卡特蘭數在其他問題上的具體應用,可以查看集訓隊的一位大佬整理的部落格.
“正是我們每天反覆做的事情，最終造就了我們，優秀不是一種行為，而是一種習慣” —亞里士多德
