[C Programming] 擴充Fibonacci數

我們定義一組叫做擴充的Fibonacci 數如下：
已知X與Y兩個數，擴充Fibonacci數Fi為
          1                             i =  0
Fi  =   1                              i  =  i
          X*Fi-2 + Y * Fi-1      i  > 1

因此，當X=Y=1時，這一組擴充的Fibonacci 數就變成一般的Fibonacci 數。
現在請寫一個函數，接受一個n值，不用陣列與遞迴的手法算出下面的結果：

F(0)*F(n)+F(1)*F(n-1)+...+F(i)*F(n-1)+...+F(n-1)*F(1)+F(n)*F(0)

本題出自Jan L.A.van de Snepscheut.

答：
注意這邊原題定義上有些問題，一般來說應該會把X係數給F(n-1)，
但此處剛好相反。原Code裡面按其定義，
則其有一行程式碼應改為temp1 = x * f0 + y * f1;。
我們下面的解答全部都以X係數是在F(n) = X * F(n-2) + Y * F(n-1)為準。

Code：

unsigned long ext_fibonacci(int n, int x, int y)
{
 // Fn+1, Fn-1, Fn , An+1, An-1, An
 unsigned long tmpfn1, fn_1, fn, tmpAn1, an_1, an;
 int i;
 if( n == 0 )
  return 1;
 else if( n == 1 )
  return 2;
 else
  for(an_1=fn=fn_1=1, an=2, i=2; i<=n; i++)
  {
   // Fn+1 = x * Fn-1 + y * Fn, 
   // An+1 = x * An-1 + y * (An - Fn) + Fn + Fn+1
   tmpfn1 = x * fn_1 + y * fn;
   tmpAn1 = x * an_1 + y * (an - fn) + fn + tmpfn1;
   
   // shift the value to next
   fn_1 = fn; fn = tmpfn1;
   an_1 = an; an = tmpan1;
  }
 return an;
}