1949: Fibonacci Numbers

最新推荐文章于 2019-09-23 21:38:54 发布

kongming_acm

最新推荐文章于 2019-09-23 21:38:54 发布

阅读量723

点赞数

分类专栏： joj acm_大数运算文章标签： numbers input output c n2

本文链接：https://blog.csdn.net/kongming_acm/article/details/5375167

版权

joj acm_大数运算专栏收录该内容

11 篇文章

订阅专栏

1949: Fibonacci Numbers

Status	In/Out	TIME Limit	MEMORY Limit	Submit Times	Solved Users	JUDGE TYPE
	stdin/stdout	3s	16384K	775	220	Special Test

A Fibonacci sequence is calculated by adding the previous two members of the sequence, with the first two members being both 1.

f(1)=1, f(2)=1, f(n>2)=f(n-1)+f(n-2)

Your task is to take a number as input, and print that fibonacci number.

Sample Input

Sample Output

354224848179261915075

Note:

No generated fibonacci number in excess of 1000 digits will be in the test data, i.e. f(20)=6765 has 4 digits.

#include <stdio.h>
#include <string.h>

#define maxn 2000

int main()
{
int n;
while(scanf("%d", &n) != -1)
{
  int a[maxn + 1] = {0}, b[maxn + 1] = {0}, c[maxn + 1] = {0};
  b[maxn] = 1;
  while(n--)
  {
   c[maxn] = 0;
   for(int i = maxn; i > 0; --i)
   {
    c[i] += a[i] + b[i];
          c[i - 1] = c[i] / 10;
          c[i] %= 10;
   }
   memcpy(a, b, sizeof(b));
   memcpy(b, c, sizeof(c));
  }
  bool flag = false;
  for(int i = 0; i <= maxn; ++i)
  {
   if(flag || a[i] || i == maxn)
   {
    printf("%d", a[i]);
    flag = true;
   }
  }
  printf("/n");
}
return 0;
}