信息學奧賽問題求解選講

1、問題求解選講江凡August 10, 2016江凡問題求解選講August 10, 2016歸納推理Contents歸納推理歸納邏輯推理初等數(shù)論遞推遞歸數(shù)據(jù)結(jié)構(gòu)其他江凡問題求解選講August 10, 201612345歸納推理歸納 例例1，根據(jù)，根據(jù)Nocomachns定理，任何一個正整數(shù)定理，任何一個正整數(shù)n的立方一定可以表示成的立方一定可以表示成n個連續(xù)的奇數(shù)的和。個連續(xù)的奇數(shù)的和。 例如：例如： 13 1 23 3 5 33 7 9 11 43= 13+15+17+19 在這里，若將每一個式中的最小奇數(shù)稱為在這里，若將每一個式中的最小奇數(shù)稱為X，那么，那么當給出當給出n之后，請寫出之后

2、，請寫出X與與n之間的關(guān)系表達式。之間的關(guān)系表達式。江凡問題求解選講August 10, 2016X=N2-N+1 歸納推理歸納 例例2，將邊長為，將邊長為n的正三角形每邊的正三角形每邊n等分，過每個等分，過每個分點分別做另外兩邊的平行線，得到若干個正三角形，分點分別做另外兩邊的平行線，得到若干個正三角形，我們稱為小三角形。正三角形的一條通路是一條連續(xù)我們稱為小三角形。正三角形的一條通路是一條連續(xù)的折線，起點是最上面的一個小三角形，終點是最下的折線，起點是最上面的一個小三角形，終點是最下面一行位于中間的小三角形。在通路中，只允許由一面一行位于中間的小三角形。在通路中，只允許由一個小三角形走到另

3、一個與其有公共邊的且位于同一行個小三角形走到另一個與其有公共邊的且位于同一行或下一行的小三角形，并且每個小三角形不能經(jīng)過兩或下一行的小三角形，并且每個小三角形不能經(jīng)過兩次或兩次以上（圖中是次或兩次以上（圖中是n=5時一條通路的例子）。設(shè)時一條通路的例子）。設(shè)n=10，則該正三角形的不同的通路的總數(shù)，則該正三角形的不同的通路的總數(shù)為為 。江凡問題求解選講August 10, 2016歸納推理江凡問題求解選講August 10, 2016n=5n=5時，方案有時，方案有1 12 23 34 44!4!n=10n=10時，方案有時，方案有1 12 29 99!9!n=2n=2時，方案有時，方案有1

4、1種。種。n=3n=3時，方案有時，方案有2 2種。種。n=4n=4時，方案有時，方案有6 6種。種。歸納邏輯推理 通常把只涉及一些相互關(guān)聯(lián)（或依存）條件或關(guān)系，極少給出（不直接賦與）數(shù)量關(guān)系與幾何圖形的一類非標準（常規(guī)）數(shù)學問題叫邏輯推理問題，處理這類問題，要從一些關(guān)聯(lián)的條件出發(fā)，應(yīng)用某些數(shù)學知識，甚至日常生活常識，依據(jù)一定的思維規(guī)律（機智靈活、準確敏捷的思考），通過分析、推理、排除不可能情況（剔除不合理成分），然后作出正確的判斷。邏輯推理問題中常用到以下三條邏輯基本規(guī)律：（1）同一律：是指同一東西（對象）。它是什么就是什么，不能模棱兩可，亦此亦彼；（2）矛盾律：是指互相對立（矛盾）的事不能

5、都真，二者必有一假（即同一思想不能既真又假）；（3）排中律：是指兩個不相容的判斷不能都假，二者必有一真（即任何判斷或同一思想不能既不真也不假）。歸納推理邏輯推理江凡問題求解選講August 10, 2016歸納推理邏輯推理利用表格輔助推理: 例3，某中學推理社招新題，答案是 _這道題的答案是AAB BC CD D第5題的答案是ACB DC AD B以下選項中哪一題的答案與其他三項不同A第3題B 第6題C 第2題D 第4題以下選項中哪兩題的答案相同A第1，5題B 第2，7題C 第1，9題D 第6，10題以下選項中哪一題的答案與本題相同A第8題B 第4題C 第9題D 第7題以下選項中哪兩題的答案與

6、第8題相同A第2，4題B 第1，6題C 第3，10題D 第5，9題在此十道題中，被選擇次數(shù)最少的選項字母為ACB BC AD D以下選項中哪一題的答案與第1題的答案在字母表中的不相鄰A第7題B 第5題C 第2題D 第10題已知“第1題與第6題的答案相同”與“第X題與第5題的答案相同”的真假性相反，那么X為A第6題B 第10題C 第2題D 第9題在此十道題中，ABCD四個字母中出現(xiàn)的次數(shù)最多者與最少者的差為A3B 2C 4D 1江凡問題求解選講August 10, 2016BCACACDABA 歸納推理邏輯推理利用圖形輔助推理美國數(shù)學家斯蒂恩說過:“如果一個特定的問題可以被轉(zhuǎn)化成一個圖形,那么,

7、思想就整體地把握了問題,并且能創(chuàng)造性地思索問題解法?！?例4，A、B、C、D、E五支球隊進行單循環(huán)比賽（每兩支球隊間都要進行一場比賽），當比賽進行到一定階段時，統(tǒng)計A、B、C、D四個球隊已經(jīng)賽過的場數(shù)，依次為A隊4場，B隊3場，C隊2場，D隊1場，這時，E隊已賽過的場數(shù)是（）A. 1B. 2C. 3D. 4 江凡問題求解選講August 10, 2016B數(shù)論基礎(chǔ)Contents歸納推理數(shù)論基礎(chǔ)同余素數(shù)排列組合遞推遞歸數(shù)據(jù)結(jié)構(gòu)其他江凡問題求解選講August 10, 201612345數(shù)論基礎(chǔ)同余如果a1a2 b1 b2(mod m)(mod m)那么b1a1 a2 b2b1 b2(mod m

8、)(mod m)江凡問題求解選講August 10, 2016a1a2同余的定義與性質(zhì)如果 m 整除 a b，我們就說 a 與 b 模 m 同余并記為a b(mod m)簡單來說，就是它們模 m 后的余數(shù)相同就可以記成這樣。數(shù)論基礎(chǔ)同余江凡問題求解選講August 10, 2016（a1 a2）mod b (a1 mod b)( a2 mod b) mod b分治思想與快速冪方法例5，輸入b，p，k的值，求 bp mod k 的值。如，59 mod 7 = ？59 = 【（5 5） （5 5）】 【（5 5） （5 5）】 54422456 x a1 x a2.數(shù)論基礎(chǔ)同余方程與中國剩余定理中

9、國剩余定理 有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二。問物幾何？孫子算經(jīng) 這個問題說的是：有一個整數(shù)，被 3 除余 2，被 5 除余 3，被 7 除余 2，問這個整數(shù)是多少？ 事實上，這個問題有無窮多個解，其中一個解是 23。中國剩余定理，又稱為孫子定理，常常簡寫成 CRT（Chinese RemainderTheorem）。它給出了構(gòu)造如下方程組解的方法：(mod m1 )(mod m2 ).x an(mod mn )其中 m1 , m2 , . . . , mn 兩兩互素。江凡問題求解選講August 10, 2016同余方程與中國剩余定理數(shù)論基礎(chǔ)中國剩余定理首先來解只有兩個

10、方程的方程組。xx a1 a2(mod m1 )(mod m2 )我們可以把這個方程組改寫成xx= a1 + k1 m1= a2 + k2 m2消去 x 之后就可以得到 a1 + k1 m1 = a2 + k2 m2 ，這剛好是關(guān)于 k1 , k2 的一個線性方程。 此外，中國剩余定理還告訴我們一個事實，在 m1 , m2 互素的條件下，假設(shè) x0是該方程組的一個解，那么該方程組的所有解都滿足如下形式：江凡問題求解選講August 10, 2016x x0(mod m1 m2 )這樣我們相當于把剛剛的兩個方程合并成為了一個方程。如果有多個方程，可以不斷進行這樣的合并，最后就可以解出結(jié)果了。x

11、2x 2數(shù)論基礎(chǔ)同余方程與中國剩余定理中國剩余定理我們來拿剛剛開頭的例子來試著算一算。那個方程組是：x 3(mod 3)(mod 5)(mod 7)江凡問題求解選講August 10, 2016首先來合并前兩個方程，聯(lián)立后得到的線性方程是 2 + 3k1 = 3 + 5k2 ，整理后可以得到一組解是 k1 = 2, k2 = 1，這樣可以得到滿足前兩個方程的 x 都滿足：x 8 (mod 15)數(shù)論基礎(chǔ)同余方程與中國剩余定理中國剩余定理之后可以得到新的方程組：xx 8 2(mod 15)(mod 7)再合并兩個方程，聯(lián)立后得到的線性方程是 8 + 15k1 = 2 + 7k2 ，整理后可以得到

12、一組解是 k1 = 1, k2 = 3，這樣可以得到滿足這兩個方程的 x 都滿足：x 23(mod 105)這便是最后的解了！江凡問題求解選講August 10, 2016數(shù)論基礎(chǔ)素數(shù)及基本知識江凡問題求解選講August 10, 2016素數(shù)及基本知識素數(shù)是只含有 1 及其本身兩個正因子的數(shù)，也稱為質(zhì)數(shù)。如果還有其它正因子的話，那么這個數(shù)就被稱為合數(shù)。注意 1 并非素數(shù)，亦非合數(shù)。我在這里介紹一個關(guān)于素數(shù)的定理，它們在算法復(fù)雜度分析中或許會用到：Theorem (素數(shù)定理)當 x 很大時，小于 x 的素數(shù)個數(shù)近似等于x/lnx數(shù)論基礎(chǔ)江凡問題求解選講August 10, 2016素數(shù)的判定

13、如何判定一個數(shù) m 是不是素數(shù)，我們可以直接從定義出發(fā)，從 2 開始到m-1 為止，檢測是否有一個數(shù)整除 m，如果沒有，那么這個數(shù)就是素數(shù)。 例6，求105內(nèi)的所有素數(shù)。 Eratosthenes 篩法篩法是一種用來求素數(shù)的方法，它的思路比較簡單。 由于每個合數(shù)都可以被分解成幾個素數(shù)的乘積，如果我們將所有素數(shù)的倍數(shù)都刪去，那么剩下的就是素數(shù)了。 因此，我們可以從 2 開始，先將 2 的所有倍數(shù)都刪去。然后往下找到第一個沒有被刪去的數(shù)，這個數(shù)一定是素數(shù)，再將這個數(shù)的所有倍數(shù)都刪去，不斷進行這個操作。素數(shù)及基本知識 線性篩法線性篩法，又稱歐拉篩法。 避免冗余的運算。每個合數(shù)必有一個最大因子（不包括

14、它本身） ，用這個因子把合數(shù)篩掉。 對于每一個數(shù)i，乘上小于等于i的最小素因數(shù)的素數(shù)，就得到以i為最大因數(shù)的合數(shù)。設(shè)有一個數(shù)t，只要將所有以比t小的數(shù)為最大因數(shù)的合數(shù)篩去，那么比t小的數(shù)里剩下的就只有素數(shù)了。組合數(shù)學基礎(chǔ)排列組合 組合數(shù)學基礎(chǔ) 例7，在1與106之間，有多少個整數(shù)的各位數(shù)字之和等于9？江凡問題求解選講August 10, 2016組合數(shù)學基礎(chǔ)排列組合 排列 現(xiàn)在來考慮一個問題：你需要在 n 個不同的人里面選出 m 個人排成一行，問有多少種排列方案？ n(n 1)(n 2) (n m + 1)這個數(shù)通常被成為排列，記成 ，或者 。 如果我們定義一種名為階乘的運算：n!= 1 2

15、3 n特別地，當 n = 0 時，0! = 1。那么這個數(shù)就可以簡單地寫成：Anm=n!(n m)!江凡問題求解選講August 10, 2016AnmP nm組合數(shù)學基礎(chǔ)排列組合 排列 圓排列圓排列 （1）由 的個元素中，每次取出r個元素排在一個圓環(huán)上，叫做一個圓排列（或叫環(huán)狀排列）。 （2）圓排列有三個特點：（i）無頭無尾；（ii）按照同一方向轉(zhuǎn)換后仍是同一排列；（iii）兩個圓排列只有在元素不同或者元素雖然相同，但元素之間的順序不同，才是不同的圓排列。 （3）定理：在的個元素中，每次取出個不同的元素進行圓排列，圓排列數(shù)為 。 不盡相異元素的全排列不盡相異元素的全排列 如果n個元素中，有p

16、1個元素相同，又有p2個元素相同，又有ps個元素相同（ ），這個n元素全部取的排列叫做不盡相異的n個元素的全排列，它的排列數(shù)是 。江凡問題求解選講August 10, 2016rPrn!21spppn,321naaaaAnppps21組合數(shù)學基礎(chǔ)排列組合組合研究無次序的選取問題。把前述排列問題改成：你只需要在 n 個不同的人里面選出 m 個人，問有多少種方案？ 如果我們選出來 m 個人后，再將他們排成一隊，那么方案數(shù)就是先前的排列數(shù) 。 但是這樣的計數(shù)會出現(xiàn)很多的重復(fù)，也就是每次我們都多算了將 m 個人排成一隊的方案數(shù)，那么這個數(shù)是什么呢？ 它就是 ，或者說 m!。 那么由于每種方案都被重復(fù)計

17、算了 m! 次，我們只要將 除以 m! 就可以得到組合數(shù)的公式了！江凡問題求解選講August 10, 2016AnmAmmAnmCnm=nAm!=n!m!(n m)!m排列組合組合數(shù)學基礎(chǔ)組合數(shù)的基本性質(zhì)首先第一個性質(zhì)就是先前的遞推關(guān)系(1)此外，直接根據(jù)通項可以得到一個對稱的性質(zhì)：(2)江凡問題求解選講August 10, 2016Cnm= Cn1 + Cn1mm-1Cnm= Cnn-m排列組合組合數(shù)學基礎(chǔ)排列組合分析原理江凡問題求解選講August 10, 2016 加法原理 如果完成一件事情有n種方式A1，An，每種方式中又有mi種方法（1in），且Ai Aj= ，則要完成此事共有 ，

18、即n1iimN12nNmmm 乘法原理 如果完成一件事情要分幾個步驟B1 ，B2 ， ，Bn ，而每個步驟Bi有mi種方法(1in) ，那么完成這事共有 ，即n1iimN12nNmmm7名學生站成一排，甲、乙必須站在一起有多少不同排法？（ ）7名學生站成一排，甲乙互不相鄰有多少不同排法？ （ ） 我們班里有43位同學,從中任抽5人,正、副班長、團支部書記至少有一人在內(nèi)的抽法有多少種? （ ）某班新年聯(lián)歡會原定的5個節(jié)目已排成節(jié)目單，開演前又增加了兩個新節(jié)目.如果將這兩個節(jié)目插入原節(jié)目單中，那么不同插法的種數(shù)為（ ）（ ） A42 B30 C20 D12 從黃瓜、白菜、油菜、扁豆4種蔬菜品種中選

19、出3種，分別種在不同土質(zhì)的三塊土地上，其中黃瓜必須種植，不同的種植方法共有（ ）（ ） A24種 B18種 C12種 D6種 7 在1與106之間，有多少個整數(shù)的各位數(shù)字之和等于9？（ ）排列組合組合數(shù)學基礎(chǔ)例題分析江凡問題求解選講August 10, 2016200251491 -69CC14402266 AA36002655 AA540543CC262216AAA222313ACA排列組合組合數(shù)學基礎(chǔ)例題分析江凡問題求解選講August 10, 2016 小陳現(xiàn)有2個任務(wù)A，B要完成，每個任務(wù)分別有若干步驟如下：A=a1-a2-a3，B=b1-b2-b3-b4-b5。在任何時候，小陳只能專

20、心做某個任務(wù)的一個步驟。但是如果愿意，他可以在做完手中任務(wù)的當前步驟后，切換至另一個任務(wù)，從上次此任務(wù)第一個未做的步驟繼續(xù)。每個任務(wù)的步驟順序不能打亂，例如a2-b2-a3-b3是合法的，而a2-b3-a3-b2是不合法的。小陳從B任務(wù)的b1步驟開始做，當恰做完某個任務(wù)的某個步驟后，就停工回家吃飯了。當他回來時，只記得自己已經(jīng)完成了整個任務(wù)A，其他的都忘了。試計算小陳飯前已做的可能的任務(wù)步驟序列共有 種。排列組合+加法原理:B任務(wù)中的b1一定做，而且肯定是第一個做的。除了b1外，第一類：完成A任務(wù) 只有1種。第二類：完成A任務(wù)和b2 有 種。第三類：完成A任務(wù)和b2、b3 有 種。第四類：完成

21、A任務(wù)和b2、b3、b4 有 種。第五類：完成A任務(wù)和b2、b3、b4、b5 有 種。14C25C36C47C排列組合組合數(shù)學基礎(chǔ) 例題分析 我們在討論重排列時，如將問題化為：設(shè)盒子是有區(qū)別的，每個盒子的容量不限，而且球數(shù)k盒數(shù)n，現(xiàn)計算無空盒出現(xiàn)的情況數(shù)目。 假設(shè)要用n-1塊隔板，將排成一行的k個球隔成n段，但任意兩塊隔板不能相鄰，否則就要出現(xiàn)空盒，同理隔板也不能出現(xiàn)在兩端。所以相當于要自k個球之間的k-1個間隔中選出n-1個來放置隔板，如圖 O|OO|O|OOO|O|O|OOO|OO|O 所以是一個組合問題，知有 種不同情況。x + y + z + w = 23，有多少正整數(shù)解？解：與前面

22、例子相似，但x、y、z、w不能等0。即知 有 個正整數(shù)解。江凡問題求解選講August 10, 20161n1kC154032214123CC遞推遞歸Contents歸納推理數(shù)論基礎(chǔ)遞推遞歸遞推遞歸數(shù)據(jù)結(jié)構(gòu)其他江凡問題求解選講August 10, 201612345遞推遞推遞歸江凡問題求解選講August 10, 2016 給定一個數(shù)的序列H0,H1,Hn,若存在整數(shù)n0，使當nn0時,可以用等號(或大于號、小于號)將Hn與其前面的某些項Hi(0i0n0），求出鋪法總數(shù)的遞推公式。），求出鋪法總數(shù)的遞推公式。 對給出的任意一個對給出的任意一個n（n0），用），用F（n）表示其鋪）表示其鋪法的總

23、數(shù)的遞推公式為法的總數(shù)的遞推公式為: F（1）=1 F（2）=2 F（n）=F（n-2）+F（n-1）（）（n3）遞推江凡問題求解選講August 10, 2016遞推遞歸設(shè)有一個共有設(shè)有一個共有n n級的樓梯，某人每步可走級的樓梯，某人每步可走1 1級，也可走級，也可走2 2級，級，也可走也可走3 3級，用遞推公式給出某人從底層開始走完全部樓梯的走法。級，用遞推公式給出某人從底層開始走完全部樓梯的走法。例如：當例如：當n=3n=3時，共有時，共有4 4種走法，即種走法，即1+1+1,1+2,2+1,31+1+1,1+2,2+1,3。 F（1）1 F（2）2 F（3）4F（N）F（N3）F（N

24、2）F（N1）（）（N4）遞推江凡問題求解選講August 10, 2016遞推遞歸遞推江凡問題求解選講August 10, 2016遞推遞歸Hanoi塔由n個大小不同的圓盤和三根木柱a,b,c組成。開始時，這n個圓盤由大到小依次套在a柱上，如圖1所示。要求把a柱上n個圓盤按下述規(guī)則移到c柱上：(1)一次只能移一個圓盤；(2)圓盤只能在三個柱上存放；(3)在移動過程中，不允許大盤壓小盤。問將這n個盤子從a柱移動到c柱上，總計需要移動多少個盤次？ a b c 圖1遞推江凡問題求解選講August 10, 2016遞推遞歸設(shè)有n條封閉曲線畫在平面上，而任何兩條封閉曲線恰好相交于兩點，且任何三條封閉

25、曲線不相交于同一點，問這些封閉曲線把平面分割成的區(qū)域個數(shù)。12132412346578圖21234567108911121314n=1n=2n=3n=4遞推江凡問題求解選講August 10, 2016遞推遞歸在一個凸n邊形中，通過不相交于n邊形內(nèi)部的對角線，把n邊形拆分成若干三角形，不同的拆分數(shù)目用hn表之，hn即為Catalan數(shù)。例如五邊形有如下五種拆分方案(圖3)，故h5=5。求對于一個任意的凸n邊形相應(yīng)的hn。 圖3112inniiCC遞推江凡問題求解選講August 10, 2016遞推遞歸錯排問題（經(jīng)典問題）。 n個數(shù)，分別為1n，排成一個長度為n的排列。若每一個數(shù)的位置都與數(shù)的

26、本身不相等，則稱這個排列是一個錯排。例如，n=3，則錯排有2 3 1、3 1 2。求n的錯排個數(shù)。我們設(shè)k個元素的錯位全排列的個數(shù)記做：W(k)。四個元素的錯位排列W(4)用窮舉法可以找到如下9個：( 4 , 3 , 2 , 1 )( 3 , 4 , 1 , 2 )( 2 , 1 , 4 , 3 )( 4 , 1 , 2 , 3 )( 3 , 4 , 2 , 1 )( 3 , 1 , 4 , 2 )(4,3,1,2)(2,4,1,3)(2,3,4,1)它們有什么規(guī)律呢？遞歸江凡問題求解選講August 10, 2016遞推遞歸通過反復(fù)的試驗，我們發(fā)現(xiàn)事實上有兩種方式產(chǎn)生錯位排列： A.將k與(

27、1，2，k1)的某一個數(shù)互換，其他k2個數(shù)進行錯排，這樣可以得到(k1)W(k-2)個錯位排列。 B.另一部分是將前k1個元素的每一個錯位排列（有W(k-1)個）中的每一個數(shù)與k互換，這樣可以得到剩下的(k1)W(k-1) 個錯位排列。根據(jù)加法原理，我們得到求錯位排列的遞推公式W(k):傳球問題江凡問題求解選講August 10, 2016其他4個人進行籃球訓(xùn)練，互相傳球接球，要求每個人接球后馬上傳給別人，開始由甲發(fā)球，并作為第一次傳球，第五次傳球后，球又回到甲手中，問有多少種傳球方式？傳球問題江凡問題求解選講August 10, 2016其他傳球問題江凡問題求解選講August 10, 20

28、16其他設(shè)有棱長為1米的正四面體ABCD，一只螞蟻從頂點A 出發(fā)，遵循下列規(guī)則爬行：在每個頂點相交的3條棱中選一條，然后沿這條棱到另一個頂點。求螞蟻爬行了7米路之后，又回到頂點A的方法總數(shù)。解：設(shè)從點解：設(shè)從點A出發(fā)走過出發(fā)走過n米回到點米回到點A的走法為的走法為an種。由于從種。由于從A出發(fā)出發(fā)走走n-1米的走法共有米的走法共有3n-1種種,其中有其中有an-1種是走到種是走到A的，下一步一定的，下一步一定離開離開A，除去這，除去這an-1種，其它的每一種都可以再走種，其它的每一種都可以再走1米到達米到達A點。點。因此，因此， an= 3n-1 - an-1。傳球問題江凡問題求解選講Augu

29、st 10, 2016其他 一個學生暑假在A、B、C三個城市游覽。他今天在這個城市，明天就到另一個城市。假設(shè)他第一天在A市，第五天又回到A市，問他有幾種不同的游覽方案？ 遞歸江凡問題求解選講August 10, 2016遞推遞歸 一個函數(shù)、過程、概念或數(shù)學結(jié)構(gòu)，如果在其定義或說明內(nèi)部又直接或間接地出現(xiàn)有其本身的引用，則稱它們是遞歸的或者是遞歸定義的。 遞歸過程是借助于一個遞歸工作棧來實現(xiàn)的 問題向一極推進，這一過程叫做遞推； 而問題逐一解決，最后回到原問題，這一過程叫做回歸。 遞歸的過程正是由遞推和回歸兩個過程組成。例，用遞歸算法求n的階乘，記n!定義：函數(shù) fact( n ) = n! fa

30、ct( n-1 ) = ( n-1 )! 則有 fact( n ) = n * fact( n-1 ) 已知 fact( 1 ) = 1遞歸江凡問題求解選講August 10, 2016下面畫出了調(diào)用和返回的遞歸示意圖 Bfact(2)fact(2)=2*fact(1)=2*fact(1)=2*1=2*1=2=2返回返回 DAfact(3)fact(3)=3*fact(2)=3*fact(2)=3*2=3*2=6=6E E返回返回 Cfact(1)=1調(diào)用調(diào)用調(diào)用調(diào)用遞推遞歸 某城市的街道是一個很規(guī)整的矩形網(wǎng)絡(luò)（見下圖），有7條南北向的縱街，5條東西向的橫街。現(xiàn)要從西南角的A走到東北角的B，最

31、短的走法共有多少種？_ 210 11111 1 1 1 1 12 3 4 5 6 7 3 6 10 15 21 28 4 10 20 35 56 84 5 15 35 70 126 210遞歸江凡問題求解選講August 10, 2016遞推遞歸遞歸江凡問題求解選講August 10, 2016遞推遞歸 將n個數(shù)（1，2，n）劃分成r個子集。每個數(shù)都恰好屬于一個子集，任何兩個不同的子集沒有共同的數(shù)，也沒有空集。將不同劃分方法的總數(shù)記為S(n,r)。 例如，S(4,2)=7， 這7種不同的劃分方法依次為(1),(234)，(2),(134)，(3),(124)，(4),(123)，(12),(3

32、4)，(13),(24)，(14),(23)。 當n=6，r=3時，S(6,3)=_。 9090遞歸江凡問題求解選講August 10, 2016遞推遞歸對任一元素an ，必然出現(xiàn)以下兩種情況：an是r個子集合中的一個，于是我們只要把a1,a2,an-1劃分為r-1個子集，便解決了本題，這種情況下的劃分數(shù)共有s(n-1,r-1)s(n-1,r-1)。 an不是r個子集合中的一個，則an必與其它的元素構(gòu)成一個子集。則問題相當于先把a1,a2,an-1劃分為r個子集，這種情況下的劃分數(shù)共有s(n-1,r)。然后再把元素an加入到r個子集合中的任一個中去，共有r種加入方式，這樣對于an的每一種加入方

33、式，都可以使集合劃分為r個子集。因此根據(jù)乘法原理，劃分數(shù)共有r r* *s(n-1,r)s(n-1,r)。遞歸江凡問題求解選講August 10, 2016遞推遞歸 首先不能把n個元素不放進任何一個集合中去，即r=0時，s(n,r)=0； 也不可能在不允許空集的情況下把n個元素放進多于n的r個集合中去，即rn時, s(n,r)=0 ； 再者，把n個元素放進一個集合或把n個元素放進n個集合，方案數(shù)顯然都是，即r=1或r=n時, s(n,r)=1。數(shù)據(jù)結(jié)構(gòu)Contents歸納推理數(shù)論基礎(chǔ)遞推遞歸數(shù)據(jù)結(jié)構(gòu)其他江凡問題求解選講August 10, 201612345棧江凡問題求解選講August 10, 2016數(shù)據(jù)結(jié)構(gòu)先進后出（FILO）結(jié)構(gòu)34521 34215 32145 32451 34251 32415 32154 35421 32541如下圖,有一個無窮大的的棧S,在棧的右邊排列著1,2,3,4,5共五個車廂。其中每個車廂可以向左行走,也可以進入棧S讓后面的車廂通過?，F(xiàn)已知第一個到達出口的是3號車廂，請寫出所有可能的到達出口的車廂排列