假设先手不能全拿，小於等於4个就不讨论了~ (1)当有5个石头时，先手胜 就先拿一个，不管对方怎麽拿，都可以全部拿光 (2)当有6个石头时，後手胜 先手不能拿超过两个，不然对手直接拿光就输了 所以先手只能拿一个，变成剩下五个，还是输 (3)当有7个石头时，先手胜 先手先拿一个，对方也只能跟着拿一个 这时剩下五个，先手胜 (4)当有8个石头时，後手胜 先手不能拿超过两个，不然对手直接拿光输掉 先手拿一个，变成7个石头的case，对方变成新的先手，获胜 (5)当有9个石头时，先手胜 拿一个石头，然後变成8个石头的case，原先手变成新的後手，新的後手胜 (6)当有10个石头时，先手胜 拿两个石头，变成8个石头的case，这时对手不能拿超过两个 (7)当有11个石头时，後手胜 因为这时先手要拿3个石头才能变成8个石头的case 但是若拿3个对手可以直接全部拿光，所以先手不会赢 (8)12个石头，先手胜 先拿一个石头变成11个石头的case (9)13个石头，先手胜 先拿两个石头变成11个石头的case (10)14个，先手胜 先手拿3个 (11)15个石头，後手胜 先手若拿4个会自爆 (12)16个石头，先手胜 先拿一个石头，变成15个石头的case ...... 以下类推 所以关键数应该是拿完後所剩的石头数会是後手胜的case 到目前为止是6,8,11,15,20也是 感觉很像a(n)=a(n-1)+n 可惜不是(我一开始也以为答案错) 不过这边要借一下原PO的最大可取数 16取1 (表示若有16个石头，先手先拿一个可以赢) 17取2 18取3 19取4 以上皆为先手胜 20取5 这一个先手赢不了，表示这种情况後手必胜 21取1 22取2 23取3 24取4 (以上这四组最大可取数量为5) 25取5 26取6 以上至此先手必胜 27取7 这一个先手会自爆，後手胜 28取8 (以上这四组最大可取数量为6) 当X取Y的最小Y大於可取数量Z时，该X为关键数 <--好烂的描述啊 这边关键数为27 28取1 找到关键数後要重来 29取2 30取3 31取4 32取5 以上最大可取数量7 33取6 34取7 35取8 36取9 以上最大可取数量8 所以这边关键数为36 37 1 38 2 39 3 40 4 最大可取为9 41 5 42 6 43 7 44 8 最大可取为10 45 9 46 10 47 11 48 12 最大可取为11 关键数为48 以下类推~不过在下写不出漂亮的一般式啊 -- 很像以前会作弄小朋友的一个题目 任写两个数字，比方说20,12 规则是可以两边同减一个数或者是任一边减去一个数 (当然不能减到为负数) 两人轮流，先让两边同时为0者就是赢家 我过了好一阵子才知道为什麽一开始友人都以这两个数字开头并且让我当先手啊~ ※ 引述《O00O (喔喔喔喔)》之铭言： : 简单讲一下,直觉这题应该是属於NP,要解出来理论上要很久... : 原文的解答,到15都是对的,不过20就错了. : 如果留20给对手,对手拿1,剩19还你,无法一手降到15,对方就可以走到15的安全局. : 这题比较难是因为安全局不是一维的,要考虑前一手. : 5->4是安全局,但是6->4就不是. : 前面几个安全局应该是: : 5->4 : 7->6 : (9~10)->8 : (12~14)->11 : (16~19)->15 : 下一手就开始复杂了,我也懒得想了. : ※ 引述《supermicro (清流是要流到哪里去?)》之铭言： : : 作者: sean0405 (灰) 看板: Math : : 标题: 益智问题 : : 时间: Sun Apr 19 11:28:02 2009 : : 玩法：一堆石头有100个，两人轮流取石，每次每人至少取一个，最多取上次对方取走的 : : 石头数的三倍。取走最後一个石头的人赢得胜利。 : : 问题：请分析这个游戏是对先手有利，还是对後手有利？为什麽？ : : 解答： : : 规则之「下ㄧ人取最多数为前人之三倍」，表示每个数字之最大可取之量为总量÷4之商 : : ，总数如为4的倍数则可取之数为商-1。 : : 例如100÷4=25，整除所以最大可取之数为25-1=24。 : : 在此前提之下，先把问题简化。从1倒算至关键数「8」，接着发现後两数「9、10」之最 : : 大可取数量为2，而11也为2。无法把对方逼到「8」，因此认定「11」也是关键数，接着 : : 继续往後推算发现15、20、27、36、48、64、86也均为关键数，所以在石头数100颗的情 : : 形下，先手取14颗剩下86颗则必胜。 : : 有高手能清楚说明解答过程的吗？感谢罗.. --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 219.70.151.17 ※ 编辑: homeik 来自: 219.70.151.17 (04/20 23:43) ※ 编辑: homeik 来自: 219.70.151.17 (04/20 23:47)