微软原题，折纸问题，详解思路

微软原题，折纸问题，详解思路

首先这是从左神视频里面出现的题目。

折纸问题：

请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。例如:N=1时，打印: down N=2时，打印: down down up。

我现在这里说一下我自己的思路：

1、首先搞清楚为什么折痕会出现凹折痕和凸折痕，一张纸折叠第一次会出现一个折痕，这个定为凹折痕，第二次折叠时我们假定吧纸中间连接处分开，就相当于直接折叠两张纸，所以会出现两个折痕，但是上面那张纸它的方向是反的，所以上面那张纸的凹折痕放下来就变成了凸折痕。画个图说明一下。

2.弄懂折叠几次会出现几个折痕。从上述分析中很轻易的可以得出，每折叠一次纸的层数会乘二，所以新增的折痕数也是乘二的，得出折痕数和折纸次数的关系为2的n次方-1。

3，开始分析折痕出现规律。一张正面的纸折一次会出现一个凹折痕，变成正反两张纸，它的下一轮折叠就变成了凹凸两道折痕，并且分布在原折痕左右两侧，而一张反的纸折一次会出现一个凸折痕，变反正两张纸，它的下一轮折叠就是凸凹两道折，也是分布在左右两侧。这种一个折痕再次折叠出现两个新折痕的样子很像二叉树结构，在这里将纸每次折叠出现的新折痕看成它