批处理之家's Archiver

老刘1号 发表于 2020-2-26 20:55

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

[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]

xczxczxcz 发表于 2020-2-26 21:42

烧脑................
设真话 =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 发表于 2020-2-27 02:20

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

red2020 发表于 2020-2-27 02:35

[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]

a20150604 发表于 2020-2-27 03:19

布尔代数化简算法:
设 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
与分析推理结果一致

老刘1号 发表于 2020-2-27 09:43

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

老刘1号 发表于 2020-2-27 09:50

[b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=226809&ptid=54930]2#[/url] [i]xczxczxcz[/i] [/b]


    看不懂.jpg

red2020 发表于 2020-2-27 10:38

[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做的。代码布尔逻辑上等价于你的代码,因为我就是按你的逻辑翻译成位运算而已。

老刘1号 发表于 2022-6-4 18:46

一万年之后学了离散数学的我又回来了,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]

cmd1152 发表于 2022-6-4 19:16

**** 作者被禁止或删除 内容自动屏蔽 ****

cmd1152 发表于 2022-6-4 19:35

**** 作者被禁止或删除 内容自动屏蔽 ****

cmd1152 发表于 2022-6-4 19:38

**** 作者被禁止或删除 内容自动屏蔽 ****

老刘1号 发表于 2022-6-4 19:45

[b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=256412&ptid=54930]10#[/url] [i]cmd1152[/i] [/b]


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

cmd1152 发表于 2022-6-4 19:48

**** 作者被禁止或删除 内容自动屏蔽 ****

页: [1]

Powered by Discuz! Archiver 7.2  © 2001-2009 Comsenz Inc.