# 巴斯卡三角形

November 29, 2021

``````                                 1
1     1
1     2     1
1     3     3     1
1     4     6     4     1
1     5    10    10     5     1
1     6    15    20    15     6     1
1     7    21    35    35    21     7     1
1     8    28    56    70    56    28     8     1
1     9    36    84   126   126    84    36     9     1
1    10    45   120   210   252   210   120    45    10     1
1    11    55   165   330   462   462   330   165    55    11     1
``````

## 解法思路

(x + 1)¹ = x + 1
(x + 1)² = x² + 2x + 1
(x + 1)³ = x³ + 3x² + 3x + 1
(x + 1)⁴ = x⁴ + 4x³ + 6x² + 4x + 1

ᵣC₀ = 1
ᵣCₙ = rCₙ₋₁ * (r - n + 1) / n

``````Procedure COMBI(R, N)
IF (N = 0)
RETURN 1
ELSE
RETURN COMBI(R, N - 1) * (R - N + 1) / N
``````

``````Procedure COMBI(R, N)
FOR(i = 1; i <= N; i = i + 1)
p = p * (R - i + 1) / i
RETURN p
``````

``````                                             1
1     1
1           1
1     3     3     1
1                       1
1     5                 5     1
1          15          15           1
1     7    21    35    35    21     7     1
1                                               1
1     9                                         9     1
1          45                                  45           1
1    11    55   165                           165    55    11     1
1                     495                     495                       1
1    13               715  1287              1287   715                13     1
1          91        1001        3003        3003        1001          91           1
1    15   105   455  1365  3003  5005  6435  6435  5005  3003  1365   455   105    15     1
``````

## 程式實作

``````#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;
}
``````
``````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++) {
}
}

int combi(int r, int n) {
return rows.get(r).get(n);
}

private List<Integer> createRow(int r){
List<Integer> row = new ArrayList<>();
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 = 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()
``````
``````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
})
``````
``````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
``````
``````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.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 "")
``````
``````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).
``````
``````# 我寫的玩具語言 https://github.com/JustinSDK/toy_lang

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