HDU (1250 Hat's Fibonacci 高精度递加)

spoiler posted @ 2011年4月21日 01:21 in 高精度相关计算 , 2061 阅读

题目的意思:就是说s[1]=1,s[2]=1,s[3]=1,s[4]=1; 其他的都用统一方程求 s [ n ]=  s[n-1 ] +s [n -2 ] + s[ n-3 ] +s [ n-4];

题目分析:

其实没什么算法,就是用二维数组里的每一行 模拟每个一个大数,这一行里的第一个数就是 实际意义上的一个 “ 位 ”! 可以是以8位为一个“位”

也可以以其他位数为一“ 位 ”,这样做是为了压缩内存,也是位了能够高效模拟! 其他的跟我们 普通的加法是一样的!从左往右,把前面四行的对应的列上的值都加到 我这行的对应的列上来! 最后一个循环考虑一下,进位之类的  所以您别 一看就慌了 毕竟每个人都是由 不会到会的  如果有不懂的 您可以密我 我更详细的跟您解说{^ _ ^}

代码如下:

#include<iostream>
#include<cstring>
#include<cstdio>
int s[10000][356]={0};
using namespace std;
int solve(){
	int i,j;
	s[1][1]=1;
	s[2][1]=1;
	s[3][1]=1;
	s[4][1]=1;
	for(i=5;i<10000;i++){
		for(j=1;j<=350;j++)
			s[i][j]+=s[i-1][j]+s[i-2][j]+s[i-3][j]+s[i-4][j];//记得这里别把j跟I弄混淆了,我第一次为这个小错误
            //找了点时间,嘿嘿
		for(j=1;j<=350;j++){
			if(s[i][j]>100000000){
				s[i][j+1]+=s[i][j]/100000000;
				s[i][j]=s[i][j]%100000000;
			}	
		}		
	}
	return 0;
}
int main(){
	int cas,i,j,n;
	solve();
	while(scanf("%d",&n)!=EOF){
		for(i=350;i>=1;i--){
			if(s[n][i]!=0)
				break;
		}
		printf("%d",s[n][i]);
		for(j=i-1;j>=1;j--)
			printf("%08d",s[n][j]);
		printf("\n");
	}
	return 0;
}

 

Avatar_small
Taro 说:
2011年4月22日 04:34

保存了9999个数……不过为什么要弄356位呢?实际上用349位……有点浪费……想不懂,只是为了356天-=?

那个cas是跑龙套的么?

Avatar_small
hello kity 说:
2011年4月24日 01:09

@Taro: 其实面对OJ 开大点放心点 免得浪费了WA

Avatar_small
comathlish 说:
2011年4月27日 02:26

该省则不必省,不该则更不能省,内存无穷溃也,何患一点小意思,变量用不用也多定义些,让它们出来见见市面~

Avatar_small
Taro 说:
2011年4月27日 03:26

@comathlish: 呃,我非OIer……见笑了


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter