看到网上有一道高精度问题，但是如果普通模拟只能拿60分，要压4位才能AC。但是压位我不会做，请高手指教

普通模拟：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int sum[10000]={0};
void rollback(char array[],int Len)//反转
{
char temp;
int i;
for(i=0;i<Len/2;i++)
temp=array[i],array[i]=array[Len-i-1],array[Len-i-1]=temp;
}
int amass(int a[],int b[],int a_length,int b_length)
{
int length=0,i,j,temp;
for(i=0;i<a_length;i++)
{
temp=0;
for(j=0;j<b_length;j++)
{
temp=a[i]*b[j]+temp/10+sum[i+j];
sum[i+j]=temp;
}
sum[i+j]=temp/10;
}
length=i+j;
return length;
}
int main()
{
int A[1000]={0},B[1000]={0};
int a_length,b_length,i,length=0;
char a[1000],b[1000];
gets(a),gets(b);
a_length=strlen(a);b_length=strlen(b);
rollback(a,a_length),rollback(b,b_length);
for(i=0;i<a_length;i++)
A[i]=a[i]-'0';
for(i=0;i<b_length;i++)
B[i]=b[i]-'0';
length=amass(A,B,a_length,b_length);
while(sum[length]==0&&length>0)
length--;
for(i=length;i>=0;i--)
printf("%d",sum[i]);
system("pause");
return 0;
}

我是说压位的预处理有点难度

顶

看了卧龙写的高精度乘法优化,模仿自己写了一个且测试通过,待会儿我会发上来.

[ 本帖最后由 sunyh1999 于 2011-2-22 10:47 编辑 ]

您没有理解我意思,我的意思是:如果一个0-9的数占一个int的空间,不仅浪费空间而且运算速度慢.如果将一个int存入一个四位数,就会不浪费空间且速度加快4倍

CODE:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int a[1000],b[1000],sum[1000]={0}; /*开大几位,避免越界*/
int flag=0;
int dismember(char array[],int length)
{
int i,j,t;
if(length%4)
{
t=4-length%4;
for(i=t+length-1;i>=t;i--)
array[i]=array[i-t];
length+=t;
for(i=0;i<t;i++) array[i]='0';
}
for(i=0,j=0;i<length;i+=4,j++)
{
if(flag==0)
a[j]=(array[i]-'0')*1000+(array[i+1]-'0')*100+(array[i+2]-'0')*10+array[i+3]-'0';
if(flag==1)
b[j]=(array[i]-'0')*1000+(array[i+1]-'0')*100+(array[i+2]-'0')*10+array[i+3]-'0';
}
length=j;
flag=1;
return length;
}
int main()
{
int i,j,t;
int a_length,b_length;
char temp[1000];
gets(temp);
a_length=strlen(temp);
a_length=dismember(temp,a_length);
gets(temp);
b_length=strlen(temp);
b_length=dismember(temp,b_length);
for(i=a_length-1;i>=0;i--)
for(j=b_length-1;j>=0;j--)
{
t=i+j; /*临时计算,最多减少7500次计算*/
sum[t]+=a[i]*b[j];
sum[t-1]+=sum[t]/10000; /*使用万进制,计算速度加快4倍*/
sum[t]=sum[t]%10000; /*使用万进制,计算速度加快4倍*/
}
while(!sum[i]) i++;
printf("%d",sum[i]);
i++;
for(;i<a_length+b_length-1;i++)
if(sum[i]>1000) printf("%d",sum[i]);
else
if(sum[i]>100) printf("0%d",sum[i]);
else
if(sum[i]>10) printf("00%d",sum[i]);
else
printf("000%d",sum[i]);
system("pause");
return 0;
}