巴斯卡三角形

说明

巴斯卡（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

演算法

1
2
3
4
5
6
7


/* 计算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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


#include <stdio.h>
#define N 12

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;
}

void paint() {
    int n, r, t;

    for(n = 0; n <= N; n++) {
        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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


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

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