不限语言解决“谁做了糗事儿”问题

老刘1号

4人中有1人做了糗事儿，已知有3人说了真话、1人说了谎话。
a说：不是我；
b说：是c；
c说：是d；
d说：c瞎说。
请判断是谁做了糗事儿？

附一个C，无脑排除法：https://tool.lu/coderunner/embed/7Xm.html

xczxczxcz

烧脑................
设真话 =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 说谎。??
纯推理。

a20150604

c说：是d；
d说：c瞎说。
这上二者矛盾, 必一真一假, 故下二者必皆真(已知有3人说了真话、1人说了谎话)
a说：不是我；
b说：是c；
故 c 做了糗事儿

red2020

过于简单，不超过20行搞定

#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;
}COPY

a20150604

布尔代数化简算法：
设 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))

用布尔代数工具化简(各种数学软件都有此能力),此处用一在线工具
https://www.dcode.fr/boolean-expressions-calculator

化简结果
! a && ! b && c && ! d
与分析推理结果一致

老刘1号

回复 4# red2020


    简洁、优雅的代码， 学习了
用按位与运算巧妙的进行了类似排除法的操作
已经被排除的人（0）不会被再次被认定（0&1=0）。

lz才疏学浅，还有一个小疑惑：
我的算法中，遇到将已经排除的”做糗事的人“认定为“做糗事的人”时，会认定为矛盾直接返回
但这个算法中似乎并没有类似的举措，只要最终有人未被排除，就直接认定为该人
这样在遇到其它类似问题时，是否可能会出现因为未返回产生的增根？

老刘1号

回复 2# xczxczxcz


    看不懂.jpg

red2020

回复 6# 老刘1号
取反后与已带有排除矛盾的运算成分，我的就是把你的代码翻译成布尔运算。那两层for已经假设了各种情况,我的1代表的是做了事，最后经过布尔运算只有c位是1，就是说是c做的。代码布尔逻辑上等价于你的代码，因为我就是按你的逻辑翻译成位运算而已。

老刘1号

一万年之后学了离散数学的我又回来了，5楼标准答案，

附一个列真值表求解的：

@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%%
)
pauseCOPY

cmd1152

A=0 （没有人说是他，所以是0人）
B=0 （没有人说是他，所以是0人）
C=2 （2人说是他，所以是2人）
D=1  （2人说是他，所以是2人）
设说C有1人是假话，那么第二个一定是真话，所以是C

cmd1152

@echo off
%格式化，设为1%
for %%i in (a b c d) do (set %%i=1)
%A说不是A%
set /a a=a-1
%B说C%
set /a c=c+1
%C说D%
set /a d=d+1
%D说C%
set /a c=c+1
setlocal enabledelayedexpansion
echo;!a!>tmp.tmp
echo;!b!>>tmp.tmp
echo;!c!>>tmp.tmp
echo;!d!>>tmp.tmp
for /f %%i in ('sort tmp.tmp') do (set xy=%%i)
del tmp.tmp
for %%i in (a b c d) do (if "!xy!"=="!%%i!" echo;%%i)
pauseCOPY

cmd1152

回复 9# 老刘1号


    啊啊啊啊，我才发现这是坟贴...

老刘1号

回复 10# cmd1152


    d说c是假不代表d说是c哦

cmd1152

回复 13# 老刘1号


    只有一个人说谎...D如果不是说C那么B就有点矛盾了