巴斯卡三角形

巴斯卡（Pascal）三角形基本上就是在解 rCn ，因為三角形上的每一個數字各對應一個rCn，其中 r 為 row，而 n 為 column，如下：
　　　　₀C₀
　　　₁C₀ ₁C₁
　　₂C₀ ₂C₁ ₂C₂
　₃C₀ ₃C₁ ₃C₂ ₃C₃
₄C₀ ₄C₁ ₄C₂ ₄C₃ ₄C₄

對應的數據如下圖所示：

解法

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

rC0
                = 1

                rCn = rCn-1 * (r -
                n + 1) / n

演算法

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

解決 rCn 的算法之後，剩下的就是如何將這些數字排版成三角形的問題了，這就要看您是如何顯示成果的了。

實作：Toy C Java Python Scala Ruby JavaScript Haskell Prolog

def combi(r, n) {
    if n == 0 {
        return 1
    }
    return combi(r, n - 1) * (r - n + 1) / n
}

def space(n) {
    return List.create(n, '').join(' ')
}

HEIGHT = 12

def printRow(row) {
    def printNumber(n) {
        c = combi(row, n) + ''
        print(c + space(6 - c.length()))
    }

    print(space((HEIGHT- row) * 3)) # indentation
    iterate(0, row + 1).forEach(printNumber)
    println()
}

iterate(0, HEIGHT).forEach(printRow)

#include <stdio.h>
#define HEIGHT 12

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

int main() {
    int r;
    for(r = 0; r < HEIGHT; r++) {
        char format[5];            
        sprintf(format, "%%%ds", (HEIGHT - r) * 3);
        printf(format, "");
        int n;
        for(n = 0; n <= r; n++) {
            printf("%6d", combi(r, n));
        }
        printf("\n");
    }
    return 0;
}

Java

import static java.lang.System.out;
import java.util.*;

public class Pascal {
    private List<List<Integer>> rows = new ArrayList<>();
    
    Pascal(int height) {
        for(int r = 0; r < height; r++) {
            rows.add(createRow(r));
        }
    }
    
    int combi(int r, int n) {
        return rows.get(r).get(n);
    }
    
    private List<Integer> createRow(int r){
        List<Integer> row = new ArrayList<>();
        row.add(1);
        for(int n = 1; n <= r; n++) {
            row.add(row.get(n - 1) * (r - n + 1) / n);
        }
        return row;
    }
    
    public static void main(String[] args) {
        final int HEIGHT = 12;
        Pascal p = new Pascal(HEIGHT);
        for(int r = 0; r < HEIGHT; r++) {
            out.printf(String.format("%%%ds", (HEIGHT - r) * 3), "");
            for(int n = 0; n <= r; n++) {
                out.printf("%6d", p.combi(r, n));
            }
            out.println();
        }
    }
}

Python

def combi(r, n):
    return 1 if n == 0 else combi(r, n - 1) * (r - n + 1) // n
	
height = 12
c = [[combi(r, n) for n in range(r + 1)] for r in range(height)]
 
for r in range(len(c)):
    print(("%" + str((len(c) - r) * 3) + "s") % "", end = "")
    for n in range(len(c[r])):
	    print("%6d" % c[r][n], end = "");
    print()

Scala

def combi(r: Int, n: Int): Int = n match {
    case 0 => 1
    case _ => combi(r, n - 1) * (r - n + 1) / n
}

val height = 12
val c = for(r <- 0 until height) yield for(n <- 0 to r) yield combi(r, n)

(0 until c.length).foreach(r => {
    printf("%%%ds".format((c.length - r) * 3), "")
    c(r).foreach(printf("%6d", _))
    println
})

Ruby

def combi(r, n)
    return 1 if n == 0; combi(r, n - 1) * (r - n + 1) / n
end

height = 12
0.upto(height - 1) do |r|
    printf "%" + ((height - r) * 3).to_s + "s", ""
    0.upto(r) do |n|
       printf "%6d", combi(r, n)
    end
    puts
end

JavaScript

function combi(r, n) {
    if(n == 0) return 1;
    else return combi(r, n - 1) * (r - n + 1) / n;
}

var height = 12;
var pascal = '';
for(var r = 0; r < height; r++) {
    pascal += new Array((height - r) * 3).join(' ');
    for(var n = 0; n <=r; n++) {
        var c = combi(r, n);
        pascal += new Array(6 - (c + '').length).join(' ') + c;
    }
    pascal += '\n';
}
print(pascal);

Haskell

import Control.Monad
import Text.Printf

combi _ 0 = 1
combi r n = combi r (n - 1) * (r - n + 1) `div` n

main = do
    let height = 12
    forM [0..height - 1] (\r -> do
        putStr \$ take ((height - r) * 3) \$ cycle " "
        sequence [printf "%6d" (combi r n) | n <- [0..r]]
        putStrLn "")

Prolog

combi(_, 0, 1).
combi(ROW, COL, Result) :- NCOL is COL - 1,
                           combi(ROW, NCOL, NR),
                           Result is (NR * (ROW - COL + 1) / COL).

pascal_row(_, 0) :- writef("%d ", [1]).
pascal_row(ROW, COL) :- combi(ROW, COL, Result),
                        writef("%d ", [Result]),
                        NCOL is COL - 1,
                        pascal_row(ROW, NCOL).

pascal(0) :- pascal_row(_, 0).
pascal(ROWS) :- pascal_row(ROWS, ROWS),
                nl,
                NROWS is ROWS - 1,
                pascal(NROWS).
  
main([Arg0|_]) :-
        atom_number(Arg0, N),
        pascal(N).