• 中文
    • English
  • 注册
  • 查看作者
    • 《算法第四版》课后练习题1.1.39答案

      习题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
    • 0
    • 0
    • 0
    • 2.2k
    • 请登录之后再进行评论

      登录

      赞助本站

      • 支付宝
      • 微信
      • QQ

      感谢一直支持本站的所有人!

      单栏布局 侧栏位置: