折纸问题公式（算法21：折纸问题）

时间2025-04-30 00:05:02分类IT科技浏览4106

导读：请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。此时折痕是凹下去的，即折痕突起的方向指向纸条的背面。如果从纸条的下边向上方连续对折2次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。...

请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。此时折痕是凹下去的，即折痕突起的方向指向纸条的背面。如果从纸条的下边向上方连续对折2次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。

给定一个输入参数N ，代表纸条都从下边向上方连续对折N次。请从上到下打印所有折痕的方向。

例如:N=1时，打印: down N=2时，打印: down down up

根据题目要求，我实际折了一把，并且每一次折的时候，我都进行了标注：1凹，代表第一次折的， 2 凹或者2凸代表第二次折的，依次类推.....

观察了上图，确实停迷惑人的，下图我通过绘图的形式，更加直观的呈现这个问题的本身

通过手动绘制的图片，我们按照折纸的先后顺序，发现每次折纸，都会在之前的折纸痕迹左右再生出2道痕迹：

第一次折： 1 凹

第二次折： 1 凹两侧生出了 2凹和 2凸

第三次折: 2凹和 2凸两侧又生成了 3凹和 3 凸

依次类推.........

最终我们发现，这就是一颗满二叉树。而想要从上到下打印这张纸的痕迹，实际上就是中序遍历整颗二叉树的节点。代码如下

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。