折纸问题

折纸问题

折纸问题

• 问题描述
• 问题解析
• 代码

问题描述

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

问题解析

按照题目描述将纸条对折，第一次对折会出现一条下折痕，将这条折痕标记为（1，下）（含义为第一次折出来的下折痕），第二次对折从上往下出现了两条下折痕分别为（2，下），（1，下）和一条上折痕（2，上）；第三次对折从下往下出现了（3，下）、（2，下）、（3，上）、（1，下）、（3，下）、（2，上）、（3，上）七条折痕。
通过对比后这三次对折，可以发现一个规律第二次对折的出来折痕在第一次的折痕的上下两侧，而且下（凹）折痕在上方、上（凸）折痕在下方，第三次对折出的折痕也是这样，在第二次折痕的两侧，同样也是下（凹）折痕在上方、上（凸）折痕在下方。这样一个规律就让我想到建一个二叉树，每个节点的左子树都是下一次对折下折痕、右子树都是上折痕。这样只要中序遍历这棵树。

代码

public class PaperFolding {public static void printAllFolds(int n){paperFolding(1,n,true);System.out.println();}// 当前你来了一个节点，脑海中想象的！// 这个节点在第i层，一共有N层，N固定不变的// 这个节点如果是凹的话，down = T// 这个节点如果是凸的话，down = F// 函数的功能：中序打印以你想象的节点为头的整棵树！public static void paperFolding(int i, int n, boolean down){if(i > n){return;}paperFolding(i + 1, n, true);System.out.println(down ? "凹" : "凸");paperFolding(i + 1, n, false);}public static void main(String[] args) {int n = 3;printAllFolds(n);}
}