写给妹妹的编程札记 6 - 搜索实战: 单词博弈

2023-11-11 10:21

本文主要是介绍写给妹妹的编程札记 6 - 搜索实战: 单词博弈,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

        最近,CSDN上的在线编程比赛中,有一道题目《单词博弈》。这道题目是一个很好的可以使用搜索来解决的例子。

题目详情
本第一次在线编程大赛由文思海辉冠名,题目如下:
甲乙两个人用一个英语单词玩游戏。两个人轮流进行,每个人每次从中删掉任意一个字母,如果剩余的字母序列是严格单调递增的(按字典序a < b < c <....<z),则这个人胜利。两个人都足够聪明(即如果有赢的方案,都不会选输的方案 ),甲先开始,问他能赢么?
输入: 一连串英文小写字母,长度不超过15,保证最开始的状态不是一个严格单增的序列。
输出:1表示甲可以赢,0表示甲不能赢。
例如: 输入 bad, 则甲可以删掉b或者a,剩余的是ad或者bd,他就赢了,输出1。
又如: 输入 aaa, 则甲只能删掉1个a,乙删掉一个a,剩余1个a,乙获胜,输出0。

        有别于以往的搜索问题,在这个问题中,有两个角色,为游戏双方 - 甲和乙。 但,需要说明的是, 这个题目比平常的围棋象棋简单很多,一个是问题的搜索空间很小, 另一个是任意一个状态对甲乙来说是一样的。比如,甲乙面对字符串bad的输赢情况是一样的。 不难看出,对于一个状态,要么先玩的选手赢,要么先玩的选手输,只有这两种可能。题目已经假设最开始的状态不是一个严格单增的序列,并且如果一个选手通过删除掉一个字母到达一个单增序列的话就可以胜利。那么,我们有下面的发现:

        1. 如果一个字母序列X是单增的, 那么,对于这个序列来说, 先行者输

        2. 否则,一个长度为k的字母序列X, 删除一个字母后, 可以得到k个字母序列(删除其中的第1,2,...,k个字母分别得到字母序列Y_1, Y_2, ..., Y_k )

            a. 如果这k个字母序列中任意一个是先行者输, 那么X是先行者赢

                为什么? 假设Y_i是先行者输,那么对于字母序列X来说, 作为先行者,我们只要删除字母i,到达Y_i, 下一个选手就输了。

            b. 如果这k个字母序列中任意一个都不是先行者输, 也就是说所有k个字母序列都是先行者赢, 那么X是先行者输

                为什么? 因为对于X这个字母序列来说, 不管我们删除哪个字母,到达的k个字母序列都是先行者赢。 也就是下一个选手会赢。


        有了上面的这些观察, 让我们来看看整棵博弈搜索树是怎样的? 拿“bdca”为例吧 (图中W表示先行者赢, L表示先行者输)


        对于字母序列"bdca",首先搜索第一个分支"_dca",当搜索完分支"_dca"之后,发现"_dca"是一个先行者输的状态,也就是说我们如果删除字母b,到达字母序列"_dca"的话,下一个选手不管怎么走都是输,也就是说"bdca"是先行者赢的,我们的取胜策略是删除第一个字母。 后面的三个分支没有必要计算了。

        到这里为止,应该不难写出一个搜索程序来了。需要注意的地方是, 像往常一样, 搜索树上有很多节点是重复的,比如上面"___a", "__c_"等。 搜索时候如何避免这些重复状态将直接影响整个程序的效率。

        考虑下,搜索树中可能的字母序列数目是多少呢? 如果输入字母序列长度为k, 那么可能的字母序列为2^k  (序列中每个字母都可能被删除了或者还没有被删除)。 题目中限制输入的字母序列长度不超过15,所以搜索树中可能的字母序列不超过2^15, 是一个很小的数目。比如,"bdca"可以用15表示 (2^4 - 1), 4个bit, 每个bit都是1. “_dca”可以用14表示,除了第一个bit其他bit都是1. 我们可以申请一个空间v[], v[i]记录i对应的字母序列是先行者赢还是先行者输。 搜索的伪代码如下:

char search(int state)
{// 检查state是否已经计算过,避免重复计算if (v[state] != '') {return v[state];}// 检查state是否是单增序列, 如果是单增序列,返回"L"if (单增序列) {return 'L';}// 尝试删除每一个字母,看是否能找到先行者输的字母序列for (int i = 0; i < k; i++) {next_state = 删除字母i之后得到的新的字母序列if (search(next_state) == 'L') return 'W';}return 'L';
}

        由于搜索的整个空间很少, 下面是一个遍历所有可能字母序列的程序, 没有按上面伪代码这样编写常规的递归搜索程序。 一个不足的地方在于,可能计算了一些字母序列,但这些字母序列根本没有必要计算。 比如上图中,经过剪枝, 需要计算的字母序列数目非常少。好处当然是图方便编写简单。 至于,为什么从小到大开始计算呢? 因为每一个字母序列x,删除其中任意一个字母后得到新的字母序列y, 那么x对应的整数一定比y对应的整数大。 从小到大遍历一遍所有可能的字母序列可以保证在计算x对应的字母序列时,该字母序列通过删除字母得到的字母序列肯定都已经计算过了。

int who(const char* word)
{int   n = strlen(word);int   nState = (1<<n);int   k, nextK, i;char* v = (char*)malloc(sizeof(char) * nState);memset(v, 0, sizeof(char) * nState);for(k = 1; k < nState; k++) {// 检查是否单增字母序列int isFinished = 1;char prevChar = 'a' - 1;for(i = 0; i < n; i++) {if ((k & (1<<i)) > 0) {if (word[i] <= prevChar) {isFinished = 0; break;} else {prevChar = word[i];}}}// 1. 如果单增序列 - 先行者输if (isFinished) {v[k] = 'L';}else{// 2. 如果不是单增序列,检查可能的子节点,当找到先行者输节点时可以提前终止int canWin = 0;for(i = 0; i < n; i++) {if ((k & (1<<i)) > 0) {nextK = k ^ (1<<i);if (v[nextK] == 'L') { canWin = 1; break;}}}if (canWin) v[k] = 'W'; else v[k] = 'L';}}int win = (v[nState - 1] == 'W') ? 1 : 0;free(v);if (win) return 1; else return 0;
}


这篇关于写给妹妹的编程札记 6 - 搜索实战: 单词博弈的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/389388

相关文章

基于Canvas的Html5多时区动态时钟实战代码

《基于Canvas的Html5多时区动态时钟实战代码》:本文主要介绍了如何使用Canvas在HTML5上实现一个多时区动态时钟的web展示,通过Canvas的API,可以绘制出6个不同城市的时钟,并且这些时钟可以动态转动,每个时钟上都会标注出对应的24小时制时间,详细内容请阅读本文,希望能对你有所帮助...

Python使用DeepSeek进行联网搜索功能详解

《Python使用DeepSeek进行联网搜索功能详解》Python作为一种非常流行的编程语言,结合DeepSeek这一高性能的深度学习工具包,可以方便地处理各种深度学习任务,本文将介绍一下如何使用P... 目录一、环境准备与依赖安装二、DeepSeek简介三、联网搜索与数据集准备四、实践示例:图像分类1.

Spring AI与DeepSeek实战一之快速打造智能对话应用

《SpringAI与DeepSeek实战一之快速打造智能对话应用》本文详细介绍了如何通过SpringAI框架集成DeepSeek大模型,实现普通对话和流式对话功能,步骤包括申请API-KEY、项目搭... 目录一、概述二、申请DeepSeek的API-KEY三、项目搭建3.1. 开发环境要求3.2. mav

基于Python实现多语言朗读与单词选择测验

《基于Python实现多语言朗读与单词选择测验》在数字化教育日益普及的今天,开发一款能够支持多语言朗读和单词选择测验的程序,对于语言学习者来说无疑是一个巨大的福音,下面我们就来用Python实现一个这... 目录一、项目概述二、环境准备三、实现朗读功能四、实现单词选择测验五、创建图形用户界面六、运行程序七、

Python与DeepSeek的深度融合实战

《Python与DeepSeek的深度融合实战》Python作为最受欢迎的编程语言之一,以其简洁易读的语法、丰富的库和广泛的应用场景,成为了无数开发者的首选,而DeepSeek,作为人工智能领域的新星... 目录一、python与DeepSeek的结合优势二、模型训练1. 数据准备2. 模型架构与参数设置3

Java实战之利用POI生成Excel图表

《Java实战之利用POI生成Excel图表》ApachePOI是Java生态中处理Office文档的核心工具,这篇文章主要为大家详细介绍了如何在Excel中创建折线图,柱状图,饼图等常见图表,需要的... 目录一、环境配置与依赖管理二、数据源准备与工作表构建三、图表生成核心步骤1. 折线图(Line Ch

Java使用Tesseract-OCR实战教程

《Java使用Tesseract-OCR实战教程》本文介绍了如何在Java中使用Tesseract-OCR进行文本提取,包括Tesseract-OCR的安装、中文训练库的配置、依赖库的引入以及具体的代... 目录Java使用Tesseract-OCRTesseract-OCR安装配置中文训练库引入依赖代码实

使用 sql-research-assistant进行 SQL 数据库研究的实战指南(代码实现演示)

《使用sql-research-assistant进行SQL数据库研究的实战指南(代码实现演示)》本文介绍了sql-research-assistant工具,该工具基于LangChain框架,集... 目录技术背景介绍核心原理解析代码实现演示安装和配置项目集成LangSmith 配置(可选)启动服务应用场景

在Java中使用ModelMapper简化Shapefile属性转JavaBean实战过程

《在Java中使用ModelMapper简化Shapefile属性转JavaBean实战过程》本文介绍了在Java中使用ModelMapper库简化Shapefile属性转JavaBean的过程,对比... 目录前言一、原始的处理办法1、使用Set方法来转换2、使用构造方法转换二、基于ModelMapper

Java实战之自助进行多张图片合成拼接

《Java实战之自助进行多张图片合成拼接》在当今数字化时代,图像处理技术在各个领域都发挥着至关重要的作用,本文为大家详细介绍了如何使用Java实现多张图片合成拼接,需要的可以了解下... 目录前言一、图片合成需求描述二、图片合成设计与实现1、编程语言2、基础数据准备3、图片合成流程4、图片合成实现三、总结前