拿到最多金幣的概率

• 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