杨辉三角也叫帕斯卡三角,在很多数量关系中可以看到,十分重要。
第0行: 1
第1行: 1 1
第2行: 1 2 1
第3行: 1 3 3 1
第4行: 1 4 6 4 1
…
两边的元素都是1, 中间的元素是左上角的元素与右上角的元素和。
我们约定,行号,列号都从0计数。
所以: 第6行的第2个元素是15,第3个元素是20
直观地看,需要开辟一个二维数组,其实一维数组也可以胜任。
如下程序就是用一维数组“腾挪”的解法。
package eight; public class yhsj { // 杨辉三角形的第row行第col列 static long f(int row, int col){ if(row<2) return 1; if(col==0) return 1; if(col==row) return 1; long[] a = new long[row+1]; a[0]=1; a[1]=1; int p = 2; while(p<=row){ a[p] = 1; for( int q=p-1;q>0;q-- ) a[q] = a[q] + a[q-1]; p++; } return a[col]; } public static void main(String[] args){ System.out.println(f(6,2)); System.out.println(f(6,3)); } }
还可以