折纸问题_输入描述: 第一行一个整数n。表示对折次数 输出描述: 输出若干行,若该折痕向下,输

折纸问题

题目描述

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

[要求]

时间复杂度为$O(2^n)$，额外空间复杂度为$O(1)$

输入描述：

第一行一个整数N。表示对折次数

输出描述：

输出若干行，若该折痕向下，输出"down"，否则输出"up"

示例1

输入

1
1

输出

down
1

示例2

输入

2
1

输出

down
down
up
1
2
3

备注：

$1⩽N⩽20$

---

题解：

我们依次打印每次折叠后从下到上的折痕：

可以看到，每次折叠，都是在上次的折痕左右两侧依次插入上、下折痕。

并且这是一棵满二叉树，打印时采用：右 根 左 的中序打印顺序即可。

代码：

#include <cstdio>

using namespace std;

void print( int dep, int n, bool down ) {
    if ( dep > n ) return;
    print( dep + 1, n, true );
    puts( down ? "down" : "up" );
    print( dep + 1, n, false );
}

int main(void) {
    int n;
    scanf("%d", &n);
    print( 1, n, true );
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17