### 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 »

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

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

« 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.    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.