经典算法(5)杨辉三角
程序员文章站
2022-07-14 16:14:01
...
一、杨辉三角的介绍
百度百科对于杨辉三角是这样介绍的:
二、杨辉三角的算法思想
(此图片来源于网络)
杨辉三角的两个腰边的数都是 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
推荐阅读
-
tp5框架使用cookie加密算法实现登录功能示例
-
NEX 3 5G手机星环影像系统详解:6400万三摄、Hyper-HDR逆光算法
-
PHP 中四大经典排序算法
-
OPPO Reno3 Pro 5G经典蓝今日开卖:4199元
-
易算11选5怎么用?11选5中奖算法说明
-
经典问题(c++/python)素数、杨辉三角(金字塔型)、统计单词数、简单计算器、密码安全程度、凯撒密码加密、汉诺塔 (python课设实验实例)-- biaobiao88
-
PHP各种常见经典算法总结【排序、查找、翻转等】
-
Python实现的朴素贝叶斯算法经典示例【测试可用】
-
Python实现的HMacMD5加密算法示例
-
经典的出入库算法(C#实现)