楊輝三角形

楊輝三角形，又稱賈憲三角形、帕斯卡三角形、海亞姆三角形
書中楊輝說明是引自賈憲的《釋鎖算術》 維基連結
參考一下它的排列方式和算法

現在把它先寫成如下圖的程式：

此例為7層，只要把它順時針轉45度就一樣了
(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(" ");
}

※