//实现输入任意两个若干位的整数，进行加法，计算并返回加和后的结果。
//（注意两个整数可以足够大，以至于double都会溢出。只要系统内存够用，
//此加法都要正常运行）
#include"stdio.h"
#include"stdlib.h"
typedef struct node{
  int x;
  struct node *next;
  struct node *before;
}llnode;

int charToNumber(char c)
{
  return c-48;
}

void getNumber(llnode* tail)
{
  char c;
  llnode *p;
  llnode *q;
  q = tail;
  printf("请输入一个整数， 输入完成后敲击回车:");
  while(1)
    {
      c = getchar();
      if(c == '\n')
	{
	  break;
	}
      else
	{
	  p = (llnode *)malloc(sizeof(llnode));
	  p->x = charToNumber(c);
	  p->before = NULL;
	  if(tail->x == 0)
	    {
	      tail->before = p;
	      p->next = tail;
	      tail->x = tail->x+1;
	    }
	  else
	    {
	      q = tail->before;
	      q->next = p;
	      p->before = q;
	      p->next = tail;
	      tail->before = p;
	      q = p;
	      tail->x = tail->x+1;
	    }
	}
    }
}

void addNumber(llnode* ctail, llnode* atail, llnode* btail)
{
  int i=0;
  int alength = atail->x;
  int blength = btail->x;
  llnode *pshort;
  llnode *plong;
  llnode *ps;
  llnode *pl;
  llnode *p;
  llnode *q;
  int a;
  int b;
  int nextc;
  int thisc;
  int d;
  if(alength>blength)
    {
      pshort = btail;
      plong = atail;
    }
  else
    {
      pshort = atail;
      plong = btail;
    }
  ps = pshort->before;
  pl = plong->before;
  while(i<pshort->x)
    {
      thisc = nextc;
      if(ps->x + pl->x >=10)
	{
	  nextc = 1;
	  d = (ps->x + pl->x)%10;
	}
      else
	{
	  nextc = 0;
	  d = (ps->x + pl->x);
	}
      ps = ps->before;
      pl = pl->before;
      p = (llnode *)malloc(sizeof(llnode));
      p->x = d+thisc; 
      p->before = NULL;
      if(ctail->x == 0)
	{
	  ctail->before = p;
	  p->next = ctail;
	  ctail->x = ctail->x+1; 
	  q = p;
	}
      else
	{
	  p->next = q;
	  q->before = p;
	  q = p;
	  ctail->x = ctail->x+1;
	}
      i = i+1;
    }
  while(i<plong->x)
    {
      if(i == pshort->x)
	{
	  p = (llnode *)malloc(sizeof(llnode));
      	  p->x = (pl->x)+nextc; 
      	  p->before = NULL;
      	}
      else
      	{
	  p = (llnode *)malloc(sizeof(llnode));
      	  p->x = pl->x;
	  p->before = NULL;
      	}
      p->next = q;
      q->before = p;
      q = p;
      ctail->x = ctail->x+1;
      pl = pl->before;
      i = i+1;
    }
}

void showResult(llnode* ctail)
{
  llnode *p;
  p = ctail;
  while(p->before != NULL)
    {
      p = p->before;
    }
  while(p != ctail)
    {
      printf("%d",p->x);
      p = p->next;
    }
  printf("\n");
}

int main()
{
  llnode *atail = (llnode *)malloc(sizeof(llnode));
  llnode *btail = (llnode *)malloc(sizeof(llnode));
  llnode *ctail = (llnode *)malloc(sizeof(llnode));
  llnode *p=atail;
  atail->x = 0;
  btail->x = 0;
  ctail->x = 0;
  atail->next = NULL;
  btail->next = NULL;
  ctail->next = NULL;
  getNumber(atail);
  getNumber(btail);
  addNumber(ctail, atail, btail);
  showResult(ctail);
  return 1;
}

//已知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;
}