• 中文
    • 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.4k
  • 请登录之后再进行评论

    登录
    单栏布局 侧栏位置: