算法实验报告一 分治法实验 一、实验目的及要求 利用分治方法设计大整数乘法的递归算法，掌握分治法的基本思想和算法设计的基本步骤。
要求：设计十进制的大整数乘法，必须利用分治的思想编写算法，利用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<iostream.h> int weishu(int x) {
int i;
while(x!=0)
{ x=x/10; i++; }
return i; }
void main() {
int u,v;
cout<<输入两个位数相同的大整数:<<endl; cin>>u; cin>>v;
int i,j,m,n; int p,x,y,z,w; int a=1; int b=1; i=weishu(u);
for(int k=1;k<=i;k++) {
a=a*10; }
for(int q=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<<u<<*<<v<<=<<p; }
教师评语： 成绩：√优 良 中 及格 不及格 算法实验报告二 动态规划法实验 一、实验目的及要求 利用动态规划方法设计背包问题算法，掌握动态规划法的基本思想和算法设计的基本步
骤。 要求：设计0/1背包问题的动态规划算法，要求输出背包内物品的最大价值以及选入背
包的物品种类。利用c语言（c++语言）实现算法，给出程序的正确运行结果。 二、算法描述
输入：各物品的体积、价值，背包容量 输出：放入背包的物品的体积，放入物品的最大价值 for i<-0 to n v[i,0]<-0 end for
for j<-0 to c v[j,0]<-0 end for
for i<-1 to n for j<-1 to c v[i,j]<-v[i-1,j]
if(si<=j and v[i-1,j-si]+vi)>v[i,j] ) v[i,j]<-v[i-1,j-si]+vi item[j]=i end for
end for
for i<-c downto 1 (i=i-item[i]的体积) printf(s[item[i]]) end for
return v[n,c]
三、调试过程及运行结果 在定义数组时数组的大小不能是变量，也不能定义一个变量从键盘输入一个常数，再用
这个变量定义数组，只能直接用常量定义数组或者用宏定义的量来定义数组。 在进行多个for循环时，不管他们之间有没有关系，循环中定义的变量不能一样。 在定义数组v[][]时，数组大小必须是n+1、c+1。 四、实验总结 在进行本次实验时，我知道了背包程序的算法以及它的基本的意思，算法想要做什么。我还掌握了一些在学c++时没有注意到的一些小问题。如在定义数组时数组的大小不能是变量，也不能定义一个变量从键盘输入一个常数，再用这个变量定义数组，只能直接用常量定义数组或者用宏定义的量来定义数组。 在进行多个for循环时，不管他们之间有没有关系，
循环中定义的变量不能一样。 在定义数组v[][]时，数组大小必须是n+1、c+1。 五、附录（源程序代码清单） #include<iostream.h> #define n 10 #define c 12 void main() {
int s[n],v[n]; int v[n+1][c+1]; int item[c];
cout<<物品的体积:<<endl; for(int f=0;f<n;f++)
cin>>s[f]; cout<<物品的价值:<<endl; for(int h=0;h<n;h++) cin>>v[h];
for(int k=0;k<=n;k++) {
v[k][0]=0; }
for(int m=0;m<=c;m++) {
v[0][m]=0; }
for(int i=1;i<=n;i++) {
for(int j=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<<放入背包的物品的体积:<<endl; for(int
p=c;p>=1;p=p-s[item[p]]) {
cout<<s[item[p]]; cout<<endl; }
cout<<背包的最大价值:; cout<<v[n][c]<<endl; }
教师评语： 成绩：√优 良 中 及格 不及格篇二：分治算法实验报告 本科学生综合性实验报告 姓名＿＿＿ 刘春云 学号＿ 0103918＿＿ ＿
专 业＿ ＿软件工程＿＿ 班级＿ 103＿ ＿ 实验项目名称＿二分搜索问题的分治算法实验 指导教师及职称＿＿＿＿＿赵晓平＿＿
＿ ＿ ＿ 开课学期 2011 至＿ 2012 学年＿ 3 ＿学期 上课时间 2012 年 2 月 18 日 学生实验报告（1） 一、问题描述 二分查找又称折半查找，即在一串已排好序的需要处理的数据中多次用折半的方法查找出要搜索出的数据。 二、解题思路 首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。 三、算法描述
用一个数组来存储数据，具体的结构体为： typedef struct list { double elem[100]; int length; }list；其中length是数据的总个数 比较表中间位置记录的关键字与查找关键字的大小，逐步缩小查找范围 实现代码为： while(low<high)
{ mid=(low+high)/2; if(l.elem[mid]==key) { } else if(l.elem[mid]<key) low=mid;
outfile<<你所要搜索的数据在第<<mid+1<<个位置<<endl; break; else
high=mid;
if(high==low+1) {
outfile<<抱歉!你所要搜索的数据不在你所输入的数据中break; <<endl;
范围 }
}在上段代码中low表示搜索区间的最小范围，hiah则表示搜索区间的最大 在代码中出现的int init_list(list&l)是一个初始函数用于从input.txt文件中读入
数据并判断数据是否升序排列。int search(int low,int high,list&l)是查找函数用于折半查找。
四、算法实现 #include <iostream> #include<fstream> using namespace std; typedef struct list {
double elem[100]; int length; }list; int init_list(list&l)//初始化函数 { } int search(int low,int high,list&l)//查找函数 { int search(int low,int high,list&l); int n=0; ifstream infile; cout<<请输入数据(必须是从小到大排序的)<<endl;
infile.open(input.txt,ios::in); ofstream outfile; outfile.open(output.txt,ios::app); while(infile>>l.elem[n])//从文件中输入已排序数组，直到文件中无数据读取 n++; infile.close(); l.length=n; for(int i=0;i<l.length-1;i++)//判断输入的数据是否有序 { if(l.elem[i]>l.elem[i+1]) { } outfile<<朋友请不要玩我!<<endl; return 0; }//判断输入的数据是否有序 cout<<二分查找中......<<endl; search(0,l.length-1,l); return 1;
ofstream outfile;
outfile.open(output.txt,ios::app); int mid=0;//中点篇三：分治法实验报告 石家庄经济学院
《算法设计与分析》实验报告 姓 名： 班 级： 学 号： 指导教师：
完成日期： 一、实验名称
分治法实验报告
