国王和犯人

constant · 发表于 2006-4-25 02:04:48

难度：++++

一个国王的监狱里有很多犯人。他不想把这些犯人再关下去，但不知道是该释放还是杀掉他们。于是他对犯人们说：

“我这里有几张纸片，每张上要写一个不同的数，你们要把这些纸片按顺序排好。我把这些纸片随便分成三堆，然后把你们按我定的顺序叫进来，进来的人只能看见最上面的三张，连每堆有几张也看不见。每个进来的人可以从看见的纸片中选一张放在另一堆上面。什么时候纸片都在左面一堆按数从小到大排好，就释放你们。如果所有人都轮了一遍还没排好，统统杀头。今天你们回去商量一个策略，然后就不会再见面了。过几天我开始叫人。可能一天叫很多人，也可能几天也不叫一个人。”

犯人有什么办法？

勇敢的辛 · 发表于 2006-4-25 09:41:17

先把所有纸片从小到大排好，国王分为三堆后，从要求“纸片都在左面一堆按数从小到大排好”看，这三堆的大小位置是知道的。为叙述简便，设左中右三堆分别是1－10，11－20，21－30。

第一个人看到三堆最上面是3个不连续数字，从中间取最上一张20放到右边那堆上，第二个人将看到中间堆最上面的数字比右边最上一张小1，即19，将小的一张放到大的那张上，以后同样直到中间这堆只剩2张，以下每个人如果看见中间有2张就取最下一张到左边一堆，看见只有一张就移动右边最上一张到中间，直到最大的数字30放到中间的最下一张。至此，中间一堆全部由小到大放到左边。

以后每个人看到是右边最上一张比中间最上一张小1，从右边取最上一张到中间直至最后2张，然后从小到大放到左边。

sean9991 · 发表于 2006-4-25 18:57:13

# of prisoners >> # of cards? I wonder if they can finish it in one round by moving one card per person.

constant · 发表于 2006-4-25 19:55:07

Yes. You do not need to worry about the efficiency of your algorithm. You may think # of prisoners is in the same order of # of different layouts of cards.

constant · 发表于 2006-4-27 17:59:13

没有人想

sean9991 · 发表于 2006-4-27 20:10:09

will try it this weekend...

勇敢的辛 · 发表于 2006-4-28 06:44:11

最上面的三张是指每堆三张还是每堆一张，共三张？

国王分为三堆牌后摆放位置是否固定，左边一堆是最靠头的几张，中间一堆放中间的几张？

如果一堆牌最后一张被拿走，还可以放牌到这堆吗？

本贴由[勇敢的辛]最后编辑于：2006-4-28 4:26:36

constant · 发表于 2006-4-28 16:43:40

1。每堆一张，只能看见一张，而且看不见下面还有没有牌。

2。堆的位置固定，牌的位置顺序是随机的。假设国王洗牌后发牌。

3。可以

4。这些数不是连续整数，甚至不一定是整数，可能是1/3, sqr(2), pi, e, ...

只看该作者 · 发表于 2009-5-22 08:32:13

提示: 作者被禁止或删除内容自动屏蔽

只看该作者 · 发表于 2009-5-23 22:25:24

提示: 作者被禁止或删除内容自动屏蔽

只看该作者 · 发表于 2009-5-23 22:36:24

提示: 作者被禁止或删除内容自动屏蔽

只看该作者 · 发表于 2009-5-24 03:40:44

提示: 作者被禁止或删除内容自动屏蔽

		自动登录	找回密码
密码			立即注册

85 该用户已被删除	9^# 发表于 2009-5-22 08:32:13 \| 只看该作者提示: 作者被禁止或删除内容自动屏蔽
85 该用户已被删除
	回复支持反对使用道具举报

85 该用户已被删除	10^# 发表于 2009-5-23 22:25:24 \| 只看该作者提示: 作者被禁止或删除内容自动屏蔽
85 该用户已被删除
	回复支持反对使用道具举报

85 该用户已被删除	11^# 发表于 2009-5-23 22:36:24 \| 只看该作者提示: 作者被禁止或删除内容自动屏蔽
85 该用户已被删除
	回复支持反对使用道具举报

85 该用户已被删除	12^# 发表于 2009-5-24 03:40:44 \| 只看该作者提示: 作者被禁止或删除内容自动屏蔽
85 该用户已被删除
	回复支持反对使用道具举报

动态微博

国王和犯人

回复：国王和犯人

a question

回复：a question

没有人想[:%][:X][:((]

will try it this weekend...

似乎理解题意有误，确认一下。

回复：似乎理解题意有误，确认一下。