最新分治法实验报告范文模板 10页.docx
- 文档编号:4352008
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:7
- 大小:16.15KB
最新分治法实验报告范文模板 10页.docx
《最新分治法实验报告范文模板 10页.docx》由会员分享,可在线阅读,更多相关《最新分治法实验报告范文模板 10页.docx(7页珍藏版)》请在冰点文库上搜索。
最新分治法实验报告范文模板10页
本文部分内容来自网络整理,本司不为其真实性负责,如有异议或侵权请及时联系,本司将立即删除!
==本文为word格式,下载后可方便编辑和修改!
==
分治法实验报告
篇一:
算法实验报告一分治法实验
算法实验报告一分治法实验
一、实验目的及要求
利用分治方法设计大整数乘法的递归算法,掌握分治法的基本思想和算法设计的基本步骤。
要求:
设计十进制的大整数乘法,必须利用分治的思想编写算法,利用c语言(或者c++语言)实现算法,给出程序的正确运行结果。
(必须完成)
设计二进制的大整数乘法,要求利用分治的思想编写递归算法,并可以实现多位数的乘法(利用数组实现),给出程序的正确运行结果。
(任选)
二、算法描述
1、
输入两个相同位数的大整数u,v
输出uv的值
判断大整数的位数i;
w=u/10^(i/2);
y=v/10^(i/2);
x=u-w*10^(i/2);
z=v-y*10^(i/2);
然后将w,x,y,z代入公式求得最后结果
uv=wy10^i+((w+x)(y+z)-wy-xz)10^(i/2)+xz
三、调试过程及运行结果
在实验中我遇到的问题:
原来以为这两个大整数的位数不同,结果题目要求是相同位数的大整数在写10的多少次方时,写的是10^(i/2),10^(i),结果不对,我就将它改成了for循环语句
四、实验总结
在本次实验中,我知道了分治算法,以及分治算法的基本思想。
我还掌握了编写大整数乘法的算法与步骤,以及如何修改在编写程序时遇到的问题。
五、附录(源程序代码清单)
1、#include
intweishu(intx)
{
inti;
while(x!
=0)
{
x=x/10;
i++;
}
returni;
}
voidmain()
{
intu,v;
cout<<"输入两个位数相同的大整数:
"< cin>>u; cin>>v; inti,j,m,n; intp,x,y,z,w; inta=1; intb=1; i=weishu(u); for(intk=1;k<=i;k++) { a=a*10; } for(intq=1;q<=i/2;q++) { b=b*10; } w=u/b; y=v/b; x=u-w*b; z=v-y*b; p=w*y*a+((w+x)*(y+z)-w*y-x*z)*b+x*z; cout< } 教师评语: 成绩: √优良中及格不及格 算法实验报告二动态规划法实验 一、实验目的及要求 利用动态规划方法设计背包问题算法,掌握动态规划法的基本思想和算法设计的基本步骤。 要求: 设计0/1背包问题的动态规划算法,要求输出背包内物品的最大价值以及选入背包的物品种类。 利用c语言(c++语言)实现算法,给出程序的正确运行结果。 二、算法描述 输入: 各物品的体积、价值,背包容量 输出: 放入背包的物品的体积,放入物品的最大价值 fori<-0ton V[i,0]<-0 endfor forj<-0toC V[j,0]<-0 endfor fori<-1ton forj<-1toC V[I,j]<-V[i-1,j] if(si<=jandV[i-1,j-si]+vi)>V[i,j]) V[i,j]<-V[i-1,j-si]+vi item[j]=i endfor endfor fori<-Cdownto1(i=i-item[i]的体积) printf(s[item[i]]) endfor returnV[n,C] 三、调试过程及运行结果 在定义数组时数组的大小不能是变量,也不能定义一个变量从键盘输入一个常数,再用这个变量定义数组,只能直接用常量定义数组或者用宏定义的量来定义数组。 在进行多个for循环时,不管他们之间有没有关系,循环中定义的变量不能一样。 在定义数组V[][]时,数组大小必须是n+1、C+1。 四、实验总结 在进行本次实验时,我知道了背包程序的算法以及它的基本的意思,算法想要做什么。 我还掌握了一些在学C++时没有注意到的一些小问题。 如在定义数组时数组的大小不能是变量,也不能定义一个变量从键盘输入一个常数,再用这个变量定义数组,只能直接用常量定义数组或者用宏定义的量来定义数组。 在进行多个for循环时,不 管他们之间有没有关系,循环中定义的变量不能一样。 在定义数组V[][]时,数组大小必须是n+1、C+1。 五、附录(源程序代码清单) #include #definen10 #defineC12 voidmain() { ints[n],v[n]; intV[n+1][C+1]; intitem[C]; cout<<"物品的体积: "< for(intf=0;f cin>>s[f]; cout<<"物品的价值: "< for(inth=0;h cin>>v[h]; for(intk=0;k<=n;k++) { V[k][0]=0; } for(intm=0;m<=C;m++) { V[0][m]=0; } for(inti=1;i<=n;i++) { for(intj=1;j<=C;j++) { V[i][j]=V[i-1][j]; if(s[i]<=j&&V[i-1][j-s[i]]+v[i]>V[i][j]){ V[i][j]=V[i-1][j-s[i]]+v[i];item[j]=i; } } } cout<<"放入背包的物品的体积: "< { cout< cout< } cout<<"背包的最大价值: "; cout< } 教师评语: 成绩: √优良中 及格不及格 篇二: 分治算法实验报告 本科学生综合性实验报告 姓名___刘春云学号_0103918__ _ 专业__软件工程__班级_103__ 实验项目名称_二分搜索问题的分治算法实验指导教师及职称_____赵晓平_____开课学期201X 至_201X学年_3_学期 上课时间201X年2月18日 学生实验报告 (1) 一、问题描述 二分查找又称折半查找,即在一串已排好序的需要处理的数据中多次用折半的方法查找出要搜索出的数据。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 最新分治法实验报告范文模板 10页 最新 分治 实验 报告 范文 模板 10
![提示](https://static.bingdoc.com/images/bang_tan.gif)