算法設(shè)計(jì)與分析大作業(yè)

1、算法分析與設(shè)計(jì) 大作業(yè)班 級(jí)： 12信科 姓 名： 郭倩南 學(xué) 號(hào)： 1242155105 完成日期： 2015-6-4 指導(dǎo)教師： 陳 平 序號(hào)選定題目所用算法設(shè)計(jì)技術(shù)1數(shù)字三角形問(wèn)題動(dòng)態(tài)規(guī)劃2集合劃分問(wèn)題分治法3求子集問(wèn)題回溯法 評(píng)分：大作業(yè)報(bào)告1、數(shù)字三角形問(wèn)題一、問(wèn)題描述對(duì)于給定的由n行數(shù)字組成的數(shù)字三角形，計(jì)算從三角形的底至頂?shù)穆窂浇?jīng)過(guò)的數(shù)字和的最大值。如：7 3 8 8 1 0 2 7 4 4 4 5 2 6 5二、實(shí)驗(yàn)內(nèi)容與實(shí)驗(yàn)步驟實(shí)驗(yàn)內(nèi)容:輸入數(shù)據(jù)的第1 行是數(shù)字三角形的行數(shù)n，1<=n<=100。接下來(lái)n行是數(shù)字三角形各行中的數(shù)字。所有數(shù)字在0.99之間實(shí)驗(yàn)步驟:

2、1、 首先證明該問(wèn)題滿足最優(yōu)化原理最優(yōu)化原理：一個(gè)最優(yōu)化策略具有這樣的性質(zhì)，不論過(guò)去狀態(tài)和決策如何，對(duì)前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。簡(jiǎn)而言之，一個(gè)最優(yōu)化策略的子策略總是最優(yōu)的。2、 建立動(dòng)態(tài)規(guī)劃函數(shù)3、 填表 三、實(shí)驗(yàn)環(huán)境Window7系統(tǒng)，vc+6.0軟件 4、 問(wèn)題分析由觀察數(shù)字三角形可知，從數(shù)字三角形的頂層出發(fā)，下一層選擇向左還是向右取決于兩個(gè)4層數(shù)字三角形的最大數(shù)字和，而對(duì)于第四層的決定取決于第三層的最大數(shù)字和，依次類推，可知該問(wèn)題是多階段決策最優(yōu)化問(wèn)題，并且劃分出來(lái)的子問(wèn)題是相互重疊的，所以該問(wèn)題采用動(dòng)態(tài)規(guī)劃法解決 動(dòng)態(tài)規(guī)劃：與分治法相似，把問(wèn)題分解按層次

3、分成子問(wèn)題，直到可以直接求解的子問(wèn)題，然后一級(jí)一級(jí)地向上求解。與分治法的出別在于：動(dòng)態(tài)規(guī)劃適用有許多重復(fù)子問(wèn)題出現(xiàn)的問(wèn)題，它保留已求出問(wèn)題的解。 7 3 8 3 8 8 1 0 8 1 1 0 2 7 4 4 2 7 4 7 4 4 4 5 2 6 5 4 5 2 6 5 2 6 5 一個(gè)五層數(shù)字三角形 子問(wèn)題（1） 子問(wèn)題（2）5、 問(wèn)題解決（1）根據(jù)對(duì)問(wèn)題的分析，寫出解決辦法。1、證明：S,S1,S2,.Sn,t是從S到t的一條數(shù)字和最大的路徑，從源點(diǎn)S開(kāi)始，設(shè)從S到下一段的頂點(diǎn)S1已經(jīng)求出，則問(wèn)題轉(zhuǎn)化為求從S1到t的數(shù)字和最大的路徑，顯然S1，S2，.Sn,t一定構(gòu)成一條從S1到t的數(shù)字

4、和最大值的路徑，如若不然，設(shè)S1，r1,r2,.rq,t是一條數(shù)字和最大的路徑，則S,S1，r1,r2,.rq,t的路徑經(jīng)過(guò)數(shù)字和的最大值比S,S1，S2，.Sn,t的路徑數(shù)字和更大，從而導(dǎo)致矛盾，所以數(shù)字三角形問(wèn)題滿足最優(yōu)性原理。2、動(dòng)態(tài)規(guī)劃函數(shù)： aij+=ai+1j 當(dāng) ai+1j>ai+1j+1 時(shí) aij+=ai+1j+1 當(dāng)ai+1j<=ai+1j+1 時(shí)3、 填表第一行7+23=30第二行3+20=238+13=21第三行8+12=201+12=130+10=10第四行2+5=97+5=124+6=104+6=10初始化45265（2） 你在調(diào)試過(guò)程中發(fā)現(xiàn)了怎樣的問(wèn)題

5、？又做了怎樣的改進(jìn)？ 答：（a）在代碼編譯成功后，顯示屏上無(wú)任何提示語(yǔ)，讓人有點(diǎn)不知所措，感覺(jué)設(shè)計(jì)的不太人性化，于是在代碼中又添加了一些提示語(yǔ)句，使其更容易理解和操作（b）算法設(shè)計(jì)比較簡(jiǎn)單，運(yùn)行結(jié)果沒(méi)有顯示路徑，所以還有待研究（3） 描述你在進(jìn)行實(shí)現(xiàn)時(shí)，主要的函數(shù)或操作內(nèi)部的主要算法；分析這個(gè)算法的時(shí)、空復(fù)雜度答：主要算法：int func() int i,j; for(i=n-1;i>=1;i-) for(j=1;j<=i;j+) if(ai+1j>ai+1j+1) aij+=ai+1j; else aij+=ai+1j+1; return a11;該段代碼是程序的核心部分

6、，可以根據(jù)此代碼進(jìn)行填表。算法復(fù)雜度：O(T(n)O(n2)6、 實(shí)驗(yàn)結(jié)果總結(jié)七、附錄及源程序#include <iostream>using namespace std;const int M=100;int n;int aMM;int func() int i,j; for(i=n-1;i>=1;i-) for(j=1;j<=i;j+) if(ai+1j>ai+1j+1) aij+=ai+1j; else aij+=ai+1j+1; return a11;int main() int i,j,max;cout<<"請(qǐng)輸入行數(shù):"

7、 cin>>n; cout<<"請(qǐng)輸入數(shù)字三角形:n" for(i=1;i<=n;i+) for(j=1;j<=i;j+) cin>>aij; max=func(); cout<<"最大值為"<<max<<endl; return 0;實(shí)驗(yàn)參考的資料【1】C+面向?qū)ο蟪绦蛟O(shè)計(jì) 清華大學(xué)出版社【2】算法分析與設(shè)計(jì)（第二版） 清華大學(xué)出版社2、集合劃分問(wèn)題一、問(wèn)題描述給定正整數(shù)n，計(jì)算出n個(gè)元素的集合1，2，n可以劃分為多少個(gè)不同的非空子集。2、 實(shí)驗(yàn)內(nèi)容與實(shí)驗(yàn)步驟n個(gè)元素的

8、集合1，2，n可以劃分為若干非空子集。例如，當(dāng)n=3時(shí)，集合1，2，3，4可以劃分為5個(gè)不同的非空子集。3、 實(shí)驗(yàn)環(huán)境Window7系統(tǒng)，vc+6.0軟件四、問(wèn)題分析分析要解決的問(wèn)題，給出你的思路，可以借助圖表等輔助表達(dá)答：該問(wèn)題采用的是分治法解決的，即將一個(gè)規(guī)模為n的問(wèn)題分解為k個(gè)規(guī)模較小的子問(wèn)題，這些子問(wèn)題相互獨(dú)立且與原問(wèn)題性質(zhì)相同。求出子問(wèn)題的解，就可得到原問(wèn)題的解分治法的求解過(guò)程由三個(gè)階段組成：1、劃分 2、求解子問(wèn)題3、合并通過(guò)大量實(shí)踐發(fā)現(xiàn)，在用分治法設(shè)計(jì)算法時(shí)，最好使子問(wèn)題的規(guī)模大致相同。5、 問(wèn)題解決（1）根據(jù)對(duì)問(wèn)題的分析，寫出解決辦法。本算法實(shí)現(xiàn)采用分治法思想，f(n,m)=f

9、(n-1,m-1)+m*f(n-1,m),設(shè)n個(gè)元素的集合可以劃分為f(n,m)個(gè)不同的由m個(gè)非空子集組成的集合。如果求3個(gè)元素的集合能夠劃分多少非空子集，可將問(wèn)題分解為求兩個(gè)元素的集合劃分問(wèn)題，進(jìn)而分解為一個(gè)元素的集合劃分問(wèn)題，顯然一個(gè)元素的集合只能劃分成一個(gè)非空子集，而f（2,1）則代表兩個(gè)元素分解成一個(gè)非空子集的個(gè)數(shù)，即1,2，所以求得f（2,1）為1，進(jìn)而根據(jù)遞歸關(guān)系式得到2個(gè)元素的的集合劃分情況，同理得到3個(gè)元素的集合劃分情況。（2）主要算法int compute_bell(int row,int position) if(row=1) return 1; if(row = 2 &a

10、mp;& position =1) return 1; else if(position = 1) return compute_bell(row-1,row-1); else return compute_bell(row,position-1)+ compute_bell(row-1,position-1); 6、 實(shí)驗(yàn)結(jié)果總結(jié)7、附錄及源程序#include <iostream>using namespace std;int compute_bell(int row,int position) if(row=1) return 1; if(row = 2 &&

11、amp; position =1) return 1; else if(position = 1) return compute_bell(row-1,row-1); else return compute_bell(row,position-1)+ compute_bell(row-1,position-1); int main() int n=0; int sum; cout<<"please input a number."<<endl; cin>>n; sum=compute_bell(n,n); cout<<&quo

12、t;the resule is "<<sum<<endl;3、求子集問(wèn)題一、問(wèn)題描述給定一個(gè)正整數(shù)集合X=x1,x2, xn和一個(gè)正整數(shù)y，設(shè)計(jì)回溯算法，求集合X的一個(gè)子集Y，使得Y中元素之和等于y2、 實(shí)驗(yàn)內(nèi)容與實(shí)驗(yàn)步驟對(duì)于給定集合xN=2,1,3,4,2和正整數(shù)12，用回溯算法求得其子集，使子集中元素之和等12，并且記錄搜索到第幾個(gè)元素三、實(shí)驗(yàn)環(huán)境Window7系統(tǒng)，vc+6.0軟件4、 問(wèn)題分析該問(wèn)題為求子集問(wèn)題。解分量的和小于y為剪枝函數(shù)。當(dāng)搜索到結(jié)點(diǎn)，并且解分量的和等于y時(shí)，找到問(wèn)題的解。五、問(wèn)題解決1x=x1,x2,x3xn ，sum=0，y= 為

13、解向量，初始化為全0;2k=0;3while (k>=0) 3.1 yk=yk-1; 3.2 如果(yk=1|yk=0)&&k<N) 3.2.1 sum=sum+(yk?xk:0); 3.2.2 如果(sum=y)break;,找到解，到步驟4 3.2.3 否則 3.2.3.1 如果(sum<n)k+;,搜索下一個(gè) 3.2.3.2 否則 sum=sum-(yk?xk:0); 3.3 否則 回溯 3.3.1 sum=sum-(yk?xk:0); yk=2; k-; sum=sum-(yk?xk:0);4.輸出k六、實(shí)驗(yàn)結(jié)果總結(jié)七、附錄及源程序#include &

14、lt;iostream.h> const int N=5; int f(int x,int y,int n) /初始化y，y為所求的集合 for(int i=0;i<N;i+) yi=2; int k=0; int sum=0; while(k>=0) yk=yk-1; if(yk=1|yk=0)&&k<N) sum=sum+(yk?xk:0); if(sum=n)break;/找到解 else if(sum<n)k+;/搜索下一個(gè) else sum=sum-(yk?xk:0); else/回溯 / sum=sum-(yk?xk:0); yk=2; k-; sum=sum-(yk?xk:0); return k; void main() int xN=2,1,3,4,2; int yN; /解向量 int n=12; /題目要求等于的和 int k=f(x,y,n);/k表示