首页 > 代码库 > hdu 1250 Hat's Fibonacci(高精度数)
hdu 1250 Hat's Fibonacci(高精度数)
// 继续大数,哎、、
Problem Description
A Fibonacci sequence is calculated by adding the previous two members the sequence, with the first two members being both 1.
F(1) = 1, F(2) = 1, F(3) = 1,F(4) = 1, F(n>4) = F(n - 1) + F(n-2) + F(n-3) + F(n-4)
Your task is to take a number as input, and print that Fibonacci number.
F(1) = 1, F(2) = 1, F(3) = 1,F(4) = 1, F(n>4) = F(n - 1) + F(n-2) + F(n-3) + F(n-4)
Your task is to take a number as input, and print that Fibonacci number.
Input
Each line will contain an integers. Process to end of file.
Output
For each case, output the result in a line.
Sample Input
100
Sample Output
4203968145672990846840663646 Note: No generated Fibonacci number in excess of 2005 digits will be in the test data, ie. F(20) = 66526 has 5 digits.
Author
戴帽子的
模拟斐波那契数列 , 不过递推公式变成了 f1 = f2 = f3 = f4 = 1 , f(n) = f(n-1) + f(n-2) + f(n-3) +f(n-4) . (n>=5) , 最大的数有2005位,所以,用大数吧
用的 跟 hdu1042 N! 的方法一样,用 十万 进制解决,每个整形存 10000,当然更大点也可以。。
**************************************/
Code:
#include <iostream> #include <string.h> #include <stdio.h> using namespace std; const int N = 7500; const int M = 500; int num[N][M]; void add() { memset(num,0,sizeof(num)); num[1][1] = num[2][1] = num[3][1] = num[4][1] = 1; int i,j,k = 0; for(i = 5;i<7500;i++) for(j = 1;j<500;j++) { k += num[i-1][j] + num[i-2][j] + num[i-3][j] + num[i-4][j];// 递推公式 num[i][j] = k%100000; k = k/100000; } while(k) { num[i][j++] = k%100000; k = k/100000; } } int main() { int n,i; add(); while(cin>>n) { for(i = 500-1;i>=0;i--) { if(num[n][i]!=0) break; } printf("%d",num[n][i--]); while(i>0) printf("%05d",num[n][i--]); printf("\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。