//已知n=0, f(n)=0; n=1, f(n)=1; n>=2, f(n)=[f(n-1)+1]*[f(n-2)-1], 求f(50)。
//注意：double也只能存储到f(18)。这道题应该不会是要考大整数乘法，所以题目出的有问题。
//这道题也可以用递归，但是递归运行速度比较慢，因为有大量重复计算，所以可以按照我的方法用链表。
//如果真的想要求出f(50)，可以用链表存储两个计算因子和计算结果，转化成大整数加法，来求大整数乘法。
//把乘法转化成加法计算，比如3×4 = 4+4+4
//以下是前20个数字的运行结果
//0:0.000000
//1:1.000000
//2:-2.000000
//3:-0.000000
//4:-3.000000
//5:2.000000
//6:-12.000000
//7:-11.000000
//8:130.000000
//9:-1572.000000
//10:-202659.000000
//11:318781034.000000
//12:-64604164553100.000000
//13:-20594582312338883346432.000000
//14:1330495784608724577563601617989664768.000000
//15:-27401004952344282189274505435890321300250290209030873808896.000000
//16:-36456921583136852485661222029923476042013772777779791392989314785761343035841829994866675810304.000000
//17:9989562888467599682490178454054145458467604867235829190066412851063708189685362766757643907501070026206
//55223767942258990500160700908909006358607921414144.000000
//18:-364188710874677328890688166883341655997440487840343568582579911102615655287833051471441667841754329590
//03497968188602575038253510532501707167150463676880377107100124867120157208280951966764835855418677107978
//345178504768013589268641567045778554224640.000000
//19:-inf
//20:inf


#include"stdio.h"
#include"stdlib.h"

typedef struct node{
  double x;
  struct node *next;
}llnode;

void generate(llnode *head, int n)
{
  llnode *p;
  llnode *m;
  double fn2 = 0;
  double fn1 = 0;
  int i = 0;
  if(n==1)
    {
      m = (llnode *)malloc(sizeof(llnode));
      m->x = 1;
      m->next = NULL;
      head->next = m;
    }
  else
    {
      p = head;
      while(i<n-2)
	{
	  p = p->next;
	  i = i+1;
	}
      fn2 = p->x;
      p = p->next;
      fn1 = p->x;
      m = (llnode *)malloc(sizeof(llnode));
      m->x = (fn1+1)*(fn2-1);
      m->next = NULL;
      p->next = m;
    }
}

double f(llnode* head, int n)
{
  int i=0;
  llnode *p = head;
  while(i<n)
    {
      p = p->next;
      i = i+1;
    }
  return p->x;
}

int main()
{
  llnode *head;
  int n = 0;
  int last = 20;//要求的最大结果
  double result=0;
  head = (llnode *)malloc(sizeof(llnode));
  head->x = 0;
  head->next = NULL;
  for(n=1; n<=last; n++)
    {
      generate(head, n);
    } 
  for(n=0; n<=last; n++)
    {
      result = f(head, n);
      printf("%d:", n);
      printf("%lf\n", result);
    }
  return 1;
}