steam上有一个叫图灵完备(turing complete)的游戏,其中一个关卡比较有意思,故此记录,也就是“成对的麻烦”。
题目大意是匹配袜子的问题,有4个输入,只要其中两个位true,最终结果就返回true,否则返回false。要求使用与或非的逻辑电路完成这种匹配结果。(还有异或、非或、非与等逻辑也可以使用)
一、分析
1、如果只要求“一个输入为真,结果为真”则比较简单,使用或逻辑把所有输入连接起来即可。
问题在于如何识别两个输入为真的情况,与或两种逻辑都可以,但如果在4个输入上面应用则略显复杂,故而,尝试将输入假设为两个的情况。
2、假设有两个输入,只要有两个true,就返回true,否则返回false。——这就是与逻辑。
3、假设有三个输入,只要有两个true,就返回true,否则返回false。首先依然使用与逻辑匹配每两个输入的组合情况,需要匹配3次。然后使用或逻辑把所有与逻辑的匹配结果收集起来,最终完成假设。——这里有3个与逻辑。
4、假设有四个输入,只要有两个true,就返回true,否则返回false。继续使用与逻辑匹配,需要匹配6次。然后使用或把所有匹配结果收集起来,完成假设。——这里有6个与逻辑。
二、答案
在最后一条的分析的里面,使用与逻辑进行匹配,使用或逻辑收集最终结果。
三、分析方法与背后的逻辑
与或非的逻辑:略。
分析方法:递归,或者数学归纳法。通过降低问题的规模,简化问题的复杂度,在解决相对简单的相似小问题后,再利用相似小问题的解决经验(公式),适配复杂的大问题。(这也可以是解决复杂问题的一般模式)
三、扩展
1、假设有N个输入呢?
2、假设需要匹配M个输入为true呢?