算法設(shè)計(jì)與分析常見(jiàn)題

1、1.數(shù)字三角形這道題目可以用遞歸的方法解決。基本思路是：以 D( r, j)表示第 r行第 j 個(gè)數(shù)字(r，j都從 1開(kāi)始算 )，以 MaxSum(r, j) 代表從第 r 行的第 j 個(gè)數(shù)字到底邊的最佳路徑的數(shù)字之和，則本題是要求 MaxSum(1, 1) 。從某個(gè) D(r, j)出發(fā)，顯然下一步只能走 D(r+1, j)或者 D(r+1, j+1)。i.如果走 D(r+1, j)，那么得到的 MaxSum(r, j)就是 MaxSum(r+1, j) + D(r, j)；ii.如果走 D(r+1, j+1)，那么得到的 MaxSum(r, j)就是 MaxSum(r+1, j+1) + D

2、(r, j)。所以，選擇往哪里走，就看 MaxSum(r+1, j)和 MaxSum(r+1, j+1)哪個(gè)更大了。程序如下：#include #define MAX_NUM 100 int DMAX_NUM + 10MAX_NUM + 10; int N; int MaxSum( int r, int j) if( r = N ) return Drj; int nSum1 = MaxSum(r+1, j); int nSum2 = MaxSum(r+1, j+1); if( nSum1 nSum2 ) return nSum1+Drj; return nSum2+Drj; main() i

3、nt m; scanf(%d, &N); for( int i = 1; i = N; i + ) for( int j = 1; j = i; j + ) scanf(%d, &Dij); printf(%d, MaxSum(1, 1); 動(dòng)態(tài)規(guī)劃：動(dòng)態(tài)規(guī)劃通常用來(lái)求最優(yōu)解，能用動(dòng)態(tài)規(guī)劃解決的求最優(yōu)解問(wèn)題，必須滿足，最優(yōu)解的每個(gè)局部解也都是最優(yōu)的，并且將中間結(jié)果保存以避免重復(fù)計(jì)算的辦法。從 aMaxSumN-1這一行元素開(kāi)始向上逐行遞推，就能求得最終 aMaxSum11的值了。程序如下： #include #include #define MAX_NUM 100 int DMAX_NUM +

4、 10MAX_NUM + 10; int N; int aMaxSumMAX_NUM + 10MAX_NUM + 10; main() inti,j; scanf(%d, & N); for( i = 1; i = N; i + ) for( j = 1; j = i; j + ) scanf(%d, &Dij); for( j = 1; j 1 ; i - ) for( j = 1; j aMaxSumij+1 ) aMaxSumi-1j = aMaxSumij + Di-1j; else aMaxSumi-1j = aMaxSumij+1 + Di-1j; printf(%d, aMaxS

5、um11); 2.馬的走法問(wèn)題描述：在45的棋盤上已知馬的起始坐標(biāo)(x,y)，求馬能夠返回到起始位置的不重復(fù)的所有不同走法的總數(shù)。算法思想：回溯法，馬當(dāng)前所在的位置是當(dāng)前擴(kuò)展結(jié)點(diǎn)，每個(gè)活結(jié)點(diǎn)可能有八個(gè)孩子結(jié)點(diǎn)。問(wèn)題所在：如何記錄馬行走的路徑？程序如下：class Horseprivate: int chess56; int d28=1,2,2,1-1,-2,-2,-1,2,1,-1,-2,-2,-1,1,2; int sx,sy; int count;public: Horse(int x,int y) sx=x; sy=y; for(int i=0;i6;i+) for(int j=0;j5

6、;j+) chessij=0; static long computer() count=0; if(sx0|sy=6|sy=5) return ; backtrack(sx,sy); return count; Private static void backtrack(int p1,int p2);Private static void Horse: backtrack(int p1,int p2) int pi,pj; for(int i=0;i=0&pi=0&pj5&chpipj=0) chesspipj=1; backtrack(pi,pj); chesspipj=0; else i

7、f(pi=sx&pj=sy) count+; ;3.會(huì)餐交友算法思想：構(gòu)造一個(gè)對(duì)稱鄰接矩陣FriendMaxMax，第i行第j列的值為1代表i和j認(rèn)識(shí)。具體步驟很簡(jiǎn)單。統(tǒng)計(jì)每一行值為1的個(gè)數(shù)，找出個(gè)數(shù)最大的行k，記錄下來(lái)，然后把第k行和第k列的元素全置為0（對(duì)稱矩陣）。循環(huán)執(zhí)行以上描述的步驟，直到鄰接矩陣所有元素為0跳出循環(huán)。程序如下：#include #define Max 500int main()/鄰接矩陣（對(duì)稱矩陣）int FriendMaxMax=0;int n;cinn;int i=-1,j=-1;while(i!=0|j!=0)cini;cinj;Friendij=Friendj

8、i=1;/每次計(jì)算記錄每行的非零個(gè)數(shù)int countMax=0;/temp存儲(chǔ)臨時(shí)最大個(gè)數(shù)，row表示最大個(gè)數(shù)的行int temp,row;int resultMax=0,number=0;while(true)/統(tǒng)計(jì)第i行是1的個(gè)數(shù)for(i=1;i=n;i+)for(j=1;j=n;j+)if(j=i)/主對(duì)角線置為0Friendij=0;continue;if(Friendij=1)counti+;/找出元素最多的行temp=count1;for(i=2;i=n;i+)if(tempcounti)row=i;temp=counti;/存儲(chǔ)結(jié)果resultnumber+=row;/判斷矩

9、陣是否全為0if(temp=0)/輸出結(jié)果coutnumberendl;for(i=0;resulti!=0;i+)coutresulti ;break;/刪除第i行和第i列的元素，并將count數(shù)組置零for(i=1;i=n;i+)if(Friendrowi=1)Friendrowi=Friendirow=0;counti=0;return 0;4.赤道大篝火輸入：第一行輸入n第二行輸入m第三行輸入n+1個(gè)地點(diǎn)所表示的位置，第一個(gè)為0第四行輸入m個(gè)點(diǎn)火的地點(diǎn)第五行輸入m個(gè)點(diǎn)火地點(diǎn)對(duì)應(yīng)的點(diǎn)火時(shí)刻第六行輸入大火蔓延速度v輸出：n個(gè)地方對(duì)應(yīng)的起火時(shí)刻解題思路：把赤道展開(kāi)平鋪成一條直線，最后一個(gè)點(diǎn)和

10、第一個(gè)點(diǎn)視為同一個(gè)點(diǎn)。初步考慮用兩個(gè)循環(huán)把問(wèn)題解決，外循環(huán)遍歷每一個(gè)地方，內(nèi)循環(huán)遍歷每一個(gè)點(diǎn)火處。假設(shè)針對(duì)第i個(gè)地點(diǎn)探討它的起火時(shí)間，則最關(guān)鍵的問(wèn)題就是子問(wèn)題的分割，將多處點(diǎn)火的情形看做多個(gè)只有一處點(diǎn)火的情形。這樣每個(gè)子問(wèn)題就可以很輕松的計(jì)算出每個(gè)起火點(diǎn)點(diǎn)火時(shí)到達(dá)點(diǎn)i的時(shí)刻?；氐匠嗟赖母拍睿僭O(shè)點(diǎn)火處為點(diǎn)j，則先通過(guò)比較點(diǎn)i到點(diǎn)j的順時(shí)針距離和逆時(shí)針距離得出最小值value，得出時(shí)間間隔為value除以速度v，假設(shè)點(diǎn)j的點(diǎn)火時(shí)刻為timej，點(diǎn)i的起火時(shí)間為resulti，就可以得出在點(diǎn)火處j使點(diǎn)i起火的時(shí)刻為resulti=value / v + timej。內(nèi)層循環(huán)可以通過(guò)這種計(jì)算，遍歷所

11、有的點(diǎn)火處j（即使點(diǎn)i就是點(diǎn)j），以覆蓋的方式，將得出最小的resulti。程序如下：#include #include #define Max 100int main()int n,m;cinn;cinm;/position代表n+1個(gè)位置,且第n個(gè)點(diǎn)就是第0個(gè)點(diǎn),第一個(gè)點(diǎn)值為0(將赤道平鋪為直線)int positionMax;/touch代表選定的點(diǎn)火位置,time對(duì)應(yīng)touch的點(diǎn)火時(shí)刻int touchMax,timeMax;int i,j;for(i=0;ipositioni;for(i=0;itouchi;for(i=0;itimei;/速度int velocity;cinvel

12、ocity;/輸出結(jié)果int resultMax;/最小距離距離,中間結(jié)果的時(shí)刻int length,temp;/對(duì)于每個(gè)點(diǎn)探討它的起火時(shí)刻for(i=0;in;i+)/比較每個(gè)點(diǎn)火處j的地方蔓延到點(diǎn)i的時(shí)刻for(j=0;jm;j+)/初始化resultiif(j=0)resulti=abs(touch0-positioni)/velocity+time0;else/挑選j到i兩個(gè)方向的較小距離,positionn指的就是赤道的長(zhǎng)度length=abs(touchj-positioni)temp)resulti=temp;for(i=0;in;i+)coutresulti ;return 0

13、;5.釣魚問(wèn)題問(wèn)題描述： 某人有h小時(shí)的時(shí)間想釣到數(shù)量最多的魚。這時(shí)他已經(jīng)在一條路邊，從他所在的地方開(kāi)始，放眼望去，n個(gè)魚場(chǎng)一字排開(kāi)，編號(hào)依次是1,2,n。他已經(jīng)知道，從魚場(chǎng)i走到魚場(chǎng)i+1需要花ti分鐘；他在魚場(chǎng)i釣魚，第一個(gè)5分鐘可釣到重fi的魚；若他繼續(xù)在魚場(chǎng)i釣魚，每過(guò)5分鐘，魚量將減少di。請(qǐng)你給他設(shè)計(jì)一個(gè)最佳釣魚方案。算法思想：貪心算法問(wèn)題描述： 某人有h小時(shí)的時(shí)間想釣到數(shù)量最多的魚。這時(shí)他已經(jīng)在一條路邊，從他所在的地方開(kāi)始，放眼望去，n個(gè)魚場(chǎng)一字排開(kāi)，編號(hào)依次是1,2,n。他已經(jīng)知道，從魚場(chǎng)i走到魚場(chǎng)i+1需要花ti分鐘；他在魚場(chǎng)i釣魚，第一個(gè)5分鐘可釣到重fi的魚；若他繼續(xù)在魚

14、場(chǎng)i釣魚，每過(guò)5分鐘，魚量將減少di。請(qǐng)你給他設(shè)計(jì)一個(gè)最佳釣魚方案。思想：貪心算法把每釣5分鐘魚稱為釣一次魚。首先枚舉這個(gè)人需要走過(guò)的池塘的數(shù)目X，即從池塘1走到池塘X。減去路上花去的時(shí)間T=sum(Ti) i=1.X-1，這樣我們可以認(rèn)為這個(gè)人能從一個(gè)池塘瞬間轉(zhuǎn)移到另一個(gè)池塘，即在任意一個(gè)時(shí)刻都可以在池塘1到池塘X中任選一個(gè)釣一次魚(很重要)。每次選擇魚最多的池塘釣一次魚。對(duì)于每個(gè)池塘來(lái)說(shuō)，由于在任何時(shí)候魚的數(shù)目只和這個(gè)人在該池塘里釣魚的次數(shù)有關(guān)，和釣魚的總次數(shù)無(wú)關(guān)，所以這個(gè)策略是最優(yōu)的。假設(shè)一共允許釣k次魚，那么每次在N個(gè)池塘中選擇魚最多的一個(gè)釣。總的時(shí)間復(fù)雜度為O(kn2)。結(jié)題步驟如下

15、：1.在枚舉了走過(guò)的池塘數(shù)目下，分別計(jì)算(總時(shí)間s-花在路上的時(shí)間t)/5=times就是釣魚的次數(shù)。2.首先選取當(dāng)前池塘魚數(shù)最多的池塘，然后可掉魚數(shù)max+魚數(shù)，然后次數(shù)減一，當(dāng)池塘中的魚0時(shí)賦值為0，并退出本次枚舉，或者次數(shù)為0時(shí)，退出本次枚舉，然后記錄魚數(shù)。如果還有次數(shù)，但是沒(méi)有魚了，把剩余次數(shù)加在第一個(gè)池塘。#includeusing namespace std;/f為每個(gè)池塘的魚數(shù)，d為每次減少的條數(shù)，t為路上花費(fèi)的時(shí)間int n,h,f30,f130,d30,t30;/用來(lái)查找當(dāng)前魚數(shù)最多的池塘int chazhao(int n)int i,falg=1;for(i=1;i=n;i

16、+)if(ffalgfi)falg=i;return falg;int main()int i,j,max,Max,falg,time,times;int count30,count130;/記錄每個(gè)湖釣的次數(shù)cout輸入總的池塘數(shù)endl;while(scanf(%d,&n)!=EOF&n)cout輸入小時(shí)：endl;scanf(%d,&h);Max=-1;memset(count1,0,sizeof(count1);memset(f,0,sizeof(f);memset(d,0,sizeof(d);memset(t,0,sizeof(t);/數(shù)據(jù)的輸入cout輸入每個(gè)池塘的魚數(shù)endl;f

17、or(i=1;i=n;i+)scanf(%d,&fi);f1i=fi;/f1用來(lái)保存每個(gè)魚塘的魚數(shù)么cout輸入每個(gè)池塘的減少的魚數(shù)endl;for(i=1;i=n;i+)scanf(%d,&di);cout輸入每個(gè)池塘的行走時(shí)間endl;for(i=1;in;i+)scanf(%d,&ti);for(i=1;i=n;i+)/依次枚舉貪心time=0;/花在路上的總時(shí)間max=0;memset(count,0,sizeof(count);for(j=1;j=i;j+)time+=tj-1*5;times=(h*60-time)/5;/可釣魚的次數(shù)if(times=0)/如果本次釣魚次數(shù)為0，則

18、結(jié)束本次枚舉continue;while(1)falg=chazhao(i);/找出本次枚舉中，每次選擇當(dāng)前魚數(shù)最多的池塘。if(ffalg=0)/如果最多池塘的魚數(shù)也小于等于0了，則也同樣跳出本次枚舉。break;max+=ffalg;/這個(gè)是在本次枚舉中，每選擇一次就要把釣到的魚加起來(lái)。countfalg+;/記錄每個(gè)池塘釣魚的次數(shù)times-;ffalg-=dfalg;if(ffalg0)ffalg=0;if(times=0)/如果次數(shù)等于0了，則跳出本次枚舉break;if(times)/這里是因?yàn)椋€有可以釣魚的次數(shù)，但是因?yàn)槌靥翛](méi)有魚了。/*min=1;for(j=2;j=i;j+)if(countmincountj)min=