推荐学习书目
› 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
这是一个创建于 2235 天前的主题，其中的信息可能已经有所发展或是发生改变。
12 个人做游戏，总共 12 个不同的数，每人对应一个不同的数。游戏开始，每个人需要说出自己不是 12 个数中哪 3 个数。12 个人说完，能猜出每个人是什么数吗。
只想到了 python 遍历每个人可能的数，然后进行判断比较。但是遍历的数太多了，有什么好方法吗？求教
只想到了 python 遍历每个人可能的数，然后进行判断比较。但是遍历的数太多了，有什么好方法吗？求教
 |
1
sunfan314 2018-11-12 11:44:13 +08:00
每个人维护一个自己可能的数的数组 所有人说完之后 每个人的数组中应该只包含 9 个数
对第一个人的数组进行遍历 假设第一个人的数 1,那么之后 11 个人的数组中都应该去除 1 这种遍历方式下 一般到最后几个人的数组大小就很小了 遍历的情况会少很多 |
 |
2
mathzhaoliang 2018-11-12 11:49:12 +08:00
如果问题的要求是每个人随便说三个与自己不同的数字，那么答案是不能。
|
|
3
mathzhaoliang 2018-11-12 11:50:32 +08:00
@sunfan314 你认真分析过复杂度吗？
|
 |
4
zynlp 2018-11-12 12:23:58 +08:00 via iPhone
不能，你把规模缩到 3 个人，每个人说一个数，有时会出现两个候选情况满足。
|
|
5
zynlp 2018-11-12 12:32:19 +08:00 via iPhone
可以试试，先建个有向图，判断有没有环
|
 |
6
Nimrod 2018-11-12 13:10:05 +08:00 via Android
粗想了下不行，看看有没有大佬能说清楚
|
|
8
sunfan314 2018-11-12 13:11:16 +08:00
这个问题实质感觉是和数独问题是一样的，所以未必有解 但是 12 个人每个人只说三个数其实有解甚至有很多解的概率也是很大的
|
 |
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 |
 |
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 来猜猜看？ |
 |
11
ccpp132 2018-11-12 13:29:11 +08:00
搜索就行了，有多种解就多种解呗。
要问这个问题最好的做法，如果 LZ 想研究的话，可以去看看 Knuth 的论文《 Dancing Links 》 |
 |
12
kx5d62Jn1J9MjoXP 2018-11-12 13:29:32 +08:00
不能
1~6 号说自己不是 10, 11, 12 7~12 号说自己不是 1, 2, 3 这样至少有 6! * 6!种可能性 |
 |
13
inhzus 2018-11-12 13:30:43 +08:00
提供一个思路 回溯法 递归实现
自己没写代码, 感觉应该行得通, 就是还是很复杂. 不过至少比 for 循环好看, 能解决楼主遍历数太多的痛点 |
 |
15
trueGate 2018-11-12 13:46:39 +08:00
把问题看做 12*12 的数独棋盘，每行每列有且只有一个元素。用二维数组来做
|
 |
16
vvvv OP 学习了，感谢楼上各位大佬~
|
Select Language