经典算法(5)杨辉三角

经典算法(5)杨辉三角杨辉三角是经典算法,这篇博客对它的算法思想进行了讲解,并有完整的代码实现。

大家好,又见面了,我是你们的朋友全栈君。

写在前面: 我是「扬帆向海」,这个昵称来源于我的名字以及女朋友的名字。我热爱技术、热爱开源、热爱编程。技术是开源的、知识是共享的。

这博客是对自己学习的一点点总结及记录,如果您对 Java算法 感兴趣,可以关注我的动态,我们一起学习。

用知识改变命运,让我们的家人过上更好的生活

相关文章

点此查看 【算法系列】 博客文章


一、杨辉三角的介绍

百度百科对于杨辉三角是这样介绍的:
在这里插入图片描述

二、杨辉三角的算法思想

经典算法(5)杨辉三角(此图片来源于网络)

杨辉三角的两个腰边的数都是 1,从第3行起,除第一个数和最后一个数外,其它位置的数都是上顶上两个数之和。

三、代码实现

1.第一种写法

public class YangHuiTriangle1 { 

public static void main(String[] args) { 

Scanner scanner = new Scanner(System.in);
System.out.print("输入要打印的行数:");
int n = scanner.nextInt();
// 打印杨辉三角
getTriangle(n);
}
/** * 打印杨辉三角 * * @param n 要打印的行数 * @return */
private static int[][] getTriangle(int n) { 

// 创建一个二维数组,此二维数组用来存放杨辉三角中每一行的值
int[][] array = new int[n][n];
// 给数组元素赋值
for (int i = 0; i < array.length; i++) { 

// 每一行的值
array[i] = new int[i + 1];
// 给首末元素赋值
array[i][0] = array[i][i] = 1;
// 给每行的非首末元素赋值
if (i > 1) { 

for (int j = 1; j < array[i].length - 1; j++) { 

array[i][j] = array[i - 1][j - 1] + array[i - 1][j];
}
}
}
// 遍历二维数组
for (int i = 0; i < array.length; i++) { 

for (int j = 0; j < array[i].length; j++) { 

System.out.print(array[i][j] + "\t");
}
System.out.println();
}
return array;
}
}

代码执行结果:

输入要打印的行数:10
1	
1	1	
1	2	1	
1	3	3	1	
1	4	6	4	1	
1	5	10	10	5	1	
1	6	15	20	15	6	1	
1	7	21	35	35	21	7	1	
1	8	28	56	70	56	28	8	1	
1	9	36	84	126	126	84	36	9	1	

2.第二种写法

public class YangHuiTriangle2 { 

public static void main(String[] args) { 

Scanner scanner = new Scanner(System.in);
System.out.println("输入要打印的行数:");
int n = scanner.nextInt();
// 打印杨辉三角
int array[][] = getTriangle(n);
// 打印成等腰三角形
printTriangle(array);
}
private static int[][] getTriangle(int n) { 

// 创建一个二维数组,此二维数组用来存放杨辉三角中每一行的值
int[][] array = new int[n][n];
// 给数组元素赋值
for (int i = 0; i < array.length; i++) { 

// 每一行的值
array[i] = new int[i + 1];
// 给首末元素赋值
array[i][0] = array[i][i] = 1;
// 给每行的非首末元素赋值
if (i > 1) { 

for (int j = 1; j < array[i].length - 1; j++) { 

array[i][j] = array[i - 1][j - 1] + array[i - 1][j];
}
}
}
return array;
}
/** * 打印成等腰三角形 * * @param array */
public static void printTriangle(int[][] array) { 

for (int i = 0; i < array.length; i++) { 

// 输出杨辉三角数字前面的空格
for (int j = 0; j < array.length - 1 - i; j++) { 

System.out.print(" ");
}
for (int j = 0; j <= i; j++) { 

// 用空格填补空位置
System.out.print(" ");
// 以十进制整数的形式输出,位宽是3,左对齐
System.out.printf("%-3d", array[i][j]);
}
System.out.println();
}
}
}

代码执行结果:

输入要打印的行数:
10
1  
1     1  
1     2     1  
1     3     3     1  
1     4     6     4     1  
1     5     10    10    5     1  
1     6     15    20    15    6     1  
1     7     21    35    35    21    7     1  
1     8     28    56    70    56    28    8     1  
1     9     36    84    126   126   84    36    9     1  

上一篇 经典算法(4)一文搞懂什么是 快速排序
下一篇 经典算法(6)斐波拉契数列、兔子繁殖、跳台阶算法


由于水平有限,本博客难免有不足,恳请各位大佬不吝赐教!

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/133405.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号