算法设计分析

武汉科技大学城市学院《算法分析与设计》上机实验报告课程名称数据结构课程设计学部信息工程学部专业软件工程班级软件三班姓名洪汉山学号201510159320指导教师林晓丽职称副教授2017年11月15日1目录实验1分治法（一）..................................................21.1实验目的.........................................................21.2实验内容及要求...................................................21.3算法设计思路及步骤...............................................21.4程序代码.........................................................31.5运行结果截图.....................................................7实验2分治法（二）_分金块...........................................82.1实验目的.........................................................82.2实验内容及要求...................................................82.3算法设计思路及步骤...............................................82.4程序代码.........................................................92.5运行结果截图....................................................11实验三动态规划_数字三角形.........................................113.1实验目的........................................................113.2实验内容及要求..................................................113.3算法设计思路及步骤..............................................123.4程序代码........................................................123.5运行结果截图....................................................14实验四购物券问题..................................................154.1实验目的........................................................154.2实验内容及要求..................................................154.3算法设计思路及步骤..............................................154.4程序代码........................................................164.5运行结果截图....................................................17总结.............................................................182实验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。所以非递归算法需要三个参数：数组起始地址、数组长度以及要查找的数字。二分递归算法思路：判断条件是一样的，在调用自身的过程中，要改变的参数要么是开始标记，要么是结束标记。所以对于递归算法，需要四个参数：数组起止地址、要查找的数字、开始标记与结束标记。3合并排序算法思路：原理,把原始数组分成若干子数组,对每一个子数组进行排序,继续把子数组与子数组合并,合并后仍然有序,直到全部合并完,形成有序的数组。快速排序算法思路：快速排序是找出一个元素（理论上可以随便找一个）作为基准(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(xs[mid]){low=mid+1;}else{high=mid-1;}}return-1;4}//递归实现intbinarySearch2(int*s,intlow,inthigh,intx){intmid=(low+high)/2;intindex=0;//设置一个指针if(low=high){if(x==s[mid]){returnmid;}elseif(xs[mid]){index=binarySearch2(s,mid+1,high,x);}else{index=binarySearch2(s,low,mid-1,x);}}elsereturn-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);elseprintf(查找的数x=%d,这个数在已知数组的元素中下标为%d。\n,x,index);}合并排序：#includestdio.h5#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++];//将a[low...m]中的记录放入a中elsea[k]=X[j++];//将a[m+1...high]中的记录放入a中}while(i=mid)//将a[low...m]余下部分复制到aa[k++]=X[i++];while(j=high)//将a[m+1...high]余下部分复制到aa[k++]=X[j++];for(k=low;k=high;k++)//将缓冲区中的数据元素复制回原序列中X[k]=a[k];}voidMergeSort(intX[],intlow,inthigh)//用递归方式定义归并排序函数{intmid;if(lowhigh){mid=(low+high)/2;MergeSort(X,low,mid);//将子序列X[low~mid]归并为有序序列MergeSort(X,mid+1,high);//将子序列X[mid+1~high]归并为有序序列merge(X,low,mid,high);//将子序列X[low~mid]和x[mid+1~high]进行归并}}intmain(void){inti;intX[N]={8,3,2,9,7,1,5,4};MergeSort(X,0,7);for(i=0;i8;i++)printf(%d,X[i]);printf(\n);6}快速排序：#includestdio.hvoidquiksort(inta[],intlow,inthigh){inti=low;intj=high;inttemp=a[i];if(lowhigh){while(ij){while((a[j]=temp)&&(ij)){j--;}a[i]=a[j];while((a[i]=temp)&&(ij)){i++;}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;i15;i++){printf(%d,arry[i]);}printf(\n);}71.5运行结果截图8实验2分治法（二）_分金块2.1实验目的1.掌握分治法的基本思想和求解步骤。2.理解分治法的精髓，即如何分？如何治？才能使得算法效率更高。3.通过实例编程，掌握运用分治法来解决实际问题的方法。2.2实验内容及要求问题描述：老板有一袋金块(共n块)，最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块，假设有一台比较重量的仪器，我们希望用最少的比较次数找出最重、最轻的金块。要求:必须用分治法(二分法)解决上述问题,禁止用排序法和蛮力法。2.3算法设计思路及步骤算法思路：假设袋中有n块金。当n很小时，如n=2时，要找出最重的金块，一次就够了。当n比较大时（n2），首先，把这袋金块分成两个小袋A和B，然后分别找出A和B中最重和最轻的金块,最后比较A中和B中最重和最轻的，这样就可以找到最重和最轻的金块。2.4程序代码#includeiostream#includestring.h#includealgorithmusingnamespacestd;floatmax(floatg1,floatg2)//比较找大值9{return(g1g2?g1:g2);}floatmin(floatg1,floatg2)//比较找小值{return(g1g2?g1:g2);}floatSearch_Max(floatg[],intleft,intright)//用二分法递归找最大值{if(left==right)//当只有一个数时，直接返回该值{floatmax;max=g[right];returnmax;}if(right-l