問題描述

小明每天玩10盤王者榮耀，且勝負完全隨機（勝率50%），請用JS寫一個模擬演算法，算出小明今天獲得過至少一次3連勝的概率，并指出該演算法的時間與空間復雜度，

解題思路

列舉找規律

眼看10盤太多了，我們來看看3盤，4盤，5盤等，看看有什么規律，隨著我們學習計算機，其實計算機所有資料都用0和1組成，這里個人用1代表勝，0代表負，勝率50%也就是
因此，3盤有三連勝概率如下
111 == 1/2^3=0.125
4盤三連勝以上概率如下
1110 == 1/2^4
0111 == 1/2^4
1111 == 1/2^4
sum = 1/2^34+ 1/2^4 + 1/2^4 = 3/2^3=0.1875
5盤三連勝的情況及概率
1110* == 1/2^4
01110 == 1/2^5
*0111 == 1/2^4
11110 == 1/2^5
01111 == 1/2^5
11111 == 1/2^5
sum = 1/2^4 + 1/2^5 + 1/2^4 + 1/2^5 + 1/2^5 + 1/2^5= 1/2^4 * 2+ 1/2^5 * 4 =0.25

列舉推演

我們知道，連勝就是1，也就是多少兩勝，就是多少個一并行移動，但是，防止超過本身連勝，所以旁邊的連勝得為0.也就是10盤三兩勝總數為
十個未知數**********
三連勝推理，01110五個數字，從左移位，總移動個數（10-5）+1會有四種，加上邊界問題有兩種1110，0111，也就是三連勝概率 1/2^5 * (10-5+1)+2/2^4
四連勝類推 1/2^6 * (10-6+1)+2/2^5
因此類推 把上面設定為N盤，success連勝概率
∑ i = s u c c e s s N \sum_{i=success}^N ∑i=successN? (1/2^(i+2) * (N-(i+2)+1)+2 * 1/(i+1)) + 1/2^N
用計算機實作如下圖

 /**
     * @param success 連勝次數
     * @param count   總局數, count>m+2
     * @return
     */
    public static double rateResult(int success, int count) {
        if (count < success) {
            return 0;
        }
        double sum = 0;
        for (int i = success; i < count; i++) {
            sum += Math.pow(1.0 / 2, i + 2) * (count - i - 1) + Math.pow(1.0 / 2, i + 1) * 2; // i-2連勝概率
        }
        sum += Math.pow(1.0 / 2, count); // n連勝的該路
        return sum;
    }

驗證推理

由上列舉推演由兩組資料，我們來驗證一下

public static void main(String[] args) {
        System.out.println(rateResult(3, 3));  // 0.125
        System.out.println(rateResult(3, 4)); // 0.1875
        System.out.println(rateResult(3, 5)); // 0.25
}

也就是說條件滿足，對于有沒有錯，還有待研究

演算法優化

N盤，連勝為success，勝概率為rate，演算法優化，

  /**
     * @param success 連勝次數
     * @param count   總局數
     * @param rate 連勝概率
     * @return
     */
    public static double rateResult(int success, int count, double rate) {
        if (count < success) {
            return 0;
        }
        double sum = 0;
        for (int i = success; i < count; i++) {
            sum += Math.pow((1 - rate), 2) * Math.pow(rate, i) * (count - i - 1) + (1 - rate) * Math.pow(rate, i) * 2; // i-2連勝概率
        }
        sum += Math.pow(1.0 / 2, count); // n連勝的該路
        return sum;
    }

實際應用

問題來了，我們怎樣才能玩游戲玩上王者呢？
1.比如平常玩游戲，如果勝負均衡，基本會出現連勝三局以上要玩多少局才出現，

   int N = 3;
        while (true) {
            if (rateResult(3, N++, 0.5) > 1) {
                System.out.println(--N);
                break;
            }
        }

輸出18，也就是我們打18局游戲一般就會有連續三勝的出現，

2.我們進一步推算演變，如果連勝10局，到底要打多少局王者游戲呢？

   int N = 3;
        while (true) {
            if (rateResult(10, N++, 0.5) > 1) {
                System.out.println(--N);
                break;
            }
        }

結果為2057，是不是很驚訝，凡是連勝超過15局的人，肯定玩不少游戲，
3. 繼續演練，但是游戲設計規則，其實基本游戲都是按照50%根據玩家的平常總結能力來綜合評分的，當然人為因素很多，其實還有手感，不同手機或者不同時間給人的玩游戲狀態不一樣，這時我們可以動態產生優勝率因子rate，此外，游戲潛意識設計規則不可能讓玩家一直沒法上段位，因此出現獎勵分數的問題，也就是輸了也獎勵積分，只要你玩到一定局數，將會可能打上王者，除非你的智慧在這個段位的人之下，否則基本上均可上王者，至于這個演算法如何統計就比較復雜了，因為上一個段位你的勝利rate就會地一點，要再次奪取分數，你就需要不斷學習和提升自己，這就是游戲潛意識規則，