hdu 1250 Hat 's Fibonacci (고밀도 덧셈)
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.
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.
2005 위 는 고정 밀도 로 계산 해 8000 위 까지 계산 하면 충분 할 것 같다.
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=2008;
char f[9000][maxn+2]; // 9000？
int main()
{
int i=5,p=maxn,n,num;
f[1][maxn]=f[2][maxn]=f[3][maxn]=f[4][maxn]=1;
while(f[i-1][1]<=1){
for(int j=maxn;j>=p;j--){
f[i][j]=f[i-1][j]+f[i-2][j]+f[i-3][j]+f[i-4][j]; //******
}
for(int j=maxn;j>=p;j--){
int c=f[i][j]/10;
if(c>0){
f[i][j]=f[i][j]%10;
f[i][j-1]+=c;
}
}
if(f[i][p-1]>0)p--;
i++;
}
while(cin>>n){
for(int k=0;k<=maxn;k++){
if(f[n][k]!=0){
num=k;
break;
}
}
for(int k=num;k<=maxn;k++)printf("%d",f[n][k]);
puts("");
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[ZJOJ] 5772 [NOIP 2008 시 뮬 레이 션] 오늘 AK 했 어 요?AK: All kill "당신 은 왜 책 을 외우 지 않 았 습 니까?" "아니요, 저 는 그냥 책 을 외우 지 않 았 습 니 다." "...............................................
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
