算法设计分析.docx
《算法设计分析.docx》由会员分享，可在线阅读，更多相关《算法设计分析.docx（20页珍藏版）》请在冰点文库上搜索。
算法设计分析
武汉科技大学城市学院
算法分析与设计》
上机实验报告
课程名称
数据结构课程设计信息工程学部
学
部
专
业
软件工程
班
级
软件三班
姓
名
洪汉山
学
号
201510159320
指导教师
林晓丽
职
称
副教授
2017年11月15日
实验1分治法
（一）2
1.1实验目的2
1.2实验内容及要求2
1.3算法设计思路及步骤2
1.4程序代码3
1.5运行结果截图7
实验2分治法
（二）_分金块8
2.1实验目的8
2.2实验内容及要求8
2.3算法设计思路及步骤8
2.4程序代码9
2.5运行结果截图11
实验三动态规划_数字三角形11
3.1实验目的11
3.2实验内容及要求11
3.3算法设计思路及步骤12
3.4程序代码12
3.5运行结果截图14
实验四购物券问题15
4.1实验目的15
4.2实验内容及要求15
4.3算法设计思路及步骤15
4.4程序代码16
4.5运行结果截图17
总结18
实验1分治法
（一）
1.1实验目的
1）掌握分治法的基本思想和求解步骤。
2）理解分治法的精髓，即如何分？
如何治？
才能使得算法效率更高。
3）通过实例编程，掌握运用分治法来解决实际问题的方法。
1.2实验内容及要求
问题一：
二分查找
给定已排好序的n个元素s1,⋯,sn，现要在这n个元素中找出一特定元素x要求采用分治法求解，即将问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题；采用递归和非递归两种方式实现。
问题二：
合并排序
设待排序列A={8，3，2，9，7，1，5，4}，采用合并排序算法对序列进行排序。
问题三：
快速排序
理解快速排序的思想，实现快速排序。
样例如：
49，38，65，97，76，13，27。
1.3算法设计思路及步骤
二分查找：
分为二分递归和二分非递归二分非递归算法思路：
要用到循环，在循环中开始标记和结束标记不断改变，循环的判断条件就是开始标记是否在结束标记之前。
若查找成功则返回中间元素标记，若查找失败则返回-1。
所以非递归算法需要三个参数：
数组起始地址、数组长度以及要查找的数字。
二分递归算法思路：
判断条件是一样的，在调用自身的过程中，要改变的参数要么是开始标记，要么是结束标记。
所以对于递归算法，需要四个参数：
数组起止地址、要查找的数字、开始标记与结束标记。
合并排序算法思路：
原理,把原始数组分成若干子数组,对每一个子数组进行排序,继续把子数组与子数组合并,合并后仍然有序,直到全部合并完,形成有序的数组。
快速排序算法思路：
快速排序是找出一个元素（理论上可以随便找一个）作为基准（pivot）,然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值都不小于基准值，如此作为基准的元素调整到排序后的正确位置。
递归快速排序，将其他n-1个元素也调整到排序后的正确位置。
最后每个元素都是在排序后的正确位置，排序完成。
1.4程序代码
//非递归实现
intbinarySearch1（int*s,intlow,inthigh,intx）{
intmid=0;
while（low<=high）
{
mid=（low+high）/2;
if（x==s[mid]）
{
returnmid;
}
elseif（x>s[mid]）
{
low=mid+1;
}
else
{
high=mid-1;
}
}return-1;
//递归实现
intbinarySearch2（int*s,intlow,inthigh,intx）
{
intmid=（low+high）/2;
intindex=0;//设置一个指针
if（low<=high）
{
if（x==s[mid]）
{returnmid;
}elseif（x>s[mid]）
{index=binarySearch2（s,mid+1,high,x）;
}
else
{
index=binarySearch2（s,low,mid-1,x）;
}
}
else
return-1;
returnindex;
}
intmain（）
{
ints[]={1,3,5,7,12,15,17,19,24};
intlen=sizeof（s）/sizeof（int）;//计算数组s中有多少个元素、长度
为多少
intx=19;
intindex=binarySearch2（s,0,len-1,x）;
if（index==-1）
printf（"查找的数x=%d,这个数在已知数组的元素中不存在。
\n",x,index）;
else
printf（"查找的数x=%d,这个数在已知数组的元素中下标为%d。
\n",x,index）;
}
合并排序：
#include
#defineN10
//用递归实现归并排序
voidmerge（intX[],intlow,intmid,inthigh）{
inta[N];//定义一个临时缓冲区
inti=low,j=mid+1,k=low;//k是a的下标，i、j分别为a[low...mid]和a[mid+1...high]的下标
for（;i<=mid&&j<=high;k++）//依次比较两个子序列中数据元素的
大小
{
if（X[i]<=X[j]）//
a[k]=X[i++];//else
a[k]=X[j++];//}while（i<=mid）//a[k++]=X[i++];while（j<=high）//a[k++]=X[j++];
将较小的数移入缓冲区
将a[low...m]中的记录放入a中
将a[m+1...high]中的记录放入a中
将a[low...m]余下部分复制到a
将a[m+1...high]余下部分复制到a
for（k=low;k<=high;k++）//
X[k]=a[k];
}
voidMergeSort（intX[],intlow,inthigh）//{
intmid;
if（low{
mid=（low+high）/2;
MergeSort（X,low,mid）;//MergeSort（X,mid+1,high）;//序列
merge（X,low,mid,high）;//行归并
}
}
intmain（void）
{
inti;
intX[N]={8,3,2,9,7,1,5,4};
MergeSort（X,0,7）;
for（i=0;i<8;i++）
printf（"%d",X[i]）;
printf（"\n"）;
将缓冲区中的数据元素复制回原序列中
用递归方式定义归并排序函数
将子序列X[low~mid]归并为有序序列将子序列X[mid+1~high]归并为有序
将子序列X[low~mid]和x[mid+1~high]进
}
快速排序：
#include
voidquiksort（inta[],intlow,inthigh）
{
inti=low;
intj=high;
inttemp=a[i];
if（low{
while（i{
while（（a[j]>=temp）&&（i{
j--;
}
a[i]=a[j];
while（（a[i]<=temp）&&（ii++;
}
a[j]=a[i];
}
a[i]=temp;
quiksort（a,low,i-1）;quiksort（a,j+1,high）;
}
else
{
return;
}
}
voidmain（）
{
intarry[]={49,38,65,97,76,13,27};
quiksort（arry,0,15）;
for（inti=0;i<15;i++）
{
printf（"%d",arry[i]）;
}
printf（"\n"）;
}
1.5运行结果截图
实验2分治法
（二）_分金块
2.1实验目的
1.掌握分治法的基本思想和求解步骤。
2.理解分治法的精髓，即如何分？
如何治？
才能使得算法效率更高。
3.通过实例编程，掌握运用分治法来解决实际问题的方法。
2.2实验内容及要求
问题描述：
老板有一袋金块（共n块），最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块，假设有一台比较重量的仪器，我们希望用最少的比较次数找出最重、最轻的金块。
要求:
必须用分治法（二分法）解决上述问题,禁止用排序法和蛮力法。
2.3算法设计思路及步骤
算法思路：
假设袋中有n块金。
当n很小时，如n=2时，要找出最重的金块，一次就够了。
当n比较大时（n>2），首先，把这袋金块分成两个小袋A和B，然后分别找出A和B中最重和最轻的金块,最后比较A中和B中最重和最轻的，这样就可以找到最重和最轻的金块。
2.4程序代码
#include
#include#includeusingnamespacestd;
floatmax（floatg1,floatg2）//比较找大值
return（g1>g2?
g1:
g2）;
}
floatmin（floatg1,floatg2）//比较找小值
{return（g1g1:
g2）;
}
floatSearch_Max（floatg[],intleft,intright）//用二分法递归找最大值
{
if（left==right）//当只有一个数时，直接返回该值
{
floatmax;
max=g[right];
returnmax;
}
if（right-left==1）
{
floatLM,RM;
LM=g[left];
RM=g[right];
return（max（LM,RM））;
}
if（right-left>1）
{
floatLM,RM;
intmid=（left+right）/2;//取中点
LM=Search_Max（g,left,mid）;
RM=Search_Max（g,mid,right）;//左半部分，右半部分的最大值比较找最大
return（max（LM,RM））;
}
}
floatSearch_Min（floatg[],intleft,intright）//用二分法递归找最小值
{
if（left==right）
{
floatmin;
min=g[right];
returnmin;
}
if（right-left==1）
{
floatLM,RM;
LM=g[left];
RM=g[right];return（min（LM,RM））;
}
if（right-left>1）
{
floatLM,RM;
intmid=（left+right）/2;
LM=Search_Min（g,left,mid）;
RM=Search_Min（g,mid,right）;//左半部分，右半部分的最小值比较找最小return（min（LM,RM））;
}
}
intmain（）
{
floatgold[100];
intn;
cout<<"请输入金块的数目:
";
cin>>n;
cout<<"请输入各金块的重量:
";
for（inti=0;i{
cin>>gold[i];
}
cout<<"最重的金块:
"<cout<<"最轻的金块:
"<return0;
}
2.5运行结果截图
实验三动态规划_数字三角形
3.1实验目的
1.掌握动态规划的基本思想和基本步骤。
2.理解动态规划的精髓，如何才能提高算法的效率。
3.比较动态规划与贪心法的区别，并思考最小硬币问题是否能用贪心法求解。
4.通过实例编程，掌握运用动态规划来解决实际问题的过程。
3.2实验内容及要求
动态规划思想实现编程：
给一个数字三角形,找出从第一层到最后一层的一条路,使得所经过的权值之和最大。
输入样例：
5
7
38
810
2744
45265
输入的第一行是一个整数N（1下面的N行给出数字三角形。
数字三角形上的数的范围都在0和100之间。
输出要求：
输出最大的和。
1、用递归函数实现。
2、用递推方法实现。
3.3算法设计思路及步骤
算法思路：
用二维数组存放数字三角形
D（r,j）:
第r行第j个数字（r,j从1开始算）
MaxSum（r,j）:
从D（r,j）到底边的各条路径中，最佳路径的数字之和。
3.4程序代码
递归：
#include
#include
#defineMAX_NUM100
intD[MAX_NUM+10][MAX_NUM+10];
intN;
intaMaxSum[MAX_NUM+10][MAX_NUM+10];
intMaxSum（intr,intj）
{
if（r==N）
returnD[r][j];
if（aMaxSum[r+1][j]==-1）aMaxSum[r+1][j]=MaxSum（r+1,j）;
if（aMaxSum[r+1][j+1]==-1）aMaxSum[r+1][j+1]=MaxSum（r+1,j+1）;
if（aMaxSum[r+1][j]>aMaxSum[r+1][j+1]）
returnaMaxSum[r+1][j]+D[r][j];
returnaMaxSum[r+1][j+1]+D[r][j];
}
intmain（）
{
intm;
scanf（"%d",&N）;
memset（aMaxSum,-1,sizeof（aMaxSum））;//将aMaxSum全部置成-1,表示开始所有的MaxSum（r,j）都没有算过
for（inti=0;i<=N;i++）
{
for（intj=1;j<=i;j++）
{scanf（"%d",&D[i][j]）;
}
}
printf（"%d",MaxSum（1,1））;return0;
}
递推：
#include
#include
#defineMAX_NUM100
intD[MAX_NUM+10][MAX_NUM+10];intN;
intaMaxSum[MAX_NUM+10][MAX_NUM+10];
voidmain（）
{
inti,j;scanf（"%d",&N）;
for（i=1;i<=N;i++）
for（j=1;j<=i;j++）scanf（"%d",&D[i][j]）;
for（j=1;j<=N;j++）aMaxSum[N][j]=D[N][j];
for（i=N;i>1;i--）
for（j=1;j{
if（aMaxSum[i][j]>aMaxSum[i][j+1]）aMaxSum[i-1][j]=aMaxSum[i][j]+D[i-1][j];else
aMaxSum[i-1][j]=aMaxSum[i][j+1]+D[i-1][j];}
printf（"%d\n",aMaxSum[1][1]）;
}
3.5运行结果截图
实验四购物券问题
4.1实验目的
4.选择合适的算法策略解决问题。
5.理解不同方法的精髓，如何才能提高算法的效率。
6.比较动态规划、贪心法、回溯法的区别
7.通过实例编程，掌握解决实际问题的过程。
4.2实验内容及要求
公司发了某商店的购物券1000元，限定只能购买店中的m种商品每种商品的价格分别为m1,m2,⋯，要求程序列出所有的正好能消费完该购物券的不同购物方法。
程序输入：
第一行是一个整数m，代表可购买的商品的种类数。
接下来是m个整数，每个1行，分别代表这m种商品的单价。
程序输出：
第一行是一个整数，表示共有多少种方案第二行开始，每种方案占1行，表示对每种商品购买的数量，中间用空格分隔。
4.3算法设计思路及步骤
算法思路：
解这道题目受到21位花朵数的启发，可以给每件商品设置一个数量标志num[]，价格prize[]，先输入价格，并从所有商品中找到最便宜的那个min，然后max=1000/min，这个max就是每个商品购买的最大数量，接下来我们对每个商品购买的数量进行枚举，通过递归实现，当枚举到第m+1位的时候，递归停止，算一下此时所购买的商品的价格，如果等于1000，就把计数器count加1，并把num[]数组中的数据全部保存下来，当递归全部结束，就可以输出count的值以及保存的num[]值。
4.4程序代码
#include#includeintm;//物品数intp[100];//价格
intans[100][100];//ans[i][j]表示第i个方案中第j个物品被选数
intnum[100];//num[i]表示第i件物品被选的个数
intcas=0;//方案数
intmoney=0;//花的钱
voidbuy（intn）//n表示当前搜索到的物品编号
{
if（money>1000||n>=m）//当花的钱超过预算或者所有的物品都已遍历过了，不再继续搜索下去
return;
if（money==1000）//当花的钱正好为1000，满足要求
{
for（inti=0;icas++;
return;
}num[n]++;//选该物品money+=p[n];
buy（n）;//可以继续选该物品num[n]--;//不选该物品，前面加的要减去
money-=p[n];//钱也相应的减buy（n+1）;//选下一个物品
}
intmain（）
{
inti;scanf（"%d",&m）;for（i=0;imemset（num,0,sizeof（num））;//将以num为起始地址的数组全部初始化为0
buy（0）;printf（"%d\n",cas）;for（i=0;ifor（intj=0;jprintf（"\n"）;
}return0;
}
4.5运行结果截图
总结
通过这几次的实验和学习，我更加清楚的知道它们的运行机理，比如分治法解题的一般步骤：
（1）分解，将要解决的问题划分成若干规模较小的同类问题；
（2）求解，当子问题划分得足够小时，用较简单的方法解决；（3）合并，按原
问题的要求，将子问题的解逐层合并构成原问题的解。
做实验重在动手动脑，还是要多写写实验，才是硬道理。
排序的话首先要掌握基本的排序思想，然后把逻辑语言转化成程序语言，参考网上的各种答案优化自己的算法程序结合所学知识。
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。
若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。
贪心算法的思路和步骤是：
建立数学模型来描述问题；把求解的问题分成若干个子问题；对每一子问题求解，得到子问题的局部最优解；把子问题的解局部最优解合成原来解问题的一个解。
感谢在这几次实验中老师和同学给予的帮助，我会在今后的学习和生活中更加努力上进。
实验报告评分表
评分标准：
1.学生是否严格遵守上机纪律，按照规定时间完成实验任务（占30%）
2.算法设计的质量与规范：
（占40%）
（1）完成题目的数量
（2）是否采用了良好的设计方法，独立完成上机编程
（3）算法设计思路是否清晰，时间复杂度是否合理
（4）程序是否运行正常
3.实验上机报告书的质量与规范（占30%）
教师评分：
1.学生出勤得分：
A）优
B）
良
C）中
D）及格
E）不及格
2算法设计得分：
A）优
B）
良
C）中
D）及格
E）不及格
3.实验报
告得分：
A）优
B）
良
C）中
D）及格
E）不及格
总分：
教师评语：
根据该生在实验上机期间，是否严格遵守上机纪律，按照规定时间完成
设计任务，完成的算法设计的质量与规范，提交的实验上机报告书的质量与规范等多方面的评分，该生本学期实验上机的评分为：
教师签名：
日期：
年月日
升级会员 