习题1.1.39
随机匹配。编写一个使用 BinarySearch 的程序,它从命令行接受一个整型参数 T,并会分别针对N = 10的三次方 、10的四次方 、10的五次方 和10的六次方 将以下实验运行 T 遍:生成两个大小为 N 的随机 6 位正整数数组并找出同时存在于两个数组中的整数的数量。打印一个表格,对于每个N,给出 T 次实验中该数量的平均值。
要点分析
这题其实很简单,就是创建两个数组,然后利用二分查找数组a的每一个元素是否在数组b中就可以了。
参考答案
import java.util.Arrays; import java.util.Random; public class Thirty_nine { /** * @description: 二分查找(BinarySearch)方法,课本第5页 * @param: a 要查找的数组 * @param: key 要查找的元素 * @return: 要查找的元素的索引 */ public static int rank(int[] a, int key) { int lo = 0; int hi = a.length - 1; while (lo <= hi) { int mid = (lo + hi) / 2; if (key < a[mid]) { hi = mid - 1; } else if (key > a[mid]) { lo = mid + 1; } else { return mid; } } return -1; } /** * @description: 建立大小为N的随机6位数整数数组 * @param: N 要建立的数组大小 * @return: 建立完成的数组 */ public static int[] build_array(int N) { int[] a = new int[N]; Random ran = new Random(); for (int i = 0; i < a.length; i++) { a[i] = ran.nextInt(1000000); } return a; } /** * @description: 打印一个表格,对于每个N,给出T次时间中的概述了的平均值 * @param: sum 存储表格信息的数组 * @return: Nothing */ public static void print(int[] sum,int N) { double sums = 0; for (int i = 0; i < sum.length; i++) { sums += sum[i]; } sums /= sum.length; System.out.println("当N = " + N + "时,平均值为: " + sums); } /** * @description: 计算同时存在于两个数组中的整数的数量 * @param: N 要加你的数组大小 * @param: T 将实验运行T遍 * @return: T次实验后,每次实验所保存的同时存在于两个数组中的整数的数量 */ public static int[] count(int N, int T) { int[] sum = new int[T]; for (int i = 0; i < T; i++) { int[] a = build_array(N); int[] b = build_array(N); Arrays.sort(b); for (int j = 0; j < N; j++) { if (rank(b,a[j]) != -1) { //如果a[j]也存在于数组b中,则sum[i]++ sum[i]++; } } } return sum; } public static void main(String[] args) { int T = Integer.parseInt(args[0]); //命令行传入T = 50 int N = (int)Math.pow(10,3); int N2 = (int)Math.pow(10,4); int N3 = (int)Math.pow(10,5); int N4 = (int)Math.pow(10,6); print(count(N,T),N); print(count(N2,T),N2); print(count(N3,T),N3); print(count(N4,T),N4); } } 输出: 当N = 1000时,平均值为: 0.94 当N = 10000时,平均值为: 96.3 当N = 100000时,平均值为: 9485.72 当N = 1000000时,平均值为: 632139.46
请登录之后再进行评论