代码之家  ›  专栏  ›  技术社区  ›  Muhammad Umer

为什么这个随机数猜谜游戏模拟产生5.8

  •  -2
  • Muhammad Umer  · 技术社区  · 22 小时前

    我构建了这个简单的模拟,试图在给定的时间内击败随机数猜测游戏,并记录下动作。

    import random
    import time
    
    def main():
        range_val = 1000000
        total_moves = 0
        
        random.seed(time.time())
    
        for i in range(range_val):
            target = random.randint(1, 100)
    
            low, high = 1, 100
            moves = 0
            guess = 0
    
            while low <= high:
                moves += 1
                guess = (low + high) // 2
    
                if guess == target:
                    break
                elif guess < target:
                    low = guess + 1
                else:
                    high = guess - 1
    
            total_moves += moves
    
        print(float(total_moves) / float(range_val))
    
    if __name__ == "__main__":
        main()
    
    

    随着range_val越来越大,我注意到所需的平均移动量接近5.8或接近5.8。我没有充分的理由来描述这一点。为什么是这个特定的数字?请帮我。

    1 回复  |  直到 22 小时前
        1
  •  1
  •   Lukinator    20 小时前

    二分查找算法

    您正在使用 二分查找算法 在你的模拟中。您可以将算法可视化为二叉树:

    1. 在你的例子中,第一次尝试总是50。它位于二叉树的顶部。你要找的数字实际上有1%的可能性是50。因此,有1%的机会尝试一次。
    2. 之后,程序将建议25或75。这些数字位于树的第二层。你要找的数字有2%的可能性是25或75。所以有2%的机会尝试两次。

    …等等。


    为什么结果是5.8

    结果如下:

    尝试 概率 解释
    1. 1% 数字50立即被找到。
    2. 2% 如果数字是25或75
    3. 4% 如果数字是12、37、62或87
    4. 8% ...
    5. 16% ...
    6. 32% ...
    7. 37% ...

    现在,如果你将尝试次数乘以概率,并将所有内容加在一起:

    1 * 0.01 +
    2 * 0.02 + 
    3 * 0.04 + 
    4 * 0.08 +
    5 * 0.16 +
    6 * 0.32 +
    7 * 0.37 = 5.8
    

    你会得到5.8的结果。


    结论

    你没有得到一个好偶数的原因是100不是2的幂。如果你在1到128的范围内搜索,结果将恰好是6。