注册 登录
Python基础教程

第一章: 环境搭建,安装Python

第二章: 挑选一款趁手的IDE

第三章: 计算机基础知识

第四章: 命令行基础知识

第五章: 从全局把握Python

第六章: Python语言基础

第七章: Python流程控制

第八章: Python数据类型与运算

第九章: Python字符串类型

第十章: Python列表类型

第十一章: Python元祖类型

第十二章: Python字典类型

第十三章: Python集合类型

第十四章: Python函数处理

第十五章: Python文件处理

第十六章: Python面向对象

第十七章: Python异常处理

第十八章: Python模块处理

第十九章: Python项目实战

首页 > Python基础教程 > 第十九章: Python项目实战 > 19.2节:进阶的猜姓名游戏

19.2节:进阶的猜姓名游戏

薯条老师 2021-08-13 10:07:13 208052 0

编辑 收藏

进阶的猜姓名游戏

上节中实现了一个简单的猜数字游戏,程序启动时获取一个随机值,根据用户的输入提示大了还是小了。在本节的程序实战中,实现一个进阶的猜谜游戏:

定义一个人名集合,例如 {"王祖贤", "李嘉欣", "李嘉诚", "刘德华", "叶倩文","叶倩倩", "王李丹妮"}。如果用户的输入前缀匹配第一个字,则提示"不错,有点接近了",前缀匹配前面两个字,则提示"厉害,比较接近了",完全匹配则提示"哇塞,你是个猜姓名天才,请收下我的膝盖"

程序难点分析

实现该程序的难点在于如何快速判断用户的输入是否为某一个姓名的前缀,若将用户的输入与词典中的所有姓名逐字符进行比较,能实现该功能,但性能很差。在数据结构中有一种经典的Trie结构,可利用字典对象来构造一个类似于Trie树的索引结构,这样就可以快速的进行姓名的前缀匹配。

1613370823(1).jpg

构造该Trie结构的算法逻辑很简单,以第一次构造为例

将姓名中的第一个字作为键插入到指针指向的空字典中,键值为一个空字典,然后将指针指向键值所对应的空字典,接着将姓名中的第二个字作为键插入到指针指向的空字典中,键值为一个空字典,同样需要将指针指向键值所对应的空字典,不断重复这样的过程,直到遍历完姓名中的所有字符。

简化的代码实例:

name = "王八蛋"
trie = {}
trie[name[0]] =  {}
trie[name[0]][name[1]] =  {}
trie[name[0]][name[1]][name[2]] =  {}

这样在查找用户的输入是否包含某姓名的前缀时,只需要遍历用户输入的字符,然后在构造好的Trie结构中进行查找。

程序完整源码

# __author__ = 薯条老师
# 微信公众号 =  薯条编程
import time



def countdown(seconds=3, message=""):
    """
    :param seconds: 倒数的秒数
    :param message:  倒计时结束后输出的提示信息
    :return:
    """
    for _ in range(seconds, 0, -1):
        _, _ = print(_), time.sleep(1)
    else:
        print(message)
        
        
        
def build_lookup_table(data):
    """
    :param data: a set of names, e.g: {"王祖贤", "李嘉欣"}
    :return: lookup table e.g:{'王': {'祖': {'贤': {}}}, '李': {'嘉': {'欣': {}}}}
    """
    lookup_table = {}
    for name in data:
        lookup_table_ = lookup_table
        for char in name:
            if char not in lookup_table_:
                lookup_table_[char] = {}
            lookup_table_ = lookup_table_[char]
    return lookup_table
    
    
    
def guess_name():
    stars = {"王祖贤", "李嘉欣", "李嘉诚", "刘德华", "叶倩文", "叶倩倩", "王李丹妮"}
    # 构造一个查找表
    lookup_table = build_lookup_table(stars)
    countdown(3, "猜姓名游戏开始,Go!!!")
    messages = {0: "不要瞎猜好吗?",  1: "不错,有点接近了",  2: "厉害,比较接近了",
                66: "哇塞,你是个猜姓名天才,请收下我的膝盖"}
    end = 2
    while True:
        name = input("请输入你要猜的姓名:____\b\b\b\b")
        if name in stars:
            print(messages[66])
            if input("按键盘任意键继续玩猜数字游戏或输入quit退出游戏:____\b\b\b\b").lower() == "quit":
                break
        else:
            lookup_table_ = lookup_table
            index = 0
            for word in name:
                if word in lookup_table_:
                    lookup_table_ = lookup_table_[word]
                    index = index+1 if index < end else index
                else:
                    break
            print(messages[index])
if __name__ == "__main__":
    guess_name()

程序的输出界面

1613372737(1).jpg

项目扩展









欢迎 发表评论:

请登录

忘记密码我要注册

注册账号

已有账号?请登录