TZOJ--1247: Hat's Fibonacci（大数）

发布时间：2020-12-14 04:28:51 所属栏目：大数据来源：网络整理

导读：1247: Hat‘s Fibonacci ? 时间限制(普通/Java):1000MS/10000MS ? ? 内存限制:32768KByte 描述 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

1247: Hat‘s Fibonacci?

时间限制(普通/Java):1000MS/10000MS ? ? 内存限制:32768KByte

描述

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.

输入

Each line will contain an integers. Process to end of file.

输出

For each case,output the result in a line.

Note：

No generated Fibonacci number in excess of 2005 digits will be in the test data,ie. F(20) = 66526 has 5 digits.

样例输入

?100

样例输出

?4203968145672990846840663646

题目来源

HDOJ

题目链接：http://tzcoder.cn/acmhome/problemdetail.do?&method=showdetail&id=1247

题目大意：F(1) = 1,F(n>4) = F(n - 1) + F(n-2) + F(n-3) + F(n-4)，根据这个公式计算F(n)

数据保证了输出最多不超过2005位，但我自己人懒不想打表估计2005位的需要开多大的数组，所以用了一个滑动的数组进行计算

f[i%4] = f[(i-1)%4]+f[(i-2)%4]+f[(i-3)%4]+f[(i-4)%4]

JAVA代码：

?import java.io.*;
import java.util.*;
import java.math.*;
public class Main
{ 
    public static void main(String args[]) throws Exception 
    { 
        Scanner cin=new Scanner(System.in); 
        BigInteger f[] = new BigInteger[10];
        f[3]=f[2]=f[1]=f[0]=BigInteger.ONE;
        while(cin.hasNext())
        {
        	int a=cin.nextInt();
        	f[3]=f[2]=f[1]=f[0]=BigInteger.ONE;
        	for(int i=4;i<a;i++)
        	{
        		f[(i)%4]=f[(i-1)%4].add(f[(i-2)%4].add(f[(i-3)%4].add(f[(i-4)%4])));
        	}
        	System.out.println(f[(a-1)%4]);
        }
    }
}

?

PYthon代码：

while True:
	try:
		n = int(input())
		f = [1,1,1]
		for i in range(4,n+1) :
		    f[i%4] = f[i%4]+f[(i-1)%4]+f[(i-2)%4]+f[(i-3)%4]
		print(f[(n-1)%4])
		
	except EOFError:
		break

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

TZOJ--1247: Hat&#39;s Fibonacci（大数）

1247: Hat‘s Fibonacci?

TZOJ--1247: Hat's Fibonacci（大数）