算法详解--杨辉三角

百度简介

杨辉（南宋著名数学家）编辑

杨辉，字谦光，汉族，钱塘（今杭州）人，南宋杰出的数学家和数学教育家，生平履历不详。曾担任过南宋地方行政官员，为政清廉，足迹遍及苏杭一带。
他在总结民间乘除捷算法、“垛积术”、纵横图以及数学教育方面，均做出了重大的贡献。他是世界上第一个排出丰富的纵横图和讨论其构成规律的数学家。著有数学著作5种21卷，即《详解九章算法》12卷（1261），《日用算法》2卷（1262），《乘除通变本末》3卷（1274），《田亩比类乘除捷法》2卷（1275）和《续古摘奇算法》2卷（1275）（其中《详解》和《日用算法》已非完书）。后三种合称为《杨辉算法》。与秦九韶、李冶、朱世杰并称“宋元数学四大家”。

杨辉三角最本质的特征是，它的两条斜边都是由数字1组成的，而其余的数则是等于它肩上的两个数之和。
java代码

package algorithm;


public class YFTriangle {
public static void main(String[] args) {
          yh(19);
        }
/**
 * 它的两条斜边都是由数字1组成的，而其余的数则是等于它肩上的两个数之和。
 * @param in
 */
public static void yh(int in){
int[] a = new int[in + 1];
int previous = 1;
for (int i = 1; i <= in; i ++){
for (int j = 1; j <= i; j++){
int current = a[j];
                    a[j] = previous + current;
                    previous = current;
                    System.out.print(a[j] + " ");
                }
                System.out.println();
            }
        }
}

运行结果

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 
1 10 45 120 210 252 210 120 45 10 1 
1 11 55 165 330 462 462 330 165 55 11 1 
1 12 66 220 495 792 924 792 495 220 66 12 1 
1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1 
1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1 
1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1 
1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1 
1 17 136 680 2380 6188 12376 19448 24310 24310 19448 12376 6188 2380 680 136 17 1 
1 18 153 816 3060 8568 18564 31824 43758 48620 43758 31824 18564 8568 3060 816 153 18 1

出现负数
如果输入20行的话，那么最大的数将达到48620
如果你使用的是16位编译器(比如Tubro C)，int型只占2字节，所以就会溢出，
导致出现负数。
解决办法

package algorithm;


public class YFTriangle {
public static void main(String[] args) {
          yh(35);
        }
/**
 * 它的两条斜边都是由数字1组成的，而其余的数则是等于它肩上的两个数之和。
 * @param in
 */
public static void yh(int in){
long [] a = new long[in + 1];
long previous = 1;
for (int i = 1; i <= in; i ++){
for (int j = 1; j <= i; j++){
long current = a[j];
                    a[j] = previous + current;
                    previous = current;
                    System.out.print(a[j] + " ");
                }
                System.out.println();
            }
        }
}

训练数据（31行开始的。。。。）

1 31 465 4495 31465 169911 736281 2629575 7888725 20160075 44352165 84672315 141120525 206253075 265182525 300540195 300540195 265182525 206253075 141120525 84672315 44352165 20160075 7888725 2629575 736281 169911 31465 4495 465 31 1 
1 32 496 4960 35960 201376 906192 3365856 10518300 28048800 64512240 129024480 225792840 347373600 471435600 565722720 601080390 565722720 471435600 347373600 225792840 129024480 64512240 28048800 10518300 3365856 906192 201376 35960 4960 496 32 1 
1 33 528 5456 40920 237336 1107568 4272048 13884156 38567100 92561040 193536720 354817320 573166440 818809200 1037158320 1166803110 1166803110 1037158320 818809200 573166440 354817320 193536720 92561040 38567100 13884156 4272048 1107568 237336 40920 5456 528 33 1 
1 34 561 5984 46376 278256 1344904 5379616 18156204 52451256 131128140 286097760 548354040 927983760 1391975640 1855967520 2203961430 2333606220 2203961430 1855967520 1391975640 927983760 548354040 286097760 131128140 52451256 18156204 5379616 1344

秒客网

算法详解--杨辉三角

相关文章