東北師范大學(xué)信息學(xué)選論第三章一、二節(jié).ppt

第三章 構(gòu)造法,構(gòu)造法:就是根據(jù)題設(shè)條件或結(jié)論所具有的特征、性質(zhì)，構(gòu)造出滿足條件或結(jié)論的數(shù)學(xué)模型，借助于該數(shù)學(xué)模型解決問(wèn)題的方法,在現(xiàn)實(shí)世界中，有大量事物存在著許多相似或相近的規(guī)律，存在著本質(zhì)相同的東西。正因?yàn)槿绱?，在求解非?biāo)準(zhǔn)題的過(guò)程中就有可能形成一些常用的方法思路（策略），按照這些方法思路分析和求解試題，一般可使解題過(guò)程變得容易一些。這些方法思路統(tǒng)稱為構(gòu)造法。 由于構(gòu)造法比較綜合地反映了選手的智慧、知識(shí)基礎(chǔ)和創(chuàng)造性思維的能力，因此是聯(lián)賽的考核重點(diǎn)。,從數(shù)學(xué)方法的分類來(lái)看，構(gòu)造的數(shù)學(xué)模型屬于初等模型或優(yōu)化模型。 一般地，數(shù)學(xué)模型具有三大功能： 1解釋功能: 利用數(shù)學(xué)模型說(shuō)明事物發(fā)生的原因。 2判斷功能：利用數(shù)學(xué)模型判斷原來(lái)的知識(shí)和認(rèn)識(shí)的可靠性。 3預(yù)見功能：利用數(shù)學(xué)模型揭示事物的發(fā)展規(guī)律，為人們的行為提供指導(dǎo)或參考。,構(gòu)造法解題的思路或步驟可以歸納為：,構(gòu)造法解題的類型一般有：,1.數(shù)學(xué)建模：通過(guò)沿用經(jīng)典的數(shù)學(xué)思想建立起模型；或者提取現(xiàn)實(shí)世界中的有效信息，用簡(jiǎn)明的方式表達(dá)其規(guī)律，這種規(guī)律可以是一條代數(shù)公式、一幅幾何圖形、一個(gè)物理原理、一個(gè)化學(xué)方程式等等。 2.直接構(gòu)造問(wèn)題解答：這是構(gòu)造法運(yùn)用的一種簡(jiǎn)單類型。它只能針對(duì)問(wèn)題本身，探索其獨(dú)有性質(zhì)，不具備可推廣性。 無(wú)論是直接構(gòu)造問(wèn)題解答還是數(shù)學(xué)建模，都要通過(guò)算法來(lái)實(shí)現(xiàn)。,如何設(shè)計(jì)一個(gè)有較低編程復(fù)雜度和時(shí)空復(fù)雜度且結(jié)構(gòu)清晰的算法，十分重要。通常考慮的因素有： (1)選擇的模型必須盡量多地體現(xiàn)問(wèn)題的本質(zhì)特征。但這并不意味著模型越復(fù)雜越好、冗余的信息會(huì)影響算法的效率。 (2)模型的建立不是一個(gè)一蹴而就的過(guò)程，而是要經(jīng)過(guò)反復(fù)地檢驗(yàn)、修改，在實(shí)踐中不斷完善。 (3)數(shù)學(xué)模型通常有嚴(yán)格的格式，但程序編寫形式可不拘一格。,構(gòu)造與建模是一個(gè)復(fù)雜的抽象過(guò)程。我們要善于描視問(wèn)題的本質(zhì)，尋找突破口，進(jìn)而選擇適當(dāng)?shù)哪Ｐ汀?gòu)造的模型可以幫助我們認(rèn)識(shí)問(wèn)題，不同的模型從不同的角度反映問(wèn)題，可以引發(fā)不同的思路，起到發(fā)散思維的作用。,但認(rèn)識(shí)問(wèn)題的最終目的是解決問(wèn)題，模型的固有性質(zhì)可幫我們建立算法，其優(yōu)劣可以通過(guò)時(shí)空復(fù)雜度等指標(biāo)來(lái)衡量，但最終還是以程序的運(yùn)行結(jié)果為標(biāo)準(zhǔn)。 所以模型不是一成不變的，同樣要通過(guò)各種技術(shù)不斷優(yōu)化。模型的產(chǎn)生雖然是人腦思維的產(chǎn)物，但它仍然是客觀事物在人腦中的反映。所以要培養(yǎng)良好的建模能力，還必須依靠在平時(shí)的學(xué)習(xí)中積累豐富的知識(shí)和經(jīng)驗(yàn)。,對(duì)應(yīng)策略：將問(wèn)題a對(duì)應(yīng)另一個(gè)便于思考或有求解方法的問(wèn)題b，化繁為簡(jiǎn)，變未知為已知。 對(duì)應(yīng)經(jīng)典問(wèn)題 對(duì)應(yīng)簡(jiǎn)單問(wèn)題 對(duì)應(yīng)數(shù)學(xué)問(wèn)題,在建模過(guò)程中經(jīng)常使用的策略有,分治策略：將問(wèn)題的規(guī)模逐漸減少，可明顯降低解決問(wèn)題的復(fù)雜程度。算法設(shè)計(jì)的這種策略稱之為分治策略，即對(duì)問(wèn)題分而治之。 遞推的分治策略 遞歸的分治策略,歸納策略：歸納策略則是通過(guò)列舉試題本身的特殊情況，經(jīng)過(guò)深入分析，最后概括出事物內(nèi)在的一般規(guī)律，并得到一種高度抽象的解題模型。 遞推式 遞歸式 制定目標(biāo) 貪心方案,在自然界或日常生活中，許多現(xiàn)象具有不確定的性質(zhì)，很難建立數(shù)據(jù)模型，一般采用模擬策略 模擬策略：模擬某個(gè)過(guò)程，通過(guò)改變數(shù)學(xué)模型的各種參數(shù)，進(jìn)而觀察變更這些參數(shù)所引起過(guò)程狀態(tài)的變化，由此展開算法設(shè)計(jì)。模擬題沒(méi)有固定的模式，一般形式有兩種：,隨機(jī)模擬：題目給定或者隱含某一概率。設(shè)計(jì)者利用隨機(jī)函數(shù)和取整函數(shù)設(shè)定某一范圍的隨機(jī)值，將符合概率的隨機(jī)值作為參數(shù)。然后根據(jù)這一模擬的數(shù)學(xué)模型展開算法設(shè)計(jì)。由于解題過(guò)程借助了計(jì)算機(jī)的偽隨機(jī)數(shù)發(fā)生數(shù)，其隨機(jī)的意義要比實(shí)際問(wèn)題中真實(shí)的隨機(jī)變量稍差一些，因此模擬效果有不確定的因素；,過(guò)程模擬：題目不給出概率，要求編程者按照題意設(shè)計(jì)數(shù)學(xué)模型的各種參數(shù)，觀察變更這些參數(shù)所引起過(guò)程狀態(tài)的變化，由此展開算法設(shè)計(jì)。 模擬效果完全取決于過(guò)程模擬的真實(shí)性和算法的正確性，不含任何不確定因素。由于過(guò)程模擬的結(jié)果無(wú)二義性，因此競(jìng)賽大都采用過(guò)程模擬。 模擬的解題方法一般有三種類型 直敘式模擬 篩選法模擬 構(gòu)造法模擬,第一節(jié)、對(duì)應(yīng)策略,將問(wèn)題a對(duì)應(yīng)于另一個(gè)便于思考或已有求解方法的問(wèn)題 b ，化繁為簡(jiǎn)，變未知為已知。 對(duì)應(yīng)經(jīng)典問(wèn)題 對(duì)應(yīng)簡(jiǎn)單問(wèn)題 對(duì)應(yīng)數(shù)學(xué)問(wèn)題,一一對(duì)應(yīng)技術(shù)是一種重要的策略。它的核心是求同，通過(guò)舉一反三、觸類旁通地對(duì)已經(jīng)解決的類似問(wèn)題和有關(guān)事實(shí)作聯(lián)想，推導(dǎo)出事物間的聯(lián)系，從而全面、深入地認(rèn)識(shí)和分析事物。“世界上沒(méi)有完全不同的東西”，相似點(diǎn)的普遍存在為我們使用對(duì)應(yīng)策略解題提供了基礎(chǔ)。 但是對(duì)應(yīng)并不等于等價(jià)，兩個(gè)問(wèn)題間的表面相似并不等于本質(zhì)的聯(lián)系。對(duì)應(yīng)策略不僅要分析問(wèn)題間的共同點(diǎn)，還要分析問(wèn)題間的不同點(diǎn)，是一種異中求同的思維方法,一、對(duì)應(yīng)經(jīng)典問(wèn)題,經(jīng)典問(wèn)題及其算法的知識(shí)積累是解題的基礎(chǔ)，競(jìng)賽的許多試題最終都可以轉(zhuǎn)化為經(jīng)典問(wèn)題，因此必須盡可能多地掌握經(jīng)典問(wèn)題及其算法的知識(shí)。解題時(shí)，心中經(jīng)?；貞浺呀?jīng)解決的經(jīng)典問(wèn)題和有關(guān)解法，往往會(huì)收到意想不到的效果。 當(dāng)然這些試題并不直接以經(jīng)典問(wèn)題的原貌出現(xiàn)。我們必須合理運(yùn)用求同思維、求異思維比較兩者間的相同點(diǎn)和不同點(diǎn)，通過(guò)適當(dāng)?shù)姆椒▽⒃囶}轉(zhuǎn)化為經(jīng)典問(wèn)題。,【例1】計(jì)算最少的公路造價(jià) 現(xiàn)有 n 個(gè)城市間的交通網(wǎng)，邊上的權(quán)是公路造價(jià)，任一對(duì)城市都是可以連通的。現(xiàn)在要用公路把 n 個(gè)城市連接起來(lái)，這至少需要修筑n-1條公路。如何設(shè)計(jì)可使得這 n 條公路的總造價(jià)最少。 輸入：頂點(diǎn)數(shù) n 和邊數(shù) e ; 以下有 e 行，每行包括一條邊的兩個(gè)頂點(diǎn)。 輸出： n - 1 行，每行為連接一條公路的兩個(gè)城市序號(hào)。,分析：我們以城市為頂點(diǎn)，公路為邊，公路的造價(jià)為邊權(quán)，構(gòu)造一張具有 n 個(gè)頂點(diǎn)的帶權(quán)連通圖，這張連通圖的生成樹有 n - 1 條邊。 問(wèn)題對(duì)應(yīng)為：如何在所有可能的生成樹中，尋找各邊的權(quán)的總和為最小的一棵生成樹。顯然，這個(gè)問(wèn)題就是經(jīng)典的最小生成樹問(wèn)題。,下圖為 6 個(gè)城市間的交通網(wǎng)，邊上的權(quán)是公路造價(jià)。修筑 5 條公路的方案如下:,Prim算法 設(shè)G=(V,E)是連通帶權(quán)圖V=0,1,n-1，用鄰接矩陣cij表示圖G中頂點(diǎn)i和頂點(diǎn)j之間的鄰接關(guān)系及邊的權(quán)，若i,j不相連，則cij置為最大值99。 構(gòu)造G的最小生成樹的Prim算法的基本思想是：首先置S=0,只要S是V的真子集，就作如下的貪心選擇：選取滿足條件iS，jV-S，且cij最小的邊，將頂點(diǎn)j添加到S中。這個(gè)過(guò)程一直進(jìn)行到S=V時(shí)為止。 過(guò)程中選取到的所有邊恰好構(gòu)成G的一棵最小生成樹。,帶權(quán)圖，按Prim算法選取邊的過(guò)程,在上述Prim算法中，還應(yīng)當(dāng)考慮如何有效地找出滿足條件iS,jV-S，且權(quán)cij最小的邊(i,j)。實(shí)現(xiàn)這個(gè)目的的較簡(jiǎn)單的辦法是設(shè)置兩個(gè)數(shù)組closest和lowcost。 在Prim算法執(zhí)行過(guò)程中，先找出V-S中使lowcost值最小的頂點(diǎn)j，然后根據(jù)數(shù)組closest選取邊(j,closestj)，最后將j添加到S中，并對(duì)closest和lowcost作必要的修改。 用這個(gè)辦法實(shí)現(xiàn)的Prim算法所需的計(jì)算時(shí)間為W(n2),#include using namespace std; const int MAXINT=1000; const int INF=99; const int N=6; void main() int cNN= 99,10,99,99,19,21, 10,99, 5, 6,99,11, 99, 5,99, 6,99,99, 99, 6, 6,99,18,14, 19,99,99,18,99,33, 21,11,99,14,33,99; Prim(c); ,void Prim(int cNN) int lowcostMAXINT; /存放當(dāng)前結(jié)點(diǎn)相連的權(quán)值 int closestMAXINT; /存放最近結(jié)節(jié) bool sMAXINT; s0=true; /放入起始結(jié)點(diǎn) for(int i=1;iN;i+) lowcosti=c0i;closesti=0;si=false; for(i=1;iN;i+) int min=INF; int j=0; for(int k=0;kN;k+) if(lowcostkmin) ,Kruskal算法,Kruskal算法構(gòu)造G的最小生成樹的基本思想是，首先將G的n個(gè)頂點(diǎn)看成n個(gè)孤立的連通分支。將所有的邊按權(quán)從小到大排序。然后從第一條邊開始，依邊權(quán)遞增的順序查看每一條邊，并按下述方法連接2個(gè)不同的連通分支：當(dāng)查看到第k條邊(v,w)時(shí)，如果端點(diǎn)v和w分別是當(dāng)前2個(gè)不同的連通分支T1和T2中的頂點(diǎn)時(shí)，就用邊(v,w)將T1和T2連接成一個(gè)連通分支，然后繼續(xù)查看第k+1條邊；如果端點(diǎn)v和w在當(dāng)前的同一個(gè)連通分支中，就直接再查看第k+1條邊。這個(gè)過(guò)程一直進(jìn)行到只剩下一個(gè)連通分支時(shí)為止。,對(duì)前面的連通帶權(quán)圖，按Kruskal算法順序得到的最小生成樹上的邊如下圖所示。,【 例 2 】挖地雷 在一個(gè)地圖上有n個(gè)地窖(n=20),每個(gè)地窖中埋有一定數(shù)量的地雷，同時(shí)，給出地窖之間的聯(lián)系路徑。 當(dāng)?shù)亟鸭捌溥B接的數(shù)據(jù)給出之后，某人可以從任一處開始挖地雷，然后可以沿著連接路徑往下挖（僅能選擇一條路徑），挖的過(guò)程中允許某人重復(fù)經(jīng)過(guò)地窖。當(dāng)無(wú)連接時(shí)，挖地雷工作結(jié)束。設(shè)計(jì)一個(gè)挖地雷的方案，使某人能挖到最多的地雷。,輸入格式： n (表示地窖的個(gè)數(shù)) w1,w2,w3,wn a(1,2)a(1,n) a(2,3)a(2,n) a(n-1,n) 表示地窖之間連接路徑(其中aij表示地窖 i 和地窖 j 之間是否有通路：如果通,則 aij=1,不通 aij=0) 輸出格式： r1-r2 rk (挖地雷的順序) max (為挖地雷的數(shù)量),例如： V1，V2， V3， V6表示地窖。 下圖給出了一個(gè)示例：,分析：我們將地窖設(shè)為頂點(diǎn)，地窖之間的通路設(shè)為邊，每個(gè)地窖中的地雷數(shù)設(shè)為頂點(diǎn)的權(quán)，使得問(wèn)題對(duì)應(yīng)一個(gè)頂點(diǎn)帶權(quán)的無(wú)向圖，解題的目的是要在這張圖中尋找一條路徑，該條路徑途經(jīng)的地窖所含的地雷數(shù)最多。但是，是否允許某人重復(fù)經(jīng)過(guò)地窖是問(wèn)題的關(guān)鍵。,如果不允許某人重復(fù)經(jīng)過(guò)地窖，則最佳路徑為 1-2-3 ，挖到的地雷數(shù)為 13 ；如果允許某人重復(fù)經(jīng)過(guò)地窖，則最佳路徑為 1 -2 -3 -2 -4 ，挖到的地雷數(shù)為 14 。,不允許重復(fù)的求解方法帶有明顯的階段特征，允許重復(fù)則不具備階段特征。允許重復(fù)與不允許重復(fù)對(duì)應(yīng)兩種不同的解決方法。 允許某人重復(fù)經(jīng)過(guò)地窖實(shí)際上是允許挖地雷的順序中出現(xiàn)回路。無(wú)論該人怎樣挖，其經(jīng)過(guò)的路徑必然在一個(gè)連通子圖中。我們采用計(jì)算無(wú)向圖傳遞閉包的方法找出所有的連通子圖，并計(jì)算出其中頂點(diǎn)權(quán)（即地雷數(shù)）和最大的一個(gè)連通子圖。最后，從該連通子圖的任一個(gè)頂點(diǎn)出發(fā)，通過(guò)深度優(yōu)先搜索輸出挖地雷的順序。,【例3】 換車問(wèn)題,一個(gè)城市有 n 個(gè)車站，已知 m 條連接這些車站的公共汽車單向路線。求站1至站n的最少換車數(shù)。 輸入: n m 以下 m 行依次列出每條線路的車站序號(hào)。 輸出：最少換車次數(shù)。,分析：這個(gè)問(wèn)題對(duì)我們來(lái)講并不陌生。如果將問(wèn)題要求改為“求站 1 到站 n 最少經(jīng)過(guò)多少站”，就變?yōu)槲覀兿喈?dāng)熟悉的最短路徑的典型應(yīng)用。 即令有向圖G=,|V|=n,若vi, vj屬于E當(dāng)且僅當(dāng)i站,j站在某條線路上相鄰,(Vi ，Vj)的權(quán)Wij設(shè)為1。顯然，汽車線路經(jīng)過(guò)的站數(shù)=路徑頂點(diǎn)數(shù)=路徑邊數(shù)+1=路徑的權(quán)和+1。為使總站數(shù)最少，只要使路徑的權(quán)和最小，即只要求出圖G中Vi至Vj間的最短路徑即可。,但現(xiàn)在的問(wèn)題是求最少換車次數(shù)，雖然它與求經(jīng)過(guò)最少站數(shù)總是有共同背景，但要求不同。我們化異為同，重新對(duì)原圖G作了修正。若 Vi,Vj屬于E當(dāng)且僅當(dāng)站 i 與站 j 依次在同一條公共汽車線路上(Vi可直達(dá)Vj)，Wij仍為1。然后運(yùn)用求最短路徑方法計(jì)算V1 至Vn的最短路徑長(zhǎng)度，其長(zhǎng)度減1即為最少換車次數(shù)。,由上可見，對(duì)應(yīng)策略使用得如何，既與其掌握經(jīng)典算法的多少和理解的透徹程度有關(guān)，也與其應(yīng)用經(jīng)典算法于實(shí)踐的能力有關(guān)，更與其拓展經(jīng)典算法應(yīng)用范圍的創(chuàng)造力息息相關(guān)。,二、對(duì)應(yīng)簡(jiǎn)單問(wèn)題,有些試題的求解方法原本很簡(jiǎn)單，但由于其表現(xiàn)形式陌生，因此乍看感到棘手。但只要你果斷地抓住主要矛盾，舍棄與目標(biāo)無(wú)關(guān)的次要信息，去粗取精，去偽存真，由此及彼，由表及里，便可以返樸歸真，將試題與一個(gè)簡(jiǎn)單的問(wèn)題對(duì)應(yīng)起來(lái),【例5】密碼鎖 (lock),憑借你多年的開鎖經(jīng)驗(yàn)，你馬上斷定眼前這扇門用的是密碼鎖。只見鎖身上有 n 行數(shù)字，在每行數(shù)字末尾都有好幾個(gè)數(shù)字撥盤?？粗@一行行多少不一的數(shù)字和數(shù)字末尾留下的空格，你忽然想起了小時(shí)候經(jīng)常玩的一個(gè)游戲：找規(guī)律。這個(gè)游戲就是給你一個(gè)數(shù)列的前幾項(xiàng)，讓你填出后一項(xiàng)，例如： 2 4 6 ( 8 ) 1 4 9 ( 16 ),在玩游戲的過(guò)程中，你發(fā)現(xiàn)了一個(gè)竅門，所有這類問(wèn)題，都可以用這種方法解決： 對(duì)于一個(gè)已知前 m 項(xiàng)的數(shù)列 a1 , a2 , a3 ， ，am，一定可以找到惟一一個(gè)不超過(guò)m-1次的多項(xiàng)式f(x)，使得 f(1) = a1 , f (2) = a2 f (m)=am ，那么 f(m+1)就是要找的下一項(xiàng)。 現(xiàn)在你決定用這種方法試著打開眼前這把密碼鎖。,輸入：第一行是一個(gè)整數(shù) n,代表門上共有n行數(shù)字,n=100。 以下 n 行，每行對(duì)應(yīng)門上的一行數(shù)字，每行的數(shù)字不超過(guò) 1000 個(gè)。 輸入的數(shù)字之間用空格隔開，每行末尾沒(méi)有多余的空格。 輸入的數(shù)字都是絕對(duì)值小于108的整數(shù)。 輸出：輸出應(yīng)該包括 n 行，每一行是根據(jù)輸入數(shù)據(jù)的規(guī)律推出的下一個(gè)數(shù)字，順序與輸入數(shù)據(jù)相對(duì)應(yīng)。結(jié)果的絕對(duì)值都小于 108 。,分析： (1)構(gòu)造數(shù)列的通項(xiàng)公式: 這是最直接的方法。 對(duì)于已知m項(xiàng)的數(shù)列,構(gòu)造出的通項(xiàng)公式共有m項(xiàng),當(dāng)i=m時(shí),有且僅有一項(xiàng)不為零，而且等于 ai .例如數(shù)列前 3 項(xiàng)為1,3,5, 通項(xiàng)公式為：,這種方法的缺點(diǎn)是運(yùn)算過(guò)程中數(shù)的規(guī)模比較大，如果用高精度計(jì)算，時(shí)空效率可能無(wú)法接受。如果不用高精度，恐怕得不到準(zhǔn)確解。,(2)求數(shù)列的 r 階差數(shù)列 定理：如果一個(gè)數(shù)列的通項(xiàng)公式是關(guān)于自然數(shù) n 的 r 次多項(xiàng)式，那么這個(gè)數(shù)列是r階等差數(shù)列。 這個(gè)定理的證明很簡(jiǎn)單，只要反復(fù)進(jìn)行以g(n)=f(n)-f(n-1)的運(yùn)算，求數(shù)列的差數(shù)列，就會(huì)發(fā)現(xiàn)通項(xiàng)公式的次數(shù)每迭帶一次都會(huì)降低一次，最終原數(shù)列的 r 階差數(shù)列就是一個(gè)常數(shù)列。也就是說(shuō)原數(shù)列是一個(gè) r 階等差數(shù)列。,在這道題里，已知這個(gè)數(shù)列的通項(xiàng)公式有m-1 項(xiàng)，那么這個(gè)數(shù)列就是一個(gè)m-1階的等差數(shù)列.于是就可以借助等差數(shù)列求出數(shù)列的第m+1項(xiàng)，例如表所示的數(shù)列 1 , 4 , 9 方法二比較簡(jiǎn)捷，要計(jì)算的數(shù)據(jù)不是很大，而且計(jì)算量較小。算法的時(shí)間復(fù)雜度為w(m2/2), m*(m+1)/2 由于計(jì)算過(guò)程中有許多數(shù)據(jù)不需要保存，所以空間需求是w(1)。,long r_cal(long num,int m) long result=0; /存放結(jié)果 for(int j=m-1;j0;j-) /計(jì)算m-1階等差數(shù)列的等差值 for(int k=0;k=j-1;k+) numk=numk+1-numk; for(j=0;jm;j+) result=result+numj; /計(jì)算第j行的最后一項(xiàng) return result; ,【例6】 空中都市,在一個(gè)未來(lái)的空中都市中,有很多個(gè)小島(城區(qū))。現(xiàn)在要求在這些島之間架一些橋梁(橋是架在兩個(gè)島之間的)。 要求：首先，如果A與B之間有橋，B與C之間有橋，則A與C之間就不能再架橋了，即對(duì)于城市中的任意三個(gè)島，不能在其中兩兩都架上橋。 在這樣的前提下，要求架的橋數(shù)最多(不考慮具體的空間結(jié)構(gòu)問(wèn)題)，并計(jì)算其中的一個(gè)可行方案。,輸入文件只包含一行，該行為一個(gè)非負(fù)整數(shù)n( 0=n=1000 ) ，即城市中有n個(gè)小島。 輸出文件：橋數(shù)的最大值 k，以下為 k 行，每行為一座橋相鄰的兩個(gè)小島序號(hào)(a , b) 輸入示例： 6 輸出示例： 9 (1,4) (1,5) (1,6) (2,4) (2,5) (2,6) (3,4) (3,5) (3,6),分析：按照題意，如果小島A與小島B之間、小島B與小島C之間和小島A 與小島C 之間都有橋的話，則說(shuō)明A, B, C三個(gè)小島之間存在傳遞性。試題要求構(gòu)造一個(gè)含n個(gè)頂點(diǎn)且滿足下述條件的圖： (1)任三個(gè)頂點(diǎn)間不含傳遞性； (2)圖中所含邊數(shù)最多。,我們通過(guò)下述方法將空中都市問(wèn)題對(duì)應(yīng)一個(gè)簡(jiǎn)單問(wèn)題：把n個(gè)小島分為盡量平均的兩部分，第一組為n/2或(n-1)/2個(gè)頂點(diǎn)，第二組為n/2 或(n + 1)/2 個(gè)頂點(diǎn)。然后第一組的每一個(gè)頂點(diǎn)分別向第二組的所有頂點(diǎn)引出，如圖所示：,由此得出橋的數(shù)目是：,下面，我們來(lái)證明這個(gè)構(gòu)造方法的正確性。 由于兩組的任一對(duì)頂點(diǎn)之間都有邊相連，因此如果再架橋的話，只能在同組的一對(duì)頂點(diǎn)之間進(jìn)行。如果在某一組的頂點(diǎn) i 和頂點(diǎn) j 間架橋，則由于頂點(diǎn) i 和頂點(diǎn) j 與另一組的任一個(gè)頂點(diǎn) k 相連，使得頂點(diǎn) i 、頂點(diǎn) j 和頂點(diǎn) k 之間存在傳遞關(guān)系，這是不允許的。而一個(gè)數(shù)拆分成兩個(gè)數(shù)的積，兩個(gè)數(shù)的值愈接近，積愈大。由此可見，按照上述方法得出的圖所含邊數(shù)最多。,#include using namespace std; int main() int n; /n為島數(shù) cinn; if (n%2=0) coutn*n/4endl; else cout(n-1)*(n+1)/4endl; for(int i=1;i=n/2;i+) /枚舉第一組島嶼 for(int j=n/2+1;j=n;j+) /枚舉第二組島嶼 cout(i,j)endl; /輸出方案 return 0; ,三、對(duì)應(yīng)數(shù)學(xué)問(wèn)題 運(yùn)用己學(xué)到的數(shù)學(xué)知識(shí)，對(duì)試題給出的各個(gè)對(duì)象及其關(guān)系進(jìn)行分析、演繹、歸納，從而建立一個(gè)清晰簡(jiǎn)練的解析式，使得試題與某個(gè)數(shù)學(xué)問(wèn)題對(duì)應(yīng)。當(dāng)然，這個(gè)數(shù)學(xué)問(wèn)題的計(jì)算量非人工演算所能及，必須譯成算法語(yǔ)言，通過(guò)計(jì)算機(jī)運(yùn)算方可完成。對(duì)應(yīng)數(shù)學(xué)問(wèn)題的方式有兩種： (1) 機(jī)理分析法 (2) 統(tǒng)計(jì)分析法,1機(jī)理分析法 根據(jù)客觀事物的特性，分析其內(nèi)部的機(jī)理，弄清關(guān)系，在適當(dāng)抽象的條件下，得到可以描述事物屬性的數(shù)學(xué)工具。我們?cè)诼?lián)賽中可以用這種方法建立數(shù)學(xué)模型，然后根據(jù)所對(duì)應(yīng)的算法求出解。 通過(guò)抽象建模得出對(duì)應(yīng)信息原型的數(shù)學(xué)模型；然后將數(shù)學(xué)模型理論對(duì)應(yīng)到算法，并編程實(shí)現(xiàn)；最后通過(guò)算法的執(zhí)行得到問(wèn)題的解。,【例7】國(guó)際象棋（ knight ),國(guó)際象棋是我們休息娛樂(lè)時(shí)常玩的游戲。在各個(gè)棋子中，馬的行進(jìn)方式最為特殊，也為人們所津津樂(lè)道。我們都知道：馬走的是“日”字，也就是說(shuō)每次都是向水平或豎直方向移動(dòng)1格，而向另一個(gè)方向移動(dòng)2格，所以也可稱作是 1x2 的馬（走法如圖所示）。在圖中我們看到一個(gè)馬有 8 種跳的方向。,小明是一個(gè)數(shù)學(xué)愛(ài)好者，他將馬的走法重新定義了一下，重新定義后的廣義馬成為 nxm 的馬。為了研究廣義馬，小明讓馬從(0 , 0 )出發(fā)，隨意地在一張足夠大的棋盤上移動(dòng)。他發(fā)現(xiàn)，有時(shí)候廣義馬總是無(wú)法跳入某些格子中，比如 2x2 的馬永遠(yuǎn)不可能跳到(1, 1)，這令他非常感興趣。他希望知道對(duì)于給定的 n , m , nx m的廣義馬是否能夠跳到所有的格子。由于 n , m 可以非常大，這令小明花了許多功夫在嘗試上，但仍不能得出肯定的結(jié)論。于是他就來(lái)找你這個(gè)計(jì)算機(jī)專家?guī)兔α恕?輸入：在輸入文件knight.in 中包含了多組測(cè)試數(shù)據(jù)，每組測(cè)試數(shù)據(jù)占一行。每組測(cè)試數(shù)據(jù)由 2 個(gè)數(shù) n , m (1 = n =108 , 1 =m =108）組成，表示廣義馬的類型。文件最后一行由2個(gè)0 表示文件結(jié)束。 輸出：將答案輸出到文件 knight.out 中，每組測(cè)試數(shù)據(jù)占一行。如果馬能跳到指定的位置輸出 YES ，否則輸出 Impossible 。 分析：通常，馬的遍歷問(wèn)題都是用搜索解決的。但本題中有一些特殊的地方：棋盤是無(wú)窮大的，馬也是廣義的。另外，更重要的是問(wèn)題規(guī)模相當(dāng)大(1=n =108 , 1 =m =108) ，所以需要深入地研究這個(gè)問(wèn)題。由于計(jì)算哪些類型的馬可以遍歷整個(gè)棋盤似乎有些困難，于是我們就先來(lái)研究對(duì)于給定的廣義馬，存在哪些到不了的特殊位置。,首先從最簡(jiǎn)單的 1Xn 的廣義馬開始分析： (1)當(dāng) n 為奇數(shù)時(shí)，將棋盤染成黑白相間。若(0 , 0)為白色，因?yàn)槊刻徊?，馬在豎直和水平方向前進(jìn)的步數(shù)之和(1+n)為偶數(shù)。所以自(0 , 0)出發(fā)的馬始終在白格子上跳躍，黑色的格子是馬永遠(yuǎn)到不了的。,(2)當(dāng) n 為偶數(shù)時(shí)，我們有這樣的移動(dòng)方案(如圖 ( b )所示)，使得馬從(0 , 0)開始經(jīng)過(guò)一系列的跳步后，到(1 , 0 )的位置，也就是說(shuō)可以讓馬到達(dá)相鄰的格子，所以馬可以遍歷整個(gè)棋盤。,下面我們分析一般的廣義馬。我們能否將 nxm 的廣義馬對(duì)應(yīng) 1xn 的廣義馬呢？分析三種情況： 第 1 種情況：若n,m 有最大公約數(shù) p ( p 1 ) ，則馬只能跳到形似(pxs , pxt)的格子上，其他的格子都到不了。 第 2 種情況：若 n+m 是偶數(shù)，類似于 1xn 馬的情況，馬只能在同色的格子內(nèi)跳動(dòng)，不能遍歷棋盤。,第3種情況：若 n +m 為奇數(shù)，且 n , m 互質(zhì)。不妨設(shè) n 為奇數(shù)，那么 m 為偶數(shù)。因?yàn)?1xn 馬的問(wèn)題已經(jīng)被徹底解決，所以很自然的想將 nxm 經(jīng)過(guò)一系列變換轉(zhuǎn)化成 1xn 馬的問(wèn)題。我們可以看到馬的跳法本質(zhì)上是 4 種（另 4 種可以看成是以下 4 種跳法反跳一步） : （ m , n ） （ m ，-n） （ n , m ） （ n ，-m） 馬經(jīng)過(guò)跳 p 次 ,q 次 ,r次 ，s次 后 水平方向的位移為(p+q ) m +(r+s) n 豎直方向的位移為(p-q)n + (r-s) m 為了利用 1xn 馬的結(jié)論，解不定方程 (p+q) m + (r+s)n=1 因?yàn)閚, m 互質(zhì)。該方程一定有解(p0, q0, r0, s0).,因?yàn)閙 是偶數(shù)， n 是奇數(shù)，所以( r0 + s0)是奇數(shù)。 因?yàn)轳R要遍歷整個(gè)棋盤，其豎直和水平方向前進(jìn)的步數(shù)之和 (p0+q0)m+(r0+s0)n+(p0-q0)n+(r0-s0)m 為奇數(shù)， 所以( p0-q0）是偶數(shù)。(p0-q0 ) n + ( r0-s0) m是偶數(shù)。 也就是馬通過(guò)一系列的跳動(dòng)所得到的效果相當(dāng)于 1xlen 的馬跳一步的效果（ len =(p0-q0 ) n + ( r0-s0 ) m）。根據(jù)前面的結(jié)論， 1 xlen 的馬可以遍歷整個(gè)棋盤，所以當(dāng) n+m 為奇數(shù)且 n , m 互質(zhì)時(shí)， nxm 的馬可以遍歷整個(gè)棋盤。 算法的時(shí)間復(fù)雜度為W（ 1 ) ，空間需求為W（ 1 ）。,#include long gcd(long a,long b) /計(jì)算n和m的最大公約數(shù) if (b=0) return a; else return gcd(b,a%b); void main() long n,m; /n，m為廣義馬的類型 cinnm; /若n+m為偶數(shù)，無(wú)解 if (n+m)%2=0) coutm long temp; temp=n; m=n; n=temp; /若n,m互質(zhì)，輸出成功，否則失敗 if (gcd(n,m)=1) cout“YES“; else cout“Impossible“; ,1657【例8】棋盤上的距離,國(guó)際象棋的棋盤是黑白相間的8 * 8的方格，棋子放在格子中間。如下圖所示：,1 2 3 4 5 6 7 8,h g f e d c b a,王、后、車、象的走子規(guī)則如下： 王：橫、直、斜都可以走，但每步限走一格。 后：橫、直、斜都可以走，每步格數(shù)不受限制。 車：橫、豎均可以走，不能斜走，格數(shù)不限。 象：只能斜走，格數(shù)不限。 寫一個(gè)程序，給定起始位置和目標(biāo)位置，計(jì)算王、后、車、象從起始位置走到目標(biāo)位置所需的最少步數(shù),Input 第一行是測(cè)試數(shù)據(jù)的組數(shù)t（0 = t = 20）。以下每行是一組測(cè)試數(shù)據(jù)，每組包括棋盤上的兩個(gè)位置，第一個(gè)是起始位置，第二個(gè)是目標(biāo)位置。位置用“字母-數(shù)字“的形式表示，字母從“a“到“h“，數(shù)字從“1“到“8“。 Output 對(duì)輸入的每組測(cè)試數(shù)據(jù)，輸出王、后、車、象所需的最少步數(shù)。如果無(wú)法到達(dá),就輸出“Inf“. Sample Input 2 a1 c3 f5 f8 Sample Output 2 1 2 1 3 1 1 Inf,解題思路,首先，王、后、車、象彼此獨(dú)立，應(yīng)分別考慮。 我們假設(shè)起始位置與終止位置在水平方向上的距離是x，在豎直方向上的距離是y 王：所需要最小步數(shù)是min(x,y)+abs(x-y) 后：1步：當(dāng)x=y或x=0或y=0 2步：當(dāng)x!y 車：1步：當(dāng)x=0或y=0 2步：x!=0且y!=0 象：只能斜走，因此橫縱坐標(biāo)增減的數(shù)值相等，所以橫縱坐標(biāo)之間的奇偶性無(wú)論如何都保持不變。橫縱坐標(biāo)之差為奇數(shù)的點(diǎn)和為偶數(shù)的點(diǎn)不能相互到達(dá)。當(dāng)它們屬于同一類點(diǎn)時(shí)， 1步，當(dāng)xy時(shí) 2步，當(dāng)x！y時(shí),#include #include using namespace std; int main() int n,i; cinn; /n是測(cè)試數(shù)據(jù)組數(shù) for(i=0;ibeginend; int x=abs(begin0-end0); int y=abs(begin1-end1); if (x=0 ,2統(tǒng)計(jì)分析法,我們?cè)谝粫r(shí)得不到事物的特征機(jī)理的情況下，可通過(guò)某種方法測(cè)試得到一些數(shù)據(jù)（即問(wèn)題的部分解），再利用數(shù)理統(tǒng)計(jì)知識(shí)對(duì)數(shù)據(jù)進(jìn)行處理，從而得到最終的數(shù)學(xué)模型。統(tǒng)計(jì)分析法是相對(duì)于機(jī)理分析法的逆向思維。這種方法在實(shí)驗(yàn)性學(xué)科中應(yīng)用十分廣泛。例如在研究f(x)= sinx 的圖像時(shí)，我們先取一些特殊點(diǎn)，再根據(jù)其大致走向作出函數(shù)圖像。在聯(lián)賽中，我們亦可以用手工或簡(jiǎn)單的程序求出問(wèn)題的部分解，然后分析出其中的規(guī)律，得到數(shù)學(xué)模型。,先從信息原型出發(fā)，通過(guò)手工或簡(jiǎn)單的程序得到問(wèn)題的部分解。然后通過(guò)對(duì)部分解的分析，運(yùn)用數(shù)理統(tǒng)計(jì)得到信息原型的主要屬性(這里的屬性大部分是某些規(guī)律),從而建立數(shù)學(xué)模型，然后通過(guò)算法得出問(wèn)題的全部解。,【 例9 】 極值問(wèn)題,m , n 為整數(shù)，且滿足下列兩個(gè)條件： m ,n屬于 1,2,3, , k (1=k=109 ); (n2-mn-m2)2=1. 由鍵盤輸入 k ，求一組滿足上述兩個(gè)條件的 m , n 并且使 m2+ n2 的值最大。 分析：本題是一道數(shù)學(xué)性很強(qiáng)的試題。信息原型本身就具有很強(qiáng)的抽象性。如果一開始就在抽象中分析，是很難理清思路的。面對(duì)(n2-mn-m2)2=1這本來(lái)就十分抽象的關(guān)系式，由于缺乏繼續(xù)抽象的線索，自然也就無(wú)法通過(guò)機(jī)理分析法得到對(duì)應(yīng)的數(shù)學(xué)模型。這時(shí)統(tǒng)計(jì)分析法就有了用武之地,首先，通過(guò)手工測(cè)試，我們得出了如表所示的一些小的數(shù)據(jù)結(jié)果： 當(dāng)m=1時(shí), 可求出n=2; 當(dāng)m=2時(shí), 可求出n=3; 當(dāng)m=3時(shí), 可求出n=5; 當(dāng)m=4時(shí), n無(wú)整數(shù)解; 當(dāng)m=5時(shí), 可求出n=8; 我們將整理出的m,n排列在一起，有1 2 3 5 8,令人驚奇的是： n , m 隨著 k 的增長(zhǎng)以斐波納契數(shù)列形式增長(zhǎng)！我們于是猜測(cè)：?jiǎn)栴}的解就是小于等于 k 的最大的相臨兩個(gè)斐波納契數(shù)。有了問(wèn)題的研究方向，我們就朝這個(gè)方向去設(shè)法證明自己的猜想。,如果我們的猜想正確，那么當(dāng)(m，n)是方程(n2-mn-m2)2=1的一組解時(shí)，根據(jù)斐波納契數(shù)列關(guān)系， ( n,n+m)也一定是方程的一組解。 即(n+m)2-(n+m)n-n2)2=1 則： (n2+2mn+m2-n2-mn-n2)2=1 (mn+m2 -n2)2=1 若(n2-mn-m2)2=1 成立，則：以上各步可逆，所以當(dāng)(n,m)是方程的一組解時(shí)，(n,n+m)一定是方程的另一組解。,#include using namespace std; int main() /m,n,next是斐波納契數(shù)列的頭三項(xiàng) long m=1,n=1,next=2,k=0; /讀入一個(gè)范圍中的K while(k1000000000) cink; while(next=k) /找出m,n的最大值 m=n; n=next; next=m+n; coutm n; return 0; ,【例10】取石子問(wèn)題,有兩堆石子，數(shù)量可能不同。有兩個(gè)人輪流取。每次有兩種不同的取法。一是在任意一堆中取走任意多的石子;二是在兩堆中同時(shí)取走相同數(shù)量的石子。最后把石子全部取完的是勝者?，F(xiàn)在給出初始的兩堆石子的數(shù)目，如果輪到你來(lái)取，又假設(shè)雙方都采取最好的策略，問(wèn)最后你是勝者還是敗者。,輸入文件只有一行，包含兩個(gè)非負(fù)整數(shù) a 和 b ，表示兩堆石子的數(shù)目。(a=109 ,b=109 )。 輸出文件也只有一行，包含一個(gè)數(shù)字。如果最后你是勝者，則輸出 1 。反之，則輸出0。 輸入示例： 6 10 輸出示例： 0,分析：我們無(wú)法直接從兩堆石子的取法中找到規(guī)律。在這種情況下，只能在測(cè)試得到的部分解答中尋找出路。 (1)分析失敗的情況 測(cè)試結(jié)果有兩種可能 ： 失敗的情況： ( 1 , 2 ) ( 3 , 5 ) ( 4 , 7 ) ( 6 , 10 ) ( 8 , 13 ) ( 9 , 15 ) ( 11 , 18 ) ( 12 , 20 ) ( 14 , 23 ) ( 16 , 26 ) ( 17 , 28 ) ( 19 , 31 ) ( 21 , 34 ） 勝利的情況： ( 1, 1 ) ( 1 , 3 ) ( 1 , 4 ) 。勝利的情況比失敗的情況多得多。,在上述兩種情況，我們選擇相對(duì)容易得出的失敗情況展開分析，尋找規(guī)律。 從 1 開始的每一個(gè)數(shù)字，在這些數(shù)字對(duì)中都會(huì)出現(xiàn)一次且僅會(huì)出現(xiàn)一次； 數(shù)對(duì)的差成等差數(shù)列 1 , 2 , 3 , 4 有些數(shù)對(duì)的數(shù)字排列(例如( 1 , 2 ) ( 3 , 5 ) ( 8 , 13 ) )來(lái)自斐波納契數(shù)列(例如 1 , 2 , 3 , 5 , 8 , 13 , 21 ) ; 有些數(shù)對(duì)(例如( 4 , 7 )和( 11 , 18 ) )，雖然不是標(biāo)準(zhǔn)斐波納契數(shù)列中的數(shù)字，但還是符合斐波納契數(shù)列的規(guī)則的；, 如果數(shù)對(duì)(a,b)出現(xiàn)在其中，則(a+b,a+2b)也必然出現(xiàn)在數(shù)對(duì)中(相反的結(jié)論是不對(duì)的) ; 數(shù)對(duì)中兩個(gè)數(shù)之比都非常接近于0.618 ，即著名的黃金分割數(shù)。 (2)判別 a , b 的輸贏 由于從 1 開始的每一個(gè)自然數(shù)，按照斐波納契數(shù)列的規(guī)則不重復(fù)地出現(xiàn)在失敗的數(shù)對(duì)中，因此，可以得出如下結(jié)論：,若數(shù)對(duì)按照遞增順序排列成( a , b )，且滿足 則確定 ( a , b ）失敗。由此得出算法：,#include Void main() long x,y,temp; cinxy; /按照遞增順序排列 x 和 y if (xy) temp=x;x=y;y=temp; /若 x 和 y 接近黃金分割數(shù)，則失??；否則勝利 if (x=y/1.618) cout0; else cout1; ,本節(jié)作業(yè),簡(jiǎn)要回答如下問(wèn)題： 1.什么是構(gòu)造法？設(shè)計(jì)構(gòu)造法模型通常要考慮哪些因素？ 2.在構(gòu)造法建模過(guò)程中經(jīng)常使用的策略有哪些？ 3.對(duì)應(yīng)策略通常分為哪幾種類型？ 4.對(duì)應(yīng)數(shù)學(xué)問(wèn)題有幾種方式，其基本思想分別是什么？,寫出算法思想,例1 例5 例6 例8 例9,第二節(jié)、分治策略,將問(wèn)題的規(guī)模逐漸減少，可明顯降低解決問(wèn)題的復(fù)雜程度。算法設(shè)計(jì)的這種策略稱之為分治策略，即對(duì)問(wèn)題分而治之。用分治策略求解一個(gè)問(wèn)題，所需的時(shí)間是由子問(wèn)題的個(gè)數(shù)、大小以及把這個(gè)問(wèn)題分解為子問(wèn)題所需的工作總量來(lái)確定。一般來(lái)說(shuō)，把任意大小的問(wèn)題盡可能地等分成兩個(gè)子問(wèn)題較為有效。競(jìng)賽中常用的分治策略有： ( 1 ）遞推的分治策略 ( 2 ）遞歸的分治策略,一、分治算法總體思想,將要求解的較大規(guī)模的問(wèn)題分割成k個(gè)更小規(guī)模的子問(wèn)題。,對(duì)這k個(gè)子問(wèn)題分別求解。如果子問(wèn)題的規(guī)模仍然不夠小，則再劃分為k個(gè)子問(wèn)題，如此遞歸的進(jìn)行下去，直到問(wèn)題規(guī)模足夠小，很容易求出其解為止。 將求出的小規(guī)模的問(wèn)題的解合并為一個(gè)更大規(guī)模的問(wèn)題的解，自底向上逐步求出原來(lái)問(wèn)題的解。,因此：分治法的設(shè)計(jì)思想是，將一個(gè)難以直接解決的大問(wèn)題，分割成一些規(guī)模較小的相同問(wèn)題，以便各個(gè)擊破，分而治之。 當(dāng)n=2時(shí)，分治法又稱為二分法。 分治算法在每一層遞歸或遞推分為三個(gè)步驟： 分：將原問(wèn)題分解成一系列的子問(wèn)題； 治：遞歸或遞推地解各子問(wèn)題，若子問(wèn)題足夠小，則直接解之； 合：將子問(wèn)題的結(jié)果合并成原問(wèn)題的解。 可以看到，決定算法時(shí)間效率的關(guān)鍵在于合并過(guò)程。,二、遞歸的概念,直接或間接地調(diào)用自身的算法稱為遞歸算法。 用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。 由分治法產(chǎn)生的子問(wèn)題往往是原問(wèn)題的較小模式，這就為使用遞歸技術(shù)提供了方便。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問(wèn)題與原問(wèn)題類型一致而其規(guī)模卻不斷縮小，最終使子問(wèn)題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過(guò)程的產(chǎn)生。 分治與遞歸像一對(duì)孿生兄弟，經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效算法。 下面來(lái)看幾個(gè)實(shí)例。,例1 階乘函數(shù),階乘函數(shù)可遞歸地定義為： 邊界條件與遞歸方程是遞歸函數(shù)的二個(gè)要素，遞歸函數(shù)只有具備了這兩個(gè)要素，才能在有限次計(jì)算后得出結(jié)果。,邊界條件,遞歸方程,例2 Fibonacci數(shù)列,無(wú)窮數(shù)列1，1，2，3，5，8，13，21，34，55，稱為Fibonacci數(shù)列。,遞歸方程,邊界條件,第n個(gè)Fibonacci數(shù)可遞歸地計(jì)算如下： int fibonacci(int n) if (n = 1) return 1; return fibonacci(n-1)+fibonacci(n-2); ,例3 Ackerman函數(shù),當(dāng)一個(gè)函數(shù)及它的一個(gè)變量是由函數(shù)自身定義時(shí)，稱這個(gè)函數(shù)是雙遞歸函數(shù)。,前2例中的函數(shù)都可以找到相應(yīng)的非遞歸方式定義： 本例中的Ackerman函數(shù)卻無(wú)法找到非遞歸的定義,A(n，m)的自變量m的每一個(gè)值都定義了一個(gè)單變量函數(shù)： m=0時(shí)，A(n,0)=n+2 m=1時(shí)，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，和A(1,1)=2故A(n,1)=2*n m=2時(shí)，A(n,2)=A(A(n-1,2),1)=2A(n-1,2)，和A(1,2)=A(A(0,2),1)=A(1,1)=2，故A(n,2)= 2n 。 m=3時(shí)，類似的可以推出 m=4時(shí)，A(n,4)的增長(zhǎng)速度非?？欤灾劣跊](méi)有適當(dāng)?shù)臄?shù)學(xué)式子來(lái)表示這一函數(shù)。,例4 排列問(wèn)題,設(shè)計(jì)一個(gè)遞歸算法生成n個(gè)元素r1,r2,rn的全排列。 設(shè)R=r1,r2,rn是要進(jìn)行排列的n個(gè)元素， Ri=R-ri。 perm(x)，集合x中元素的全排列。 (ri)perm(x)表示在全排列perm(x)的每一個(gè)排列前加上前綴得到的排列。 R的全排列可歸納定義如下： 當(dāng)n=1時(shí)，perm(R)=(r)，其中r是集合R中唯一的元素； 當(dāng)n1時(shí)，perm(R)由(r1)perm(R1), (r2)perm(R2)，(rn)perm(Rn)構(gòu)成。,template void perm(Type list,int k,int m) /產(chǎn)生listk:m的所有排列 if (k=m) /單元素排列 for(int i=0;i=m;i+) coutlisti; coutendl; else /多元素序列，遞歸產(chǎn)生排列 for(int i=k;i=m;i+) swap(listk,listi); perm(list,k+1,m); swap(listk,listi); ,#include #include using namespace std; int main() /示例0到4的全排列。 int a5=0,1,2,3,4; perm(a,0,4); /示例a到d的全排列 char b5=“abcd“; perm(b,0,3); return 0; ,例5 整數(shù)劃分問(wèn)題,將正整數(shù)n表示成一系列正整數(shù)之和。 n=n1+n2+nk, 其中n1n2nk1，k1. 正整數(shù)n的這種表示稱為正整數(shù)n的劃分。求正整數(shù)n的不同劃分個(gè)數(shù)。 例如正整數(shù)6有如下11種不同的劃分： 6； 5+1； 4+2，4+1+1； 3+3，3+2+1，3+1+1+1； 2+2+2，2+2+1+1，2+1+1+1+1； 1+1+1+1+1+1。,前面的幾個(gè)例子中，問(wèn)題本身都具有比較明顯的遞歸關(guān)系，因而容易用遞歸函數(shù)直接求解。 在本例中，如果設(shè)p(n)為正整數(shù)n的劃分?jǐn)?shù)，則難以找到遞歸關(guān)系，因此考慮增加一個(gè)自變量：將最大加數(shù)n1不大于m的劃分個(gè)數(shù)記作q(n,m)。可以建立q(n,m)的如下遞歸關(guān)系。,(1) q(n,1)=1,n1; 當(dāng)最大加數(shù)n1不大于1時(shí)，任何正整數(shù)n只有一種劃分形式，即n=1+1+1+1 (2) q(n,m)=q(n,n),m n; 最大加數(shù)n1實(shí)際上不能大于n。因此，q(1,m)=1。 (3) q(n,n)=1+q(n,n-1); 正整數(shù)n的劃分由n1=n的劃分和n1n-1的劃分組成。 (4) q(n,m)=q(n,m-1)+q(n-m,m),nm1; 正整數(shù)n的最大加數(shù)n1不大于m的劃分由n1=m的劃分和n1m-1 的劃分組成。 正整數(shù)n的劃分?jǐn)?shù)p(n)=q(n,n)。,#include using namespace std; int q(int n,int m) if(n1)|(m1) return 0; if(n=1)|(m=1) return 1; if(nm) return q(n,n); if(n=m) return q(n,m-1)+1; return q(n,m-1)+q(n-m,m); void main() coutq(6,6); ,例6 Hanoi塔問(wèn)題,設(shè)a,b,c是3個(gè)塔座。開始時(shí)，在塔座a上有一疊共n個(gè)圓盤，這些圓盤自下而上，由大到小地疊在一起。各圓盤從小到大編號(hào)為1,2,n,現(xiàn)要求將塔座a上的這一疊圓盤移到塔座b上，并仍按同樣順序疊置。在移動(dòng)圓盤時(shí)應(yīng)遵守以下移動(dòng)規(guī)則： 規(guī)則1：每次只能移動(dòng)1個(gè)圓盤； 規(guī)則2：任何時(shí)刻都不允許將較大的圓盤壓在較小的圓盤之上； 規(guī)則3：在滿足移動(dòng)規(guī)則1和2的前提下，可將圓盤移至a,b,c中任一塔座上。,#include using namespace std; void hanoi(int n, char a, char b, char c) if (n 0) hanoi(n-1, a, c, b); move(a,c); hanoi(n-1, b, a, c); ,void move(char x,char y) cout“m; hanoi(m,a,b,c); return 0; ,【例7】排序工量(sequence quantity),SORT 公司是一個(gè)專門為人們提供排序服務(wù)的公司，該公司的宗旨是：“順序是最美麗的”。他們的工作是通過(guò)一系列移動(dòng)，將某些物品按順序擺好。他們的服務(wù)是通過(guò)工作量來(lái)計(jì)算的，即移動(dòng)?xùn)|西的次數(shù)。所以，在工作前必須先考察工作量，以便向用戶提出收費(fèi)數(shù)目。,用戶并不需要知道精確的移動(dòng)次數(shù)，實(shí)質(zhì)上，大多數(shù)人都是憑感覺(jué)來(lái)認(rèn)定這一列物品的混亂程度. 根據(jù) SORT 公司的經(jīng)驗(yàn)，人們一般是根據(jù)“逆序?qū)Α钡臄?shù)目多少來(lái)稱呼這一序列的混亂程度的。假設(shè)我們將序列中第i物品的參數(shù)定義為 ai，那么排序就是指將 a1 ， ， an由小到大排列。若iaj ，則就為一個(gè)“逆序?qū)Α薄?例如，數(shù)組（ 3 , 1 , 4 , 5 , 2 ）的“逆序?qū)Α庇?, , , ，共 4 個(gè)。,SORT 公司請(qǐng)你寫一個(gè)程序，在盡量短的時(shí)間內(nèi)，統(tǒng)計(jì)出“逆序?qū)Α钡臄?shù)目。 輸入：n, a1, ,an,其中n10000,ai為小于 1000 的正整數(shù) 輸出：數(shù)列 a1, ,an的“逆序?qū)Α睌?shù)目，即“逆序數(shù)”,分析：( 1 ）簡(jiǎn)單搜索法 要單純地計(jì)算出結(jié)果并不難，最直接，最簡(jiǎn)易的方法就是使用兩重循環(huán)，依次枚舉數(shù)列中 i n; /n是數(shù)據(jù)個(gè)數(shù) for(int i=0;iai; /使用兩重循環(huán)依次列舉所有數(shù)對(duì) for(i=0;iaj) c+; /判斷是否為逆序?qū)?，是則計(jì)數(shù),我們可以看到這種算法雖然簡(jiǎn)捷，但兩重循環(huán)中循環(huán)體共執(zhí)行了n*(n-1)/2，即時(shí)間復(fù)雜度為W(n2) ，當(dāng)n很大時(shí)，程序出解速度非常慢，運(yùn)行效率較低。那么有沒(méi)有什么更好的算法可以降低程序的時(shí)間復(fù)雜度，提高程序的運(yùn)行效率呢？,(2)分治算法(Divide and Conquer) 我們用數(shù)組 alo hi存放當(dāng)前子數(shù)列,用d(lo, hi)記錄該子數(shù)列中的所有逆序?qū)Α?分：令med=(lo+hi)/2,將子數(shù)列alo hi分成元素個(gè)數(shù)盡量相等的兩部分:左子數(shù)列alo med和右子數(shù)列amed+1,hi,兩個(gè)子數(shù)列已按由小到大的順序排序。繼續(xù)劃分子數(shù)列，直至 lo=hi 為止。,治：若逆序?qū)Φ膬蓚€(gè)數(shù)分別取自子數(shù)列 alo med 和amed+1 hi 的話，則將該逆序?qū)Υ嫒?f(lo, med, hi)。 合：顯然 alo hi中的逆序?qū)?shù)d(lo,hi) =其子數(shù)列alo med 中的逆序?qū)?shù)d(lo, med) +amed+1hi中逆序?qū)?shù)d(med+1, hi) +當(dāng)前數(shù)列新得逆序?qū)?shù)f(lo, med , hi) ， 即 d(lo, hi)=d(lo, med)+d(med+1 ,hi)+f(lo, med , hi ),最后得到的d(lo,hi)中的逆序?qū)€(gè)數(shù)就是我們所求的結(jié)果。而計(jì)算當(dāng)前子數(shù)列的f(lo,med,hi ）的快慢是算法時(shí)效的瓶頸。如果擺脫不了“搜索思想”的影響，依然用兩重循環(huán)來(lái)算的話，其時(shí)效不會(huì)提高。 設(shè)指針i, j分別指向左子數(shù)列 alomed和右子數(shù)列 amed+1hi中的某個(gè)數(shù),即 lo=i=med , med+1=j=hi。,顯然 i =aj，即ai,aj為一對(duì)逆序?qū)r(shí)，則繼續(xù)向下比較，直至 aj=ai。因?yàn)樽訑?shù)列 alo med和 amed+1 hi 己按由小到大的順序排序，可知 amed+1 , aj-1均小于 ai,計(jì)算可得amed+1hi中比 ai 小的數(shù)共有j-med-1個(gè)，如圖所示。將j-med-1 計(jì)入 f(lo , med , hi)。,由于 alomed和