ZOJ 1828 Fibonacci Numbers
发布时间:2020-12-14 02:01:20 所属栏目:大数据 来源:网络整理
导读:Fibonacci Numbers Time Limit:? 2 Seconds ????? Memory Limit:? 65536 KB 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
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.
100
354224848179261915075
No generated Fibonacci number in excess of 1000 digits will be in the test data,i.e. f(20) = 6765 has 4 digits. 分析:数据太大,模拟大数加法
#include <cstdio> #include <iostream> #include <algorithm> using namespace std; int f[5005][1010]; //保存最终结果 int len[5005]; //保存最终结果的长度 void display() { f[1][1] = 1; f[2][1] = 1; len[1] = 1; len[2] = 1; int i,j; for (i = 3; i <= 5000; i++) { int jin = 0; //判断是否有进位 for (j = 1; j <= max(len[i - 1],len[i - 2]) ; j++) { f[i][j] = f[i - 1][j] + f[i - 2][j] + jin; jin = f[i][j] / 10; f[i][j] %= 10; } if (jin) { f[i][j] = 1; len[i] = j; } else { len[i] = j - 1; } } } int main() { display(); int n; while (~scanf("%d",&n)) { for (int i = len[n]; i >= 1; i--) printf("%d",f[n][i]); printf("n"); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |