算法設計與分析 思政課件 第3章 基本算法設計方法

第3章基本算法設計方法3.1窮舉法3.2歸納法CONTENTS提綱3.3迭代法3.4遞歸法3.5遞推式計算1/77窮舉法又稱枚舉法或者列舉法，是一種簡單而直接地解決問題的方法?；舅枷胧窍却_定有哪些窮舉對象和窮舉對象的順序，按窮舉對象的順序逐一列舉每個窮舉對象的所有情況，再根據(jù)問題提出的約束條件檢驗哪些是問題的解，哪些應予排除。3.1.1窮舉法概述3.1窮舉法1.什么是窮舉法2/77常用的列舉方法順序列舉。是指答案范圍內(nèi)的各種情況很容易與自然數(shù)對應甚至就是自然數(shù)，可以按自然數(shù)的變化順序去列舉。排列列舉。有時答案的數(shù)據(jù)形式是一組數(shù)的排列，列舉出所有答案所在范圍內(nèi)的排列，為排列列舉。組合列舉。當答案的數(shù)據(jù)形式為一些元素的組合時，往往需要用組合列舉。組合是無序的。3/77窮舉法的作用理論上講窮舉法可以解決可計算領域中的各種問題。在實際應用中，通常要解決的問題規(guī)模不大，用窮舉法設計的算法其運算速度是可以接受的。舉法算法一般邏輯清晰，編寫的程序簡潔明了。窮舉法算法一般不需要特別證明算法的正確性。窮舉法可作為某類問題時間性能的底限，用來衡量同樣問題的更高效率的算法。4/772.窮舉法框架voidExhaustive(x,n,y,m){for(inti=1;i<=n;i++) //枚舉x的所有可能的值for(intj=1;j<=m;j++) //枚舉y的所有可能的值{…if(p(x[i],y[j]))

輸出一個解;

…}}x和y所有可能的搜索范圍是笛卡爾積即（[x1，y1]，[x1，y2]，…，[x1，ym]，…，[xn，y1]，[xn，y2]，…，[xn，ym]）。這樣的搜索范圍可以用一棵樹表示，稱為解空間樹。5/77【例3-1】雞兔同籠問題?，F(xiàn)有一籠子，里面有雞和兔子若干只，數(shù)一數(shù)，共有a個頭，b條腿。設計一個算法求雞和兔子各有多少只？解x表示雞的只數(shù)，y表示兔的只數(shù)，那么窮舉對象就是x和y，假設窮舉對象的順序是先x后y（本問題中也可以先y后x）。x和y的取值范圍都是0～a，約束條件

p(x，y)為x+y=a&&2x+4y=b。6/77a=3，b=812300123×××0123××××0123×××0123××××x的可能取值y的可能取值滿足條件voidsolve1(inta,intb){ for(intx=0;x<=a;x++) for(inty=0;y<=a;y++) { if(x+y==a&&2*x+4*y==b) printf("x=%d,y=%d\n",x,y); }}解空間樹中共21個結點，顯然結點個數(shù)越多時間性能越差！×7/77優(yōu)化：雞的只數(shù)最多為min(a，b/2)，兔的只數(shù)最多為min(a，b/4)voidsolve2(inta,intb){ for(intx=0;x<=min(a,b/2);x++) for(inty=0;y<=min(a,b/4);y++) { if(x+y==a&&2*x+4*y==b) printf("x=%d,y=%d\n",x,y); }}8/771230012××012×××012××012×××x的可能取值y的可能取值滿足條件以a=3，b=8為例，x的取值范圍是0～3，y的取值范圍是0～2共17個結點！盡管窮舉法算法通常性能較差，但可以以它為基礎進行優(yōu)化繼而得到高性能的算法，優(yōu)化的關鍵是能夠找出求解問題的優(yōu)化點！×9/773.1.2最大連續(xù)子序列和給定一個含n（n≥1）個整數(shù)的序列，要求求出其中最大連續(xù)子序列的和。序列（-2，11，-4，13，-5，-2）的最大子序列和為20。序列（-6，2，4，-7，5，3，2，-1，6，-9，10，-2）的最大子序列和為16。規(guī)定一個序列最大連續(xù)子序列和至少是0，如果小于0，其結果為0。10/77-20i9152183134115117201513-211-413-5-2初始序列-49421386-2-5-7j012345a[0..5]={-2，11，-4，13，-5，-2}解法1：設含有n個整數(shù)的序列a[0..n-1]，枚舉所有連續(xù)子序列a[i..j]。11/77intmaxSubSum1(vector<int>&a) //解法1{ intn=a.size(); intmaxsum=0,cursum; for(inti=0;i<n;i++) //兩重循環(huán)窮舉所有連續(xù)子序列 { for(intj=i;j<n;j++) { cursum=0; for(intk=i;k<=j;k++) //求a[i..j]子序列元素和cursum cursum+=a[k];

maxsum=max(maxsum,cursum); //比較求最大連續(xù)子序列之和 } } returnmaxsum;}12/77解法2：優(yōu)化點避免起始下標i開始的子序列的重復計算。用Sum(a[i..j])表示子序列a[i..j]元素和，初始時置Sum(a[i..j])=0，顯然有如下遞推關系：

Sum(a[i..j])=Sum(a[i..j-1])+a[j] 當j≥i時連續(xù)求a[i..j]子序列和（j=i，i+1，…，n-1）時沒有必要使用循環(huán)變量為k的第3重循環(huán)。-20i9152183134115117201513-211-413-5-2初始序列-49421386-2-5-7j012345Sum[1]=Sum[0]+a[1]=913/77intmaxSubSum2(vector<int>&a) //解法2{ intn=a.size(); intmaxsum=0,cursum; for(inti=0;i<n;i++) { cursum=0; for(intj=i;j<n;j++) //連續(xù)求a[i..j]子序列元素和cursum { cursum+=a[j];

maxsum=max(maxsum,cursum); //比較求最大maxsum } } returnmaxsum;}14/77解法3：優(yōu)化點

maxsum至少為0。a[0..5]={-2， 11， -4， 13， -5， -2}maxsum=0,cursum=0（cursum表示以a[i]結尾的最大和）cursum=0+(-2)=-2maxsum=0cursum<0從頭開始cursum=0cursum=0+11=11maxsum=11cursum=11+(-4)=7maxsum=11cursum=7+13=20maxsum=20cursum=20+(-5)=15maxsum=20cursum=15+(-2)=13maxsum=20maxsum=2015/77解法3：優(yōu)化點

maxsum至少為0。intmaxSubSum3(vector<int>&a) //解法3{ intn=a.size(); intmaxsum=0,cursum=0; for(inti=0;i<n;i++) { cursum+=a[i]; //cursum表示以a[i]結尾的最大和

maxsum=max(maxsum,cursum); //比較求最大maxsum

if(cursum<0) //若cursum<0，從下一個位置開始

cursum=0; } returnmaxsum;}T(n)=O(n)16/77【例3-2】素數(shù)個數(shù)問題。給定兩個均含n個正整數(shù)的數(shù)組a和b，其中整數(shù)元素的范圍是2到20000，求出每對a[i]和b[i]（0≤i<n）之間的素數(shù)個數(shù)（含a[i]和b[i]）。解解法1：采用窮舉法。設計isPrime(x)算法判斷x是否是素數(shù)，Count1(a，b)求整數(shù)a到b之間的素數(shù)個數(shù)。

在此基礎上設計求解算法solve(a，b，n)求每對a[i]和b[i]（0≤i<n）之間的素數(shù)個數(shù)。17/77boolisPrime(intx) //判斷x是否是素數(shù){ for(inti=2;i<=(int)sqrt(x);i++) if(x%i==0) //x能夠被i整除 returnfalse; returntrue;}intCount1(inta,intb) //求a到b的素數(shù)個數(shù){ if(a>b)return0; intcnt=0; for(intx=a;x<=b;x++) if(isPrime(x)) cnt++; returncnt;}voidsolve1(inta[],intb[],intn) //求解算法{ for(inti=0;i<n;i++) printf("%d-%d之間的素數(shù)個數(shù)=%d\n",a[i],b[i],Count1(a[i],b[i]));}solve1算法的最壞時間復雜度為

。18/77解法2：優(yōu)化。設計一個整數(shù)數(shù)組prime，其中prime[i]表示整數(shù)i是否是素數(shù)，初始時置prime所有元素為1，采用素數(shù)篩選法（若i是素數(shù)，則i的倍數(shù)一定不是素數(shù)）求出所有的非素數(shù)。

再將prime轉換為前綴和，即將prime[i]由原來表示整數(shù)i是否是素數(shù)轉換為表示小于等于i的素數(shù)個數(shù)，轉換公式如下：prime[i]+=prime[i-1]這樣a到b之間的素數(shù)個數(shù)為prime[b]-prime[a-1]。19/77intprime[MAXD]; //prime[i]=1表示i是素數(shù)voidInit() //求出prime數(shù)組{ for(inti=0;i<=MAXD;i++) prime[i]=1; prime[0]=prime[1]=0; for(inti=2;i<=MAXD;i++) { if(prime[i]) //若i是素數(shù) { for(intj=2*i;j<=MAXD;j+=i) //則i的倍數(shù)都不是素數(shù) prime[j]=0; } }}voidsolve2(inta[],intb[],intn) //求解算法{ Init(); for(inti=2;i<=MAXD;i++) //prime[i]累計小于等于i的素數(shù)個數(shù)

prime[i]+=prime[i-1]; for(inti=0;i<n;i++) printf("%d-%d之間的素數(shù)個數(shù)=%d\n",a[i],b[i],prime[b[i]]-prime[a[i]-1]);}solve2算法的最壞時間復雜度為O(m+n)。20/773.1.3字符串匹配對于兩個字符串s和t，若t是s子串，返回t在s中的位置（t的首字符在s中對應的下標），否則返回-1。例如：s="aaaabc"，t="aab"，n=6，m=321/77BF算法s="aaaabc"，t="aab"，n=6，m=3aaaabcsaabt（a）從s0/t0開始jiaaaabcsaabtji（b）從s1/t0開始aaaabcsaabtji（c）從s2/t0開始，成功si=sj：i++,j++si≠sj：i=i-j+1,j=022/77intBF(strings,stringt) //字符串匹配{ intn=s.size(),m=t.size(); inti=0,j=0; while(i<n&&j<m) { if(s[i]==t[j]) //比較的兩個字符相同時 { i++; j++; } else //比較的兩個字符不相同時 { i=i-j+1; //i回退到原i的下一個位置 j=0; //j從0開始 } } if(j>=m)returni-m; //t的字符比較完畢表示t是s的子串 elsereturn-1; //否則表示t不是s的子串}平均時間復雜度為O(n*m)23/77KMP算法aaabcsbtji

aa

aaaaaabcsaabtjinext[j]=k表示tj前面最多有k個字符與t開頭的字符相同。失配處si/tj：i不變，j右滑到si/tnext[j]開始比較。24/77voidgetnext(string&t,vector<int>&next){ intj,k; j=0;k=-1; //j遍歷t，k記錄t[j]之前與t開頭相同的字符個數(shù) next[0]=k; //設置next[0]值 while(j<t.size()-1) //求t所有位置的next值 { if(k==-1||t[j]==t[k]) //k為-1或比較的字符相等時 { j++;k++; //j、k依次移到下一個字符 next[j]=k; //設置next[j]為k } elsek=next[k]; //k回退 }}25/77intKMP(strings,stringt) //KMP算法{ intn=s.size(); intm=t.size(); vector<int>next(m,-1);

getnext(t,next); inti=0,j=0; while(i<n&&j<m) { if(j==-1||s[i]==t[j]) //j為-1或者字符相同，i和j均后移 { i++; j++; } elsej=next[j]; //比較字符不相同，j尋找之前匹配的位置 } if(j>=m)returni-t.size(); //j超界說明t是s的子串 elsereturn-1; //否則說明t不是s的子串}平均時間復雜度為O(n+m)。26/77aaaabcsa

abt（a）從s0/t0開始jiaaaabcsaabtji（c）從s3/t1開始，成功失敗處為i=2/j=2修改為i=2/j=next[2]=1aaa

abcsaa

btji（b）從s2/t1開始失敗處為i=3/j=2修改為i=2/j=next[2]=127/77【例3-3】有兩個字符串s和t，設計一個算法求t在s中出現(xiàn)的次數(shù)。

例如，s="abababa"，t="aba"，則t在s中出現(xiàn)2次（不考慮子串重疊的情況）。28/77解解法1：采用BF算法思路。用cnt記錄t在s中出現(xiàn)的次數(shù)（初始時為0）。當在s中找到t的一次出現(xiàn)時置cnt++，此時j=t的長度，i指向s中本次出現(xiàn)t子串的下一個字符，所以為了繼續(xù)查找t子串的下一次出現(xiàn)，只需要置j=0即可。29/77intCount1(strings,stringt) //解法1{ intcnt=0; //累計出現(xiàn)次數(shù) intn=s.size(),m=t.size(); inti=0,j=0; while(i<n&&j<m) { if(s[i]==t[j]) //比較的兩個字符相同時 { i++; j++; } else //比較的兩個字符不相同時 { i=i-j+1; //i回退 j=0; //j從0開始 } if(j>=m) { cnt++;

//出現(xiàn)次數(shù)增1

j=0;

//j從0開始繼續(xù)比較 } } returncnt;}30/77解法2：采用KMP算法思路。先求出t的next數(shù)組（同前面的getnext算法）。在s中找到t的一次出現(xiàn)時置cnt++，同樣i不變只需要置j=0即可。31/77intCount2(strings,stringt) //解法2{ intcnt=0; //累計出現(xiàn)次數(shù) intn=s.size(),m=t.size(); vector<int>next(m,-1);

getnext(t,next); inti=0,j=0; while(i<n) { if(j==-1||s[i]==t[j]) //j=-1或兩字符相同，i和j均后移 { i++; j++; } elsej=next[j]; //兩字符不相同，j尋找之前匹配的位置 if(j>=m) //成功匹配一次 { cnt++; j=0;

//匹配成功后t從頭開始比較 } } returncnt;}32/773.1.4實戰(zhàn)—查找單詞（POJ1501）輸入格式：輸入的第一行為正方形的字母矩陣的長度n（以字符為單位，1≤n≤100），接下來的n行輸入字母矩陣，每行僅包含n個大寫字母。隨后是一個單詞列表，每個單詞占一行，最多100個單詞，每個單詞不超過100個字符，并且只包含大寫字母。輸入的最后一行包含一個0字符。輸出格式：在字母矩陣中查找單詞列表中的每個單詞，如果一個單詞中的所有字母都可以在字母矩陣中的單個（單向）水平、垂直或對角線中找到，則該單詞查找成功。單詞不會出現(xiàn)環(huán)繞，但在水平或者對角線上可以從右到左。若一個單詞查找成功（測試數(shù)據(jù)保證每個單詞最多只能查找成功一次），在一行中輸出其在字母矩陣中第一個和最后一個字母的坐標，坐標是逗號分隔的整數(shù)對，其中第一個整數(shù)指定行號，第二個整數(shù)指定列號（行、列號均從1開始），兩組坐標之間一個空格分隔。如果一個單詞沒有找到，則輸出"Notfound''字符串。33/77輸入樣例：5EDEEEDISKEESEEEECEEEEEEEEDISCDISKDISP0輸出樣例：1,2

4,22,12,4Notfound34/77解用二維字符數(shù)組map存放字母矩陣，在其中查找單詞str（長度為len）時只能依次按8個方位（用dir數(shù)組表示8個方位的偏移量）搜索。沒有回退，所以采用窮舉法，i和j枚舉行列坐標，d枚舉8個方位，k遍歷str，其中str[k]字符的坐標是(i+dir[d][0]*k，j+dir[d][1]*k)。若str的全部字符均查找到即k=len-1成立，則說明查找成功。所以情況下都沒有找到str說明查找失敗。最后輸出結果。35/77#include<iostream>#include<cstring>#defineMAXN105usingnamespacestd;intdir[8][2]={{0,1},{0,-1},{1,0},{-1,0},{-1,-1},{-1,1},{1,-1},{1,1}};charmap[MAXN][MAXN];charstr[MAXN];36/77intmain(){ intn,i,j,x,y; scanf("%d",&n); for(i=0;i<n;i++) //輸入字母矩陣 scanf("%s",map[i]); while(scanf("%s",str)) //輸入若干個單詞 { if(str[0]=='0')break; //輸入"0"結束 intlen=strlen(str); boolflag=false;37/77 for(i=0;i<n;i++) //窮舉每個行 { for(j=0;j<n;j++) //窮舉每個列 { for(intd=0;d<8;d++) //窮舉每個方位 { for(intk=0;k<len;k++) //遍歷str單詞 { x=i+dir[d][0]*k; //求出str[k]字母的坐標(x,y) y=j+dir[d][1]*k; if(x<0||x>=n||y<0||y>=n||map[x][y]!=str[k]) break; //坐標超界或者不相同退出k的循環(huán) if(k==len-1)flag=true; //查找成功，置flag為true } if(flag)break; } if(flag)break; } if(flag)break; } if(flag) //輸出查找結果 printf("%d,%d%d,%d\n",i+1,j+1,x+1,y+1); else printf("Notfound\n");}return0;}38/773.2.1歸納法概述3.2歸納法1.什么是數(shù)學歸納法第一數(shù)學歸納法原理：若{P(1)，P(2)，P(3)，P(4)，…}是命題序列且滿足以下兩個性質(zhì)，則所有命題均為真：①P(1)為真。②任何命題均可以從它的前一個命題推導得出。第二數(shù)學歸納法原理：若{P(1)，P(2)，P(3)，P(4)，…}是滿足以下兩個性質(zhì)的命題序列，則對于其他自然數(shù)，該命題序列均為真：①P(1)為真。②任何命題均可以從它的前面所有命題推導得出。39/772.什么是歸納法40/7741/77歸納法

遞推關系基本流程：按推導問題方向研究最初最原始的若干問題。按推導問題方向尋求問題間的轉換規(guī)律即遞推關系，使問題逐次轉化成較低層級或簡單的且能解決問題的或已解決的問題。順推法和逆推法：順推法是從已知條件出發(fā)逐步推算出要解決問題的結果。逆推法從已知問題的結果出發(fā)逐步推算出問題的開始條件。42/77數(shù)學歸納法不是歸納法，但它與歸納法有著一定程度的關聯(lián)。在結論的發(fā)現(xiàn)過程中，往往先通過對大量個別事實的觀察，通過不完全歸納法歸納形成一般性的結論，最終利用數(shù)學歸納法對結論的正確性予以證明。43/773.2.2直接插入排序有一個整數(shù)序列R[0..n-1]，采用直接插入排序實現(xiàn)R的遞增有序排序。直接插入排序的過程是，i從1到n-1循環(huán)，將R[i]有序插入到R[0..i-1]中。44/77

采用不完全歸納法產(chǎn)生直接插入排序的遞推關系。

例如R=（2，5，4，1，3），這里n=5，用[]表示有序區(qū)，各趟的排序結果如下：初始：

（[2]，5，4，1，3）i=1：

（[2，5]，4，1，3）i=2：

（[2，4，5]，1，3）i=3：

（[1，2，4，5]，3）i=4：

（[1，2，3，4，5]）

設f(R，i)用于實現(xiàn)R[0..i]（共i+1個元素）的遞增排序，它是大問題，則f(R，i-1)實現(xiàn)R[0..i-1]（共i個元素）的排序，它是小問題。對應的遞推關系：f(R，i)≡不做任何事情

當i=0f(R，i)≡f(R，i-1);將R[i]有序插入到R[0..i-1]中; 其他解45/77f(R，i)≡不做任何事情

當i=1f(R，i)≡f(R，i-1);將R[i]有序插入到R[0..i-1]中; 其他顯然f(R，n-1)用于實現(xiàn)R[0..n-1]的遞增排序。采用不完全歸納法得到的結論是否正確呢？

①證明歸納基礎成立。當n=0時直接返回，由于此時R中只有一個元素，它是遞增有序的，所以結論成立。

②證明歸納遞推成立。假設n=k時成立，也就是說f(R，k-1)用于實現(xiàn)R[0..k-1]的遞增排序。

當n=k+1時對應f(R，k)，先調(diào)用f(R，k-1)將R[0..k-1]排序，再將R[k]有序插入到R[0..k-1]中，這樣R[0..k]變成遞增有序序列了，所以f(R，k)實現(xiàn)R[0..k]的遞增排序，結論成立。46/77voidInsert(vector<int>&R,inti) //插入操作：將R[i]有序插入到R[0..i-1]中{ inttmp=R[i]; intj=i-1; do //找R[i]的插入位置 { R[j+1]=R[j]; //將關鍵字大于R[i]的元素后移 j--; }while(j>=0&&R[j]>tmp); //直到R[j]<=tmp為止 R[j+1]=tmp; //在j+1處插入R[i]}voidInsertSort1(vector<int>&R) //直接插入排序{ intn=R.size(); for(inti=1;i<n;i++) { if(R[i]<R[i-1]) //反序時

Insert(R,i); }}47/773.2.3樓梯問題一個樓梯共有n個臺階，規(guī)定每一步只能跨一個或兩個臺階。設計一個算法求登上第n級臺階有多少種不同走法。48/77采用歸納法中的順推法。設f(n)表示登上第n級臺階的不同的走法數(shù)。當n=1時，只有跨一個臺階的一種走法，即f(1)=1。當n=2時，可以走兩步每步跨一個臺階，也可以走一步跨兩個臺階，這樣共有兩種走法，即f(2)=2。當n=3時，考慮第一步，第一步跨兩個臺階，剩下一個臺階（剩下一個臺階的不同走法數(shù)為f(1)），對應的不同走法數(shù)為f(1)；第一步跨一個臺階，剩下2個臺階（剩下2個臺階的不同走法數(shù)為f(2)），對應的不同走法數(shù)為f(2)。采用加法原理有f(3)=f(1)+f(2)。當n=4時，f(4)=f(2)+f(3)。f(1)=1f(2)=2f(n)=f(n-2)+f(n-1) 當n>249/77intCount(intn){ inta=1,b=2,c; if(n==1) returna; elseif(n==2) returnb; else { for(inti=3;i<=n;i++) { c=a+b; a=b; b=c; } returnc; }}…

f(n-2)f(n-1)f(n)f(n+1)abcabc50/773.2.4猴子摘桃子問題自學（歸納法中的逆推法）51/773.2.5實戰(zhàn)—骨牌鋪方格（HDU2046）在2×n的一個長方形方格中，用一個1×2的骨牌鋪滿方格。輸入n，輸出鋪放方案的總數(shù)。例如n=3時，為2×3方格，骨牌的鋪放方案有3種。(a)方案1(b)方案2(c)方案3輸入格式：輸入數(shù)據(jù)由多行組成，每行包含一個整數(shù)n，表示該測試實例的長方形方格的規(guī)格是2×n（0<n≤50）。輸出格式：對于每個測試實例，請輸出鋪放方案的總數(shù)，每個實例的輸出占一行。52/77設f(n)表示用1×2的骨牌鋪滿2×n的一個長方形方格的鋪放方案總數(shù)。當n=1時，用一塊1×2的骨牌鋪滿，即f(1)=1。當n=2時，用兩塊1×2的骨牌橫向或者縱向鋪滿，即f(2)=2。解53/77n>2時，2×n的一個長方形方格看成是高度為2的n個方格組成，編號依次是1～n，鋪放分為如下情況：

（1）先鋪好方格1，剩下2～n共n-1個方格有f(n-1)種鋪放方案，采用乘法原理，情況1的鋪放方案總數(shù)=1*f(n-1)=f(n-1)?！?a)情況1f(n-1)12n54/77（2）

先鋪好方格1和方格2，剩下3～n共n-2個方格有f(n-2)種鋪放方案。前面兩個個方格對應兩種鋪放方案：

①

鋪放方案總數(shù)=1*f(n-2)=f(n-2)，但該鋪放方案包含在情況1中。

②

鋪放方案總數(shù)=1*f(n-2)=f(n-2)，該鋪放方案沒有包含在情況1中。采用加法原理，鋪放方案總數(shù)f(n)=f(n-1)+f(n-2)。…(b)情況①f(n-2)13n2…(c)情況②f(n-2)13n255/77合并起來得到如下遞推關系如下：f(1)=1f(2)=2f(n)=f(n-2)+f(n-1) 當n>256/77#include<iostream>usingnamespacestd;longlongCount(intn) //求鋪放方案的總數(shù){ longlonga=1,b=2,c; //a,b,c分別對應f(n-2),f(n-1),f(n) if(n==1) returna; elseif(n==2) returnb; else { for(inti=3;i<=n;i++) { c=a+b; a=b; b=c; } returnc; }}57/77intmain(){ intn; while(~scanf("%d",&n)) printf("%lld\n",Count(n)); return0;}58/77#include<iostream>usingnamespacestd;intmain(){ intn; longlonga[55]={0,1,2}; for(inti=3;i<=51;i++)

a[i]=a[i-1]+a[i-2]; while(~scanf("%d",&n)) printf("%lld\n",a[n]); return0;}優(yōu)化：數(shù)組a（大小為55），a[i]存放f(i)，先求出a中所有元素，再對于每個測試實例n直接輸出a[n]即可。59/773.3.1迭代法概述3.3迭代法迭代法也稱輾轉法，是一種不斷用變量的舊值推出新值的過程。通過讓計算機對一組指令（或一定步驟）進行重復執(zhí)行，在每次執(zhí)行這組指令（或這些步驟）時，都從變量的原值推出它的一個新值。60/77迭代法算法框架voidIterative(){迭代變量賦初值;while(迭代條件成立){根據(jù)遞推關系式由舊值計算出新值;

新值取代舊值，為下一次迭代做準備;}}61/77迭代法算法包含循環(huán)，對循環(huán)的證明引入循環(huán)不變量的概念。循環(huán)不變量是指在每輪迭代開始前后要操作的數(shù)據(jù)必須保持的某種特性（比如在直接插入排序中，排序表前面部分必須是有序的）。循環(huán)不變量是進行循環(huán)的必備條件，因為它保證了循環(huán)進行的有效性，有助于理解算法的正確性。循環(huán)體循環(huán)不變量：每輪迭代前后保持不變，從而保證了算法的正確性62/77循環(huán)不變量必須證明它的三個性質(zhì)：初始化：在循環(huán)的第一輪迭代開始之前，應該是正確的。保持：如果循環(huán)的第一次迭代開始之前正確，那么在下一次迭代開始之前它也應該保持正確。終止：當循環(huán)結束時，循環(huán)不變量給了我們一個有用的性質(zhì)，它有助于表明算法是正確的。63/77【例3-5】采用循環(huán)不變量方法證明3.2.2節(jié)中直接插入排序算法的正確性。證明：直接插入排序算法中循環(huán)不變量為R[0..i-1]是遞增有序的。初始化：循環(huán)時i從1開始，循環(huán)之前R[0..0]只有一個元素，顯然成立。保持：需要證明每一輪循環(huán)都能使循環(huán)不變量保持成立。對于R[i]排序的這一趟，之前R[0..i-1]是遞增有序的：①如果R[i]≥R[i-1]即正序，則該趟結束，結束后循環(huán)不變量R[0..i]顯然是遞增有序的。②如果R[i]<R[i-1]即反序，則在R[0..i-1]中從后向前找到第一個R[j]≤R[i]，將R[j+1..i-1]均后移一個位置，并且將原R[i]放在R[j+1]位置，這樣結束后循環(huán)不變量R[0..i]顯然也是遞增有序的。終止：循環(huán)結束時i=n，在循環(huán)不變量中用i替換n，就有R[0..n-1]包含原來的全部元素，現(xiàn)在已經(jīng)排好序了，即說循環(huán)不變量也是成立的。64/773.3.2簡單選擇排序有一個整數(shù)序列R[0..n-1]，采用簡單選擇排序實現(xiàn)R的遞增有序排序。簡單選擇排序的過程是：i從0到n-2循環(huán)，R[0..i-1]是有序區(qū)，R[i..n-1]是無序區(qū)，并且前者的所有元素均小于等于后者的任意元素，在R[i..n-1]無序區(qū)通過簡單比較找到最小元素R[minj]，通過交換將其放在R[i]位置。65/77采用不完全歸納法產(chǎn)生簡單選擇排序的遞推關系。例如R=（2，5，4，1，3），這里n=5，用[]表示有序區(qū)，各趟的排序結果如下：初始：

（[]2，5，4，1，3）i=0：

（[1]，5，4，2，3）i=1：

（[1，2]，4，5，3）i=2：

（[1，2，3]，5，4）i=3：

（[1，2，3，4]，5）解66/77設f(R，i)用于實現(xiàn)R[i..n-1]（共n-i個元素）的遞增排序，它是大問題，則f(R，i-1)實現(xiàn)R[i-1..n-1]（共n-i-1個元素）的排序，它是小問題。f(R，i)≡不做任何事情

當i=n-1時f(R，i)≡在R[i..n-1]中選擇最小元素交換到R[i]位置; 否則

f(R，i+1);67/77voidSelect(vector<int>&R,inti) //選擇操作：R[i..n-1]選最小元素交換到R[i]{ intminj=i; //minj表示R[i..n-1]中最小元素的下標 for(intj=i+1;j<R.size();j++) //在R[i..n-1]中找最小元素 if(R[j]<R[minj]) minj=j; if(minj!=i) //若最小元素不是R[i] swap(R[minj],R[i]); //交換}voidSelectSort1(vector<int>&R) //迭代法：簡單選擇排序{ intn=R.size(); for(inti=0;i<n-1;i++) //進行n-1趟排序

Select(R,i);}68/773.3.4求多數(shù)元素自學(老師講的太多了)69/773.3.5求冪集給定正整數(shù)n（n≥1），求{1～n}的冪集的遞歸模型和迭代算法。例如，n=3時，{1，2，3}的冪集合為{{}，{1}，{2}，{1，2}，{3}，{1，3}，{2，3}，{1，2，3}}。70/77解以n=3為例，求1～3的冪集的過程1的冪集M1：{{},{1}}M1中每個集合元素添加2得到A2A2：{{2},{1,2}}1～2的冪集M2：{{},{1},{2},{1,2}}M2=M1∪A2M2中每個集合元素添加3得到A3A3：{{3},{1,3},{2,3},{1,2,3}}1～3的冪集M3：{{},{1},{2},{1,2},{3},{1,3},{2,3},{1,2,3}}M3=M2∪A371/77定義運算appendi(Mi-1，i)返回在Mi-1中每個集合元素末尾插入整數(shù)i的結果這樣求{1～n}的冪集的遞推關系如下：M1={{}，{1}}Mi=Mi-1∪Ai

當i>1時72/77vector<vector<int>>appendi(vector<vector<int>>Mi_1,inti)//向Mi_1中每個集合元素末尾添加i{ vector<vector<int>>Ai=Mi_1; for(intj=0;j<Ai.size();j++) Ai[j].push_back(i); returnAi;}vector<vector<int>>subsets1(intn) //迭代法：求{1～n}的冪集{ vector<vector<int>>Mi; //存放{1～n}的冪集 vector<vector<int>>Mi_1={{},{1}}; //初始時存放M1 if(n==1)returnMi_1; //處理特殊情況 for(inti=2;i<=n;i++) //迭代循環(huán) { vector<vector<int>>Ai=appendi(Mi_1,i); Mi=Mi_1; for(intj=0;j<Ai.size();j++) //將Ai所有集合元素添加到Mi中 Mi.push_back(Ai[j]); Mi_1=Mi; //新值取代舊值 } returnMi;}73/773.3.4實戰(zhàn)—子集（LeetCode78）

給定一個整數(shù)數(shù)組

nums，長度范圍是1～10，其中所有元素互不相同。求該數(shù)組所有可能的子集（冪集），結果中不能包含重復的子集，可以按任意順序返回冪集。

例如，nums=[1，2，3]，結果為[[]，[1]，[2]，[1，2]，[3]，[1，3]，[2，3]，[1，2，3]]。

要求設計如下成員函數(shù)：class

Solution

{public:

vector<vector<int>>

subsets(vector<int>&

nums)

{

}};74/77解求nums[0..n-1]的冪集。求nums的冪集的遞推關系如下：M1={{}，{nums[0]}}Mi=Mi-1∪Ai 當i>0時75/77class

Solution

{ //迭代法：求nums的冪集public: vector<vector<int>>

subsets(vector<int>&

nums)

{ vector<vector<int>>

Mi;

//存放冪集

vector<vector<int>>

Mi_1={{},{nums[0]}};

//存放M1

if(nums.size()==1)

return

Mi_1; //處理特殊情況

for(int

i=1;i<nums.size();i++)

{ vector<vector<int>>

Ai=appendi(Mi_1,nums[i]);

Mi=Mi_1;

for(int

j=0;j<Ai.size();j++)

//將Ai所有集合元素添加到Mi中

Mi.push_back(Ai[j]);

Mi_1=Mi;

}

return

Mi;

}76/77

vector<vector<int>>

appendi(vector<vector<int>>

Mi_1,int

e)

//向Mi_1中每個集合元素末尾添加e

{ vector<vector<int>>

Ai=Mi_1;

for(int

j=0;j<Ai.size();j++)

Ai[j].push_back(e);

return

Ai;

}};77/7778/77思政案例第3章基本算法設計方法3.1窮舉法3.2歸納法CONTENTS提綱3.3迭代法3.4遞歸法3.5遞推式計算79/363.4.1遞歸法概述3.4遞歸法遞歸算法是指在算法定義中又調(diào)用自身的算法。遞歸算法通常把一個大的復雜問題層層轉化為一個或多個與原問題相似的規(guī)模較小的問題來求解，具有思路清晰和代碼少的優(yōu)點。一般來說，能夠用遞歸解決的問題應該滿足以下3個條件：原問題可以轉化為一個或多個子問題來求解，而這些子問題的求解方法與原問題完全相同，只是在數(shù)量規(guī)模上不同。遞歸調(diào)用的次數(shù)必須是有限的。必須有結束遞歸的條件來終止遞歸。1.什么是遞歸80/362.遞歸模型f(s1)=mf(sn)=g(f(sn-1)，c)簡化的遞歸模型：f(sn)

f(sn-1)81/363.提取求解問題的遞歸模型對大問題f(s)進行分析，假設出合理的“小問題”f(s')。假設小問題f(s')是可解的，在此基礎上確定大問題f(s)的解，即給出f(s)與f(s')之間的遞推關系，也就是提取遞歸體（與數(shù)學歸納法中假設i=n-1時等式成立，再求證i=n時等式成立的過程相似）。確定一個特定情況（如f(1)或f(0)）的解，由此作為遞歸出口（與數(shù)學歸納法中求證i=1或i=0時等式成立相似）。82/364.遞歸算法框架voidrecursion1(n) //先遞后合的遞歸框架{if(滿足出口條件)

直接解決;else{recursion1(m); //遞去，遞到最深處

merge(); //歸來時執(zhí)行合并操作}}voidrecursion2(n) //先合后遞的遞歸框架{if(滿足出口條件)

直接解決;else{merg(); //合并：遞去

recursion2(m); //遞到最深處后，再不斷地歸來}}83/36【例3-6】假設二叉樹采用二叉鏈存儲，設計一個算法判斷兩棵二叉樹t1和t2是否相同，所謂相同是指它們的形態(tài)相同并且對應的結點值相同。解設f(t1，t2)表示二叉樹t1和t2是否相同，它們的左右子樹的判斷是兩個小問題。t1f(t1->left,t2->left)t2f(t1->right,t2->right)f(t1，t2)=true 當t1和t2均為空f(t1，t2)=false 當t1、t2中一空一非空f(t1，t2)=false 當均不空但結點值不同f(t1，t2)=f(t1->left,t2->left)&&f(t1->right,t2->right) 其他84/36boolsame(TreeNode*t1,TreeNode*t2) //遞歸算法：判斷t1和t2是否相同{ if(t1==NULL&&t2==NULL) returntrue; elseif(t1==NULL||t2==NULL) returnfalse; if(t1->val!=t2->val) returnfalse; boolleft=same(t1->left,t2->left); //遞歸調(diào)用1 boolright=same(t1->right,t2->right); //遞歸調(diào)用2 returnleft&&right;}85/363.4.2冒泡排序有一個整數(shù)序列R[0..n-1]，采用冒泡排序實現(xiàn)R的遞增有序排序。冒泡排序的過程是，i從0到n-2循環(huán)，R[0..i-1]是有序區(qū)，R[i..n-1]是無序區(qū)，并且前者的所有元素均小于等于后者的任意元素，在R[i..n-1]無序區(qū)通過冒泡方式將最大元素放在R[i]位置。86/36采用不完全歸納法產(chǎn)生冒泡排序的遞推關系。例如R=（2，5，4，1，3），這里n=5，用[]表示有序區(qū)，各趟的排序結果如下：初始：

（[]2，5，4，1，3）i=0：

（[1]，2，5，4，3）i=1：

（[1，2]，3，5，4）i=2：

（[1，2，3]，4，5）i=3：

（[1，2，3，4]，5）解87/36

設f(R，i)用于實現(xiàn)R[0..i]（共i+1個元素）的遞增排序，它是大問題，則f(R，i-1)實現(xiàn)R[0..i-1]（共i個元素）的排序，它是小問題。當i=-1時，R[0..i]為空，看成是有序的。f(R，i)≡不做任何事情

當i=-1f(R，i)≡f(R，i-1); 否則

在R[i..n-1]中冒泡最小元素到R[i]位置;先遞后合88/36voidBubble1(vector<int>&R,inti) //冒泡操作：R[i..n-1]冒最小元素R[i]{ intn=R.size(); for(intj=n-1;j>i;j--) //無序區(qū)元素比較,找出最小元素 if(R[j-1]>R[j]) //當相鄰元素反序時 swap(R[j],R[j-1]); //R[j]與R[j-1]進行交換}voidBubbleSort21(vector<int>&R,inti) //被BubbleSort2調(diào)用{ if(i==-1)return; //滿足遞歸出口條件

BubbleSort21(R,i-1); //遞歸調(diào)用

Bubble1(R,i); //合并操作}voidBubbleSort2(vector<int>&R) //遞歸算法：冒泡排序{ intn=R.size();

BubbleSort21(R,n-2);}89/36

設f(R，i)用于實現(xiàn)R[i..n-1]（共n-i個元素）的遞增排序，它是大問題，則f(R，i-1)實現(xiàn)R[i-1..n-1]（共n-i-1個元素）的排序，它是小問題。當i=n-1時，R[n-1..n-1]僅包含最后一個元素，它一定是最大元素，排序結束。f(R，i)≡不做任何事情

當i=n-1f(R，i)≡在R[i..n-1]中冒泡最小元素到R[i]位置; 否則

f(R，i+1);先合后遞90/36voidBubbleSort31(vector<int>&R,inti) //被BubbleSort3調(diào)用{ intn=R.size(); if(i==n-1)return; //滿足遞歸出口條件

Bubble1(R,i); //合并操作

BubbleSort31(R,i+1); //遞歸調(diào)用}voidBubbleSort3(vector<int>&R) //遞歸算法：冒泡排序{

BubbleSort31(R,0);}91/363.4.3求全排列給定正整數(shù)n（n≥1），給出求1～n的全排序的遞歸模型和遞歸算法。例如，n=3時，全排列是{{1，2，3}，{1，3，2}，{3，1，2}，{2，1，3}，{2，3，1}，{3，2，1}}。92/36以n=3為例，求1～3的全排列的步驟。解1將2插入到各位上1212313231221213231321將3插入到各位上初始時為1求解中間結果求解的最終結果93/36

設Pi表示1～i（i≥1，共i個元素）的全排列（是一個兩層集合，其中每個集合元素表示1～i的某個排列），為大問題，則Pi-1為1～i-1（共i-1個元素）的全排列，為小問題。顯然有P1={{1}}。P1={{1}}

當i>1時94/36vector<vector<int>>CreatePi(vector<int>s,inti)//在s集合中i-1到0位置插入i{ vector<vector<int>>tmp; for(intj=s.size();j>=0;j--) //在s(含i-1個整數(shù))每個位置插入i { vector<int>s1=Insert(s,i,j); tmp.push_back(s1); //添加到Pi中 } returntmp;}95/36vector<int>Insert(vector<int>s,inti,intj) //在s的位置j插入i{ vector<int>::iteratorit=s.begin()+j; //求出插入位置 s.insert(it,i); //插入整數(shù)i returns;}vector<vector<int>>perm21(intn,inti) //被Perm2調(diào)用{ if(i==1) //遞歸出口 return{{1}}; else { vector<vector<int>>Pi; vector<vector<int>>Pi_1=perm21(n,i-1); //求出Pi_1 for(autoit=Pi_1.begin();it!=Pi_1.end();it++) //Pi每個元素的各位置插入i { vector<vector<int>>tmp=CreatePi(*it,i); for(intk=0;k<tmp.size();k++) Pi.push_back(tmp[k]); //將tmp全部元素添加到Pi中 } returnPi; }}vector<vector<int>>Perm2(intn) //遞歸法求1～n的全排列{ returnperm21(n,n);}96/363.4.4實戰(zhàn)—展開字符串（HDU1274）問題描述：例如abc表示三根紗線的排列。重復可以用數(shù)字和括號表示，例如2(abc)表示abcabc，1(a)=1a表示a，2ab表示aab。如果括號前面沒有表示重復的數(shù)字出現(xiàn)，則就可認為是1被省略了，如cd(abc)=cd1(abc)=cdabc。這種表示方法非常簡單緊湊。請你編寫一個