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

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

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

3、分成子問題，直到可以直接求解的子問題，然后一級一級地向上求解。與分治法的出別在于：動態(tài)規(guī)劃適用有許多重復子問題出現(xià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 一個五層數(shù)字三角形 子問題（1） 子問題（2）5、 問題解決（1）根據(jù)對問題的分析，寫出解決辦法。1、證明：S,S1,S2,.Sn,t是從S到t的一條數(shù)字和最大的路徑，從源點S開始，設(shè)從S到下一段的頂點S1已經(jīng)求出，則問題轉(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)過數(shù)字和的最大值比S,S1，S2，.Sn,t的路徑數(shù)字和更大，從而導致矛盾，所以數(shù)字三角形問題滿足最優(yōu)性原理。2、動態(tài)規(guī)劃函數(shù)： aij+=ai+1j 當 ai+1j>ai+1j+1 時 aij+=ai+1j+1 當ai+1j<=ai+1j+1 時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)試過程中發(fā)現(xiàn)了怎樣的問題

5、？又做了怎樣的改進？ 答：（a）在代碼編譯成功后，顯示屏上無任何提示語，讓人有點不知所措，感覺設(shè)計的不太人性化，于是在代碼中又添加了一些提示語句，使其更容易理解和操作（b）算法設(shè)計比較簡單，運行結(jié)果沒有顯示路徑，所以還有待研究（3） 描述你在進行實現(xiàn)時，主要的函數(shù)或操作內(nèi)部的主要算法；分析這個算法的時、空復雜度答：主要算法：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ù)此代碼進行填表。算法復雜度：O(T(n)O(n2)6、 實驗結(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<<"請輸入行數(shù):"

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

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

9、(n-1,m-1)+m*f(n-1,m),設(shè)n個元素的集合可以劃分為f(n,m)個不同的由m個非空子集組成的集合。如果求3個元素的集合能夠劃分多少非空子集，可將問題分解為求兩個元素的集合劃分問題，進而分解為一個元素的集合劃分問題，顯然一個元素的集合只能劃分成一個非空子集，而f（2,1）則代表兩個元素分解成一個非空子集的個數(shù)，即1,2，所以求得f（2,1）為1，進而根據(jù)遞歸關(guān)系式得到2個元素的的集合劃分情況，同理得到3個元素的集合劃分情況。（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、 實驗結(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、求子集問題一、問題描述給定一個正整數(shù)集合X=x1,x2, xn和一個正整數(shù)y，設(shè)計回溯算法，求集合X的一個子集Y，使得Y中元素之和等于y2、 實驗內(nèi)容與實驗步驟對于給定集合xN=2,1,3,4,2和正整數(shù)12，用回溯算法求得其子集，使子集中元素之和等12，并且記錄搜索到第幾個元素三、實驗環(huán)境Window7系統(tǒng)，vc+6.0軟件4、 問題分析該問題為求子集問題。解分量的和小于y為剪枝函數(shù)。當搜索到結(jié)點，并且解分量的和等于y時，找到問題的解。五、問題解決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+;,搜索下一個 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六、實驗結(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+;/搜索下一個 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表示