信息學(xué)奧賽問題求解選講

信息學(xué)奧賽問題求解選講第一頁，共五十一頁，2022年，8月28日

歸納推理Contents歸納推理

歸納

邏輯推理初等數(shù)論遞推遞歸數(shù)據(jù)結(jié)構(gòu)其他江凡問題求解選講August10,201612345第二頁，共五十一頁，2022年，8月28日歸納推理歸納

例1，根據(jù)Nocomachns定理，任何一個正整數(shù)n的立方一定可以表示成n個連續(xù)的奇數(shù)的和。例如：

13＝123＝3＋533＝7＋9＋1143=13+15+17+19

在這里，若將每一個式中的最小奇數(shù)稱為X，那么當(dāng)給出n之后，請寫出X與n之間的關(guān)系表達(dá)式。江凡問題求解選講August10,2016X=N2-N+1第三頁，共五十一頁，2022年，8月28日歸納推理歸納

例2，將邊長為n的正三角形每邊n等分，過每個分點(diǎn)分別做另外兩邊的平行線，得到若干個正三角形，我們稱為小三角形。正三角形的一條通路是一條連續(xù)的折線，起點(diǎn)是最上面的一個小三角形，終點(diǎn)是最下面一行位于中間的小三角形。在通路中，只允許由一個小三角形走到另一個與其有公共邊的且位于同一行或下一行的小三角形，并且每個小三角形不能經(jīng)過兩次或兩次以上（圖中是n=5時(shí)一條通路的例子）。設(shè)n=10，則該正三角形的不同的通路的總數(shù)為

。

江凡問題求解選講August10,2016362880第四頁，共五十一頁，2022年，8月28日歸納推理江凡問題求解選講August10,2016n=5時(shí)，方案有1×2×3×4＝4!n=10時(shí)，方案有1×2×…×9＝9!n=2時(shí)，方案有1種。n=3時(shí)，方案有2種。n=4時(shí)，方案有6種。歸納第五頁，共五十一頁，2022年，8月28日邏輯推理

通常把只涉及一些相互關(guān)聯(lián)（或依存）條件或關(guān)系，極少給出（不直接賦與）數(shù)量關(guān)系與幾何圖形的一類非標(biāo)準(zhǔn)（常規(guī)）數(shù)學(xué)問題叫邏輯推理問題，處理這類問題，要從一些關(guān)聯(lián)的條件出發(fā)，應(yīng)用某些數(shù)學(xué)知識，甚至日常生活常識，依據(jù)一定的思維規(guī)律（機(jī)智靈活、準(zhǔn)確敏捷的思考），通過分析、推理、排除不可能情況（剔除不合理成分），然后作出正確的判斷。邏輯推理問題中常用到以下三條邏輯基本規(guī)律：（1）同一律：是指同一東西（對象）。它是什么就是什么，不能模棱兩可，亦此亦彼；（2）矛盾律：是指互相對立（矛盾）的事不能都真，二者必有一假（即同一思想不能既真又假）；（3）排中律：是指兩個不相容的判斷不能都假，二者必有一真（即任何判斷或同一思想不能既不真也不假）。歸納推理邏輯推理江凡問題求解選講August10,2016第六頁，共五十一頁，2022年，8月28日歸納推理邏輯推理利用表格輔助推理:

例3，某中學(xué)推理社招新題，答案是_____________⒈這道題的答案是A．A B．B C．C D．D⒉第5題的答案是A．C B．D C．A D．B⒊以下選項(xiàng)中哪一題的答案與其他三項(xiàng)不同A．第3題 B．第6題 C．第2題 D．第4題⒋以下選項(xiàng)中哪兩題的答案相同A．第1，5題 B．第2，7題 C．第1，9題 D．第6，10題⒌以下選項(xiàng)中哪一題的答案與本題相同A．第8題 B．第4題 C．第9題 D．第7題⒍以下選項(xiàng)中哪兩題的答案與第8題相同A．第2，4題 B．第1，6題 C．第3，10題 D．第5，9題⒎在此十道題中，被選擇次數(shù)最少的選項(xiàng)字母為A．C B．B C．A D．D⒏以下選項(xiàng)中哪一題的答案與第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ù)最多者與最少者的差為A．3 B．2 C．4 D．1江凡問題求解選講August10,2016BCACACDABA

第七頁，共五十一頁，2022年，8月28日歸納推理邏輯推理利用圖形輔助推理美國數(shù)學(xué)家斯蒂恩說過:“如果一個特定的問題可以被轉(zhuǎn)化成一個圖形,那么,思想就整體地把握了問題,并且能創(chuàng)造性地思索問題解法。”例4，A、B、C、D、E五支球隊(duì)進(jìn)行單循環(huán)比賽（每兩支球隊(duì)間都要進(jìn)行一場比賽），當(dāng)比賽進(jìn)行到一定階段時(shí)，統(tǒng)計(jì)A、B、C、D四個球隊(duì)已經(jīng)賽過的場數(shù)，依次為A隊(duì)4場，B隊(duì)3場，C隊(duì)2場，D隊(duì)1場，這時(shí)，E隊(duì)已賽過的場數(shù)是（ ）A.1 B.2 C.3 D.4江凡問題求解選講August10,2016B第八頁，共五十一頁，2022年，8月28日

數(shù)論基礎(chǔ)Contents歸納推理數(shù)論基礎(chǔ)同余素?cái)?shù)排列組合遞推遞歸數(shù)據(jù)結(jié)構(gòu)其他江凡問題求解選講August10,201612345第九頁，共五十一頁，2022年，8月28日數(shù)論基礎(chǔ)同余如果a1a2≡b1≡b2(modm)(modm)那么b1a1

±a2≡±b2b1

b2(modm)(modm)江凡問題求解選講August10,2016a1a2≡同余的定義與性質(zhì)

如果m整除a?b，我們就說a與b模m同余并記為a≡b(modm)簡單來說，就是它們模m后的余數(shù)相同就可以記成這樣。第十頁，共五十一頁，2022年，8月28日數(shù)論基礎(chǔ)同余江凡問題求解選講August10,2016（a1×a2）modb＝(a1modb)×(a2modb)modb分治思想與快速冪方法例5，輸入b，p，k的值，求bpmodk的值。如，59mod7=？59=【（5×5）×（5×5）】×【（5×5）×（5×5）】×54422456第十一頁，共五十一頁，2022年，8月28日x≡a1x≡a2..數(shù)論基礎(chǔ)同余方程與中國剩余定理

中國剩余定理有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二。問物幾何？

——《孫子算經(jīng)》

這個問題說的是：有一個整數(shù)，被3除余2，被5除余3，被7除余2，問這個整數(shù)是多少？事實(shí)上，這個問題有無窮多個解，其中一個解是23。

中國剩余定理，又稱為孫子定理，常常簡寫成CRT（ChineseRemainderTheorem）。它給出了構(gòu)造如下方程組解的方法：(modm1)(modm2).x≡an(modmn)其中m1,m2,...,mn

兩兩互素。江凡問題求解選講August10,2016第十二頁，共五十一頁，2022年，8月28日同余方程與中國剩余定理

數(shù)論基礎(chǔ)中國剩余定理

首先來解只有兩個方程的方程組。xx≡a1≡a2(modm1)(modm2)我們可以把這個方程組改寫成xx=a1+k1m1=a2+k2m2

消去x之后就可以得到a1+k1m1=a2+k2m2

，這剛好是關(guān)于k1,k2的一個線性方程。此外，中國剩余定理還告訴我們一個事實(shí)，在m1,m2互素的條件下，假設(shè)x0是該方程組的一個解，那么該方程組的所有解都滿足如下形式：江凡問題求解選講August10,2016x≡x0(modm1m2)

這樣我們相當(dāng)于把剛剛的兩個方程合并成為了一個方程。如果有多個方程，可以不斷進(jìn)行這樣的合并，最后就可以解出結(jié)果了。第十三頁，共五十一頁，2022年，8月28日x≡2x≡2數(shù)論基礎(chǔ)同余方程與中國剩余定理中國剩余定理

我們來拿剛剛開頭的例子來試著算一算。那個方程組是：x≡3(mod3)(mod5)(mod7)江凡問題求解選講August10,2016

首先來合并前兩個方程，聯(lián)立后得到的線性方程是2+3k1=3+5k2

，整理后可以得到一組解是k1=2,k2=1，這樣可以得到滿足前兩個方程的x都滿足：x≡8(mod15)第十四頁，共五十一頁，2022年，8月28日數(shù)論基礎(chǔ)同余方程與中國剩余定理中國剩余定理

之后可以得到新的方程組：xx≡8≡2(mod15)(mod7)

再合并兩個方程，聯(lián)立后得到的線性方程是8+15k1=2+7k2

，整理后可以得到一組解是k1=1,k2=3，這樣可以得到滿足這兩個方程的x都滿足：x≡23(mod105)這便是最后的解了！江凡問題求解選講August10,2016第十五頁，共五十一頁，2022年，8月28日數(shù)論基礎(chǔ)素?cái)?shù)及基本知識江凡問題求解選講August10,2016

素?cái)?shù)及基本知識

素?cái)?shù)是只含有1及其本身兩個正因子的數(shù)，也稱為質(zhì)數(shù)。如果還有其它正因子的話，那么這個數(shù)就被稱為合數(shù)。注意1并非素?cái)?shù)，亦非合數(shù)。 我在這里介紹一個關(guān)于素?cái)?shù)的定理，它們在算法復(fù)雜度分析中或許會用到：Theorem(素?cái)?shù)定理)當(dāng)x很大時(shí)，小于x的素?cái)?shù)個數(shù)近似等于x/lnx第十六頁，共五十一頁，2022年，8月28日數(shù)論基礎(chǔ)江凡問題求解選講August10,2016

素?cái)?shù)的判定

如何判定一個數(shù)m是不是素?cái)?shù)，我們可以直接從定義出發(fā)，從2開始到m-1為止，檢測是否有一個數(shù)整除m，如果沒有，那么這個數(shù)就是素?cái)?shù)。

例6，求105內(nèi)的所有素?cái)?shù)。

⒈Eratosthenes篩法是一種用來求素?cái)?shù)的方法，它的思路比較簡單。由于每個合數(shù)都可以被分解成幾個素?cái)?shù)的乘積，如果我們將所有素?cái)?shù)的倍數(shù)都刪去，那么剩下的就是素?cái)?shù)了。因此，我們可以從2開始，先將2的所有倍數(shù)都刪去。然后往下找到第一個沒有被刪去的數(shù)，這個數(shù)一定是素?cái)?shù)，再將這個數(shù)的所有倍數(shù)都刪去，不斷進(jìn)行這個操作。素?cái)?shù)及基本知識

⒉線性篩法，又稱歐拉篩法。避免冗余的運(yùn)算。每個合數(shù)必有一個最大因子（不包括它本身），用這個因子把合數(shù)篩掉。對于每一個數(shù)i，乘上小于等于i的最小素因數(shù)的素?cái)?shù)，就得到以i為最大因數(shù)的合數(shù)。設(shè)有一個數(shù)t，只要將所有以比t小的數(shù)為最大因數(shù)的合數(shù)篩去，那么比t小的數(shù)里剩下的就只有素?cái)?shù)了。第十七頁，共五十一頁，2022年，8月28日組合數(shù)學(xué)基礎(chǔ)排列組合

組合數(shù)學(xué)基礎(chǔ)例7，在1與106之間，有多少個整數(shù)的各位數(shù)字之和等于9？江凡問題求解選講August10,2016第十八頁，共五十一頁，2022年，8月28日組合數(shù)學(xué)基礎(chǔ)排列組合

排列現(xiàn)在來考慮一個問題：你需要在n個不同的人里面選出m個人排成一行，問有多少種排列方案？

n(n?1)(n?2)···(n?m+1)

這個數(shù)通常被成為排列，記成，或者。如果我們定義一種名為階乘的運(yùn)算：n!=1×2×3×···×n特別地，當(dāng)n=0時(shí)，0!=1。那么這個數(shù)就可以簡單地寫成：Anm=

n!(n?m)!江凡問題求解選講August10,2016AnmPnm第十九頁，共五十一頁，2022年，8月28日組合數(shù)學(xué)基礎(chǔ)排列組合

排列圓排列（1）由的個元素中，每次取出r個元素排在一個圓環(huán)上，叫做一個圓排列（或叫環(huán)狀排列）。（2）圓排列有三個特點(diǎn)：（i）無頭無尾；（ii）按照同一方向轉(zhuǎn)換后仍是同一排列；（iii）兩個圓排列只有在元素不同或者元素雖然相同，但元素之間的順序不同，才是不同的圓排列。（3）定理：在的個元素中，每次取出個不同的元素進(jìn)行圓排列，圓排列數(shù)為。不盡相異元素的全排列如果n個元素中，有p1個元素相同，又有p2個元素相同，…，又有ps個元素相同（），這個n元素全部取的排列叫做不盡相異的n個元素的全排列，它的排列數(shù)是。江凡問題求解選講August10,2016第二十頁，共五十一頁，2022年，8月28日組合數(shù)學(xué)基礎(chǔ)排列組合

組合

研究無次序的選取問題。把前述排列問題改成：你只需要在n個不同的人里面選出m個人，問有多少種方案？如果我們選出來m個人后，再將他們排成一隊(duì)，那么方案數(shù)就是先前的排列數(shù)

。但是這樣的計(jì)數(shù)會出現(xiàn)很多的重復(fù)，也就是每次我們都多算了將m個人排成一隊(duì)的方案數(shù)，那么這個數(shù)是什么呢？它就是

，或者說m!。那么由于每種方案都被重復(fù)計(jì)算了m!次，我們只要將

除以m!就可以得到組合數(shù)的公式了！江凡問題求解選講August10,2016AnmAmmAnmCnm=nAm!=

n!m!(n?m)!m第二十一頁，共五十一頁，2022年，8月28日排列組合

組合數(shù)學(xué)基礎(chǔ)組合數(shù)的基本性質(zhì)

首先第一個性質(zhì)就是先前的遞推關(guān)系(1)此外，直接根據(jù)通項(xiàng)可以得到一個對稱的性質(zhì)：(2)江凡問題求解選講August10,2016Cnm=Cn?1+Cn?1mm-1Cnm=Cnn-m第二十二頁，共五十一頁，2022年，8月28日排列組合

組合數(shù)學(xué)基礎(chǔ)排列組合分析原理全部組合分析公式的推導(dǎo)基于以下兩原理：江凡問題求解選講August10,2016

⒈加法原理如果完成一件事情有n種方式A1，???，An，每種方式中又有mi種方法（1≤i≤n），且AiAj=?，則要完成此事共有，即

⒉乘法原理如果完成一件事情要分幾個步驟B1

，B2

，…，Bn

，而每個步驟Bi有mi種方法(1≤i≤n)，那么完成這事共有，即第二十三頁，共五十一頁，2022年，8月28日例8．7名學(xué)生站成一排，甲、乙必須站在一起有多少不同排法？（相臨問題——整體捆綁法）例9．7名學(xué)生站成一排，甲乙互不相鄰有多少不同排法？（不相臨問題——選空插入法）例10．我們班里有43位同學(xué),從中任抽5人,正、副班長、團(tuán)支部書記至少有一人在內(nèi)的抽法有多少種?（復(fù)雜問題——總體排除法或排異法）例11．某班新年聯(lián)歡會原定的5個節(jié)目已排成節(jié)目單，開演前又增加了兩個新節(jié)目.如果將這兩個節(jié)目插入原節(jié)目單中，那么不同插法的種數(shù)為（）（多元問題——分類討論法）

A．42B．30C．20D．12例12．從黃瓜、白菜、油菜、扁豆4種蔬菜品種中選出3種，分別種在不同土質(zhì)的三塊土地上，其中黃瓜必須種植，不同的種植方法共有（）（混合問題——先選后排法）

A．24種

B．18種

C．12種

D．6種例7．在1與106之間，有多少個整數(shù)的各位數(shù)字之和等于9？（相同元素分配——轉(zhuǎn)化與檔板分隔法）排列組合

組合數(shù)學(xué)基礎(chǔ)例題分析江凡問題求解選講August10,2016第二十四頁，共五十一頁，2022年，8月28日排列組合

組合數(shù)學(xué)基礎(chǔ)例題分析江凡問題求解選講August10,2016

例13

．小陳現(xiàn)有2個任務(wù)A，B要完成，每個任務(wù)分別有若干步驟如下：A=a1->a2->a3，B=b1->b2->b3->b4->b5。在任何時(shí)候，小陳只能專心做某個任務(wù)的一個步驟。但是如果愿意，他可以在做完手中任務(wù)的當(dāng)前步驟后，切換至另一個任務(wù)，從上次此任務(wù)第一個未做的步驟繼續(xù)。每個任務(wù)的步驟順序不能打亂，例如……a2->b2->a3->b3……是合法的，而……a2->b3->a3->b2……是不合法的。小陳從B任務(wù)的b1步驟開始做，當(dāng)恰做完某個任務(wù)的某個步驟后，就停工回家吃飯了。當(dāng)他回來時(shí)，只記得自己已經(jīng)完成了整個任務(wù)A，其他的都忘了。試計(jì)算小陳飯前已做的可能的任務(wù)步驟序列共有

種。排列組合+加法原理:B任務(wù)中的b1一定做，而且肯定是第一個做的。除了b1外，第一類：完成A任務(wù)只有1種。第二類：完成A任務(wù)和b2有種。第三類：完成A任務(wù)和b2、b3有種。第四類：完成A任務(wù)和b2、b3、b4有種。第五類：完成A任務(wù)和b2、b3、b4、b5有種。1+4+10+20+35=70第二十五頁，共五十一頁，2022年，8月28日排列組合

組合數(shù)學(xué)基礎(chǔ)例題分析鴿巢原理（又稱抽屜原理）（簡介）我們在討論重排列時(shí)，如將問題化為：設(shè)盒子是有區(qū)別的，每個盒子的容量不限，而且球數(shù)k≥盒數(shù)n，現(xiàn)計(jì)算無空盒出現(xiàn)的情況數(shù)目。

假設(shè)要用n-1塊隔板，將排成一行的k個球隔成n段，但任意兩塊隔板不能相鄰，否則就要出現(xiàn)空盒，同理隔板也不能出現(xiàn)在兩端。所以相當(dāng)于要自k個球之間的k-1個間隔中選出n-1個來放置隔板，如圖O|OO|O|OOO|O|O|OOO|OO|O

所以是一個組合問題，知有種不同情況。例14．x+y+z+w=23，有多少正整數(shù)解？解：與前面例子相似，但x、y、z、w不能等0。即知有個正整數(shù)解。江凡問題求解選講August10,2016第二十六頁，共五十一頁，2022年，8月28日

遞推遞歸Contents歸納推理數(shù)論基礎(chǔ)遞推遞歸遞推遞歸數(shù)據(jù)結(jié)構(gòu)其他江凡問題求解選講August10,201612345第二十七頁，共五十一頁，2022年，8月28日遞推

遞推遞歸遞推江凡問題求解選講August10,2016

給定一個數(shù)的序列H0,H1,…,Hn,…若存在整數(shù)n0，使當(dāng)n>n0時(shí),可以用等號(或大于號、小于號)將Hn與其前面的某些項(xiàng)Hi(0<i<n)聯(lián)系起來，這樣的式子就叫做遞推關(guān)系。幾種典型遞推關(guān)系

Fibonacci數(shù)列

Hanoi塔問題平面分割問題

Catalan數(shù)解決遞推問題的一般步驟：建立遞推關(guān)系式確定邊界條件遞推求解第二十八頁，共五十一頁，2022年，8月28日

例15．有2×n的一個長方形方格，用一個1×2的骨牌鋪滿方格。例如n=3時(shí)，為2×3方格。此時(shí)用一個1×2的骨牌鋪滿方格，共有3種鋪法：試對給出的任意一個n（n>0），求出鋪法總數(shù)的遞推公式。對給出的任意一個n（n>0），用F（n）表示其鋪法的總數(shù)的遞推公式為:F（1）=1F（2）=2F（n）=F（n-2）+F（n-1）（n≥3）遞推江凡問題求解選講August10,2016

遞推遞歸遞推——斐波那契數(shù)列第二十九頁，共五十一頁，2022年，8月28日練習(xí)，設(shè)有一個共有n級的樓梯，某人每步可走1級，也可走2級，也可走3級，用遞推公式給出某人從底層開始走完全部樓梯的走法。例如：當(dāng)n=3時(shí)，共有4種走法，即1+1+1,1+2,2+1,3。F（1）＝1

F（2）＝2

F（3）＝4

F（N）＝F（N－3）＋F（N－2）＋F（N－1）（N≥4）遞推江凡問題求解選講August10,2016

遞推遞歸遞推——斐波那契數(shù)列第三十頁，共五十一頁，2022年，8月28日遞推江凡問題求解選講August10,2016

遞推遞歸遞推——Hanoi塔問題例16．Hanoi塔由n個大小不同的圓盤和三根木柱a,b,c組成。開始時(shí)，這n個圓盤由大到小依次套在a柱上，如圖1所示。

要求把a(bǔ)柱上n個圓盤按下述規(guī)則移到c柱上：(1)一次只能移一個圓盤；(2)圓盤只能在三個柱上存放；(3)在移動過程中，不允許大盤壓小盤。問將這n個盤子從a柱移動到c柱上，總計(jì)需要移動多少個盤次？abc

圖1遞推關(guān)系：hn=2hn-1+1邊界條件：h1=1第三十一頁，共五十一頁，2022年，8月28日遞推江凡問題求解選講August10,2016

遞推遞歸遞推——平面分割問題例17．設(shè)有n條封閉曲線畫在平面上，而任何兩條封閉曲線恰好相交于兩點(diǎn)，且任何三條封閉曲線不相交于同一點(diǎn)，問這些封閉曲線把平面分割成的區(qū)域個數(shù)。12132412346578圖21234567108911121314n=1n=2n=3n=4遞推關(guān)系：an=an-1+2(n-1)邊界條件：a1=2第三十二頁，共五十一頁，2022年，8月28日遞推江凡問題求解選講August10,2016

遞推遞歸遞推——Catalan數(shù)例18．在一個凸n邊形中，通過不相交于n邊形內(nèi)部的對角線，把n邊形拆分成若干三角形，不同的拆分?jǐn)?shù)目用hn表之，hn即為Catalan數(shù)。例如五邊形有如下五種拆分方案(圖3)，故h5=5。求對于一個任意的凸n邊形相應(yīng)的hn。圖3邊界條件：C2=1第三十三頁，共五十一頁，2022年，8月28日遞推江凡問題求解選講August10,2016

遞推遞歸遞推的應(yīng)用——組合計(jì)數(shù)例19．錯排問題（經(jīng)典問題）。

n個數(shù)，分別為1~n，排成一個長度為n的排列。若每一個數(shù)的位置都與數(shù)的本身不相等，則稱這個排列是一個錯排。例如，n=3，則錯排有231、312。求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ī)律呢？第三十四頁，共五十一頁，2022年，8月28日遞歸江凡問題求解選講August10,2016

遞推遞歸遞推的應(yīng)用——組合計(jì)數(shù)通過反復(fù)的試驗(yàn)，我們發(fā)現(xiàn)事實(shí)上有兩種方式產(chǎn)生錯位排列：

A.將k與(1，2，…，k－1)的某一個數(shù)互換，其他k－2個數(shù)進(jìn)行錯排，這樣可以得到(k－1)×W(k-2)個錯位排列。

B.另一部分是將前k－1個元素的每一個錯位排列（有W(k-1)個）中的每一個數(shù)與k互換，這樣可以得到剩下的(k－1)×W(k-1)個錯位排列。根據(jù)加法原理，我們得到求錯位排列的遞推公式W(k):W(k)=(k–1)×[W(k–1)+W(k–2)]第三十五頁，共五十一頁，2022年，8月28日傳球問題江凡問題求解選講August10,2016

其他傳球問題

例20．4個人進(jìn)行籃球訓(xùn)練，互相傳球接球，要求每個人接球后馬上傳給別人，開始由甲發(fā)球，并作為第一次傳球，第五次傳球后，球又回到甲手中，問有多少種傳球方式？第三十六頁，共五十一頁，2022年，8月28日傳球問題江凡問題求解選講August10,2016

其他傳球問題第三十七頁，共五十一頁，2022年，8月28日傳球問題江凡問題求解選講August10,2016

其他傳球問題應(yīng)用

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

其他傳球問題應(yīng)用

練習(xí)：一個學(xué)生暑假在A、B、C三個城市游覽。他今天在這個城市，明天就到另一個城市。假設(shè)他第一天在A市，第五天又回到A市，問他有幾種不同的游覽方案？

第三十九頁，共五十一頁，2022年，8月28日遞歸江凡問題求解選講August10,2016

遞推遞歸遞歸的概念與基本思想

一個函數(shù)、過程、概念或數(shù)學(xué)結(jié)構(gòu)，如果在其定義或說明內(nèi)部又直接或間接地出現(xiàn)有其本身的引用，則稱它們是遞歸的或者是遞歸定義的。遞歸過程是借助于一個遞歸工作棧來實(shí)現(xiàn)的問題向一極推進(jìn)，這一過程叫做遞推；而問題逐一解決，最后回到原問題，這一過程叫做回歸。遞歸的過程正是由遞推和回歸兩個過程組成。例，用遞歸算法求n的階乘，記n!定義：函數(shù)fact(n)=n! fact(n-1)=(n-1)!

則有fact(n)=n*fact(n-1)

已知fact(1)=1第四十頁，共五十一頁，2022年，8月28日遞歸江凡問題求解選講August10,2016下面畫出了調(diào)用和返回的遞歸示意圖

遞推遞歸遞歸的概念與基本思想第四十一頁，共五十一頁，2022年，8月28日

例21．某城市的街道是一個很規(guī)整的矩形網(wǎng)絡(luò)（見下圖），有7條南北向的縱街，5條東西向的橫街。現(xiàn)要從西南角的A走到東北角的B，最短的走法共有多少種？_____21011111111112345673610152128410203556845153570126210遞歸江凡問題求解選講August10,2016

遞推遞歸遞歸的應(yīng)用遞歸關(guān)系：F(x,y)=F(x-1,y)+F(x,y-1)邊界條件：F(1,y)=1F(x,1)=1第四十二頁，共五十一頁，2022年，8月28日遞歸江凡問題求解選講August10,2016

遞推遞歸遞歸的應(yīng)用——子集劃分

例22．將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),(34)}，{(13),(24)}，{(14),(23)}。當(dāng)n=6，r=3時(shí)，S(6,3)=______。90第四十三頁，共五十一頁，2022年，8月28日遞歸江凡問題求解選講August10,2016

遞推遞歸遞歸的應(yīng)用——子集劃分對任一元素an

，必然出現(xiàn)以下兩種情況：⑴｛an｝是r個子集合中的一個，于是我們只要把a(bǔ)1,a2,…,an-1劃分為r-1個子集，便解決了本題，這種情況下的劃分?jǐn)?shù)共有s(n-1,r-1)。⑵｛an｝不是r個子集合中的一個，則an必與其它的元素構(gòu)成一個子集。則問題相當(dāng)于先把a(bǔ)1,a2,…,an-1劃分為r個子集，這種情況下的劃分?jǐn)?shù)共有s(n-1,r)。然后再把元素an加入到r個子集合中的任一個中去，共有r種加入方式，這樣對于an的每一種加入方式，都可以使集合劃分為r個子集。因此根據(jù)乘法原理，劃分?jǐn)?shù)共有r*s(n-1,r)。S(n,r)=S(n-1,r-1)+r×S(n-1,r)第四十四頁，共五十一頁，2022年，8月28日遞歸江凡問題求解選講August10,2016

遞推遞歸遞歸的應(yīng)用——子集劃分確定邊界：首先不能把n個元素不放進(jìn)任何一個集合中去，即r=0時(shí)，s(n,r)=0；也不可能在不允許空集的情況下把n個元素放進(jìn)多于n的r個集合中去，即r>n時(shí),s(n,r)=0；再者，把n個元素放進(jìn)一個集合或把n個元素放進(jìn)n個集合，方案數(shù)顯然都是１，即r=1或r=n時(shí),s(n,r)=1。S(6,3)=S(5,2)+3×S(5,3)=S(4,1)+2×S(4,2)+3×(S(4,2)+3×S(4,3))=……=90第四十五頁，共五十一頁，2022年，8月28日

數(shù)據(jù)結(jié)構(gòu)Contents歸納推理數(shù)論基礎(chǔ)遞推遞歸數(shù)據(jù)結(jié)構(gòu)其他江凡問題求解選講August10,201612345第四十六頁，共五十一頁，2022年，8月28日棧江凡問題求解選講August10,2016

數(shù)據(jù)結(jié)構(gòu)?！冗M(jìn)后出（FILO）結(jié)構(gòu)34521342153214532451

34251

32415321543542132541

例23．如下圖,有一個無窮大的的棧S,在棧的右邊排列著1,2,3,4,5共五個車廂。其中每個車廂可以向左行走,也可以進(jìn)入棧S讓后面的車廂通過?，F(xiàn)已知第一個到達(dá)出口的是3號車廂，請寫出所有可能的到達(dá)出口的車廂排列方案。3214