最新消息:网站改版咯

巴斯卡三角形

C语言 Yovae 1492浏览

巴斯卡三角形

巴斯卡(Pascal)三角形基本上就是在解 nCr ,因為三角形上的每一個數字各對應一個nCr,其中 n 為 row,而 r 為 column,如下:
0
C0
1
C0 1C1
2
C0 2C1 2C2
3
C0 3C1 3C2 3C3
4
C0 4C1 4C2 4C3 4C4

對應的數據如下圖所示:

巴斯卡三角

解法

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

nCr = [(n-r+1)/r] * nCr-1
n
C0 = 1

演算法

/* 計算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
#include <stdio.h>;
#define N 12

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

void paint() {
    int n;
    for(n = 0; n &lt;= N; n++) {
        int r;
        for(r = 0; r &lt;= n; r++) {
            int i;
            // 排版設定開始
            if(r == 0) {  
                for(i = 0; i &lt;= (N-n); i++) {
                    printf("   ");
                }
            }
            else {
                printf("   ");
            } 
            // 排版設定結束

            printf("%3d", combi(n, r));
        }
        printf("\n");
    }
}

int main() {
    paint();
    return 0;
} 
  • Java
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 &lt;= 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 &lt;= N; n++) { 
            for(r = 0; r &lt;= 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(); 
    } 
}
  • Python
def combi(n, r):
    p = 1
    for i in range(1, r + 1):
        p = p * (n - i + 1) / i
    return p

def paint(number):
    for n in range(number + 1):
        for r in range(n + 1):
            if r == 0:
                for i in range(number - n + 1):
                    print("   ", end="")
            else:
                print("   ", end="")
            print("%3d" % combi(n, r), end="")
        print("")
    
paint(12)
  • Scala
def combi(n: Int, r: Int) = {
    def c(p: Int, i: Int): Int = if(i &lt;= r) c(p * (n-i+1)/i, i+1) else p
    c(1, 1)
}

def paint(number: Int) {
    for(n &lt;- 0 to number) {
        for(r &lt;- 0 to n) {
            if(r == 0)             
                for(i &lt;- 0 to (number -n)) print("   ")
            else 
                print("   ")
            printf("%3d", combi(n, r))
        }
        println()
    }
}

paint(12)

转载请注明:Yovae Studio » 巴斯卡三角形