3021:解决Pell数列的两种方法

解题思路:

注意事项:递归题不给用递归不然会超时

参考代码:递归法：

#include<stdio.h>

long long int pell(long long int n)

{ if(n==1)

  return 1;

  else if(n==2)

  return 2;

  else

  return (2*pell(n-1)+pell(n-2))%32767;

}

int main()

{ long long int i,n;

  scanf("%lld",&i);

  for(int k=1;k<=i;k++)

  { scanf("%ld",&n);

    printf("%lld\n",pell(n));

  }

  return 0;

}

循环法：

#include<stdio.h>

long long int pell(long long int n)

{ int a1=1,a2=2;

  if(n==1)

  return a1;

  else if(n==2)

  return a2;

  else

  { for(int k=3;k<=n;k++)

   { int temp=(2*a2+a1)%32767;

     a1=a2;

     a2=temp;

   }

  return a2;

  }

}

int main()

{ long long int i,n;

  scanf("%lld",&i);

  for(int k=1;k<=i;k++)

  { scanf("%ld",&n);

    printf("%lld\n",pell(n));

  }

  return 0;

}