import edu.princeton.cs.algs4.StdStats; //导入依赖的package包/类
/**
* perform trials independent experiments on an n-by-n grid
* @param n
*          grid的大小
* @param trials
*          尝试trials次试验
*/
public PercolationStats(int n, int trials) {
    //检验参数合法性
    if (n <= 0 || trials <= 0)
        throw new IllegalArgumentException("参数不能小于等于0!");

    results = new double[trials];

    for(int i = 0;i < trials;i++) {
        Percolation percolationTest = new Percolation(n);

        int rndRow, rndCol;
        while (!percolationTest.percolates()) {
            if(percolationTest.isOpen(rndRow = (StdRandom.uniform(n) + 1), rndCol = (StdRandom.uniform(n) + 1)))
                continue;
            else
                percolationTest.open(rndRow, rndCol);
        }
        results[i] = (percolationTest.numberOfOpenSites() * 1.0) / (n * n);
    }

    mean = StdStats.mean(results);
    stddev = StdStats.stddev(results);
}
 

import edu.princeton.cs.algs4.StdStats; //导入依赖的package包/类
public PercolationStats(int n, int trials) {
    if (n <= 0 || trials <= 0) throw new IllegalArgumentException();

    results = new double[trials];

    for (int i = 0; i < trials; i++) {
        Percolation percolation = new Percolation(n);
        while (!percolation.percolates()) {
            int row = StdRandom.uniform(1, n + 1);
            int col = StdRandom.uniform(1, n + 1);
            if (!percolation.isOpen(row, col)) percolation.open(row, col);
        }

        int openSites = percolation.numberOfOpenSites();
        results[i] = (double) openSites / (double) (n * n);

    }

    mean = StdStats.mean(results);
    stddev = StdStats.stddev(results);
}
 

import edu.princeton.cs.algs4.StdStats; //导入依赖的package包/类
private static void histogram(List<Integer> subArraySizes, int cutoff) {

        double[] sizesArray = new double[subArraySizes.size()];
        double maxCount = 0;

        for(int i=0; i < subArraySizes.size(); i++) {
            sizesArray[i] = subArraySizes.get(i);

            if(sizesArray[i] > maxCount) {
                maxCount = sizesArray[i];
            }
        }

        StdDraw.setCanvasSize(1024, 512);
        StdDraw.setXscale(0, sizesArray.length);

        //Labels
        if(cutoff != 50) {
            StdDraw.setYscale(-1, maxCount + 2);
            StdDraw.text(200, maxCount + 0.5, String.valueOf(maxCount));
            StdDraw.text(200, -0.5, String.valueOf(2));
            StdDraw.text(sizesArray.length - 500, -0.5, String.valueOf(sizesArray.length));
        } else {
            StdDraw.setYscale(-5, maxCount + 5);
            StdDraw.text(100, maxCount + 0.5, String.valueOf(maxCount));
            StdDraw.text(100, -1.5, String.valueOf(2));
            StdDraw.text(sizesArray.length - 100, -1.5, String.valueOf(sizesArray.length));
        }

        StdDraw.text(sizesArray.length / 2, maxCount + 1, "Cutoff: " + cutoff);

        StdStats.plotBars(sizesArray);
    }
 

import edu.princeton.cs.algs4.StdStats; //导入依赖的package包/类
private static void histogram(List<Double> runningTimes) {

        double[] runningTimesArray = new double[runningTimes.size()];
        double maxCount = 0;

        for(int i=0; i < runningTimes.size(); i++) {
            runningTimesArray[i] = runningTimes.get(i);

            if(runningTimesArray[i] > maxCount) {
                maxCount = runningTimesArray[i];
            }
        }

        StdDraw.setCanvasSize(1024, 512);
        StdDraw.setXscale(0, runningTimesArray.length);
        StdDraw.setYscale(-0.2, maxCount + 0.5);

        //Labels
        StdDraw.text(runningTimesArray.length / 2, maxCount + 0.4, "Running Times");
        StdDraw.text(5, maxCount, String.valueOf(maxCount) + " seconds");
        StdDraw.text(0.8, -0.1, String.valueOf(0));
        StdDraw.text(runningTimesArray.length - 1.5, -0.1, String.valueOf(runningTimesArray.length));

        int horizontalSpace = runningTimes.size() / NUMBER_OF_ARRAYS;
        int leftOffset = (horizontalSpace / 2) * -1;

        for(int i=0; i < NUMBER_OF_ARRAYS; i++) {
            StdDraw.text(leftOffset + (i + 1) * horizontalSpace, maxCount + 0.2, "10^" + (i+3));
        }

        StdStats.plotBars(runningTimesArray);
    }
 

import edu.princeton.cs.algs4.StdStats; //导入依赖的package包/类
public static void main(String[] args) {

        Exercise31_DistinctValues distinctValues = new Exercise31_DistinctValues();

        if(args.length == 3) {
            int maxValue = Integer.parseInt(args[0]);
            int numberOfValues = Integer.parseInt(args[1]);
            int numberOfTrials = Integer.parseInt(args[2]);

            int distinct[] = new int[numberOfTrials];
            int distinctArrayIndex = 0;

            for(int i=0; i < numberOfTrials; i++) {
                int numberOfDistinctValues = distinctValues.countDistinctValues(numberOfValues, maxValue);
                distinct[distinctArrayIndex++] = numberOfDistinctValues;
            }

            double distinctValuesMean = StdStats.mean(distinct);
            StdOut.printf("Number of distinct values: %.2f", distinctValuesMean);

            double alpha = ((double) numberOfValues) / ((double) maxValue);
            double expectedValue = maxValue * (1 - Math.exp(-alpha));
            StdOut.printf("\nExpected:  %.2f", expectedValue);
        } else {
            distinctValues.doExperiment();
        }
    }
 

import edu.princeton.cs.algs4.StdStats; //导入依赖的package包/类
public double mean(){
	numOfMean = StdStats.mean(fraction);
	return numOfMean;
}
 

import edu.princeton.cs.algs4.StdStats; //导入依赖的package包/类
public double stddev(){
	numOfStddev = StdStats.stddev(fraction);
	return numOfStddev;  
}
 

import edu.princeton.cs.algs4.StdStats; //导入依赖的package包/类
private static void histogram(int n, double l, double r, double[] numbers) {
	
	int[] numbersInInterval = new int[n];
	
	verifyIntervals(n, l, r, numbers, numbersInInterval);
	
	int maxCount = StdStats.max(numbersInInterval);
	
	StdDraw.setCanvasSize(1024, 512);
       StdDraw.setXscale(l, r);
       StdDraw.setYscale(0, maxCount + 1);
       
       double intervalOfNumbers = (r - l) / n;
       
       for (int i = 0; i < n; i++) {
       	
           double x = l + (i + 0.5) * intervalOfNumbers,
                  y = numbersInInterval[i] / 2.0,
                  rw = intervalOfNumbers / 2.0,
                  rh = numbersInInterval[i] / 2.0;
           
           StdDraw.filledRectangle(x, y, rw, rh);
       }
       
}
 

import edu.princeton.cs.algs4.StdStats; //导入依赖的package包/类
public void doExperiment() {

        int numberOfTrials = 10;

        /**
         * T = 10
         * N = 10^3, 10^4, 10^5, 10^6
         * M = N/2, N, 2N
         */
        int[] values = {1000, 10000, 100000, 1000000};

        StdOut.printf("%13s %13s %13s %23s\n", "Values Generated | ", "Max Value | ", "Distinct Values | "
                , "Expected Distinct Values");

        for(int n = 0; n < values.length; n++) {
            for(int m = 0 ; m < 3; m++) {
                int numberOfValues = values[n];

                int maxValue = 0;
                if(m == 0) {
                    maxValue = numberOfValues / 2;
                } else if(m == 1){
                    maxValue = numberOfValues;
                } else if(m == 2){
                    maxValue = 2 * numberOfValues;
                }

                int distinct[] = new int[numberOfTrials];
                int distinctArrayIndex = 0;

                for(int trial = 0; trial < numberOfTrials; trial++) {
                    int distinctValues = countDistinctValues(numberOfValues, maxValue);
                    distinct[distinctArrayIndex++] = distinctValues;
                }

                double distinctValuesMean = StdStats.mean(distinct);
                double alpha = ((double) numberOfValues) / ((double) maxValue);
                double expectedValue = maxValue * (1 - Math.pow(Math.E, -alpha));

                printResults(numberOfValues, maxValue, distinctValuesMean, expectedValue);
            }
        }
    }
 

import edu.princeton.cs.algs4.StdStats; //导入依赖的package包/类
public double mean()
{
       return StdStats.mean(ratios);
   }
 

import edu.princeton.cs.algs4.StdStats; //导入依赖的package包/类
public double stddev()
{
       return StdStats.stddev(ratios);
}