Author Topic: 每周一题: 桌面上的牌 (1/3/05 -- 1/9/05)  (Read 11031 times)

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
每周一题: 桌面上的牌 (1/3/05 -- 1/9/05)
« on: 一月 03, 2005, 11:04:56 am »
圣诞新年期间,本坛出了开坛以来的第一次事故。本坛用的是PHPBB2软件。据说原来的版本被发现有安全漏洞,我没有及时更新,结果本坛被禁用。正赶上我外出度假,结果读者不能读这个论坛达一周之久,非常抱歉。现在一切恢复正常,但愿我们没有因此而失去很多读者。

上周我外出度假,每周一题空缺一周。

上周问题讨论:

FZY的解法与我所知道的解法一样。关键是要找到中心点的集合。证明空间中所有整数点都与中心点集合中某一点(对该点来说唯一)距离为一。也就是说属於N维十字架上的一个方块。找中心点的技巧在於构造一个辅助函数:

  f(X) = X1 + 2*X2 + 3*X3 + ... + N*XN mod(2N+1)

很容易证明F(X)=0的点满足中心点的要求,每个中心点恰好有2N个与其距离为一的点。

本周的问题比较繁,但很有趣,与我们以前出过的阿里巴巴开山门类似,每步都失去以前的信息。

本周问题:桌面上的牌

桌子上放着三张牌面朝上的牌:ACE,KING,QUEEN。它们的位置可以是左中右三个位置的任何一个。也可能两张牌或三张牌都放在同一个位置。这种时候你只能看见上面那张牌,看不见下面的牌(根本不知道下面有没有牌)。你每次可以把一张牌移到另一个位置(放在一个空位或另一张牌上面都可以)。如果三张牌以AKQ的顺序放在最左面的位置上,某一盏灯就会亮,也就是说你过关了。唯一的问题是,你完全失去了短期记忆。记不得上次的牌的位置或任何以前的操作过程。你的所有信息只能从你现在能看见的牌得到。我们的问题是让你设计一套操作程序,使得不管初始是什么情况(三张牌在什么位置),你都能过关。

把这个问题推广到任意多牌,如果有N张牌放在桌子上左中右三个位置,你是否能把它们按一到N的顺序放在最左面的位置上。
« Last Edit: 十月 08, 2009, 09:36:29 pm by 万精油 »

Anonymous

  • Guest
每周一题: 桌面上的牌 (1/3/05 -- 1/9/05)
« Reply #1 on: 一月 04, 2005, 06:19:15 pm »
Question: Is the final order top to bottom or bottom to top? In another word, when done, which card is on top?

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
每周一题: 桌面上的牌 (1/3/05 -- 1/9/05)
« Reply #2 on: 一月 04, 2005, 07:32:22 pm »
It should be A on top. That is, you only see A after it is done.

It should not really matter though, if you have an approach that works one way, there should be an approach that works the other way too.  After all, A, K, Q are just symbols.

fzy

  • Hero Member
  • *****
  • Posts: 520
每周一题: 桌面上的牌 (1/3/05 -- 1/9/05)
« Reply #3 on: 一月 06, 2005, 11:30:27 am »
This should work:

When there are no empty stacks:
If the middle card is the biggest, move the second biggest card to the middle stack. Otherwise move middle to cover the smallest card.

When the left stack is empty and middle is not:
If middle is bigger than right or right is empty, move the middle card to right. Otherwise move middle to left.

When the middle stack is empty and right is not:
If right is smaller than left or left is empty, move right to left. Otherwise move right to middle.

When the right stack is empty and left is not:
If left is bigger than middle or middle is empty, move left to middle. Otherwise move left to right.


The basic idea is to set the middle stack to the correct order. When done, dump it to the right stack in reversed order, and then dump it back to left in the correct order. If failed in any step, start the next round with the middle stack again. In each round, the "orderliness" is better than the previous round. So in finite steps we will achieve total orderliness.

It is a very slow process, taking O(N^2) steps or more.

I tried to find a simple proof such as assigning an orderliness value to each state. But I was not successful.  :x  I believe I have a messy inductive proof. It was so messy that it is not worth to write it out.  :(

MW

  • Guest
每周一题: 桌面上的牌 (1/3/05 -- 1/9/05)
« Reply #4 on: 一月 06, 2005, 12:17:09 pm »
I can't see why this problem is complicated.  

The easy way is to empty the left side first.  Then continue to move cards between right and middle, and put the right card on the left if you see it.   Each round you will at least find one card you want in the order.  So the worst time it takes is N^2.

Anonymous

  • Guest
每周一题: 桌面上的牌 (1/3/05 -- 1/9/05)
« Reply #5 on: 一月 06, 2005, 01:07:22 pm »
Quote
I can't see why this problem is complicated.

The easy way is to empty the left side first.


Obviously, you don't understand the problem, that's why you find it is easy.

What do you mean by "first"? Everytime it is "first".  Remember you have no short time memory, you have no idea whether you have been here before or what have you done before. Your only information is the card you see.