Binomial Coefficient (二項式係數) + Pascal (巴斯卡三角形)

(1) Write a recursive C program

(2) = ?
(3) 共呼叫此函數幾次 (連同第一次呼叫)?

Ans:
(1)

int Bin(int n, int m) {
  if (n==m||m==0) {
     return 1;
  } else {
     return Bin(n-1, m)+Bin(n-1, m-1);
  }
}

(2)
Bin(5,3) = Bin(4,3)+Bin(4,2)
= Bin(3,3)+Bin(3,2)+Bin(3,2)+Bin(3,1)
= 1+Bin(2,2)+Bin(2,1)+Bin(2,2)+Bin(2,1)+Bin(2,1)+Bin(2,0)
= 1+1+Bin(1,1)+Bin(1,0)+1+Bin(1,1)+Bin(1,0)+Bin(1,1)+Bin(1,0)+1
= 1+1+1+1+1+1+1+1+1+1
= 10

(3)
共19次

=============

Pascal 巴斯卡三角形
n 為 row, r 為 column
nC0 = 1
nCr = [(n-r+1)/r] * nCr-1

int main()
{
int N=4;
int n,r,i;
    for (n=0;n<=N;n++) {
        for (r=0;r<=n;r++) {        
            long nCr = 1;
            for(i=1;i<=r;i++) {
                nCr = nCr * (n-i+1)/i;
            }
            cout << nCr;
        }
        cout << "\n";
    }

    system ("pause");
    return 0 ; 
}

1
11
121
1331
14641