问题描述

请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折 1 次，压出折痕后展开。此时折痕是凹下去的，即折痕突起的方向指向纸条的背面。如果从纸条的下边向上方连续对折 2 次，压出折痕后展开，此时有三条折痕，从上到下依次是凹折痕、凹折痕和凸折痕。 给定一个输入参数 N，代表纸条都从下边向上方连续对折 N 次，请从上到下打印所有折痕的方向。
例如:
N=1 时，打印 down;
N=2 时，打印 down, down, up

思路过程

这个问题将生活中很常见的折纸现象与算法联系起来，很考察我们的问题抽象能力。

拿出一张纸条，将其对折三次：

从上到下为：凹，凹，凸，凹，凹，凸，凸

嘶~压根看不出什么，那让我们再精细一些，将折痕按折叠次数划分开，画出如下简图：

啊哈，这样是不是马上就有感觉啦？没错，第一眼感觉就是二叉树。显然，从上而下依次打印折痕，即为中序遍历该二叉树。而且发现 每个节点的左孩子为凹，右孩子为凸，这样问题就变得清晰了，容易给出如下代码：

//fold times-n, current layer-cur, direction-dir(false-down, true-up)
void process(int n, int cur, bool dir)
{
    if(cur > n)
        return;
    process(n, cur + 1, false);
    std::cout << (dir ? "up " : "down ");
    process(n, cur + 1, true);
}

void fold(int n)
{
    if(n < 1)
        return;
    process(n, 1, false);
}

int main()
{
    fold(3);
}

总结

本题的代码没有任何难度，难的是将问题本质抽象出来。解决本题须经过以下几个步骤：

1. 实践，动手折纸
2. 将折纸结果进行书面表达
3. 就像我们之前直接展示折三次的结果，很难直接看出什么端倪
4. 再精细化，根据次数将各个折痕区分开，呈现出一棵树状图
5. 分析树状图特征，书写代码

其中第 4 步是最难的，如果你没有将折纸结果用上面那样的树状图表示出来，最后也很难将问题与树的遍历联系起来。

本文结束。

参考：左程云算法课