图灵完备-奇数个信号
前言:我不知道背后逻辑,我没有推测完成,但我成功了。
奇数个信号是图灵完备游戏-成对的麻烦的下一个关卡,大意是在四个输入中,只有奇数个输入true才返回true,否则返回false。关卡要求只能使用三个逻辑元件。记录上一篇文章的原因是其分析方法很有意思,记录本文的原因是,我按照上一文中的分析方法,分析到一半的时候直接猜中了答案。
一、分析
按照本文题意进行如下分析:
1、假设2个输入中,只有一个输入true才返回true,否则返回false。实际上就是要求true和false不同的时候才返回true(两个true和两个false都不符合要求),即符合异或逻辑的条件。
2、假设3个输入中,只有一个输入true才返回true,否则返回false。因为或是“只要”的逻辑,不符合题意中“只有”的要求,所以无法使用或逻辑收集异或的结果。使用第一个异或匹配两个输入,然后用第二个异或处理前一个异或的结果和第三个输入,经验证除了在3个true的输入中,这种结构返回true之外,其他情况都符合假设。而三个true的输入符合题意,即奇数个true。
因为关卡要求只能使用三个逻辑元件,所以这里我尝试了三个堆叠的异或逻辑,结果通过!!!(这也就是前言中,我懵懂的通过了关卡)
3、假设4个输入中,只有一个输入true才返回true,否则返回false。这里蕴含的规律感觉很难说明,大概是异或逻辑要求必须不同的数才返回true,在堆叠状态下的数量无法确定,但总true的数量总是奇数个。感觉此关卡专为该规律而设计。
二、答案
4个输入,将三个异或堆叠起来,最终实现题意要求,即匹配奇数个信号。
三、背后逻辑
略。
四、扩展
1、假设有N个输入呢?
2、假设需要匹配偶数个输入为true呢?