Hat's Fibonacci
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2208 Accepted Submission(s): 684
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.
Input
Each line will contain an integers. Process to end of file.
Output
For each case, output the result in a line.
Sample Input
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.
/*
Mail to : miyubai@gamil.com
MyBlog : baiyun.me
Link : http://www.cnblogs.com/MiYu || http://www.shnenglu.com/MiYu
Author By : MiYu
Test : 1
Complier : g++ mingw32-3.4.2
Program : Hat's Fibonacci
Doc Name : HDU_1250
*/
/*
高精度的水題 , JAVA 水過(guò), 當(dāng)然 用模板也一樣
*/
package main;
import java.util.*;
import java.math.*;
import java.io.*;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner ( System.in );
while ( cin.hasNext() ) {
int N = cin.nextInt();
if ( N <= 4 ) {
System.out.println ( 1 );
} else {
BigInteger one = new BigInteger ( "1" );
BigInteger two = new BigInteger ( "1" );
BigInteger three = new BigInteger ( "1" );
BigInteger four = new BigInteger ( "1" );
BigInteger res = new BigInteger ( "1" );
BigInteger temp = new BigInteger ( "1" );
for ( int i = 4; i < N; ++ i ) {
res = one.add(two).add(three).add(four);
temp = res;
one= two;
two = three;
three = four;
four = temp;
}
System.out.println( res );
}
}
}
}