算法设计与分析报告大作业

1、实用标准文案条徽祈华浄兜ANHUI X1INHLJA LWIVKKSITY算法分析与设计大作业精彩文档级:12信科名:郭倩南口号:1242155105完成日期:2015-6-4指导教师:序号选定题目所用算法设计技术1数字三角形问题动态规划2集合划分问题分治法3求子集问题回溯法评分:大作业报告1、数字三角形问题、问题描述 对于给定的由n行数字组成的数字三角形，计算从三角形的底至顶的路径经过 的数字和的最大值。如:、实验内容与实验步骤 实验内容: 输入数据的第1行是数字三角形的行数n，1<=*=100 。接下来n行是数字三角形各行中的数字。所有数字在0.99之间实验步骤:1、首先证明该问题满

2、足最优化原理最优化原理：一个最优化策略具有这样的性质，不论过去状态和决策如何，对 前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之, 一个最优化策略的子策略总是最优的。2、建立动态规划函数3、填表三、实验环境Window7 系统，vc+6.0 软件 四、问题分析 由观察数字三角形可知，从数字三角形的顶层出发，下一层选择向左还是向右取 决于两个4层数字三角形的最大数字和，而对于第四层的决定取决于第三层的最 大数字和，依次类推，可知该问题是多阶段决策最优化问题， 并且划分出来的子 问题是相互重叠的，所以该问题采用动态规划法解决动态规划：与分治法相似，把问题分解按层次分成子问题，直

3、到可以直接求解的 子问题，然后一级一级地向上求解。它保留已求与分治法的出别在于：动态规划适用有许多重复子问题出现的问题,出问题的解。一个五层数字三角形子问题（1）子问题五、问题解决(1) 根据对问题的分析，写出解决办法。1、证明：S,S1,S2,.Sn,t是从S到t的一条数字和最大的路径，从源点 S开始,设从S到下一段的顶点S1已经求出，则问题转化为求从 S1到t的数字和最大的路径，显然S1，S2，Sn,t 定构成一条从S1到t的数字和最大值的路径,如若不然，设S1，r1,r2,.rq,t是一条数字和最大的路径，则S,S1，r1,r2,.rq,t的路径经过数字和的最大值比S,S1, S2, .

4、Sn,t的路径数字和更大，从而导致矛盾，所以数字三角形问题满足最优性原理。2、动态规划函数:aij+=ai+1jaij+=ai+1j+1当 ai+1j>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) 你在调试过程中发现了怎样的问题？又做了怎样的改进?答：(a)在代码编译成功后，显示屏上无任何提示语，让人有点不知所措,感觉设计的不太人性化，于是在代码中又添加了一些提示语句， 使其更容易理

5、解和操作(b)算法设计比较简单，运行结果没有显示路径，所以还有待研究(3) 描述你在进行实现时，主要的函数或操作内部的主要算法；分析这个算法的时、空复杂度答：主要算法:int func()int i,j;for(i=n-1;i>=1;i-)for(j=1;jv=i;j+)if(ai+1j>ai+1j+1) aij+=ai+1j;else aij+=ai+1j+1;return a11;该段代码是程序的核心部分，可以根据此代码进行填表。算法复杂度：0(T(n) O(nA2)六、实验结果总结回C：VLls0rsAd!mini：strato rDesktoplDeb u形角-b ”u最大

6、值沟玄匕J.5Pi*?r*T any Wpy rn (rnnt;1r»u*=f七、附录及源程序#in elude <iostream>using n ames pace 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()coutvv"请输入行数："cin>>n;cout

7、vv"请输入数字三角形:n"for(i=1;i<=n ;i+)for(j=1;jv=i;j+)cin> >aij;max=fu nc();coutvv"最大值为"vvmaxvvendl;return 0;实验参考的资料【1】C+面向对象程序设计清华大学出版社【2】算法分析与设计（第二版）清华大学出版社2、集合划分问题、问题描述给定正整数n,计算出n个元素的集合1 , 2，n可以划分为多少个不同的非空子集。二、实验内容与实验步骤n个元素的集合1 , 2，n可以划分为若干非空子集。例如，当n=3时,集合1, 2 , 3, 4可以划分为5个不

8、同的非空子集。三、实验环境Window7 系统，vc+6.0 软件四、问题分析 分析要解决的问题，给出你的思路，可以借助图表等辅助表达答：该问题采用的是分治法解决的，即将一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题性质相同。 求出子问题的解，就 可得到原问题的解 分治法的求解过程由三个阶段组成：1、划分2、求解子问题3、合并 通过大量实践发现，在用分治法设计算法时，最好使子问题的规模大致相同。五、问题解决(1)根据对问题的分析，写出解决办法。本算法实现采用分治法思想，f(n,m)=f(n-1,m-1)+m*f(n-1,m),设n个元素的集合可以划分为f(n,m)个

9、不同的由m个非空子集组成的集合。如果求 3个元素的集合能够划分多少非空子集，可将问题分解为求两个元素的集合划分问题，进而分解为一个元素的集合划分问题， 显然一个元素的集合只能划分成一个非空子集，而f(2,1)则代表两个元素分解成一个非空子集的个数,即1,2，所以求得f(2,1 )为1，进而根据递归关系式得到2个元素的的集合划分情况，同理得到3个元素的集合划分情况。(2)主要算法 int compu te_bell(i nt row,i nt po siti on)if(row=1)return 1;if(row = 2 && po siti on =1)return 1;els

10、eif(p ositi on = 1)return comp ute_bell(row-1,row-1);elsereturn comp ute_bell(row, po sitio n-1)+comp ute_bell(row-1, positio n-1);六、实验结果总结Cl ' C:Use Ad rn i n i itraitorDe& ktopDeb ugl, exe"the PCEule is 5 Press anp key to continue7、附录及源程序 #in elude <iostream> using n ames pace s

11、td;int compu te_bell(i nt row,i nt po siti on)if(row=1)return 1;if(row = 2 && po siti on =1)return 1;elseif(p ositi on = 1)return comp ute_bell(row-1,row-1);elsereturn comp ute_bell(row, po sitio n-1)+comp ute_bell(row-1, positio n-1);int mai n()int n=0;int sum;coutvv" pl ease input a n

12、u mber."vve ndl;cin>>n;sum=co mp ute_bell( n,n);cout<<"the resule is "<<sum<<e ndl;3、求子集问题、问题描述 给定一个正整数集合X=X1,X2,Xn和一个正整数y，设计回溯算法，求集合X 的一个子集丫，使得丫中元素之和等于y 二、实验内容与实验步骤 对于给定集合xN=2,1,3,4,2和正整数12 ,用回溯算法求得其子集，使子集中 元素之和等12，并且记录搜索到第几个元素 三、实验环境Window7 系统，vc+6.0 软件 四、问题分

13、析 该冋题为求子集冋题。解分量的和小于y为剪枝函数。当搜索到结点，并且解分量的和等于 y时，找到问题的解。五、问题解决x=x1,x2,x3 xn , sum=O , y= 为解向量，初始化为全 0;k=0;while (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 s

14、um=sum-(yk?xk:0);yk=2;k-;sum=sum-(yk?xk:0);4.输出k六、实验结果总结I I ' C ：U iersA dmi n itorDes kto pDeb ugl. e>fe'21342Ppess any key to continue七、附录及源程序#i nclude viostream.h> const int N=5;int f(int x,i nt y,i nt n)/初始化y, y为所求的集合for(i nt 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;/找到解elseif(sum< n)k+;/ 搜索下一个elsesum=sum-(yk?xk:O);else/ 回溯/sum=sum-(yk?xk:O);yk=2;k-;sum=sum-(yk?xk:O);return k;void mai n()int xN=2,1,3,4,2;int yN; / 解向量in