首页 > 编程笔记 > Java笔记 阅读:48

Java用队列实现杨辉三角(解析+完整实现源码)

杨辉三角是一个由数字排列成的三角形数表,一个 8 阶的杨辉三角图形如下图所示。


图 1 8 阶的杨辉三角

从上图可以看出,杨辉三角具有以下性质:

队列实现杨辉三角

杨辉三角的第 i 行元素是根据第 i-1 行元素得到的,杨辉三角的形成序列是具有先后顺序的,因此杨辉三角可以通过队列来构造。

可以把杨辉三角分为 2 个部分来构造队列:所有的两端元素 1 作为已知部分,剩下的元素作为要构造的部分。

我们可以通过循环队列来实现杨辉三角的打印,在循环队列中依次存入第 i-1 行元素,再利用第 i-1 行元素得到第 i 行元素,然后依次入队,同时第 i-1 行元素出队并打印输出。

从整体来考虑,利用队列构造杨辉三角的过程,其实就是利用上一层元素序列产生下一层元素序列并入队,然后将上一层元素出队并输出,接着由队列中的元素生成下一层元素,以此类推,直到生成最后一层元素并输出。

我们以第 8 行元素为例来理解杨辉三角的具体构造过程:
1) 在第 8 行中,第一个元素先入队。假设队列为 Q:
Q.queue[rear]=1
Q.rear=(Q.rear+1)%QUEUESIZE

2) 第 8 行的中间 6 个元素通过第 7 行元素(已经入队)得到并入队:
Q.queue[rear]=Q.queue[front]+Q.queue[front+1]
Q.rear=(Q.rear+1)% QUEUESIZ
Q.front=(Q.front+1)% QUEUESIZE

3) 第 7 行最后一个元素出队:
Q.front=(Q.front+1)% QUEUESIZE

4) 第 8 行最后一个元素入队:
Q.queue[rear]=1
Q.rear=(Q.rear+1)% QUEUESIZE

至此,第 8 行的所有元素都已经入队。其他行的入队操作类似。

杨辉三角队列的实现

打印杨辉三角可以使用顺序队列或链式队列的基本算法实现,也可以直接使用数组模拟队列实现。下面只给出打印杨辉三角的顺序队列实现,使用数组模拟队列实现留给读者自行完成。

【实例】打印杨辉三角。
public class YangHuiTriangleTest {
    int count;          // 记录输出的行

    public void YangHuiTriangle(int N) throws Exception { // 顺序队列实现打印杨辉三角
        int QUEUESIZE = 20;
        Integer temp[] = new Integer[QUEUESIZE]; // 用于存放每一行的元素
        int k = 0;
        SeqQueue Q = new SeqQueue(); // 初始化顺序队列
        Q.EnQueue(1); // 第一行元素入队
        for (int i = 2; i < N + 1; i++) { // 产生第 i 行元素并入队,同时将第 i-1 行元素保存在临时数组中
            k = 0;
            Q.EnQueue(1); // 第 i 行的第一个元素入队
            for (int j = 1; j < i - 1; j++) { // 利用队列