打印折纸凹凸痕迹

本文主要是介绍打印折纸凹凸痕迹，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- 打印折纸凹凸痕迹
- - 折纸问题
  - - 算法思路
    - 相应代码

打印折纸凹凸痕迹

折纸问题

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

算法思路

下
下上
产生第i+1次折痕的过程，就是在第i次对折产生的每一条折痕的左右两侧，依次插入下折痕和上折痕的过程。
中序遍历：左头右
算法时间复杂度为O( $2^n$ )，空间复杂度为O(n)。

相应代码

递归实现

def printAllFolds(N):printProcess(1, N, True)print()def printProcess(i, N, down):if i > N:returnprintProcess(i+1, N, True)if down is True:print('down', end=' ')else:print('up', end=' ')printProcess(i + 1, N, False)# 简单测试
if __name__ == '__main__':printAllFolds(1)  # downprintAllFolds(2)  # down down upprintAllFolds(3)  # down down up down down up up