欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

hdu 1297 大数加法

程序员文章站 2024-01-12 19:42:16
...

/*
	这个代码对我自己来说,写的算是比较工整了(大牛勿BS);
	里面的函数可以当模板用
*/


#include <stdio.h>
#include <string.h>
char dpM[1100][1100],dpF[1100][1100]; 

void in_add(char s[], char max[],char min[])
{
	int l1=strlen(max);
	int l2=strlen(min);
	int yu=0,i;
	for(i=0;i<l2;i++)
	{
		s[i]=((yu + (min[i] - '1' + 1) + (max[i] - '1' + 1)) % 10) + '1' - 1;
		yu = ((yu + (min[i] - '1' + 1) + (max[i] - '1' + 1)) / 10);
	}
	for(i=l2;i<l1;i++)
	{
		s[i] = ((yu + max[i] - '1' + 1) % 10) + '1' - 1;
		yu = (( yu + max[i] - '1' + 1) / 10);
	}
	if(yu){
		s[l1] = yu + '1' - 1;
	}
}

void ADD(char s[] , char a[] , char b[])
{
	int l1=strlen(a);
	int l2=strlen(b);
	in_add( s, l1 >= l2 ? a : b, l1 < l2 ? a : b);
}

void Print( char max[], char min[])
{
	int l1=strlen(max);
	int l2=strlen(min);
	int s[1000];
	int yu=0,a,b,i;
	for(i=0;i<l2;i++)
	{
		s[i] = (yu + (min[i] - '1' + 1) + (max[i] - '1' + 1)) % 10;
		yu = (yu + (min[i] - '1' + 1) + (max[i] - '1' + 1)) / 10;
	}
	for(i=l2;i<l1;i++)
	{
		s[i] = ( yu + max[i] - '1' + 1) % 10;
		yu = ( yu + max[i] - '1' + 1) / 10;
	}
	if(yu) printf("%d",yu);
	for(i=l1-1;i>=0;i--)
	{
		printf("%d",s[i]);
	}
	printf("\n");
}
int main()
{
	int n;
	int i,l1,l2;
	strcpy( dpM[1] , "1");
	strcpy( dpF[1] , "0");
	strcpy( dpM[2] , "1");
	strcpy( dpF[2] , "1");
	
	for( i = 3; i <= 1000; i++)
	{
		ADD( dpM[i], dpF[i - 1], dpM[i - 1]);
		ADD( dpF[i], dpM[i - 2], dpF[i - 1]);
//		dpM[i] = dpF[i - 1] + dpM[i - 2];
//		dpF[i] = dpM[i - 1] + dpF[i - 1];
	}
	while(scanf("%d",&n)!=EOF)
	{
		l1=strlen(dpM[n]);
		l2=strlen(dpF[n]);
		Print( l1 >= l2 ? dpM[n] : dpF[n] , l1 < l2 ? dpM[n] : dpF[n]);
	}
	return 0;
}


转载于:https://www.cnblogs.com/cykun/archive/2010/12/20/1911290.html