拿到最多金币的概率

• 2020 年 6 月 22 日
• 筆記
• 算法笔记

问题描述

在10个房间每个房间里放随机数量的金币，每个房间只允许进入一次，金币只能拿一个房间的。
若一个人采取如下策略，问拿到最多金币的概率：先进入前4个房间，均不拿金币，之后每进入一个房间只要比前四个房间的金币都要多，就拿，否则拿取最后一个房间的金币。

编程模拟

import java.util.Random;

public class test {
    /**
     *
     * @param n 房间个数
     * @return 一次模拟情况下，能否拿到最多金币
     */
    public static boolean getMax(int n){
        if(n<1){
            System.out.println("参数不合法！");
            return false;
        }
        int i;
        int a[] = new int[n];//n个房间

        Random ran = new Random();
        for ( i = 0; i < n; i++) {
            a[i] = ran.nextInt(n)+1;//每个房间金币为1~n
        }

        int max = 0; //10个房间最大的金币数
        for ( i = 0; i < n; i++) {
            if(a[i]>max)
                max = a[i];
        }

        int max4 = 0;//前4个房间的最大金币数
        for ( i = 0; i < 4; i++) {
            if(a[i]>max4)
                max4 = a[i];
        }


        for(i=4;i<n-1;i++){  //后边房间金币数大于前4个房间最大值时拿取，并且这个金币数=10个房间最大的金币数时，返回true
            if(i==9&&a[i]==max){  //最后一个房间直接拿取，并判断是否为最大值
                return true;
            }else{
                if(a[i]>max4) {
                    if(max==a[i]){
                        return true;
                    }
                    return false;
                }
            }

        }
        return false;
    }

    public static void main(String[] args) {
        int a =100000;
        int suc =0;
        for (int i = 0; i < a; i++) {
            if(getMax(10)){
                suc++;
            }
        }
        System.out.println((double)suc/(double)a);
    }

}

最后运算结果为0.326