巴斯卡三角形

0C0
1C0 1C1
2C0 2C1 2C2
3C0 3C1 3C2 3C3
4C0 4C1 4C2 4C3 4C4

解法

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``

``````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 12int 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;} ``

``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();        }    }}``

``def combi(r, n):    return 1 if n == 0 else combi(r, n - 1) * (r - n + 1) // n	height = 12c = [[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()``

``def combi(r: Int, n: Int): Int = n match {    case 0 => 1    case _ => combi(r, n - 1) * (r - n + 1) / n}val height = 12val 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})``

``def combi(r, n)    return 1 if n == 0; combi(r, n - 1) * (r - n + 1) / nendheight = 120.upto(height - 1) do |r|    printf "%" + ((height - r) * 3).to_s + "s", ""    0.upto(r) do |n|       printf "%6d", combi(r, n)    end    putsend``

``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);``

``import Control.Monadimport Text.Printfcombi _ 0 = 1combi r n = combi r (n - 1) * (r - n + 1) `div` nmain = 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 "")``

``````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).``````