关于数组乱序后的两个问题?


题目:
编写一个程序ShuffleTest,接受命令行参数M 和N,将大小为M 的数组打乱N 次且在每次打乱之前都将数组重新初始化为a[i] = i。打印一个M×M 的表格,对于所有的列j,行i 表示的是i 在打乱后落到j 的位置的次数。数组中的所有元素的值都应该接近于N/M。
(题目来自《算法》练习题第1.1.36,下面中的部分代码用到该书中的stdlib.jar)
问题在代码的注释中:


 java


 public class quiz_1_1_36 {
    public static int[] shuffle(int[] a) {
        int N = a.length;
        for (int i = 0; i < N; i++) {
            int r = i + StdRandom.uniform( N - i );      //随机产生一个(i, N)之间的数r
            int temp = a[i];
            a[i] = a[r];
            a[r] = temp;
        }
        return a;
    }
    public static void shuffleTest(int m, int n) {
        int [][] s = new int[m][m];

        for(int k = 0; k < n; k++) {   
            //初始化数组
            int[] a = new int[m];
            for (int i = 0; i < m; i++) {
                a[i] = i;
            }
            //打乱数组
            shuffle(a);
            //问题: i在打乱后落在j的位置上的次数??
            //对于题目的这个要求看的不是很明白,行i表示的是i在打乱后落到j的位置的次数该怎样实现?

        }
        //输出
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                StdOut.printf("%7d", s[i][j]);
            }
            StdOut.println();
        }
        //问题: 怎样检查数组中的所有元素的值都应该接近于N/M ??
        //用循环把每个数组中每个值遍历下,那怎么判定接近?

    }
    public static void main(String[] args) {
        int m = Integer.parseInt(args[0]);
        int n = Integer.parseInt(args[1]);

        shuffleTest(m, n);
    }
}

下面这个是实现题目要求的程序(来自: 这里 ),但是程序中的两个部分不懂,如下:


 java


 public class quiz_1_1_36
{
    public interface IShuffle        //问题:这个作用是什么?
    {
        public void shuffle(int[] a);     
    }

    public static void ShuffleTest(IShuffle shuffle, int m, int n)     //问题:第一个参数是干嘛用的?
    {
        int[][] s = new int[m][m];

        for (int k = 0; k < n; k++)
        {
            int[] a = new int[m];
            for (int i = 0; i < m; i++)
                a[i] = i;

            shuffle.shuffle(a);

            for (int i = 0; i < m; i++)
             //这里是实现行i 表示的是i 在打乱后落到j 的位置的次数,
                s[i][a[i]]++;   
        }

        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < m; j++)
                StdOut.printf("%7d", s[i][j]);
            StdOut.println();
        }
    }

    public static void main(String[] args)
    {
        int m = Integer.parseInt(args[0]);
        int n = Integer.parseInt(args[1]);

        //问题:这段这样写是什么意思??
        //----
        IShuffle shuffle = new IShuffle()
        {
            public void shuffle(int[] a)
            {
                StdRandom.shuffle(a);   //调用《算法》中的stdlib.jar中的StdRandom库中的随机将元素排序方法
            }
        };
        //------
        ShuffleTest(shuffle, m, n);
    }
}

用10 50做参数测试,运行后发现,貌似也没有实现检测数组中的所有元素的值都应该接近于N/M。

java 算法 数组

一起画圆圈 9 years, 9 months ago

定义 IShuffle 这个接口的目的是为了将“打乱”这个操作包装起来。整个程序的逻辑,归结起来分为两部分:1、打乱数组;2、对打乱结果进行统计。 ShuffleTest() 方法将前者包装成一个接口,这样该方法自身就突出了后者的逻辑,整个代码更加容易看懂。

悲剧的小控 answered 9 years, 9 months ago

Your Answer