algorithm - 不懂翻转的技巧

Question

我正在尝试解决名为 Stack of Flapjacks 的 acm 问题.但不幸的是我没能理解这个问题。所以我尝试谷歌并找到a better explanation .这个解释说 flip(k)。但我不知道该怎么做。有人请为我解释一下。提前致谢。

Answer 1

这是您的原始 ACM 问题的相关内容:

A flip consists of inserting a spatula between two pancakes in a stack and flipping (reversing) the pancakes on the spatula (reversing the sub-stack). A flip is specified by giving the position of the pancake on the bottom of the sub-stack to be flipped (relative to the whole stack). The pancake on the bottom of the whole stack has position 1 and the pancake on the top of a stack of n pancakes has position n.

flip(k) 表示将煎饼的顺序从 1..k 反转。部分问题在于弄清楚如何去做!

使用问题中的示例，假设您像这样实现了一堆煎饼:

int[] pancakes = [8, 4, 6, 7, 5, 2];

翻转操作可以这样写:

int flip(int pos) {
    int spare;
    for (int i = 1; i < pos/2; i++) {
        // swap element [i] with element [pos-i+1]
        spare = pancakes[i];
        pancakes[i] = pancakes[pos-i+1];
        pancakes[pos-i+1] = spare;
    }
}

flip(3) 只会交换 [1] 和 [3]，[2] 保持不变
flip(4) 会交换 [1] 和 [4]，然后交换 [2] 和 [3]