信息學(xué)奧賽問題求解選講學(xué)科競賽高中教育教育專區(qū)

1、歸納推理歸納 例1，根據(jù)Nocomachns定理，任何一個正整數(shù)n的立方一定可以表示成n個連續(xù)的奇數(shù)的和。 例如： 13 1 23 3 5 33 7 9 11 43= 13+15+17+19 在這里，假設(shè)將每一個式中的最小奇數(shù)稱為X，那么當給出n之后，請寫出X與n之間的關(guān)系表達式。江凡問題求解選講August 10, 2021X=N2-N+1 歸納推理歸納 例2，將邊長為n的正三角形每邊n等分，過每個分點分別做另外兩邊的平行線，得到假設(shè)干個正三角形，我們稱為小三角形。正三角形的一條通路是一條連續(xù)的折線，起點是最上面的一個小三角形，終點是最下面一行位于中間的小三角形。在通路中，只允許由一個小三角

2、形走到另一個與其有公共邊的且位于同一行或下一行的小三角形，并且每個小三角形不能經(jīng)過兩次或兩次以上圖中是n=5時一條通路的例子。設(shè)n=10，那么該正三角形的不同的通路的總數(shù)為 。江凡問題求解選講August 10, 2021歸納推理江凡問題求解選講August 10, 2021n=5n=5時，方案有時，方案有1 12 23 34 44!4!n=10n=10時，方案有時，方案有1 12 29 99!9!n=2n=2時，方案有時，方案有1 1種。種。n=3n=3時，方案有時，方案有2 2種。種。n=4n=4時，方案有時，方案有6 6種。種。歸納邏輯推理 通常把只涉及一些相互關(guān)聯(lián)或依存條件或關(guān)系，極少

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

4、推理邏輯推理利用表格輔助推理: 例3，某中學(xué)推理社招新題，答案是 _這道題的答案是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題以下選項中哪兩題的答案與第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題

5、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, 2021BCACACDABA 歸納推理邏輯推理利用圖形輔助推理美國數(shù)學(xué)家斯蒂恩說過:“如果一個特定的問題可以被轉(zhuǎn)化成一個圖形,那么,思想就整體地把握了問題,并且能創(chuàng)造性地思索問題解法。 例4，A、B、C、D、E五支球隊進展單循環(huán)比賽每兩支球隊間都要進展一場比賽，當比賽進展到一定階段時，統(tǒng)計A、B、C、D四個球隊已經(jīng)賽過的場數(shù)，依次為A隊4場，B隊3

6、場，C隊2場，D隊1場，這時，E隊已賽過的場數(shù)是A. 1B. 2C. 3D. 4 江凡問題求解選講August 10, 2021B數(shù)論根底Contents歸納推理數(shù)論根底同余素數(shù)排列組合遞推遞歸數(shù)據(jù)構(gòu)造其他江凡問題求解選講August 10, 202112345數(shù)論根底同余如果a1a2 b1 b2(mod m)(mod m)那么b1a1 a2 b2b1 b2(mod m)(mod m)江凡問題求解選講August 10, 2021a1a2同余的定義與性質(zhì)如果 m 整除 a b，我們就說 a 與 b 模 m 同余并記為a b(mod m)簡單來說，就是它們模 m 后的余數(shù)一樣就可以記成這樣。數(shù)論

7、根底同余江凡問題求解選講August 10, 2021a1 a2mod 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ù)論根底同余方程與中國剩余定理中國剩余定理 有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二。問物幾何？?孫子算經(jīng)? 這個問題說的是：有一個整數(shù)，被 3 除余 2，被 5 除余 3，被 7 除余 2，問這個整數(shù)是多少？ 事實上，這個問題有無窮多個解，其中一個解是 23。中國

8、剩余定理，又稱為孫子定理，常常簡寫成 CRTChinese RemainderTheorem。它給出了構(gòu)造如下方程組解的方法：(mod m1 )(mod m2 ).x an(mod mn )其中 m1 , m2 , . . . , mn 兩兩互素。江凡問題求解選講August 10, 2021同余方程與中國剩余定理數(shù)論根底中國剩余定理首先來解只有兩個方程的方程組。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

9、 的一個線性方程。 此外，中國剩余定理還告訴我們一個事實，在 m1 , m2 互素的條件下，假設(shè) x0是該方程組的一個解，那么該方程組的所有解都滿足如下形式：江凡問題求解選講August 10, 2021x x0(mod m1 m2 )這樣我們相當于把剛剛的兩個方程合并成為了一個方程。如果有多個方程，可以不斷進展這樣的合并，最后就可以解出結(jié)果了。x 2x 2數(shù)論根底同余方程與中國剩余定理中國剩余定理我們來拿剛剛開頭的例子來試著算一算。那個方程組是：x 3(mod 3)(mod 5)(mod 7)江凡問題求解選講August 10, 2021首先來合并前兩個方程，聯(lián)立后得到的線性方程是 2 +

10、3k1 = 3 + 5k2 ，整理后可以得到一組解是 k1 = 2, k2 = 1，這樣可以得到滿足前兩個方程的 x 都滿足：x 8 (mod 15)數(shù)論根底同余方程與中國剩余定理中國剩余定理之后可以得到新的方程組：xx 8 2(mod 15)(mod 7)再合并兩個方程，聯(lián)立后得到的線性方程是 8 + 15k1 = 2 + 7k2 ，整理后可以得到一組解是 k1 = 1, k2 = 3，這樣可以得到滿足這兩個方程的 x 都滿足：x 23(mod 105)這便是最后的解了！江凡問題求解選講August 10, 2021數(shù)論根底素數(shù)及根本知識江凡問題求解選講August 10, 2021素數(shù)及根

11、本知識素數(shù)是只含有 1 及其本身兩個正因子的數(shù)，也稱為質(zhì)數(shù)。如果還有其它正因子的話，那么這個數(shù)就被稱為合數(shù)。注意 1 并非素數(shù)，亦非合數(shù)。我在這里介紹一個關(guān)于素數(shù)的定理，它們在算法復(fù)雜度分析中或許會用到：Theorem (素數(shù)定理)當 x 很大時，小于 x 的素數(shù)個數(shù)近似等于x/lnx數(shù)論根底江凡問題求解選講August 10, 2021素數(shù)的判定 如何判定一個數(shù) m 是不是素數(shù)，我們可以直接從定義出發(fā)，從 2 開場到m-1 為止，檢測是否有一個數(shù)整除 m，如果沒有，那么這個數(shù)就是素數(shù)。 例6，求105內(nèi)的所有素數(shù)。 Eratosthenes 篩法是一種用來求素數(shù)的方法，它的思路比較簡單。篩法

12、是一種用來求素數(shù)的方法，它的思路比較簡單。 由于每個合數(shù)都可以被分解成幾個素數(shù)的乘積，如果我們將所有素數(shù)的倍數(shù)都刪由于每個合數(shù)都可以被分解成幾個素數(shù)的乘積，如果我們將所有素數(shù)的倍數(shù)都刪去，那么剩下的就是素數(shù)了。去，那么剩下的就是素數(shù)了。 因此，我們可以從因此，我們可以從 2 開場，先將開場，先將 2 的所有倍數(shù)都刪去。然后往下找到第一個沒有的所有倍數(shù)都刪去。然后往下找到第一個沒有被刪去的數(shù)，這個數(shù)一定是素數(shù)，再將這個數(shù)的所有倍數(shù)都刪去，不斷進展這個操作。被刪去的數(shù)，這個數(shù)一定是素數(shù)，再將這個數(shù)的所有倍數(shù)都刪去，不斷進展這個操作。素數(shù)及根本知識 線性篩法，又稱歐拉篩法。線性篩法，又稱歐拉篩法。

13、防止冗余的運算。每個合數(shù)必有一個最大因子不包括它本身防止冗余的運算。每個合數(shù)必有一個最大因子不包括它本身 ，用這個因子把，用這個因子把合數(shù)篩掉。合數(shù)篩掉。 對于每一個數(shù)對于每一個數(shù)i，乘上小于等于，乘上小于等于i的最小素因數(shù)的素數(shù)，就得到以的最小素因數(shù)的素數(shù)，就得到以i為最大因數(shù)的合為最大因數(shù)的合數(shù)。設(shè)有一個數(shù)數(shù)。設(shè)有一個數(shù)t，只要將所有以比，只要將所有以比t小的數(shù)為最大因數(shù)的合數(shù)篩去，那么比小的數(shù)為最大因數(shù)的合數(shù)篩去，那么比t小的數(shù)里小的數(shù)里剩下的就只有素數(shù)了。剩下的就只有素數(shù)了。組合數(shù)學(xué)根底排列組合 組合數(shù)學(xué)根底 例7，在1與106之間，有多少個整數(shù)的各位數(shù)字之和等于9？江凡問題求解選講A

14、ugust 10, 2021組合數(shù)學(xué)根底排列組合 排列 現(xiàn)在來考慮一個問題：你需要在 n 個不同的人里面選出 m 個人排成一行，問有多少種排列方案？ n(n 1)(n 2) (n m + 1)這個數(shù)通常被成為排列，記成 ，或者 。 如果我們定義一種名為階乘的運算：n!= 1 2 3 n特別地，當 n = 0 時，0! = 1。那么這個數(shù)就可以簡單地寫成：Anm=n!(n m)!江凡問題求解選講August 10, 2021AnmP nm組合數(shù)學(xué)根底排列組合 排列 圓排列 1由 的個元素中，每次取出r個元素排在一個圓環(huán)上，叫做一個圓排列或叫環(huán)狀排列。 2圓排列有三個特點：i無頭無尾；ii按照同一

15、方向轉(zhuǎn)換后仍是同一排列；iii兩個圓排列只有在元素不同或者元素雖然一樣，但元素之間的順序不同，才是不同的圓排列。 3定理：在的個元素中，每次取出個不同的元素進展圓排列，圓排列數(shù)為 。 不盡相異元素的全排列 如果n個元素中，有p1個元素一樣，又有p2個元素一樣，又有ps個元素一樣 ，這個n元素全部取的排列叫做不盡相異的n個元素的全排列，它的排列數(shù)是 。江凡問題求解選講August 10, 2021rPrn!21spppn,321naaaaAnppps21組合數(shù)學(xué)根底排列組合組合研究無次序的選取問題。把前述排列問題改成：你只需要在 n 個不同的人里面選出 m 個人，問有多少種方案？ 如果我們選出來

16、 m 個人后，再將他們排成一隊，那么方案數(shù)就是先前的排列數(shù) 。 但是這樣的計數(shù)會出現(xiàn)很多的重復(fù)，也就是每次我們都多算了將 m 個人排成一隊的方案數(shù)，那么這個數(shù)是什么呢？ 它就是 ，或者說 m!。 那么由于每種方案都被重復(fù)計算了 m! 次，我們只要將 除以 m! 就可以得到組合數(shù)的公式了！江凡問題求解選講August 10, 2021AnmAmmAnmCnm=nAm!=n!m!(n m)!m排列組合組合數(shù)學(xué)根底組合數(shù)的根本性質(zhì)首先第一個性質(zhì)就是先前的遞推關(guān)系(1)此外，直接根據(jù)通項可以得到一個對稱的性質(zhì)：(2)江凡問題求解選講August 10, 2021Cnm= Cn1 + Cn1mm-1Cn

17、m= Cnn-m排列組合組合數(shù)學(xué)根底排列組合分析原理全部組合分析公式的推導(dǎo)基于以下兩原理：江凡問題求解選講August 10, 2021 加法原理 如果完成一件事情有n種方式A1，An，每種方式中又有mi種方法1in，且Ai Aj= ，那么要完成此事共有 ，即n1iimN12nNmmm 乘法原理 如果完成一件事情要分幾個步驟B1 ，B2 ， ，Bn ，而每個步驟Bi有mi種方法(1in) ，那么完成這事共有 ，即n1iimN12nNmmm排列組合組合數(shù)學(xué)根底例題分析江凡問題求解選講August 10, 2021200251491 -69CC14402266 AA36002655 AA54054

18、3CC262216AAA222313ACA排列組合組合數(shù)學(xué)根底例題分析江凡問題求解選講August 10, 2021 例13 小陳現(xiàn)有2個任務(wù)A，B要完成，每個任務(wù)分別有假設(shè)干步驟如下：A=a1-a2-a3，B=b1-b2-b3-b4-b5。在任何時候，小陳只能專心做某個任務(wù)的一個步驟。但是如果愿意，他可以在做完手中任務(wù)的當前步驟后，切換至另一個任務(wù)，從上次此任務(wù)第一個未做的步驟繼續(xù)。每個任務(wù)的步驟順序不能打亂，例如a2-b2-a3-b3是合法的，而a2-b3-a3-b2是不合法的。小陳從B任務(wù)的b1步驟開場做，當恰做完某個任務(wù)的某個步驟后，就停工回家吃飯了。當他回來時，只記得自己已經(jīng)完成了整

19、個任務(wù)A，其他的都忘了。試計算小陳飯前已做的可能的任務(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 有 種。14C25C36C47C排列組合組合數(shù)學(xué)根底 例題分析鴿巢原理又稱抽屜原理簡介 我們在討論重排列時，如將問題化為：設(shè)盒子是有區(qū)別的，每個盒子的容量不限，而且球數(shù)k盒數(shù)n，現(xiàn)計算無空盒出現(xiàn)的情況數(shù)目。 假設(shè)要用n-1塊隔板，將排成一行的k個球隔成n段，

20、但任意兩塊隔板不能相鄰，否那么就要出現(xiàn)空盒，同理隔板也不能出現(xiàn)在兩端。所以相當于要自k個球之間的k-1個間隔中選出n-1個來放置隔板，如圖 O|OO|O|OOO|O|O|OOO|OO|O 所以是一個組合問題，知有 種不同情況。例14x + y + z + w = 23，有多少正整數(shù)解？解：與前面例子相似，但x、y、z、w不能等0。即知 有 個正整數(shù)解。江凡問題求解選講August 10, 20211n1kC154032214123CC遞推遞歸Contents歸納推理數(shù)論根底遞推遞歸遞推遞歸數(shù)據(jù)構(gòu)造其他江凡問題求解選講August 10, 202112345遞推遞推遞歸江凡問題求解選講Augus

21、t 10, 2021 給定一個數(shù)的序列H0,H1,Hn,假設(shè)存在整數(shù)n0，使當nn0時,可以用等號(或大于號、小于號)將Hn與其前面的某些項Hi(0i0n0，求出鋪法總數(shù)的遞推公式。，求出鋪法總數(shù)的遞推公式。 對給出的任意一個對給出的任意一個n（n0），用），用F（n）表示其鋪）表示其鋪法的總數(shù)的遞推公式為法的總數(shù)的遞推公式為: F（1）=1 F（2）=2 F（n）=F（n-2）+F（n-1）（）（n3）遞推江凡問題求解選講August 10, 2021遞推遞歸F11 F22 F34FNFN3FN2FN1N4遞推江凡問題求解選講August 10, 2021遞推遞歸遞推江凡問題求解選講Augu

22、st 10, 2021遞推遞歸 a b c 圖1遞推江凡問題求解選講August 10, 2021遞推遞歸設(shè)有n條封閉曲線畫在平面上，而任何兩條封閉曲線恰好相交于兩點，且任何三條封閉曲線不相交于同一點，問這些封閉曲線把平面分割成的區(qū)域個數(shù)。12132412346578圖21234567108911121314n=1n=2n=3n=4遞推江凡問題求解選講August 10, 2021遞推遞歸圖3112inniiCC遞推江凡問題求解選講August 10, 2021遞推遞歸我們設(shè)k個元素的錯位全排列的個數(shù)記做：W(k)。四個元素的錯位排列W(4)用窮舉法可以找到如下9個：( 4 , 3 , 2 ,

23、 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, 2021遞推遞歸通過反復(fù)的試驗，我們發(fā)現(xiàn)事實上有兩種方式產(chǎn)生錯位排列： A.將k與(1，2，k1)的某一個數(shù)互換，其他k2個數(shù)進展錯排，這樣可以得到(k1)W(k-2)個錯位排列。 B.另一局部是將前k1個元素的每一個錯位排列有W(k-1)個中的每一個數(shù)與k互換，這樣可以得到剩下的(k1)W(k-1) 個錯

24、位排列。根據(jù)加法原理，我們得到求錯位排列的遞推公式W(k):傳球問題江凡問題求解選講August 10, 2021其他傳球問題江凡問題求解選講August 10, 2021其他傳球問題江凡問題求解選講August 10, 2021其他解：設(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 -

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

26、法求n的階乘，記n!定義：函數(shù) fact( n ) = n! fact( n-1 ) = ( n-1 )! 那么有 fact( n ) = n * fact( n-1 ) fact( 1 ) = 1遞歸江凡問題求解選講August 10, 2021下面畫出了調(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)用遞推遞歸遞歸的概念與根本思想 例21某城市的街道是一個很規(guī)整的矩形

27、網(wǎng)絡(luò)見以下圖，有7條南北向的縱街，5條東西向的橫街?，F(xiàn)要從西南角的A走到東北角的B，最短的走法共有多少種？_ 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, 2021遞推遞歸遞歸江凡問題求解選講August 10, 2021遞推遞歸 例22將n個數(shù)1，2，n劃分成r個子集。每個數(shù)都恰好屬于一個子集，任何兩個不同的子集沒有共同的數(shù)，也沒有空集。將不同劃分方法的總數(shù)記為S(n,r)。 例如，S(4,2)=7， 這7種不同的劃分方法依次為(1)

28、,(234)，(2),(134)，(3),(124)，(4),(123)，(12),(34)，(13),(24)，(14),(23)。 當n=6，r=3時，S(6,3)=_。 9090遞歸江凡問題求解選講August 10, 2021遞推遞歸對任一元素an ，必然出現(xiàn)以下兩種情況：an是r個子集合中的一個，于是我們只要把a1,a2,an-1劃分為r-1個子集，便解決了此題，這種情況下的劃分數(shù)共有s(n-1,r-1)。 an不是r個子集合中的一個，那么an必與其它的元素構(gòu)成一個子集。那么問題相當于先把a1,a2,an-1劃分為r個子集，這種情況下的劃分數(shù)共有s(n-1,r)。然后再把元素an參加到r個子集合中的任一個中去，共有r種參加方式，這樣對于an的每一種參加方式，都可以使集合劃分為r個子集。因此根據(jù)乘法原理，劃分數(shù)共有r*s(n-1,r)。遞歸江凡問題求解選講August 10, 2021遞推遞歸 首先不能把n個元素不放進任何一個集合中去，即r=0時，s(n,r)=0； 也不可能在不允許空集的情況下把n個元素放進多于n的r個集合中去，即rn時, s(n,r)