不限语言解决“谁做了糗事儿”问题
[i=s] 本帖最后由 老刘1号 于 2020-2-26 21:04 编辑 [/i][quote]4人中有1人做了糗事儿,已知有3人说了真话、1人说了谎话。
a说:不是我;
b说:是c;
c说:是d;
d说:c瞎说。
请判断是谁做了糗事儿?[/quote]
附一个C,无脑排除法:[url]https://tool.lu/coderunner/embed/7Xm.html[/url] 烧脑................
设真话 =1 ; a=b=c=d=1; 假话为 -1;
a说不是我 a=1;
b说是c c=1+(-1)=0;
c说是d d=1+(-1)=0;
d说c瞎说 c=0+(-1)=-1;
所以 C 说谎。??
纯推理。 :) c说:是d;
d说:c瞎说。
这上二者矛盾, 必一真一假, 故下二者必皆真(已知有3人说了真话、1人说了谎话)
a说:不是我;
b说:是c;
故 c 做了糗事儿 [i=s] 本帖最后由 red2020 于 2020-2-27 02:37 编辑 [/i]
过于简单,不超过20行搞定[code]#include <stdio.h>
int main ()
{
unsigned char matrix[128];
matrix['a'] = 0x07; //二进制 0111 ,a说不是我,相当于其他人都有可能,所以除一号位其他位都标记为二进制1
matrix['b'] = 0x02; //二进制 0010 ,b说是c,把三号位标记为二进制1
matrix['c'] = 0x01; //二进制 0001 ,c说是d,把四号位标记为二进制1
matrix['d'] = (~matrix['c'])&0x0F; //二进制 1110 ,d说c瞎说,相当c的矩阵值取反,~matrix['c']表示
for(int j = 'a'; j <= 'd'; j++)
{
unsigned char judgeMark = 0x0F; //只取一个字节的后4位标记abcd做的状态
for(int i = 'a'; i <= 'd'; i++)
judgeMark &= (i == j)?~matrix[i]:matrix[i];
if(judgeMark)
printf("It's '%c'. :[%d,%d,%d,%d]\n", j, (judgeMark>>3)&1, (judgeMark>>2)&1, (judgeMark>>1)&1, judgeMark&1);
}
return 0;
}
[/code] 布尔代数化简算法:
设 a,b,c,d 4个基本命题分别表示4人中的同命题字母代号者做了糗事儿
由 "4人中有1人做了糗事儿" 可得
P式:
(a && !b && !c && !d) ||
(!a && b && !c && !d) ||
(!a && !b && c && !d) ||
(!a && !b && !c && d)
将4人的说法转化为基本命题布尔代数式
a说:不是我; asay: !a
b说:是c; bsay: c
c说:是d; csay: d
d说:c瞎说。 dsay: !csay <==> !d
由 "有3人说了真话、1人说了谎话" 可得
Q式:
(! !a && c && d && !d) ||
(!a && !c && d && !d) ||
(!a && c && !d && !d) ||
(!a && c && d && ! !d)
P式 && Q式:
(
(a && !b && !c && !d) ||
(!a && b && !c && !d) ||
(!a && !b && c && !d) ||
(!a && !b && !c && d)
) && (
(! !a && c && d && !d) ||
(!a && !c && d && !d) ||
(!a && c && !d && !d) ||
(!a && c && d && ! !d)
)
格式化为单行排版
((a && !b && !c && !d) || (!a && b && !c && !d) || (!a && !b && c && !d) || (!a && !b && !c && d)) && ((! !a && c && d && !d) || (!a && !c && d && !d) || (!a && c && !d && !d) || (!a && c && d && ! !d))
用布尔代数工具化简(各种数学软件都有此能力),此处用一在线工具
[url]https://www.dcode.fr/boolean-expressions-calculator[/url]
化简结果
! a && ! b && c && ! d
与分析推理结果一致 [b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=226813&ptid=54930]4#[/url] [i]red2020[/i] [/b]
简洁、优雅的代码, 学习了
用按位与运算巧妙的进行了类似排除法的操作
已经被排除的人(0)不会被再次被认定(0&1=0)。
lz才疏学浅,还有一个小疑惑:
我的算法中,遇到将已经排除的”做糗事的人“认定为“做糗事的人”时,会认定为矛盾直接返回
但这个算法中似乎并没有类似的举措,只要最终有人未被排除,就直接认定为该人
这样在遇到其它类似问题时,是否可能会出现因为未返回产生的增根? [b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=226809&ptid=54930]2#[/url] [i]xczxczxcz[/i] [/b]
看不懂.jpg [b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=226816&ptid=54930]6#[/url] [i]老刘1号[/i] [/b]
取反后与已带有排除矛盾的运算成分,我的就是把你的代码翻译成布尔运算。那两层for已经假设了各种情况,我的1代表的是做了事,最后经过布尔运算只有c位是1,就是说是c做的。代码布尔逻辑上等价于你的代码,因为我就是按你的逻辑翻译成位运算而已。 一万年之后学了离散数学的我又回来了,5楼标准答案,
附一个列真值表求解的:[code]@echo off
for /l %%i in (0 1 0xf) do (
set /a "a=%%i&1,b=(%%i>>1)&1,c=(%%i>>2)&1,d=(%%i>>3)&1"
set /a "result=((a & !b & !c & !d) | (!a & b & !c & !d) | (!a & !b & c & !d) | (!a & !b & !c & d)) & ((! !a & c & d & !d) | (!a & !c & d & !d) | (!a & c & !d & !d) | (!a & c & d & ! !d))"
call echo [%%a%% %%b%% %%c%% %%d%%] - %%result%%
)
pause
[/code] **** 作者被禁止或删除 内容自动屏蔽 **** **** 作者被禁止或删除 内容自动屏蔽 **** **** 作者被禁止或删除 内容自动屏蔽 **** [b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=256412&ptid=54930]10#[/url] [i]cmd1152[/i] [/b]
d说c是假不代表d说是c哦 **** 作者被禁止或删除 内容自动屏蔽 ****
页:
[1]