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實作）的解法。

實作：C Java Python Scala Ruby

#include <stdio.h>
#define N 12

long combi(int n, int r){
    long p = 1;
    int i;
    for(i = 1; i <= r; i++)
        p = p * (n-i+1) / i;
    return p;
}

void paint() {
    int n;
    for(n = 0; n <= N; n++) {
        int r;
        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); 
        setVisible(true)
    } 

    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[]) { 
        new Pascal(); 
    } 
}

Python

def combi(n, r):
    p = 1
    for i in range(1, r + 1):
        p = p * (n - i + 1) / i
    return p

def paint(number):
    for n in range(number + 1):
        for r in range(n + 1):
            if r == 0:
                for i in range(number - n + 1):
                    print("   ", end="")
            else:
                print("   ", end="")
            print("%3d" % combi(n, r), end="")
        print("")
    
paint(12)

Scala

def combi(n: Int, r: Int) = {
    def c(p: Int, i: Int): Int = if(i <= r) c(p * (n-i+1)/i, i+1) else p
    c(1, 1)
}

def paint(number: Int) {
    for(n <- 0 to number) {
        for(r <- 0 to n) {
            if(r == 0)             
                for(i <- 0 to (number -n)) print("   ")
            else 
                print("   ")
            printf("%3d", combi(n, r))
        }
        println()
    }
}

paint(12)

Ruby

def combi(n, r)
    p = 1
    1.upto(r) { |i|
        p = p * (n - i + 1) / i
    }
    p
end

def paint(number)
    0.upto(number) { |n|
        0.upto(n) { |r|
            if r == 0
                (number - n).times {
                    print "   "
                }
            else
                print "   "
            end
            printf "%3d", combi(n, r)
        }
        puts
    }
end

paint(12)