算法竞赛--高精度加法

1.高精度加法

输入两个整数a和b，输出这两个整数的和。a和b都不超过100位

算法描述

由于a和b都比较大，所以不能直接使用语言中的标准数据类型来存储。对于这种问题，一般使用数组来处理。

定义一个数组A，A[0]用于存储a的个位，A[1]用于存储a的十位，依此类推。同样可以用一个数组B来存储b。

计算c = a + b的时候，首先将A[0]与B[0]相加，如果有进位产生，则把进位（即和的十位数）存入r，把和的个位数存入C[0]，即C[0]等于(A[0]+B[0])%10。然后计算A[1]与B[1]相加，这时还应将低位进上来的值r也加起来，即C[1]应该是A[1]、B[1]和r三个数的和．如果又有进位产生，则仍可将新的进位存入到r中，和的个位存到C[1]中。依此类推，即可求出C的所有位。

最后将C输出即可。

输入格式:

输入包括两行，第一行为一个非负整数a，第二行为一个非负整数b。两个整数都不超过100位，两数的最高位都不是0。

输出格式:

输出一行，表示a + b的值。

样例输入:

1 2	20100122201001221234567890 2010012220100122

样例输出:

1	20100122203011233454668012

代码:

#include <stdio.h>
#include <string.h>
char a[200],b[200];
int x[200],y[200],sum[200];
int main()
{
	scanf("%s",a);				//用字符数组接收两个非负整数
	scanf("%s",b);
	for(int i=0;i<strlen(a);i++)//从个位数起将各位数存储到数组中
		x[i]=a[strlen(a)-i-1]-'0';
	for(int i=0;i<strlen(b);i++)
		y[i]=b[strlen(b)-i-1]-'0';
	int len=strlen(a)>strlen(b)?strlen(a):strlen(b),s,temp=0;
	for(int i=0;i<len;i++)//将对应位置数字相加，并存储到sum数组中，若该数大于10，向高位进1
	{
		s=x[i]+y[i];
		if(s+temp>=10)
		{
			sum[i]=(s+temp)%10;
			temp=1;
		}
		else
		{
			sum[i]=s+temp;
			temp=0;
		}
	}					
	if(temp==1)			//数字处理完，若仍有进位，则最高为1，并存储在sum数组最高位
	{
		sum[len]=1;
		len++;
	}
	for(int i=len-1;i>=0;i--)//逆序输出该数字
		printf("%d",sum[i]);
	return 0;
}

2.回文数(该题将回文数与高精度加法相结合)

若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。

例如：给定一个10进制数56，将56加65（即把56从右向左读），得到121是一个回文数。

又如：对于10进制数87：

STEP1：87+78 = 165

STEP2：165+561 = 726

STEP3：726+627 = 1353

STEP4：1353+3531 = 4884

在这里的一步是指进行了一次N进制的加法，上例最少用了4步得到回文数4884。

写一个程序，给定一个N（2< =N< =10或N=16）进制数M（其中16进制数字为0-9与A-F），求最少经过几步可以得到回文数。

如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible!”

输入格式:

两行，N与M 100位，两数的最高位都不是0。

输出格式:

如果能在30步以内得到回文数，输出“STEP=xx”（不含引号），其中xx是步数；否则输出一行”Impossible!”（不含引号）

样例输入:

1
2

9 
87

样例输出:

STEP=6

代码:

#include <stdio.h>
#include <string.h>
char c[100];
int a[100],b[100];
int main()
{
	int n,count=0;
	scanf("%d",&n);
	scanf("%s",c);
	int len=strlen(c);
	for(int i=0;i<len;i++)
	{
		if(c[i]>='A')
			a[i]=c[i]-'7';
		else
			a[i]=c[i]-'0';
	}
    while(1)
    {
    	int flag=0,i;
		for(i=0;i<len;i++)
			b[i]=a[i]+a[len-i-1];
		for(i=0;i<len;i++)      //该处进行相加时，和高精度加法相同，逐步求和，大于n,则高位进1.
		{
			int temp=b[i];
			b[i]=(temp+flag)%n;
			if((flag+temp)>=n)
				flag=1;
			else
				flag=0;
			a[i]=b[i];
		}
		if(flag==1)
		{
			a[len]=b[len]=1;
			len++; 
		}	
		count++;
		int fa=1;
		for(int i=0;i<len/2;i++)
			if(b[i]!=b[len-i-1])
			{
				fa=0;
				break;
			}
		if(fa&&count<30)
		{
			printf("STEP=%d\n",count);
			break;
		}
		if(count>=30)
		{
			printf("Impossible!");
			break;
		}
	}
    return 0;
}