在網(wǎng)上看到一個(gè)關(guān)于遞推求解的課件，感覺里面的問題很經(jīng)典有趣，層層遞進(jìn)，因此在這里記錄一下。

1、在一個(gè)平面上有一個(gè)圓和n條直線，這些直線中的每一條在圓內(nèi)同其他直線相交，假設(shè)沒有三條直線相交于一點(diǎn)，試問這些直線將圓分成多少區(qū)域。

2、平面上有n條折線，問這些折線最多能將平面分割成多少塊？（已知1—>2，2—>7）

3、設(shè)有n條封閉曲線畫在平面上，而任何兩條封閉曲線恰好交于兩點(diǎn)，且任何三條封閉曲線不相交于同一點(diǎn)，問這些封閉曲線能把平面分割成的區(qū)域個(gè)數(shù)。

4、在2*n的長方形方格中，用n個(gè)1*2的骨牌鋪滿方格，例如n = 3 時(shí)，為2*3方格，骨牌的鋪設(shè)方案有三種，問對于n，鋪設(shè)方案的總數(shù)是多少。

5、有一個(gè)1*n的一個(gè)長方形，用1*1、1*2、1*3的骨牌鋪滿方格。例如當(dāng)n = 3 時(shí)為1*3的方格，此時(shí)用1*1，1*2，1*3的骨牌鋪滿方格，共有四種鋪法。問對于n，鋪設(shè)方案的總數(shù)是多少。

6、There are many students in PHT School. One day, the headmaster whose name is PigHeader wanted all students stand in a line. He prescribed that girl can not be in single. In other words, either no girl in the queue or more than one girl stands side by side. The case n=4 (n is the number of children) is like FFFF, FFFM, MFFF, FFMM, MFFM, MMFF, MMMM Here F stands for a girl and M stands for a boy. The total number of queue satisfied the headmaster’s needs is 7. Can you make a program to find the total number of queue with n children? 懶得翻譯了：~

7、有排成一行的n個(gè)方格，用紅、綠、藍(lán)三原色給每個(gè)格子上色，每格涂一色，要求任何相鄰的方格不能同色，且首尾兩格也不同色。求全部的滿足要求的涂法。

8、某人寫了n封信，還有n個(gè)信封，如果所有的信都裝錯(cuò)了信封，求共有多少種可能的情況？

?

————————————————————————^^我是漂亮的分割線^^————————————————————————

參考答案：

1、F(1) = 2; F(n) = F(n-1) + n 通項(xiàng)：F(n) = n(n+1)/2 + 1

2、F(1) = 2; F(n) = F(n-1) + 4(n-1) + 1 通項(xiàng)：F(n) = 2n^2 - n + 1

3、F(1) = 2; F(n) = F(n-1) + 2(n-1) 通項(xiàng)：F(n) = n^2 - n + 2

4、考慮最后一個(gè)格的鋪法，容易得到：F(1) = 1, F(2) = 2; F(n) = F(n-1) + F(n-2), n≥3

5、仍然是考慮最后一個(gè)格的鋪法，有：F(1) = 1, F(2) = 2, F(3) = 4; F(n) = F(n-1) + F(n-2) + F(n-3), n≥4

6、根據(jù)最后一個(gè)人的性別分情況討論（設(shè)F(n)表示n個(gè)人的合法隊(duì)列）。如果是男生，直接站在隊(duì)列的最后，有F(n-1)種情況。如果是女生，則最后兩個(gè)人必須都是女生，再分類：如果隊(duì)列的前n-2個(gè)人是合法的隊(duì)列，在隊(duì)列后面追加兩個(gè)女生，有F(n-2)種情況；另外，即使前面n-2個(gè)人不是合法的隊(duì)列，再加上兩個(gè)女生也可能是合法隊(duì)列，且不合法的地方一定是長度為n-2的隊(duì)列的尾部，即F(n-4) + 1男 + 1女，這樣再跟上兩個(gè)女生才能成為合法隊(duì)列，這種情況有F(n-4)種。

綜上，有遞推公式：F(1) = 1, F(2) = 2, F(3) = 4, F(4) = 7; F(n) = F(n-1) + F(n-2) + F(n-4), n＞4

7、如果前面n-1個(gè)格子已經(jīng)合法地涂上色，則最后一個(gè)格子只有唯一地一種涂法，有F(n-1)種方法；另外一種情況是前n-1個(gè)格子不是合法的，那么不合法的地方一定是其尾部，即第n-1個(gè)格子與第1個(gè)格子同色，那么最后一個(gè)格子有兩種涂法，因此有2*F(n-2)種方法。

綜上，有遞推公式：F(1) = 3, F(2) = 6; F(n) = F(n-1) + 2*F(n-2), n>2

8、如果前n-1封信已經(jīng)全部錯(cuò)裝，只需從中任取一封和第n封錯(cuò)裝，有(n-1)*F(n-1)種方式；另外如果前n-1封信中有且只有一封信沒有裝錯(cuò)（注意只能有一封，否則就呵呵了：），有(n-1)*F(n-2)種方式。

綜上，有遞推公式：F(1) = 0, F(2) = 1; F(n) = (n-1)*[F(n-1) + F(n-2)]。另外，它還有一個(gè)帥氣的名字叫做錯(cuò)排公式。

PS:斐波那契數(shù)列實(shí)在太有用了，哪天有空寫一下如何用生成函數(shù)求解其通項(xiàng)公式。

轉(zhuǎn)載于:https://www.cnblogs.com/xpjiang/p/4388540.html

總結(jié)

以上是生活随笔為你收集整理的递推趣题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。