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
vvvv
V2EX  ›  Python

Python 新手,遇到一个数学题目,想用 Python 解决。求支招

  •  
  •   vvvv · 2018-11-12 11:29:09 +08:00 · 3122 次点击
    这是一个创建于 1963 天前的主题,其中的信息可能已经有所发展或是发生改变。
    12 个人做游戏,总共 12 个不同的数,每人对应一个不同的数。游戏开始,每个人需要说出自己不是 12 个数中哪 3 个数。12 个人说完,能猜出每个人是什么数吗。
    只想到了 python 遍历每个人可能的数,然后进行判断比较。但是遍历的数太多了,有什么好方法吗?求教
    17 条回复    2018-11-13 15:34:33 +08:00
    sunfan314
        1
    sunfan314  
       2018-11-12 11:44:13 +08:00
    每个人维护一个自己可能的数的数组 所有人说完之后 每个人的数组中应该只包含 9 个数
    对第一个人的数组进行遍历 假设第一个人的数 1,那么之后 11 个人的数组中都应该去除 1

    这种遍历方式下 一般到最后几个人的数组大小就很小了 遍历的情况会少很多
    mathzhaoliang
        2
    mathzhaoliang  
       2018-11-12 11:49:12 +08:00
    如果问题的要求是每个人随便说三个与自己不同的数字,那么答案是不能。
    mathzhaoliang
        3
    mathzhaoliang  
       2018-11-12 11:50:32 +08:00
    @sunfan314 你认真分析过复杂度吗?
    zynlp
        4
    zynlp  
       2018-11-12 12:23:58 +08:00 via iPhone
    不能,你把规模缩到 3 个人,每个人说一个数,有时会出现两个候选情况满足。
    zynlp
        5
    zynlp  
       2018-11-12 12:32:19 +08:00 via iPhone
    可以试试,先建个有向图,判断有没有环
    Nimrod
        6
    Nimrod  
       2018-11-12 13:10:05 +08:00 via Android
    粗想了下不行,看看有没有大佬能说清楚
    Nimrod
        7
    Nimrod  
       2018-11-12 13:10:22 +08:00 via Android
    @zynlp 请问这个怎么理解成图的问题?
    sunfan314
        8
    sunfan314  
       2018-11-12 13:11:16 +08:00
    这个问题实质感觉是和数独问题是一样的,所以未必有解 但是 12 个人每个人只说三个数其实有解甚至有很多解的概率也是很大的
    cdwyd
        9
    cdwyd  
       2018-11-12 13:16:53 +08:00 via Android
    不能,极端考虑一下
    1 号报数:3 4 5
    2 号报数:3 4 5

    其他人从不是 1 2 和自身的数里面随便选 3 个,这样至少是分不出来谁是 1 谁是 2
    upczww
        10
    upczww  
       2018-11-12 13:26:19 +08:00
    1 234
    2 134
    3 124
    4 123
    5 123
    6 123
    7 123
    8 123
    9 123
    10 123
    11 123
    12 123
    来猜猜看?
    ccpp132
        11
    ccpp132  
       2018-11-12 13:29:11 +08:00
    搜索就行了,有多种解就多种解呗。

    要问这个问题最好的做法,如果 LZ 想研究的话,可以去看看 Knuth 的论文《 Dancing Links 》
    ssynhtn
        12
    ssynhtn  
       2018-11-12 13:29:32 +08:00
    不能
    1~6 号说自己不是 10, 11, 12
    7~12 号说自己不是 1, 2, 3

    这样至少有 6! * 6!种可能性
    inhzus
        13
    inhzus  
       2018-11-12 13:30:43 +08:00
    提供一个思路 回溯法 递归实现
    自己没写代码, 感觉应该行得通, 就是还是很复杂. 不过至少比 for 循环好看, 能解决楼主遍历数太多的痛点
    inhzus
        14
    inhzus  
       2018-11-12 13:32:14 +08:00
    @inhzus #13 补充一下 类似的问题参考 八皇后问题 回溯法的思路差不多
    trueGate
        15
    trueGate  
       2018-11-12 13:46:39 +08:00
    把问题看做 12*12 的数独棋盘,每行每列有且只有一个元素。用二维数组来做
    vvvv
        16
    vvvv  
    OP
       2018-11-12 13:47:02 +08:00
    学习了,感谢楼上各位大佬~
    vuser
        17
    vuser  
       2018-11-13 15:34:33 +08:00
    @trueGate 思路不错
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3231 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 14:23 · PVG 22:23 · LAX 07:23 · JFK 10:23
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.