一. 概率算法

概率算法(Randomized algorithm)

二. 三门问题

1.题目描述

2.代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class ThreeDoor {
    public static void main(String[] args) {
        int trial_num = 10000;
        int change_revenue;
        int no_change_revenue;

        //选手没有改变选择的情况下，10000次下成功的概率
        no_change_revenue = 0;
        for (int i = 0; i < trial_num; i++) {
            int real = new Random().nextInt(3);
            int choose = new Random().nextInt(3);
            if (real == choose){
                no_change_revenue = no_change_revenue + 1;
            }
        }

        //选手改变选择的情况，10000次下成功的概率
        change_revenue = 0;
        for (int i = 0; i < trial_num; i++) {
            int real = new Random().nextInt(3);
            int choose = new Random().nextInt(3);

            if (real != choose){
                change_revenue = change_revenue + 1;
            }
        }

        System.out.println("Change revenue："+change_revenue+"; not change revenue："+no_change_revenue);
    }
}

//某次的运行结果
Change revenue：6714; not change revenue：3266

三. 相亲问题

1.题目描述

2.代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
public class SecretaryProblem {
    /**
     * 检查某一次相亲是否选中最佳的人
     */
    private static boolean check_success(double[] candidates, int stop_time){
        double max_in_observation = 0;
        double choosen = 0;

        //观察选出stop_time之前条件最好的人
        for (int i = 0; i < stop_time; i++) {
            if (candidates[i] > max_in_observation){
                max_in_observation = candidates[i];
            }
        }

        //stop_time之后，只要遇到条件超过之前观察的就选它为相亲对象
        for (int i = stop_time; i < candidates.length; i++) {
            if (candidates[i] >= max_in_observation){
                choosen = candidates[i];
                break;
            }
        }

        //找到stop_time之后，真正条件最好的人
        double max_in_all = max_in_observation;
        for (int i = stop_time; i < candidates.length; i++) {
            if (candidates[i] >= max_in_all) {
                max_in_all = candidates[i];
            }
        }

        //比较得到结果
        if (choosen == max_in_all) return true;
        else return false;
    }

    /**
     * 测试程序
     * @param args
     */
    public static void main(String[] args) {
        //实验次数
        int trial_num = 1000000;
        //一组相亲的次数
        int n = 20;

        //对应成功的次数
        int[] success_times = new int[n];

        for (int i = 0; i < trial_num; i++) {
            //生成一组相亲数据
            double[] candidates = generateRandomNumbers(n);

            //判断每一种选择的成功次数
            for (int stop_time = 0; stop_time < n; stop_time++) {
                if (check_success(candidates,stop_time)){
                    success_times[stop_time]++;
                }
            }
        }

        System.out.println(Arrays.toString(success_times));
    }

    /**
     * 生成一组随机数
     * @param n
     * @return
     */
    private static double[] generateRandomNumbers(int n) {
        double[] randoms = new double[n];

        for (int i = 0; i < n; i++) {
            double v = new Random().nextDouble();

            randoms[i] = v;
        }

        return randoms;
    }
}

//某次的运行结果
[49864, 177246, 254832, 307353, 343039, 365779, 378529, 383169, 380892, 372516, 358383, 339562, 316130, 288496, 257085, 222080, 183753, 141744, 97207, 49862]