内容发布更新时间 : 2024/11/19 13:18:58星期一 下面是文章的全部内容请认真阅读。

算法设计与分析实验报

告

专 业 姓 名 实验名称 实验目的 实验内容 算法描述 班 级 学 号 实验一：递归与分治算法设计 1.掌握递归与分治策略的基本思想。 2.通过设计求解给定问题的递归算法和分治算法学会使用递归和分治法解决问题的一般技巧。 1. 二分搜索问题： 设a[0:n-1]是已排好序的数组。试改写二分搜索算法，使得当搜索元素x不在数组a中时，返回小于x的最大元素的位置i和大于x的最小元素的位置j；当搜索元素x在数组a中时，返回x在数组中的位置，此时i和j相同。 2. 假币识别问题： 一个袋子里有n个硬币，其中一枚是假币，假币和真币外观一模一样，仅凭肉眼无法区分，但是已知假币比真币轻一些。试设计识别假币的分治算法。 1.二分搜索问题的解题思路或算法思想： 将n个元素分成个数大致相同的两半， 取a[n/2]与x进行比较。 如果x=a[n/2]，则找到x算法终止， 如果xx){ right = mid - 1; }else{ left = mid + 1; } } return left; } } public static void main(String[] args) { int []a = new int[]{2,3,4,5,6,8,9}; //0 1 2 3 4 5 6 Scanner scn = new Scanner(System.in); int x = scn.nextInt(); int m = new Digui().binarySearch(a, x,0,a.length-1); if(a[m]==x){ System.out.println(\与x相等的数据元素的下标是\ }else{ System.out.println(\不存在\ if(a[m]>x){ System.out.println(\比x大的最小数组元素的下标是\+ m); if((m-1)<0){ System.out.println(\不存在比x小的数组元素\ } }else{ System.out.println(\比x小的最大数组元素的下标是\+ m); if(m >= a.length-1){ System.out.println(\不存在比x大的数组元素\ }else{ System.out.println(\比x大的最小数组元素的下标是\ } } } } 实例： 1） 2） 3） 4） 2. 假币识别问题的程序： package com.t3; //假币问题 import java.util.Scanner; public class Main { static final int MAXNUM = 20; private static int FalseCoin(int[] coin, int low, int high) { int sum1 = 0, sum2 = 0, sum3 = 0; int re = 0; if ( low+1 == high ) { if ( coin[low] < coin[high] ) { re = low+1; return re; }else { re = high+1; return re; } } if ( (high-low+1)%2 == 0 ) {//如果n是偶数 //前半段 for ( int i = low; i <= low+(high-low)/2; i++ ) { sum1 = sum1 + coin[i]; } //后半段 for ( int i = low+(high-low)/2+1; i <= high; i++ ) {