递归与分治算法设计

算法设计与分析实验报

告专业班级姓名学号实验名称实验一：递归与分治算法设计实验目的掌握递归与分治策略的基本思想。通过设计求解给定问题的递归算法和分治算法学会使用递归和分治法解决问题的一般技巧。实验内容二分搜索问题：设a[0:n-1]是己排好序的数组。试改写二分搜索算法，使得当搜索元素x不在数组a中时，返回小于x的最大元素的位置i和大于x的最小元素的位置j；当搜索元素x在数组a中时，返回x在数组中的位置，此时i和j相同。假币识别问题：一个袋子里有n个硬币，其中一枚是假币，假币和真币外观一模一样，仅凭肉眼无法区分，但是已知假币比真币轻一些。试设计识别假币的分治算法。_算法描述二分搜索问题的解题思路或算法思想：将n个元素分成个数大致相同的两半，取a[n/2]与x进行比较。如果x=a[n/2]，则找到x算法终止，如果x<x[n/2]，则在数组的右边部分继续搜索，如果x<x[n/2]，则在数组的左边部分继续搜索。假币识别问题的解题思路或算法思想：将这n个硬币分成两等份，然后放到天平的两端，则假币在较轻的那一端；然后将较轻的那端的硬币再分成2等份，然后再放到天平的两端进行比较，假币还是在较轻的那一段；直到最后只剩下两个硬币了，分别放到天平的两端，轻的哪个就是假币。当然，最后也可能剩下3个硬币，我们可以将这3个硬币中任意拿出来个，然后将剩下的两个放到天平的两端，如果天平是平的，则说明拿出来的那个硬币就是假币；如果天平不是平的，则轻的那端是假币。程序及运行结果1.二分搜索问题的程序：packagecom.tl;importjava.util.Scanner;publicclassDigui(publicstaticintbinarySearch(inta[],intx,intleft,intright)(intmid=0;

while(left<right)(mid=(left+right)/2;if(a[mid]==x)returnmid;if(a[mid]>x)(right=mid-1;}else(left=mid+1;}}returnleft;}}publicstaticvoidmain(String[]args)(int[]a=newint[]{2,3,4,5,6,8,9};//0123456Scannerscn=newScanner(System.沮)；intx=scn.nextInt();intm=newDigui().binarySearch(a,x,0,a.length-1);if(a[m]==x){System.。以.println(”与x相等的薮据元素的下标是"+m);}else{System.。以.println("不、存在"+x);if(a[m]>x){System.。以.println("比x大的取小数组儿素的下标是”+m);if((m-1)<0){System.。以.println("不存在比x小的数组元素");}}else{System.。以.println("比x小的最大数组兀素的下标是”+m);if(m>=a.length-1){System.。以.println("不存在比x大的数组元素”)；}else{System.。以.println(”上匕x大的取小数组儿素的下标是"+(m+1));}}}}实例：1)0相存在。比甚大的最小数组元麦的下标是。不存在比*卜的数组元素2)10忆存在比不小的最大数组元素的下标是6不存在比*大的数组元素3)不存在7比*小的最大数组元素的下标是4比x大的最小致组元素的下标是54)与对目等的数据元素的下标是22.假币识别问题的程序：packagecom.t3;〃假币问题importjava.util.Scanner;publicclassMain(staticfinalintMAXNUM=20;privatestaticintFalseCoin(int[]coin,intlow,inthigh)(intsum1=0,sum2=0,sum3=0;intre=0;if(low+1==high)(if(coin[low]<coin[high])(re=low+1;returnre;}else(re=high+1;returnre;if((high-low+1)%2==0){//如果n是偶数〃前半段for(inti=low;i<=low+(high-low)/2;i++){sum1=sum1+coin[i];//后半段for(inti=low+(high-low)/2+1;i<=high;i++){sum2=sum2+coin[i];if(suml>sum2)(re=FalseCoin(coin,low,low+(high-low)/2);returnre;}elseif(sum2>sum1)(//sum2>sum1re=FalseCoin(coin,low+(high-low)/2+1,high);returnre;}}else{//如果是奇数〃前半段，除去中间的一个硬币for(inti=low;i<=low+(high-low)/2-1;i++){sum1=sum1+coin[i];}//后半段，除去中间的一个硬币for(inti=low+(high-low)/2+1;i<=high;i++){sum2=sum2+coin[i];}sum3=coin[low+(high-low)/2];if(sum1>sum2){re=FalseCoin(coin,low,low+(high-low)/2-1);returnre;}elseif(sum2>sum1){re=FalseCoin(coin,low+(high-low)/2+1,high);returnre;}if(sum1==sum2){re=low+(high-low)/2+1;returnre;}}returnre;}publicstaticvoidmain(String[]args){int[]coin=newint[MAXNUM];System.o以.println("请输入硬币总的个数:");Scannerin=newScanner(System.in);

intn=in.nextInt();System—以.println("请输入所有硬币质量：");for(inti=0;i<n;i++)(coin[i]=in.nextInt();}intp=FalseCoin(coin,0,n-1);System.—以.println("假币在"+p+"个位置");}}实例：1)请输入硬币总的个数：6请输入所有硬币质里:111121偏币在5个位置2)清输人硬币总的个教：7请输人所有硬币质量：1211111幅币在2个位置实验心得体会：通过该试验，我掌握递归与分治策略的基本思想，并通过