HDU 1250Hat's Fibonacci(两种方法处理大数)
发布时间：2020-12-14 04:02:00 所属栏目：大数据 来源：网络整理
导读：Hat's Fibonacci Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 5891????Accepted Submission(s): 1944 Problem Description A Fibonacci sequence is calculated by adding the previous two
Hat's FibonacciTime Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 5891????Accepted Submission(s): 1944
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
?
? ? ? ? ? ? ? ? ?
?题目大意：题目的意思就不说了，主要是简单地处理大数。
? ? ? ? ? ? 解题思路：先是用C++写的处理大数，每次只涉及到两个数相加，直接转换成string，所以位数就取len较大的那位。如果第一位超过了10则直接再最前面加一个1，第一位减去10，string支持直接用"1"+。详见代码。
? ? ? ? ? ? 题目地址：Hat's Fibonacci
C++代码：
#include<iostream>
#include<string>
using namespace std;
string add(string s1,string s2)
{
int j,l,la,lb;
string ma,mi;
ma=s1;mi=s2;
if(s1.length()<s2.length())
{ma=s2;mi=s1;}
la=ma.size();lb=mi.size();
l=la-1;
for(j=lb-1;j>=0;j--,l--)
ma[l] += mi[j]-'0';
for(j=la-1;j>=1;j--)
if(ma[j]>'9')
{ma[j]-=10;ma[j-1]++;}
if(ma[0]>'9') //处理第一位超过9了。
{ma[0]-=10;ma='1'+ma;}
return ma;
}
int main(){
int n,i;
string a[8008];
a[1]="1";
a[2]="1";
a[3]="1";
a[4]="1";
for(i=5;i<8008;++i)
a[i]=add(add(add(a[i-1],a[i-2]),a[i-3]),a[i-4]);
while(cin>>n)
cout<<a[n]<<endl;
return 0;
}
? ? ? ? ? 以后遇到大数的问题，不用那么坑爹的再敲该死的那么长的模板了，直接上JAVA。
JAVA代码：
import java.util.*;
import java.math.*;
public class Main {
public static void main(String args[])
{
Scanner cin = new Scanner(System.in);
BigInteger res[];
res = new BigInteger[8008];
res[1]=BigInteger.ONE;
res[2]=BigInteger.ONE;
res[3]=BigInteger.ONE;
res[4]=BigInteger.ONE;
for(int i=5;i<=8000;i++)
{
res[i]=res[i-1].add(res[i-2]);
res[i]=res[i].add(res[i-3]);
res[i]=res[i].add(res[i-4]);
}
int p;
while(cin.hasNext())
{
p=cin.nextInt();
System.out.println(res[p]);
}
}
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |