珍珠湾ART

标题: 国王和犯人 [打印本页]

作者: constant 时间: 2006-4-25 02:04
标题: 国王和犯人

难度：++++

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

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

犯人有什么办法？

作者: 勇敢的辛 时间: 2006-4-25 09:41
标题: 回复：国王和犯人

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

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

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

作者: sean9991 时间: 2006-4-25 18:57
标题: a question

# 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
标题: 回复：a question

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
标题: 没有人想[:%][:X][:((]

没有人想