首页 > 编程语言 >算法21:折纸问题

算法21:折纸问题

时间:2023-02-22 11:13:52浏览次数:32  
标签:21 curTimes 纸条 折纸 times down 算法 折痕

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

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

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

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

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

第一次折: 1 凹

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

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

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

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

package code03.二叉树_02;

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

    /**
     * @param times 代表折了几次纸,也代表二叉树的层数
     * @param n     代表二叉树的层数
     * @param down  凹代表true,凸代表false
     */
    public void process (int times, int curTimes, boolean down)
    {
        //上一层已经是最下方的层数,没有下挂节点了
        if (curTimes > times) {
            return;
        }
        //根据观察,每一层的左节点都是凹
        process(times, curTimes + 1, true);
        System.out.print(down ? "down " : "up ");
        //每一层的右节点都是凸
        process(times, curTimes + 1, false);
    }

    public void paperOut (int times)
    {
        //times小于1,代表没折纸
        if (times < 1) {
            return;
        }

        //系统记录折纸的次数, 用来与times作比较用
        int curTimes = 1;
        //第一次默认是凹下去的
        process(times, curTimes, true);
    }

    public static void main(String[] args) {
        Code03_PaperTree test = new Code03_PaperTree();
        int times = 2; //折纸次数
        test.paperOut(times);
    }
}

 

标签:21,curTimes,纸条,折纸,times,down,算法,折痕
From: https://www.cnblogs.com/chen1-kerr/p/17143641.html

相关文章

  • 【2023-02-21】思考改进
    20:00最大的决心会产生最高的智慧。                                         ......
  • 运筹优化算法工程师问题记录(个人收藏记录用)
    一、运筹优化相关介绍一个做的最好的一个项目用过哪些求解器如果求解器求解问题时间太长,该怎么优化元启发式算法有哪些有两个约束,是与的关系,怎么在建模中体现(建模技......
  • 模型压缩-剪枝算法详解
    一,前言1.1,模型剪枝定义二,深度神经网络的稀疏性2.1,权重稀疏2.2,激活稀疏2.3,梯度稀疏2.4,小结三,结构化稀疏3.1,结构化稀疏分类3.1.1,channel剪枝3.1.2,阶段......
  • 每日训练-2023.2.21
    还是很有必要进行每日训练的,之前摆一摆倒还好,组队之后比赛量肯定会上去,再不练一练到时候只能天天拖队友后腿了(悲这学期的学业压力也不小,尤其是我非常不擅长物理+实验,模电......
  • 第一周学习总结(02.21)
    这一周主要学习了python爬虫,主要是列表,元组,函数,文件操作,异常处理和爬虫基本概念的学习,除此之外还学习了一点xml。列表:[],列表可以存储混合类型,for循环遍历输出,以及列表的增......
  • 2月21日总结
    代码量:0行今日是写总结的第二天。今日上午上了5节课,下午上了2节课。剩下的下午和晚上的时间本事可以用来写代码的,但是我今日的代码量为0行,原因是什么呢?我用这些时间干什......
  • 每日博客2023/2/21
    今天上课,上口语课,和两个美女坐同桌,打破了自高一分班之后没和女生坐同桌的记录(高兴了一会),然后上了数据库,听了杨子光老师的讲解,虽然现在忘了讲了什么,但是听到很认真,了解了数......
  • 算法和数据结构新手班课程内容(1~8节)
    01位运算、算法是什么、介绍位运算和简单排序内容:讲解二进制、位运算介绍什么是算法讲解冒泡、选择、插入排序题目:实现打印一个整数的二进制给定一个参数N,返回1!+2......
  • 算法和数据结构新手班课程内容(1~8节)
    01位运算、算法是什么、介绍位运算和简单排序内容:讲解二进制、位运算介绍什么是算法讲解冒泡、选择、插入排序题目:实现打印一个整数的二进制给定一个参数N,返回1!+2......
  • 算法杂记 2023/02/21
    算法杂记2023/02/21目录算法杂记2023/02/21D.MovingDots2000今天分享的是Codeforce上的一道2000分的组合+计数题。目前的目标是从紫冲橙。D.MovingDots......