書中楊輝說明是引自賈憲的《釋鎖算術》 維基連結
參考一下它的排列方式和算法
現在把它先寫成如下圖的程式：
(1,1)表示第一層第一個；(5,3)表示第5層第3個
先寫個框框吧！
※第一階段：座標
public static void main(String[] args) {
pascal(7);
}
public static void pascal(final int layer) {
int rightCoordinate = layer;
for (int i = 1; i <= layer; i++) {
for (int j = 1; j <= rightCoordinate; j++) {
System.out.print("(" + i + "," + j + ") ");
}
System.out.println();
rightCoordinate--;
}
}
※外層迴圈表示第幾層，內層迴圈表示要印出的座標，要和上圖的座標一樣才表示正確的
※因為第一層要印7個，第二層印6個，每次減1，而一開始印的7個剛好和要印幾層一樣，所以宣告了rightCoordinate變數
※第二階段：左/上 兩層
private static void pascal(final int layer) {
int rightCoordinate = layer;
for (int i = 1; i <= layer; i++) {
for (int j = 1; j <= rightCoordinate; j++) {
// System.out.print("(" + i + "," + j + ") ");
System.out.print(coordinate(i, j) + " ");
}
System.out.println();
rightCoordinate--;
}
}
private static int coordinate(int left, int right) {
if (left == 1 || right == 1) {
return 1;
}
if (left == 2 || right == 2) {
return left > right ? left : right;
}
return 0;
}
※根據上圖會發現，座標有1的，結果就是1；座標有2的，結果是比較大的那一個，如(2,4)或(4,2)，結果都是4
但如果有1也有2，如(2,1)和(1,2)，結果是1，所以if有1的判斷式要放在前面
※其他暫時回傳0
※第三階段：完成
private static int coordinate(int left, int right) {
if (left == 1 || right == 1) return 1;
if (left == 2 || right == 2) return left > right ? left : right;
return coordinate(left - 1, right) + coordinate(left, right - 1);
}
※(4,3)的結果是10，是由(4,2)和(3,3)算來的，所以是左-1和右-1相加而得
(4,2)的結果是由(4,1)和(3,2)算來的，所以是左-1和右-1相加而得
(3,3)的結果是由(3,2)和(2,3)算來的，所以是左-1和右-1相加而得
其他也都是一樣，所以公式是「左-1加右-1」
所以將這個公式呼叫自己，也就是遞迴，答案即為所求
※此時想將排版改成和楊輝三角形時，也就是左邊要補空格，是不可行的，以5層為例，會變成如下的樣子
1 1 1 1 1
1 2 3 4
1 3 6
1 4
1
所以一開始的圖是不夠正確的，將它改成如下的樣子
※
public static void main(String[] args) {
pascal(7);
}
private static void pascal(final int layer) {
int space = layer - 1;
for (int i = 1; i <= layer; i++) {
getSpace(space--);
for (int j = 1; j <= i; j++) {
// System.out.print("(" + i + "," + j + ") ");
System.out.print(coordinate(i, j) + "|");
}
System.out.println();
}
}
private static int coordinate(int left, int right) {
if (right == 1 || left == right) {
return 1;
}
return coordinate(left - 1, right - 1) + coordinate(left - 1, right);
}
private static void getSpace(int s) {
for (int space = s; space > 0; space--)
System.out.print(" ");
}
※不熟的一樣要用剛剛的三階段比較好了解，但此時的做法又不太一樣了
會回傳1的要改成右邊是1或者左右座標一樣的，看圖即可知道
※遞迴也要改，本來是左邊和上面的加總，要改成上面和上面的左邊加總，一樣看圖即可知道
所以公式變成「左-1加上左右-1」，將公式放在遞迴的位置上即可
※此時可以排版了，宣告的space變數即為排版用的，但太多層時，因位數字的關係，如幾百幾千，就是要佔3、4個位置，和一開始的佔1、2個位置有差，所以不好排版，可能還要再想一下才會好看
※陣列寫法
上面的座標，當然也是可以用陣列來實現，會變得更加簡單，但因為陣列都是從0開始，所以再將圖改成以下的樣子
改成都是從0開始
※
public static void main(String[] args) {
pascal(10);
}
private static void pascal(final int layer) {
int l = layer - 1;
int[][] lr = new int[l][l];
for (int i = 0; i < lr.length; i++) {
for (int j = 0; j <= i; j++) {
if (j == 0 || i == j) {
lr[i][j] = 1;
} else {
lr[i][j] = lr[i - 1][j - 1] + lr[i - 1][j];
}
System.out.print(lr[i][j] + "|");
}
System.out.println();
}
}
※layer-1是因為從0開始，0~9就是10層了，所以-1
※由於一開始是0，所以一開始進迴圈不能減1，所以直接在裡面判斷，判斷的方法和上面介紹的一樣，看圖說故事
※還沒有排版，直接使用上面寫的getSpace方法，但因為陣列的關係，所以還得再減1，如下：
public static void main(String[] args) {
pascal(10);
}
private static void pascal(final int layer) {
int l = layer - 1;
int space = l - 1;
int[][] lr = new int[l][l];
for (int i = 0; i < lr.length; i++) {
getSpace(space--);
for (int j = 0; j <= i; j++) {
if (j == 0 || i == j) {
lr[i][j] = 1;
} else {
lr[i][j] = lr[i - 1][j - 1] + lr[i - 1][j];
}
System.out.print(lr[i][j] + "|");
}
System.out.println();
}
}
private static void getSpace(int s) {
for (int space = s; space > 0; space--)
System.out.print(" ");
}
※
