还剩9页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
卑献新华冷的ANHUI XINHUA1NIVBRS1TY算法分析与设计大作业信科12班级:IMS姓名:学1242155105号:完成日期:指导教2015-6-4师:序号选定题目所用算法设计技术1数字三角形问题动态规划2集合划分问题分治法3回溯法求子集问题评分:
3、求子集问题
一、问题描述给定一个正整数集合X二{X1,X2,…,xj和一个正整数y,设计回溯算法,求集合X的一个子集Y,使得丫中元素之和等于y
二、实验内容与实验步骤对于给定集合*[皿={2,1,3,4,2}和正整数12,用回溯算法求得其子集,使子集中元素之和等12,并且记录搜索到第几个元素
三、实验环境Ui该问题为求子集问题解分量的和小于y为剪枝函数当搜索到结点,并且解分量的和等于y时,找到问题的解
五、问题解决
1.X={x1,x2,x
3.......xn},sum=O,y={}为解向量,初始化为全0;
2.k=0;
3.while k=0y[k]=y[k]-1;
3.2如果y[k]=1||y[k]=0kN
3.
2.1sum=sum+y[k]x[k]:0;
4.
2.2如果sum=y{break;},找到解,到步骤
45.
2.3否如此
3.
2.
3.1如果sumn{k++;},搜索下一个
3.
2.
3.2否如此sum=sum-y[k]x[k]:0;
3.3否如此回溯
3.
3.1sum=sum-y[k]x[k]:0;y[k]=2;sum=sum-y[k]x[k]:0;大作业报告
1、数字三角形问题
一、问题描述对于给定的由n行数字组成的数字三角形,计算从三角形的底至顶的路径经过的数字和的最大值如738810274445265
二、实验内容与实验步骤实验内容输入数据的第1行是数字三角形的行数n,1=n=100o接下来n行是数字三角形各行中的数字所有数字在0—99之间实验步骤
1、首先证明该问题满足最优化原理最优化原理一个最优化策略具有这样的性质,不论过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略简而言之,一个最优化策略的子策略总是最优的
2、建立动态规划函数
3、填表
三、实验环境Window系统,vc++
6.0软件么!由观察数字三角形可知,从数字三角形的顶层出发,下一层选择向左还是向右取决于两个4层数字三角形的最大数字和,而对于第四层的决定取决于第三层的最大数字和,依次类推,可知该问题是多阶段决策最优化问题,并且划分出来的子问题是相互重叠的,所以该问题采用动态规划法解决动态规划与分治法相似,把问题分解按层次分成子问题,直到可以直接求解的子问题,然后一级一级地向上求解与分治法的出别在于动态规划适用有许多重复子问题出现的问题,它保存已求出问题的解3838810—-►811027442747444526545265265一个五层数字三角形子问题〔1〕子问题〔2〕
五、问题解决写出解决方法〔1〕根据对问题的分析,
71、证明S,S1,S
2...Sn,t是从S到t的一条数字和最大的路径,从源点S开始,设从S到下一段的顶点S1已经求出,如此问题转化为求从S1到t的数字和最大的路径,显然S1,S2,...Sn,t一定构成一条从S1到t的数字和最大值的路径,如假如不然,设S1,“,r
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初始化452652你在调试过程中发现了怎样的问题?又做了怎样的改良答〔a〕在代码编译成功后,显示屏上无任何提示语,让人有点不知所措,感觉设计的不太人性化,于是在代码中又添加了一些提示语句,使其更容易理解和操作〔b〕算法设计比拟简单,运行结果没有显示路径,所以还有待研究3描述你在进展实现时,主要的函数或操作内部的主要算法;分析这个算法的时、空复杂度答主要算法i ntfunc{i nt i,j;fori=n-1;i=1;i―f j=1;j=i;j++orifa[i+1][j]a[i+1][j+1]a[i][j]+=a[i+1][j];else a[i][j]+=a[i+1][j+1];}return a
[1]
[1];1该段代码是程序的核心局部,可以根据此代码进展填表算法复杂度:算法n0r2£
六、实验结果总结睡理矮整角形诵:*C:\Users\Adm inistrator\Desktop\Debug\l.exe输274445265最大值为30Press anykey tocont;±nue
七、附录与源程序#i ncIudei ostreamusingnamespace std;const i nt M=100;i nta[M][M];i ntfunc0for i=n-1;i=1;i——forj=1;j=i;j-F+if a[i+1][j]a[i+1][j+1]a[i][j]+=a[i+1][j];else a[i][j]+=a[i+1][j+1];return a
[1]
[1];i ntma in int i,j,max;cout“请输入行数”;cout”请输入数字三角形:\n”;for i=1;i=n;i++for产1;j=i;j++cin a[i][j];»max=func;cout“最大值为max endl;«return0;实睑参考的资料【1】C++面向对象程序设计清华大学
[2]算法分析与设计〔第二版〕清华大学
2、集合划分问题
一、问题描述给定正整数n,计算出n个元素的集合{1,2,…,n}可以划分为多少个不同的非空子集
二、实验内容与实验步骤n个元素的集合{1,2,n}可以划分为假如干非空子集例如,当n=3时,集合{1,2,3,4}可以划分为5个不同的非空子集
三、实验环境Ui分析要解决的问题,给出你的思路,可以借助图表等辅助表达答该问题采用的是分治法解决的,即将一个规模为n的问题分解为k个规模较小的子问题,这些子问题相互独立且与原问题性质一样求出子问题的解,就可得到原问题的解分治法的求解过程由三个阶段组成
1、划分
2、求解子问题
3、合并通过大量实践发现,在用分治法设计算法时,最好使子问题的规模大致一样
五、问题解决〔1〕根据对问题的分析,写出解决方法本算法实现采用分治法思想,f n,m=f n-1,m-1+m*f n-1,m,设n个元素的集合可以划分为千n,m个不同的由m个非空子集组成的集合如果求3个元素的集合能够划分多少非空子集,可将问题分解为求两个元素的集合划分问题,进而分解为一个元素的集合划分问题,显然一个元素的集合只能划分成一个非空子集,而f〔2,1〕如此代表两个元素分解成一个非空子集的个数,即{1,2},所以求得f〔2,1〕为1,进而根据递归关系式得到2个元素的的集合划分情况,同理得到3个元素的集合划分情况〔2〕主要算法i ntpute_beI Ii ntrow,i ntpos it ionif row—1return1;if row==2position=1return1;e Iseif posit ion==1return pute_beI Irow-1,row-1;e Isereturn pute_beI Irow,pos ition-1+pute_beI Irow-1,position-1;}
六、实验结果总结LC:\Users\Administrator\Desktop\Debug\l.exewplease inputa number.3the resale is5Press anykey tocontinue
7、附录与源程序#i ncIudei ostreamusi ngnamespace std;i ntpute_beI Ii ntrow,i ntpos ition{if row-1return1;if row==2position=1return1;e Iseif position==1return pute_beI Irow-1,row-1;e Isereturn pute_beI Irow,position-1+pute_beI Irow-1,position-1;}intma in{int n=0;int sum;cout pI easei nputa number.H endI;««c in n;»sum=pute_belIn,n;cout ntheresu Ieissum endI;«««。