V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
dwadewyp
V2EX  ›  Python

这道逻辑题 用 Python 代码 如何实现?

  •  1
     
  •   dwadewyp · 116 天前 · 2434 次点击
    这是一个创建于 116 天前的主题,其中的信息可能已经有所发展或是发生改变。
    1.第一个答案是 A 的问题是哪一个?  ()
    	A:1  B:2  C:3  D:4
    
    2.唯一的连续两个具有相同答案的问题是 ()
    	A:5,6  B:6,7  C:7,8  D:8,9
    
    3.本问题答案和哪一个问题的答案相同 ()
    	A:4  B:9  C:8  D:2
    
    4.答案是 A 的问题的个数是 ()
    	A:5  B:4  C:3  D:2 
    
    5.本问题答案和哪一个问题的答案相同 ()
    	A:1  B:2  C:3  D:4
    
    6.答案选 A 的问题的个数和答案选什么的问题的个数相同 ()	
    	A:无  B:C  C:C  D:D
    
    7.按照字母顺序, 本题答案与下一题相差 () {A 与 B 间,或 B 与 A 间均相差 1}
    	A:3  B:2  C:1  D:0
    
    8.十道题中答案为元音的题数为 ()
    	A:0  B:1  C:2  D:3
    
    9.十道题中答案为辅音的题数为 ()
    	A:是合数  B:是质数  C:<5  D:是平方数
    
    10.本题答案为 ()
    	A:A  B:B  C:C  D:D
    
    25 条回复    2021-01-18 21:43:55 +08:00
    imn1
        1
    imn1   116 天前
    有趣
    先确定一下,你说的是解题吧?

    跟什么语言无关,主要难题是问题的语义要准确翻译到逻辑式
    穷举肯定是可以的,逻辑判断解法就要想了……
    XiaoxiaoPu
        2
    XiaoxiaoPu   116 天前   ❤️ 1
    可以类似解数独的方式去做,只不过各个格子(各个问题)的合法性判断不是统一的规则,而是 10 个不同的逻辑。
    把这 10 个问题 “翻译” 成判定代码,可能是最繁琐的事情了。
    superrichman
        3
    superrichman   116 天前 via iPhone
    穷举,要优化也就调整一下题目验证顺序
    dwadewyp
        4
    dwadewyp   116 天前
    @imn1 确实和语言无关, 主要是在于思路
    XiaoxiaoPu
        5
    XiaoxiaoPu   116 天前
    第一个问题可以翻译成下面的函数,answers 是一个长度为 10 的 list

    def q1(answers):
    𑑛𑑛𑑛𑑛for i in range(4):
    𑑛𑑛𑑛𑑛𑑛𑑛𑑛𑑛if answers[i] == 'A':
    𑑛𑑛𑑛𑑛𑑛𑑛𑑛𑑛𑑛𑑛𑑛𑑛return answers[0] == 'ABCD'[i]
    𑑛𑑛𑑛𑑛return False
    lithiumii
        6
    lithiumii   116 天前
    笨办法:先按 10 道题的要求写测试,然后穷举,直到能通过测试
    dwadewyp
        7
    dwadewyp   116 天前
    我想知道 如果用穷举的话, 代码实现怎么实现呢?
    washbrain
        9
    washbrain   116 天前
    用 python 做的话应该就是 DFS 了,类似数独的思想去做就行,优化就是剪枝啥的
    不过这种逻辑推理题其实最合适的是直接用 prolog 做推理,你把规则和事实告诉程序,让机器去帮你推理,当然背后本质也是搜索那一套
    hello2060
        10
    hello2060   116 天前 via iPhone
    @dwadewyp

    answer = new list

    Getanswer(pos:0, answer) {
    if (pos 越界) return
    // 检查 answer 里所有现有答案逻辑是否一致,不一致返回

    for (int i = 0; i < 4; I++) {
    answer.push(I)
    getanswer(pos + 1, answer)
    answer.poplast()
    }
    }
    dwadewyp
        11
    dwadewyp   116 天前
    @washbrain 能否细说下 如果 dfs 的话,这棵树如何构建?
    dwadewyp
        12
    dwadewyp   116 天前
    @zhuangzhuang1988 这个通用模版 学习到了, 感谢!
    dwadewyp
        13
    dwadewyp   116 天前
    @zhuangzhuang1988 我刚才把约束满足问题框架读了一遍,不过本人愚笨,写不出我提出的这个问题的约束条件,大佬能否点拨一下?
    dwadewyp
        14
    dwadewyp   116 天前
    @washbrain 回溯思路: 一旦在搜索中碰到障碍,就会回到碰到障碍之前的最后一次做出判断的已知点, 然后选择其他一条路径(可以理解为递归式的深度优先搜索); ps:其实我在推演的过程中, 就想到了这是典型的回溯递归 dfs ;只是编码起来 有点难 😄。。。
    imn1
        15
    imn1   116 天前
    @dwadewyp #7
    穷举的话
    每题写一个逻辑表达式
    把答案排列组合写出来,逐个去测试逻辑表达式,遇到 False 就 continue 测试下一个,直到 10 题 all True 就是正解
    例如 10 个 A,第二题答案 A 就 False 了,('A'*10).find('AA')==5 --> False,当然第二题的逻辑式不是 find 这么简单,只是举例而已
    imn1
        16
    imn1   116 天前
    @dwadewyp
    呃,楼上应该是==4,第一题序号为 0,大致意思,看得明就行
    dwadewyp
        17
    dwadewyp   116 天前
    @imn1 穷举的大致思路明白了 谢谢, 我在想一下 每一个测试的逻辑表达式,该如何写
    Dvel
        18
    Dvel   116 天前
    @dwadewyp #17 每题写一个函数,每个函数写 4 个 if,每个 if 返回一个 bool,这样逻辑清晰,就是逻辑繁杂写着麻烦。
    wuyamao
        19
    wuyamao   116 天前
    if Ans1 == 1 or (Ans1==2 and Ans2==1) or (Ans1==3 and Ans2!=1 and Ans3==1) or (Ans1==4 and Ans2!=1 and Ans3!=1 and Ans1==1):
    if (Ans2 == 1 and Ans5==Ans6 and Ans1 != Ans2 and Ans2 != Ans3 and Ans3 != Ans4 and Ans4 != Ans5 and Ans6 != Ans7 and Ans7 != Ans8 and Ans8 != Ans9 and Ans9 != Ans10) or (Ans2 == 2 and Ans6==Ans7 and Ans1 != Ans2 and Ans2 != Ans3 and Ans3 != Ans4 and Ans4 != Ans5 and Ans5 != Ans6 and Ans7 != Ans8 and Ans8 != Ans9 and Ans9 != Ans10) or (Ans2 == 3 and Ans8==Ans7 and Ans1 != Ans2 and Ans2 != Ans3 and Ans3 != Ans4 and Ans4 != Ans5 and Ans6 != Ans7 and Ans5 != Ans6 and Ans8 != Ans9 and Ans9 != Ans10) or (Ans2 == 4 and Ans8==Ans9 and Ans1 != Ans2 and Ans2 != Ans3 and Ans3 != Ans4 and Ans4 != Ans5 and Ans6 != Ans7 and Ans5 != Ans6 and Ans9 != Ans10):
    if (Ans3 == 1 and Ans4==1) or (Ans3 == 2 and Ans9==2) or (Ans3 == 3 and Ans8==3)or (Ans3 == 4 and Ans2==4):
    countA = count(1,Ans1,Ans2,Ans3,Ans4,Ans5,Ans6,Ans7,Ans8,Ans9,Ans10)
    if (Ans4 == 3 and countA == 3 ) or (Ans4 == 4 and countA ==2 ):
    if (Ans5 == 1 and Ans1==1) or (Ans5 == 2 and Ans2==2) or (Ans5 == 3 and Ans3==3)or (Ans5 == 4 and Ans4==4):
    countB = count(2,Ans1,Ans2,Ans3,Ans4,Ans5,Ans6,Ans7,Ans8,Ans9,Ans10)
    countC = count(3,Ans1,Ans2,Ans3,Ans4,Ans5,Ans6,Ans7,Ans8,Ans9,Ans10)
    countD = count(4,Ans1,Ans2,Ans3,Ans4,Ans5,Ans6,Ans7,Ans8,Ans9,Ans10)
    if (Ans6 == 1 and countA != countB and countA != countC and countA != countD) or (Ans6 == 2 and countA == countC and countA != countD) or (Ans6 == 3 and countA == countC and countA != countD) or (Ans6 == 4 and countA == countD and countA != countC):
    if (Ans7 == 1 and abs(Ans7-Ans8)==3) or (Ans7 == 2 and abs(Ans7-Ans8)==2) or (Ans7 == 3 and abs(Ans7-Ans8)==1)or (Ans7 == 4 and Ans8==4):
    if (Ans8 == 3 and Ans4 == 4) or (Ans8 == 4 and Ans4 == 3):
    countBCD = 10 - countA
    if (Ans9==1 and (countBCD in [6,8])) or (Ans9==2 and (countBCD in [5,7])) or (Ans9==4 and countBCD ==9 ):


    自己排版吧,可能有些有点漏
    Lightbright
        20
    Lightbright   115 天前 via Android
    也就 100 多万种可能,暴力枚举一下(🐶
    washbrain
        21
    washbrain   115 天前
    @dwadewyp 约束本身是很简单的
    FirstA = ans(1), OnlySameAnswerIndex = ans(2), sameAnswerWithThree = ans(3) ..... 以此类推
    关键是约束传播与更新这一步不太好做
    从实际操作角度来说,最好是对每一道题目选某个值的约束传播简单分成两种
    1. 添加全局约束检查,比如说题目 6,选 A 的时候,就添加一条检查约束,每次变量更新都做一个检查,判断是否回溯
    2. 更新其他变量的值域, 比如说选择题目 1 选 D,就可以更新 1,2,3,4 的值域; 题目 3,5,7 这种直接更新的也不用说了
    当然还有复合形的,比如题目 2 既有全局约束,又能更新值域
    然后递归回溯,保存每一次搜索的具体值域和全局检查约束
    不算通用的 CSP 问题解法,只是针对这种 CSP 问题的一种特定解法
    polymer
        22
    polymer   115 天前 via iPhone
    A, C, B, C, A, C, D, D, B, A
    chengfeng1992
        23
    chengfeng1992   114 天前


    用 java 写的,穷举然后各种判断,除了没判断选项的唯一,其它都差不多了。
    JeffGe
        24
    JeffGe   113 天前
    https://paste.ubuntu.com/p/b3NYTy4mcB/

    就算穷举都挺快的,0.882 秒。优化的话可以剪枝,最简单的剪枝方法之一就是在判断题目正确性的函数里面返回数字 n 代替 True/False,代表前 n 道题的答案就已经不满足要求了,穷举的下一项选择递增第 n 个答案,后面全置 A 即可。比如第二道题,“AAAAAAAAAA”的前两项可以直接判断题目 2 不可能满足,下一项判断“ABAAAAAAAA”即可,跳过了 65535 项。
    washbrain
        25
    washbrain   113 天前


    @dwadewyp
    用 js 写了一个约束传播剪枝 csp 的简单 demo,可以复制到浏览器 console 跑一下,搜索到正确结果只用了 61 次搜索,全部搜索完只用了 114 次搜索
    当然这个 CSP 用的约束传播和选择算法还很粗糙,比如:
    1. 约束传播是自己手动写的如何传播,主要是本题的约束相对复杂一点,手工作业比较多,不过具体是怎么传播的都写了注释
    2. 选择下一个搜索目标是基于值域大小来的,可以有更好的方案,稍微优化一下选择搜索的方式,搜索次数可以减少到 27 次(见注释)
    3. 不像真正的约束传播算法,我们这里其实值域只会在手动选择的时候做一次约束传播,理论上可以一直迭代变动到值域稳定为止,也有更多优化空间
    关于   ·   帮助文档   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   1192 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 17:58 · PVG 01:58 · LAX 10:58 · JFK 13:58
    ♥ Do have faith in what you're doing.