From Gossip@caterpillar

Algorithm Gossip: 巴斯卡三角形

巴斯卡（Pascal）三角形基本上就是在解 nCr ，因為三角形上的每一個數字各對應一個nCr，其中 n 為 row，而 r 為 column，如下：
　　　　0C0
　　　1C0 1C1
　　2C0 2C1 2C2
　3C0 3C1 3C2 3C3
4C0 4C1 4C2 4C3 4C4

對應的數據如下圖所示：

解法

巴斯卡三角形中的 nCr 可以使用以下這個公式來計算，以避免階乘運算時的數值溢位：

nCr = [(n-r+1)/r] * nCr-1 

nC0 = 1

演算法

/* 計算nCr，但是並不快，只是方便 */
Procedure COMBI(n, r) [
    FOR(i = 1; i <= r; i = i + 1)
        p = p * (n-i+1) / i;

    RETURN p;
]

解決 nCr 的算法之後，剩下的就是如何將這些數字排版成三角形的問題了，這就要看您是如何顯示成果的了，下面的程式將分別示範文字模式（C實作）與視窗模式（Java實作）的解法。

實作

#include <stdio.h>
#define N 12

long combi(int n, int r){
    int i;
    long p = 1;

    for(i = 1; i <= r; i++)
        p = p * (n-i+1) / i;

    return p;
}

void paint() {
    int n, r, t;

    for(n = 0; n <= N; n++) {
        for(r = 0; r <= n; r++) {
            int i;
            /* 排版設定開始 */
            if(r == 0) {  
                for(i = 0; i <= (N-n); i++) {
                    printf("   ");
                }
            }
            else {
                printf("   ");
            } /* 排版設定結束 */

            printf("%3d", combi(n, r));
        }
        printf("\n");
    }
}

int main() {
    paint();
    return 0;
}

Java

import java.awt.*; 
import javax.swing.*; 

public class Pascal extends JFrame { 
    public Pascal() { 
        setBackground(Color.white); 
        setTitle("巴斯卡三角形"); 
        setSize(520, 350); 
        setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); 
        show(); 
    } 

    private long combi(int n, int r){ 
        int i; 
        long p = 1; 

        for(i = 1; i <= r; i++) 
            p = p * (n-i+1) / i; 
  
        return p; 
    } 

    public void paint(Graphics g) { 
        final int N = 12; 
        int n, r, t; 

        for(n = 0; n <= N; n++) { 
            for(r = 0; r <= n; r++) 
                g.drawString(" " + combi(n, r), 
                    (N-n)*20 + r * 40, n * 20 + 50); 
        } 
    } 

    public static void main(String args[]) { 
        Pascal frm = new Pascal(); 
    } 
}