hdoj 1250 Hat's Fibonacci 【高精度】

Fibonacci。。。

策略：用Java 做这道题较简单一些，但是，C语言是基础。

用java的话，就是最简单的BigInteger的使用。

下面简单讲一下C语言的做法：

一个12位的整数，可以表示为，3个四位的整数的集合，例如123412341234就可以转化为1234， 1234， 1234。下面的就是按照此原理做的。

c代码：

#include <stdio.h>//每一个int都代表6个数。
#include <string.h>
#define M 10000  
int a[M][450];
void table(){
    int i,j;
    memset(a,sizeof(a));
    a[1][0] = a[2][0] = a[3][0] = a[4][0] = 1;
    for(i = 5; i < M; i ++){
        for(j = 0; j < 450; j ++) 
            a[i][j] = a[i-1][j]+a[i-2][j]+a[i-3][j]+a[i-4][j];
        for(j = 0; j < 449; j ++){
            if(a[i][j] >= 1000000){
                int temp = a[i][j]/1000000;
                a[i][j] %= 1000000;
                a[i][j+1] += temp;
            }
        }
    }
}
int main(){
    table();
    int i,n;
    while(scanf("%d",&n) == 1){
        i = 449;
        while(a[n][i] == 0) i--;
        printf("%d",a[n][i]);
        while(-- i >= 0 ){
            printf("%06d",a[n][i]);//这里输出的时候，不足六位的时候要用0补上
        }
        puts("");
    }
    return 0;
}

java代码：

import java.util.Scanner;
import java.math.*;

public class Main{
    
    public static void main(String[] args){
        Scanner cin = new Scanner(System.in);
        BigInteger[] s = new BigInteger[20005];
        s[1] = new BigInteger("1");
        s[2] = s[3] = s[4]= s[1];
        int i;
        for(i = 5; i < 20005; i ++){
            s[i] = s[i-1].add(s[i-2]).add(s[i-3]).add(s[i-4]);
        }
        int n;
        while(cin.hasNextInt()){
            n = cin.nextInt();
            System.out.println(s[n]);
        }
    }
}

题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=1250