【Python】猜数字游戏的极限在哪里

2022年01月13日 阅读数:7
这篇文章主要向大家介绍【Python】猜数字游戏的极限在哪里,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

猜数字游戏:在给定区间内得到一个随机整数,而后猜想这个随机整数是多少。php

如下代码均运行在 Win10 + Python 3.9.5 的环境下。python

1、在给定区间内进行猜想

        场景描述:在[0, 100]的区间内,随机生成一个整数,而后猜想这个数字。算法

1.1.远古猜测法

        远古猜测法(我本身瞎取的名字)就是从边界的一端开始进行猜数,猜不中则每次增长1(或减小1),直到猜中为止。dom

from random import randint


def guess_number(v_start=0, v_end=100):
    random_num = randint(v_start, v_end)
    print("得到的{0}~{1}之间的随机数为:{2}".format(v_start, v_end, random_num))

    t_guess = v_start
    times = 0
    while True:
        times += 1
        if t_guess > random_num:
            t_guess -= 1
            print("第{0}次猜想的数字为{1},大了,".format(times, t_guess))
        elif t_guess < random_num:
            t_guess += 1
            print("第{0}次猜想的数字为{1},小了,".format(times, t_guess))
        else:
            print("第{0}次猜想的数字为{1},恭喜您猜对了!".format(times, t_guess))
            break


if __name__ == '__main__':
    guess_number()

        远古猜测法很笨重,在长度为n的区间内,最好状况是1次蒙对,最坏状况是要猜n次。因此他的时间复杂度为o(n/2)。函数

运行结果以下:学习

1.2.折半查找法

        折半查找法,就是每次都猜区间首末的平均值m,猜大了就让m成为区间末尾,猜小了就让m成为区间开头。时间复杂度大概是log2(n)。(即底为2的对数函数,n为区间长度)网站

from random import randint


def guess_number(v_start=0, v_end=100):
    random_num = randint(v_start, v_end)
    print("得到的{0}~{1}之间的随机数为:{2}".format(v_start, v_end, random_num))

    t_head, t_rear = v_start, v_end
    times = 0
    while True:
        times += 1
        t_guess = int((t_head + t_rear)/2)
        if t_guess > random_num:
            t_rear = t_guess
            print("第{0}次猜想的数字为{1},大了,".format(times, t_guess))
        elif t_guess < random_num:
            t_head = t_guess
            print("第{0}次猜想的数字为{1},小了,".format(times, t_guess))
        else:
            print("第{0}次猜想的数字为{1},恭喜您猜对了!".format(times, t_guess))
            break


if __name__ == '__main__':
    guess_number()

       通常在第6次猜想时就能出结果,最多猜7次,不能再多了。毕竟 2的7次幂 2<span style="font-size: 8px; vertical-align: top;">7</span>=128,足够覆盖100之内的随机猜数了。url

运行结果以下:spa

        经过上面两个在不一样写法(还谈不上算法)下执行结果来看,在实现某项功能时,仍是要尽量想得深刻些,这样能让你的程序bug更少,运行效率更高。.net

        若是哪位大佬还有比第2种写法更高效的写法,能够在评论区留言,你们能够相互学习和探讨。

2、在未知区间内进行猜想

        场景描述:在未知的区间内,随机生成一个整数,而后猜想这个数字。

2.1.指对数结合猜测1

        先经过指数(2的n次幂)去肯定范围,而后在用对数(折半)查找法来进行猜想。这样猜想,时间复杂度大概在2*n

2.2.指对数结合猜测2

        先经过指数(10的m次幂)去肯定范围,而后在用对数(折半)查找法来进行猜想。这样猜想,时间复杂度大概在m + log2(10^m))

        2.1 和 2.2 ,哪一个的时间复杂度更优呢?我这个数学学渣只能猜会有个交点,交点先后其时间复杂度会有变化。至于更细致严谨的过程,原谅我有点懒,只是简单找个在线网站(https://zh.numberempire.com/graphingcalculator.php?functions=log(x)%2Csqrt(x)%2Csin(x)%2C1%2Fx%2Cx%5E2&xmin=0&xmax=3&ymin=-1.0&ymax=1.0&var=x)验证了下,以下图:

总结:

        一、有限区间,目前以个人眼界来讲,最少猜想次数为log2(n),其中n为区间长度;

        二、无限区间,最少猜想次数为2*n 或 m + log2(10^m)),其中m/n均为肯定未知范围的猜想次数。

上一篇: RS485简介