国王和犯人解答

constant

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

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

犯人有什么办法？

 

注1．       这些数不是连续整数，而且犯人不知道这些数的范围。www.ddhw.com

注2．       有足够多犯人，不必考虑算法的效率。www.ddhw.com

解答：

这里给出一个方法。

 www.ddhw.com

1．设每一堆都有卡片。如果中间的卡片最大，把第二大的移到中间，否则将中间的卡片移到最小的卡片上。

 

2．设左边是空的但中间不空。如果中间比右边大或右边是空的，中间卡片移到右边，否则中间卡片移到左边。www.ddhw.com

 

3．设中间是空的但右边不空。如果右边比左边小或左边是空的，右边卡片移到左边，否则右边卡片移到中间。

 www.ddhw.com

4．设右边是空的但左边不空。如果左边比中间大或中间是空的，左边卡片移到中间，否则左边卡片移到右边。

 www.ddhw.com

这个方法分三步：首先把卡片按顺序（大数在下小数在上）放到中间一堆上，然后把中间一堆按倒序（大数在上小数在下）移到右边，最后把右边一堆按正序移到左边。后两步中如果发现顺序不对，退回第一步重来。如果所有卡片都到了左边但顺序还是不对（国王没有释放囚犯），也再回第一步重来。每重来一次，所有卡片的顺序都会改进一点，经有限次重复后必然会排好。

 

这个过程很慢，是 O(N^2) 级的，因此要有很多囚犯才行。

www.ddhw.com