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

Fibonacci Number (費氏數列)

(1) Write a recursive finction in C
(2) Fib (5) = ?
(3) Fib(5)求值過程中, 共呼叫幾次Fib Function?

Ans:

(1)

int Fib(int n) {
 if(n==0) return 0;
    else if(n==1) return 1;
       else return Fib(n-1)+Fib(n-2);
}

(2)
Fib(5) = Fib(4) + Fib(3)
= Fib(3) + Fib(2) + Fib(2) + Fib(1)
= Fib(2) + Fib(1) + Fib(1) + Fib(0) + Fib(1) + Fib(0) + 1
= Fib(1) + Fib(0) + 1 + 0 + 1 + 0 + 1
= 1+0+1+0+1+0+1
= 5

(3)
共15次