首页 > 代码库 > hdoj 1250 Hat's Fibonacci 【高精度】
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, 0, 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
hdoj 1250 Hat's Fibonacci 【高精度】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。