算法设计: 成语接龙，自动接龙到“为所欲为”？简单递归搜索就行！

2023-12-18 13:51| 来源: 网络整理| 查看: 265

头图？这个能少？

博客：https://www.mintimate.cn Mintimate’s Blog，只为与你分享

成语接龙

“成语接龙”的话，大家应该很熟悉，就是以一个成语开始，根据成语最后一个字，找到另一个可以接上的成语；再根据最后一个字继续找，一直连接下去。本身就是一个递归的过程，这是一个富有挑战且充满乐趣的语言游戏。

当然，不同地方有不同的版本，一般有两个主要分支版本：

多音字版本：成语与成语间，使用多音字进行连接；如：风和日丽（lì）->立足之地（dì）->地大物博（bó）精准字版本：成语与成语间，使用精确的字进行连接；如：明知故问->问长问短->短兵相接

记得我小时候，语文老师就喜欢课前成语接龙，成语接龙失败的同学，就在三天后的语文课上一起表演节目；我当时偶尔接龙不出来，要上台表演唱歌，我每次都是假唱、对口型（🤫哔~~）

为所欲为

接龙到“为所欲为”的话，是上次粉丝突然和我说，给她任意一个成语，她可以接龙到“为所欲为”；我立马让她接龙一个: 魑魅魍魉。

图片仅供参考

于是…… 我成功结束了对话……

牛吧

不过，后来我得知，是因为她发现了一个神奇的网站：

自动成语接龙

确实挺好玩的；不过，不够有趣，我们能不能更有趣点？比如：接龙的内容更长？接龙的成语有些随机？

算法设计

我们需要设计一个自动接龙到成语接龙的算法，需要如何设计呢？

算法的设计很简单，在有用词库的前提下，主要分为两种：

广度优先和词图的算法；递归搜索成语。

实际上，上文展示的网站，使用的算法就是广度优先和词图的算法，建立一个词图，内部包含多条路径，根据所给的词进行命中。这个留到下期，有机会和大家说说如何设计。

本次，我们就演示看看，如何靠递归，一层一层搜索出成语。

词库获取

首先，我们需要一个词库，用一个词库来获取成语。你当然可以使用数据库实现，把古汉语大全直接入库，之后使用SQL去查询。

当然，对于我来说有些尴尬，最近我用的比较多的是Nuxt3；暂时，不想直接上Java。虽然用Nodejs，写个中间件或者直接用Nodejs也可以作为后端操作Sqlite、MySQL等等数据库，但是就为了一个小小的功能，引入数据库，我认为不是很划算。

为此，我这里找到了这个库： https://github.com/theajack/cnchar

cnchar库

而这个库有一个子库，集成了一个成语库：

成语库

我们按提示，使用一下，试试看：

import cnchar from "cnchar"; import 'cnchar-idiom' const testWords = cnchar.idiom(['为', '', '', '']); // 查找“为”开头的成语 console.log(testWords)

打印结果：

打印结果

这样就解决了词库问题。不过词库可能有点不准，或者和古汉语词典有所差异；如果有严格的要求，建议还是需要SQL。

嘿嘿递归搜索

接下来，我们需要构建递归搜索的算法，总体的逻辑：

递归逻辑

调用API的方法，我们留在下次讲，也就是使用图的方法，实现的快速搜索。

这次我们的递归逻辑很简单，在Vue内，首先是判断是不是“为”结尾，如果是，就不用“为所欲为”遍历了：

// 获取成语最后一个字（或拼音=>预留，本次未使用） const getLastWordOrSpell = (s, m) => { s = s || '' if (m === 'spell') { return cnchar.spell(s.replace(/^(.*[n])*.*(.|n)$/g, '$2')).toLowerCase() } else { return s.slice(-1); } } … const keyWord = inputWord.value const lastWord = getLastWordOrSpell(keyWord) if (lastWord === '为') { generatorChainsWords.value = "『" + inputWord.value + "』不用『为所欲为』，也能『为所欲为』"; loading.value = false; return }

之后，我们定义一个方法，用于查找每个成语最后一个字，可以关联出的成语：

注意，我这里还使用了一个洗牌算法，实际上就是数组乱序打乱，参考：

// 洗牌算法 const shuffleArray = (array) => { for (let i = array.length - 1; i > 0; i--) { const j = Math.floor(Math.random() * (i + 1)); [array[i], array[j]] = [array[j], array[i]]; } return array; }

当然，最后生成一个入口函数：

const chainWords = getIdiomChainByRecursive(lastWord, 0, false, [keyWord], selected) if (chainWords === -1) { generatorChainsWords.value = "『" + inputWord.value + "』不能『为所欲为』" } else if (chainWords === 0) { generatorChainsWords.value = "『" + inputWord.value + "』迷路了，请重试『为所欲为』" } else { generatorChainsWords.value = chainWords + "->为所欲为" } loading.value = false

到此，我们的递归就生成完成了。

效果

最后，我们来看看效果，我这里用Nuxt3配合NuxtUI构建：