vlambda博客
学习文章列表

从猜数游戏到二分查找算法


不点蓝字,我们哪来故事?



往期推荐  

点击标题即可阅读




今天我们一起用python写一个猜数游戏。先来看看现实生活中我们是什么玩法。首先我们需要在大脑中假定一个数字,当然这个数需要有一个范围,比如1到100,然后让对方去猜这个数字,如果数字大于或者小于目标数字就给出相应的提示,直到对方猜出数字,游戏结束。

01


先来写个猜数游戏.


思路分析:(算法描述)


下面我们按照这个流程图来实现这个程序。按照惯例,我们先用scratch试一下。


从猜数游戏到二分查找算法


你用几次能猜到这个数捏?游戏如果没有挑战性,也就失去了它的趣味。所以我们需要在上面的程序中,稍作修改,增加次数限制。


从猜数游戏到二分查找算法

python程序又该如何实现呢?


import random
import time
print('猜数字游戏:随机抽取一个1~100内的秘密数字,猜对了游戏结束')# 打印游戏提示
time.sleep(1)
print('不过,你只有5次机会哦~')
time.sleep(1)
secret_number = random.randint(1, 100) # 生成秘密数字
times = 5 # 设置游戏可猜次数
    # 直到猜数字次数用完之前,循环
while times:
    times -= 1 # 执行一轮猜测消耗一次猜数次数
    guess=int(input('你猜的数字是:'))
    time.sleep(0.5)
    if guess > secret_number :# 当猜测值比秘密数字大时的提示
        print('比秘密数字大!(>﹏<)~~')
    elif guess < secret_number:# 当猜测值比秘密数字小时的提示
        print('比秘密数字小!(´д`)ゞ。。。。')
    # 猜中时的提示,并且结束游戏
    else:
        print('你猜对啦!秘密数字是:{},你猜了{}次就猜到了(^_^)~~~'.format(secret_number,5-times))
        break
     # 当次数剩下一次的提示
    if times == 1:
        time.sleep(0.8)
        print('最后一次机会啦!猜不到就公布答案')
    # 猜不中的提示
    elif times == 0:
        time.sleep(0.8)
        print('你有5次机会,可惜你没有珍惜!正确答案是:{}!'.format(secret_number))
    time.sleep(0.8)


程序中用了random模块,用于生成随机数,random.randint(1, 100)生成了一个1到100之间的整数。time模块,time.sleep(0.8)产生一个以秒为单位的时间间隔。为什么循环条件是  while times: 在python中像while 1, while 2, while -1, while -2, while x, 只要不等于0, 就是条件永远为真, 等价于while True,while 0 等价于 while False。所以循环的条件就是times不等于0。


程序最重要的是要严谨,如果用户不按套路出牌,输入了大于100的数,或者直接输入字符而不是数字呢,程序是不是也应该做出一些回应?这就是异常。我们在程序开发的时候,很难将所有的特殊情况都处理,通过异常捕获可以针对突发事件做集中处理,从而保证程序的健壮性和稳定性。


在程序开发中,可以增加try来捕获异常。

try:尝试执行的代码
except:出现错误的处理


try:
    guess = int(guess)
    if guess < 1 or guess > 100:
        raise ValueError
# 报错时输出提示
except ValueError:
    print('\n请输入一个1~100的数字哦!')


接下来,给出完整的代码:


import random
import time
print('猜数字游戏:随机抽取一个1~100内的秘密数字,猜对了游戏结束')# 打印游戏提示
time.sleep(1)
print('不过,你只有5次机会哦~')
time.sleep(1)
secret_number = random.randint(1, 100) # 生成秘密数字
times = 5 # 设置游戏可猜次数
    # 直到猜数字次数用完之前,循环
while times:
    times -= 1 # 执行一轮猜测消耗一次猜数次数
    guess=input('你猜的数字是:')
    time.sleep(0.5)
    try:
        guess = int(guess)
        if guess < 1 or guess > 100:
            raise ValueError
    # 报错时输出提示
    except ValueError:
        print('\n请输入一个1~100的数字哦!')
    else:
        if guess > secret_number :# 当猜测值比秘密数字大时的提示
            print('比秘密数字大!(>﹏<)~~')
        elif guess < secret_number:# 当猜测值比秘密数字小时的提示
            print('比秘密数字小!(´д`)ゞ。。。。')
        # 猜中时的提示,并且结束游戏
        else:
            print('你猜对啦!秘密数字是:{},你猜了{}次就猜到了(^_^)~~~'.format(secret_number,5-times))
            break
     # 当次数剩下一次的提示
    if times == 1:
        time.sleep(0.8)
        print('最后一次机会啦!猜不到就公布答案')
    # 猜不中的提示
    elif times == 0:
        time.sleep(0.8)
        print('你有5次机会,可惜你没有珍惜!正确答案是:{}!'.format(secret_number))
    time.sleep(0.8)


你5次之内能猜到这个数吗?我试了一下,好像有点难度,这是我猜数的过程。


从猜数游戏到二分查找算法



02㏒


开个外挂,二分查找法.


你的目标是以最少的次数猜到这个数字。假设你从1开始依次往上猜,那么你每次只能排除一个数字,这种方法就是通俗的傻找法,如果这个数是100,你就需要找100次。


下面是一种更佳的猜法,从50开始,如果小了,你知道1--50都小了,接下来你猜75,大了,50--75都大了,余下的数字又排除了一半。这种搜索算法每一次比较都使搜索范围缩小一半。这就是二分查找法,这是一种算法。


不管你心里想的是哪个数字,1--100的一个数,你最多7次,都能猜到它。


一般来说,对于包含n个元素的列表,用二分查找法,最多需要从猜数游戏到二分查找算法步。如果让你猜一个1--1000的数,需要从猜数游戏到二分查找算法,也就是10次。需要说明的是,仅当列表有序的时候,二分查找才有用。


下面看看如何写出用二分查找法猜数的python代码。


import random
secret_number = random.randint(1, 1000) # 生成秘密数字
lis=list(range(1,1001))
low=0
high=len(lis)-1
n=0
while low<=high: #直到范围缩小到一个元素
    mid=(low+high)//2 #取中间值,向下取整,将索引赋值给mid
    guess=lis[mid]#在列表中找到这个数
    print(guess,end="\t")
    n+=1
    if guess==secret_number:
        print("\n我猜到这个数了,它是:{}。我猜了{}次".format(guess,n))
        break
    if guess>secret_number:
        high=mid-1
    else:
        low=mid+1
print("秘密数字是:{}".format(secret_number))


来吧,展示。


从猜数游戏到二分查找算法


如果要猜的数字是1--40亿,需要多少次呢?答案是最多猜32次,这也太厉害了吧,感觉像开了外挂。二分查找的运行时间为对数时间。


和你的小伙伴用二分查找法玩猜数游戏吧,注意尽量让他想的数大一点,再大一点。


差一点

我们就擦肩而过了

有趣

有用

有态度