算法设计与分析报告大作业_第1页
算法设计与分析报告大作业_第2页
算法设计与分析报告大作业_第3页
算法设计与分析报告大作业_第4页
算法设计与分析报告大作业_第5页
已阅读5页,还剩11页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

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

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论