巴斯卡三角形

From Gossip@caterpillar

说明：
巴斯卡（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;
] 

算法实现之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(); 
    } 
}

http://www.freeage.cn/article.asp?id=73