巴斯卡三角形
November 29, 2021巴斯卡（Pascal）三角形的最上面是 1，每列左右兩端也都是 1，第二列起各行相鄰兩數字相加，就是下一列兩數間的數字。例如：
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
若要求第 n 列的數字，該怎麼求呢？
解法思路
- 巴斯卡三角形與 (x + 1)ⁿ 多項式展開後的係數有關係，來觀察一下：
- (x + 1)¹ = x + 1
- (x + 1)² = x² + 2x + 1
- (x + 1)³ = x³ + 3x² + 3x + 1
- (x + 1)⁴ = x⁴ + 4x³ + 6x² + 4x + 1
- …
- 巴斯卡三角形第 n + 1 列的數字，就是 (x + 1)ⁿ 的多項式展開後降冪排列後的係數。若巴斯卡三角形的每一個數字各對應一個 ᵣCₙ，可以使用以下公式計算，以避免階乘運算時的數值溢位：
- ᵣ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
巴斯卡三角形有個與質數相關的特性，(x + 1)ⁿ 的多項式展開後降冪排列後的係數，除了 xⁿ 與 1 以外的係數，若可以被 n 整除，n 就是質數，你可以自行驗證看看。
巴斯卡三角形裡也隱藏著〈費氏數列〉，將方才的巴斯卡三角形靠左對齊（比較好觀察罷了），按照箭頭方向各自加總看看吧！
如果去掉巴斯卡三角形裡 2 的倍數，你會發現 Sierpinski 三角形：
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
你可以試著去掉 3、4、5 的倍數，各自會發現不同的圖樣喔！
程式實作
#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++) {
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 = 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)
