[C Programming] Fibonacci數非遞迴解-延伸

請參見Fibonacci數非遞迴解。
延伸問題：
1. 使用遞迴的解法會使用return f(n-1)+f(n-2);型態的方式來進行計算，
    這種方式會產生許多重複。
    試以手算的方式來計算f(13)會有多少次的重複計算。
2. (續上題) 請問，算fn時一共用了多少個加法，請導出一條公式。
3. k階的Fibonacci數f1k, f2k, ... , fik, ...是這樣定義的(k是上標)，
    f1k=f2k=...=fkk=1
    fik = f(i-1)k + f(i-2)k + ... + f(n-k+1)k  ( i > k )。
   換言之，fjk是前k個fik的和，因此當k=2時就是一般的Fibonacci數列，
   請不用遞迴(但或許可以用陣列)，寫一個函數fibK(n, k)，
   接收n與k算出fnk。
4. 為什麼函數值要用unsigned long 而不用int呢？請說出你的看法。
個人解答：
1. f(13)  = f(12) + f(11) = 2f(11) + f(10) = 3 f(10)+2 f(9)
             =5 f(9) + 3 f(8) = 8 f(8) + 5 f(7) = 13 f(7) + 8 f(6)
             = 21 f(6) + 13 f(5) = 34 f(5) + 21 f(4) = 55 f(4) + 34 f(3)
             = 89 f(3) + 55 f(2) = 144 f(2) + 89 f(1) = 233
   這當中由於最後都會分解到f(2)和f(1)，
   所以實際分解成233個項次，扣掉f(2)和f(1)，一共重複了231次。
2. Tfn =  fn - 1   , n > 0
3. 利用原題的方法，每次將前面的數加總後遞移往下，
    只是我們需要限定一個陣列最大值K，沒有用到的就不要用。

Code：

#include <stdio.h>
#include <stdlib.h>

#define MAX_K 20
unsigned long fnk[MAX_K+1];

unsigned long fibK(int n, int k)
{
 unsigned long tmp;
 int i, j;
 if( n <= k )
  return 1;
 else
 {
  for(i=1; i<=k; i++)
   fnk[i] = 1;
  for(i=k+1; i<=n; i++)
  {
   tmp  = fnk[k];     // tmp = fnk[1]+...+fnk[k]
   for(j=1; j<k; j++)
    tmp += fnk[j];

   // fnk[1] = fnk[2], fnk[2] = fnk[3], ... , fnk[k] = tmp
   for(j=1; j<k; j++)    
    fnk[j] = fnk[j+1];
   fnk[k] = tmp;
  }
 }
 return tmp;
}

int main(int argc, char *argv[])
{ 
 int n;
 for(n = 1; n <= 20; n++)
  printf("f(%d) = %ld\n", n, fibK(n,4));
 system("PAUSE");
 return 0;
}

4. unsigned long比int大阿廢話，
    簡單說可以放更大的可能值，同時unsigned可以多出一個bit放值，
    因為我們在這個狀況下不需要用到負值。