算法竞赛--高精度(一)

大整数的存储及初始化

复制

����

struct big
{
	int N[1010];
	int len;
	big()
	{
		memset(N,0,1010);
		len=0;
	}
};

复制

大整数的读取转换

复制

����

big change(char c[])//大整数以字符串的形式读取，然后进行转换
{
	big a;
	a.len=strlen(c); 
	for(int i=0;i<a.len;i++)
		a.N[i]=c[a.len-i-1]-'0';
	return a;
}

复制

1.实现一个加法器，使其能够输出a+b的值。

输入信息:

输入包括两个数a和b，其中a和b的位数不超过1000位。

输出信息:

可能有多组测试数据，对于每组数据，输出a+b的值。

样例输入:

复制

����

6 8
2000000000 30000000000000000000

复制

样例输出:

复制

����

14
30000000002000000000

复制

代码如下:

复制

����

#include <bits/stdc++.h>
using namespace std;
struct big
{
	int N[1010];
	int len;
	big()
	{
		memset(N,0,1010);
		len=0;
	}
};
big change(char c[])
{
	big a;
	a.len=strlen(c); 
	for(int i=0;i<a.len;i++)
		a.N[i]=c[a.len-i-1]-'0';
	return a;
}
big add(big x,big y)
{
	big z;
	int l=x.len>y.len?x.len:y.len;
	int flag=0;
	for(int i=0;i<l;i++)
	{
		z.N[i]=(x.N[i]+y.N[i]+flag)%10;
		flag=(x.N[i]+y.N[i]+flag)/10;
	}
	if(flag)
		z.N[l++]=flag;
	z.len=l;
	return z;
}
int main()
{
	big x,y,z;
	char a[1010],b[1010];
	while(scanf("%s%s",a,b)==2)
	{
		x=change(a);
		y=change(b);
		z=add(x,y);
		for(int i=z.len-1;i>=0;i--)
			printf("%d",z.N[i]);
		printf("\n");
	}
	return 0;
}

复制

2.大整数排序

对N个长度最长可达到1000的数进行排序。

输入信息:

输入第一行为一个整数N，(1<=N<=100)。接下来的N行每行有一个数，数的长度范围为1<=len<=1000。每个数都是一个正数，并且保证不包含前缀零。

输出信息:

可能有多组测试数据，对于每组数据，将给出的N个数从小到大进行排序，输出排序后的结果，每个数占一行。

样例输入:

复制

����

4
123
1234
12345
2345

复制

样例输出:

复制

����

123
1234
2345
12345

复制

代码如下:

复制

����

#include<bits/stdc++.h>
using namespace std;
struct big
{
	char N[1010];
	int len;
	big()
	{
		memset(N,0,1010);
		len=0;
	}
}B[105];
bool cmp(big a,big b)
{
	if(a.len!=b.len)
		return a.len<b.len;
	else
	{
		for(int i=0;i<a.len;i++)
			if(a.N[i]!=b.N[i])
				return a.N[i]<b.N[i];
	} 
}
int main()
{
	int n;
	while(scanf("%d",&n)==1)
	{
		for(int i=0;i<n;i++)
		{
			scanf("%s",B[i].N);
			B[i].len=strlen(B[i].N);
		}
		sort(B,B+n,cmp);
		for(int i=0;i<n;i++)
		{
			printf("%s",B[i].N);
			if(i==n-1)
				printf("\n");
			else
				printf(" ");
		}
	}
	return 0;
}

复制