標籤：

具體數學書籍數學遞歸

具體數學-第1課（遞歸求解實際問題）

05-11

原文鏈接：

具體數學-第1課 - WeiYang Blog?

godweiyang.com

這學期提前選修了研究生的課程：具體數學、人工智慧前沿、NLP討論班，就隨便記記具體數學每一節課所學的東西吧。

第一節課講的都是一些很簡單的東西，這裡就一帶而過了。

漢諾塔問題

這是個老生常談的問題了，n個盤子，3個柱子的漢諾塔問題，最少移動次數記為 $(T(n))$ 。

那麼 $[T(n)=2T(n-1)+1]$

邊界條件為 $(T(0)=0)$ 。

解出 $[T(n)=2^n-1]$

驗證可以採用數學歸納法，這裡就不多說了。

直線分割平面問題

這也是個高中問題了，n條直線最多分割平面為幾部分，記為 $(L(n))$ 。

那麼 $[L(n)=L(n-1)+n]$

邊界條件為 $(L(0)=1)$ 。

解出 $[L(n)=n(n+1)/2+1]$

這題有個擴展，n個V型最多分割平面為幾部分？

解決思路如下：

如上圖所示，將V型補全（紅色虛線部分），那麼就轉化為了 $(2n)$ 條直線劃分平面數，那麼n個V型劃分數只要減去 $(2n)$ 就行了，所以答案為：

$[Z(n)=L(2n)-2n=2n^2-n+1]$

約瑟夫環問題

這個問題暴力求解的話模擬就行了，複雜度是 $(O(n^2))$ 的，這裡探索一種直接求解的方法。

分兩種情況討論：

當有 $(2n)$ 個人時，踢掉 $(n)$ 個人之後，情況如下圖所示

觀察對應關係可以得出

$[J(2n)=2J(n)-1]$

同理，當有 $(2n+1)$ 個人時，踢掉 $(n+1)$ 個人之後，情況如下圖所示

觀察對應關係可以得出

$[J(2n+1)=2J(n)+1]$

邊界條件為

$[J(1)=1]$

這個遞推式很難求解，但是枚舉出前面幾項可以發現，如果令 $(n=2^m+l)$ ，其中 $(2^m)$ 是小於等於 $(n)$ 的最大2的冪，那麼

$[J(n)=2l+1]$

正確性可以通過數學歸納法求證。

第一節課就講了這麼多，約瑟夫環還有很多問題值得探討，下節課繼續。。。

推薦閱讀：

TAG:具體數學書籍 | 數學 | 遞歸 |