ACM通信
最后一个字节
困惑:解决方案和来源
资料来源:Merchant of Magic Ltd.
1.三张牌
虽然看起来只有三张卡可以做的事情不多，但实际上有1.64 × 1018无记忆算法尝试过，用了大部分都不行。你需要脑力。通过一些推理和实验，您可能会发现，将卡片主要朝一个方向移动(例如向右移动，包括从右边的堆栈到左边的堆栈的“拐角处”)有助于避免循环。此外，你通常想要暴露更多的牌，除了一些你可能会赢的位置。在几个有效的算法中，我喜欢下面这个算法，这是我的数学博士学生Ewa Infeld提出的，根据这四个优先级排序规则给出的:
- 看到2,1，-，把1放在2上;
- 否则，看到两张牌，将一张牌移到右边(必要时绕过角落)的空地上;
- 看到一张牌，把它移到左边;和
- 看到三张牌，将中等级别的牌移到右边。
2.任意数量的牌。
同样的算法适用于任意数量的牌，从1到1n．在最坏情况下，也就是随机情况下，需要二次时间，或者近似常数时间n2步骤。
评论
Marc Auslander
我相信下面是二次的，中间没有多于一张牌
称这些堆栈(以及它们最上面的卡片)为A、B和C
如果B为空:
如果C为空，则将A移到B
elIf A是空的或A > C移动C到A
否则将C移到B
如果B不为空:
如果A是空的，将B移到A
如果C不为空，A > B > C移动B到A
否则将C移到A
直观地，从左到右搜索无序的卡，然后从右到左搜索插入它的位置。
一旦所有东西都排好序，从左到右的搜索将迫使所有东西进入最左边的堆栈。
显示1评论