Java队列实现杨辉三角的生成

前言

本篇文章主要讲述通过队列打印输出杨辉三角的思想及C/C++的代码实现,希望阅读本篇文章以后大家有所收获,帮助大家对相关内容的理解更加深入。

杨辉三角

其实我之前就写过一篇关于C++实现杨辉三角的文章,所以今天这篇的内容除了以那篇为样,仅代码语言、代码逻辑有些许变化。明白C++的可以直接看那篇,大差不差。

C/C++队列实现杨辉三角 - 麦瑞克博客 (unitymake.com)

杨辉三角是公元1261年,我国宋代数学家杨辉在其著作《详解九章算法》中给出的一个用数字排列起来的三角形阵。由于杨辉在书中引用了贾宪著的《开方作法本源》和“增乘开方法”,因此这个三角形也称“贾宪三角”。在欧洲,这个三角形叫帕斯卡三角形,是帕斯卡在1654年研究出来的,比杨辉晚了近400年时间。

——以上介绍引用文章zhuanlan.zhihu.com/p/55686745。

下面是杨辉三角的规律图

特点

1、第一行有 1 个元素,第 n 行有 n 个元素

2、每一行的第一个元素和最后一个元素都是 1

3、从第三行开始,除去首尾位置的元素,每个元素等于上方元素与左上方元素之和

根据这些特点,我们可以直接使用循环来输出杨辉三角,不会绕什么弯子,实现起来应该很简单。

但今天笔者想说说队列实现杨辉三角的思想,那么让我们开始吧。

实现

思想

我们根据特点3知道杨辉三角“除去首尾位置的元素,每个元素等于上方元素与左上方元素之和”,我们想一想有没有什么办法让首尾元素也按照这个规律,这样的话规律就更加统一了。再让我们看看杨辉三角的规律图能不能发现什么规律。我们可以发现只要在每行的首尾位置都补上0,那么我们在杨辉三角中首尾元素的1也可以按照这个规律计算出来。

那么就很棒了,我们直接就可以通过计算出前后两个元素,得到下一行的元素,同时输出出来,依次向后计算,最后这就得到了下一行的所有元素。我们都知道队列的特性是先进先出。利用这个特性我们将第i行存进去,用来计算i+1行,依次下去。那为了杨辉三角继续循环运算得到第n行,我们同时也需要将得到的下一行(i+1行)的所有元素依次入队列。

过程图:箭头表示出队,黄色表示新入队列的元素。曲线表示前后两个元素。

最终队列里的元素,总是上一行的结果。

代码实现

代码逻辑:从第二行开始,先入队一个辅助元素0,作为下一行的首辅助元素与这一行的尾辅助元素。内层循环先删除当前队列的头元素,再得到删除操作后当前队列的头元素,计算两元素之和并输出,同时入队。内层列循环直到遍历到下一个的辅助元素时,退出该循环完成当前行的打印。紧接着继续行循环,向下打印每一行。

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class program {
    public static void main(String[] args)
    {
        System.out.println("hello");
        System.out.println("输入要生成的杨辉三角的行数");
        Scanner scanner=new Scanner(System.in);
        YHSJ(scanner.nextInt());
    }
    public static void YHSJ(int row)
    {
        if (row<1)
        {
            System.out.println("无效数据");
            return;
        }
        Queue<Integer> queue=new LinkedList<Integer>();
        Queue<Integer> afterQueue=new LinkedList<Integer>();
        queue.add(0);
        queue.add(1);
        queue.add(0);

        for (int i=0;i<row;i++)
        {
            for (int nbsp=row-i-1;nbsp>0;nbsp--)
            {
                System.out.print(" ");
            }
            if (i==0)
            {
                System.out.println("1");
                continue;
            }
            for (int j=1;j<=i+1;j++)
            {
                int a=queue.remove();
                int b=queue.element();
                int n=a+b;
                afterQueue.add(n);
                System.out.print(String.format("%d ",n));

            }

            queue.remove();
            queue.add(0);
            for(int k=1;k<=i+1;k++)
            {
                queue.add(afterQueue.remove());
            }
            queue.add(0);
            afterQueue.clear();
            System.out.println("");
        }
    }
}

效果

 

 

作者:Miracle
来源:麦瑞克博客
链接:https://www.unitymake.com/archives/programming-life/java/2958
本博客所有文章除特别声明外,均采用CC BY-NC-SA 4.0许可协议,转载请注明!
THE END
分享
打赏
海报
Java队列实现杨辉三角的生成
前言 本篇文章主要讲述通过队列打印输出杨辉三角的思想及C/C++的代码实现,希望阅读本篇文章以后大家有所收获,帮助大家对相关内容的理解更加深入。 杨辉三角 ……
<<上一篇
下一篇>>
文章目录
关闭
目 录