請問一下二項示係數(巴斯卡三角形)的c++程式要如何寫呢?

shin1520

請輸入n 和 k，用
(a)遞迴方式印出 C(n, k) 的值；
(b) 迴圈 (非遞迴) 方式印出所有小於n的二項式係數 (binomial coefficient)：(如下)

n=4 (假設)

1
11
121
1331
14641

n和 k 都要使用者自行輸入，輸出上圖的巴斯卡三角形圖形

c(n,k)=n!/k!(n-k)!,o<=k<=n

如果有大大會的話，麻煩請教一下，謝謝!

malictiamo

這邊只講方法，code交給你去練習

(a)
要使用Recursion就要知道C(n, k)可以從哪邊組合出來。
我們可以用巴斯卡三角形推出以下公式：
C(n, k) = C(n-1, k-1)+C(n-1,k), when 0<k<n
例如：C(4, 2) = C(3,1)+C(3, 2)
到什麼時候終止，就要看什麼時候無法做
C(2,1)=C(1,0)+C(1,1)，後面這兩個我們可以很簡單的算出來，因此只要以下條件，就可以完成
if k=n, then return 1
...

瀏覽完整內容，請先 註冊 或 登入會員

daviddr

也可以一個個算:

1. int main()
   
2. {
   
3.     int i=1,j,c,n;   
   
4.     for (cin>>n; i<=n; i++, puts(""))
   
5.         for (c=1, j=i; j--; c*=j, c/=i-j)
   
6.             cout <<' ' <<c;
   
7. }

複製代碼

[ 本帖最後由 daviddr 於 2008-12-7 12:47 PM 編輯 ]...

瀏覽完整內容，請先 註冊 或 登入會員

daviddr

如果滿足 n<5，可以如此偽裝：

    long long i=0, j=1, n;   
    for (cin>>n; ++i<=n; j+=(j<<1)+(j<<3)) cout<< j<<endl;