Tommy的学术区

今天凌晨3：30，终于实现了我学习OI一来的一个夙愿：写高精度除法，并较好的实现了压位操作以及与之配套的输入输出操作。贴代码纪念一下：
1、无压位操作的
[code=cpp]
#include
#include

/*
大整数储存方式:
1、a[0]存位数
2、a[1]、a[2]……依次存个位、十位……（倒序，个位在a[1]对齐）

这样存的话，中间关于位置的计算全都不用带MAXL，个位对齐方便
*/

#define MAXL 500

void Hi_Add(int a[], int b[], int c[]);//加法
void Hi_Sub(int a[], int b[], int c[]);//减法
void Hi_Mul(int a[], int b[], int c[]);//乘法
void Hi_Div(int a[], int b[], int c[]);//除法，感觉还是不太容易直接调用Hi_Sub函数，所以给除法单独写了个Hi_Div_Sub减法函数
int Hi_Div_Cmp(int a[], int b[]);//供除法调用的比较函数
void Hi_Div_Sub(int a[], int b[]);//供除法调用的减法函数，指针很容易实现对位
void print(int a[]);//打印大整数
void swap(int *a, int *b);

int a[MAXL]={0},b[MAXL]={0},c[MAXL]={0};
char operater;

void init()//这是读入部分，把表达式拆开，格式和C++有点不一样，领会意思就行了
{
char ch;
int i;
while (scanf("%c",&ch),ch>='0'&&ch<='9') a[++a[0]]=ch-'0'; operater=ch; while (scanf("%c",&ch),ch>='0'&&ch<='9') b[++b[0]]=ch-'0'; for (i=1; i<=a[0]/2; i++) swap(a+i,a+a[0]+1-i); for (i=1; i<=b[0]/2; i++) swap(b+i,b+b[0]+1-i); } void doit() { print(a); printf("%c",operater); print(b); printf("="); switch (operater) { case '+': Hi_Add(a,b,c); print(c); printf("\n"); break; case '-': Hi_Sub(a,b,c); print(c); printf("\n"); break; case '*': Hi_Mul(a,b,c); print(c); printf("\n"); break; case '/': Hi_Div(a,b,c);//经过除法操作后，a数组剩下的刚好是余数（详见Hi_Div函数定义） print(c); printf("……");//顺便加个余数显示 print(a); printf("\n"); break; } } int main() { init(); doit(); return 0; } void Hi_Add(int a[], int b[], int c[]) { int i; memset(c,0,sizeof(c)); c[0]=a[0]>b[0] ? a[0]:b[0];//c位数初始化
for (i=1; i<=c[0]; i++) { c[i]+=a[i]+b[i]; c[i+1]+=c[i]/10; c[i]%=10; } if (c[c[0]+1]) c[0]++;//如最高位有进位 } void Hi_Sub(int a[], int b[], int c[]) { int i; memset(c,0,sizeof(c)); c[0]=a[0]; for (i=1; i<=c[0]; i++) { c[i]+=a[i]-b[i]; if (c[i]<0) { c[i]+=10; c[i+1]--; } } while (c[c[0]]==0&&c[0]>1) c[0]--;//去掉高位的0，注意，如果结果是0，个位的0要保留（位数至少为1，下同）
}

void Hi_Mul(int a[], int b[], int c[])
{
int i,j;
memset(c,0,sizeof(c));
c[0]=a[0]+b[0]-1;
for (i=1; i<=a[0]; i++) for (j=1; j<=b[0]; j++) { c[i+j-1]+=a[i]*b[j]; c[i+j]+=c[i+j-1]/10; c[i+j-1]%=10; } while (c[c[0]+1]!=0)//处理最高位后的进位 { c[0]++; c[c[0]+1]=c[c[0]]/10; c[c[0]]%=10; } while (c[c[0]]==0&&c[0]>1) c[0]--;//万一有个乘数是0的情况，位数会减少，去0
}

void Hi_Div(int a[], int b[], int c[])
{
int i;
memset(c,0,sizeof(c));
c[0]=a[0]-b[0]+1;//商最高位不超过a[0]-b[0]+1，c位数初始化一下
for (i=a[0]-b[0]+1; i>0; i--)
while (Hi_Div_Cmp(a+i-1,b)>=0)//用指针，对齐待减的部分和b的个位（联想竖式除法）
{ //其实可以完全不用为试除作乘法，在当前位一直减就可以了，直到减不动为止（时间效率理论上比乘法试除要高）
Hi_Div_Sub(a+i-1,b); //每对a减一次，就在c的对应位+1（a中不断地减去b的倍数，最后剩下的就是余数）
c[i]++;
}
while (c[c[0]]==0&&c[0]>1) c[0]--;
while (a[a[0]]==0&&a[0]>1) a[0]--;//剩下的a作为余数，化为标准大整数形式，以备输出
}

int Hi_Div_Cmp(int a[], int b[])//比较函数，看是否还能再做减法
{
int i;
for (i=b[0]+1; i>0; i--)
{
if (a[i]>b[i]) return 1;
if (a[i]<=b[0]; i++) { a[i]-=b[i]; if (a[i]<0) { a[i]+=10; a[i+1]--; } } } void print(int a[])//打印大整数 { int i; for (i=a[0]; i>0; i--) printf("%i",a[i]);
}

void swap(int *a, int *b)
{
int c;
c=*a;
*a=*b;
*b=c;
}
[/code]

2、经过压位操作的
[code=cpp]
//这是经过压位的大整数计算，比较一下，其实主过程和普通几乎一样
//不一样的地方：1、所有跟10进制有关的地方都改成UPPERBOUND控制（可以改成10,100,10000...），同时对应的位数DIGITS也要改
// 2、打印大整数部分会有些不同
// 3、读入时处理复杂一些
// 4、优点：加减乘运算减少运算次数，压位后空间利用率变高
// 5、缺点：读入和输出稍复杂，除法每次作差试除效率变低

#include
#include

/*
大整数储存方式:
1、a[0]存位数
2、a[1]、a[2]……依次存个位、十位……（倒序，个位在a[1]对齐）

这样存的话，中间关于位置的计算全都不用带MAXL，个位对齐方便
*/

#define MAXL 500
#define UPPERBOUND 10000
#define DIGITS 4

void Hi_Add(int a[], int b[], int c[]);//加法
void Hi_Sub(int a[], int b[], int c[]);//减法
void Hi_Mul(int a[], int b[], int c[]);//乘法
void Hi_Div(int a[], int b[], int c[]);//除法，感觉还是不太容易直接调用Hi_Sub函数，所以给除法单独写了个Hi_Div_Sub减法函数
int Hi_Div_Cmp(int a[], int b[]);//供除法调用的比较函数
void Hi_Div_Sub(int a[], int b[]);//供除法调用的减法函数，指针很容易实现对位
void print(int a[]);//打印大整数

int a[MAXL]={0},b[MAXL]={0},c[MAXL]={0};
char operater;

void init()//这是读入部分，把表达式拆开，格式和C++有点不一样，领会意思就行了。有兴趣可以认真读一下。
{
int temp[MAXL]={0},i,mask;
char ch;

while (scanf("%c",&ch),ch>='0'&&ch<='9') temp[++temp[0]]=ch-'0'; operater=ch; for (i=1; i<=temp[0]; i++) { if (i%DIGITS==1) mask=1; else mask*=10; a[(i+DIGITS-1)/DIGITS]=a[(i+DIGITS-1)/DIGITS]+=temp[temp[0]+1-i]*mask; } a[0]=(temp[0]+DIGITS-1)/DIGITS; memset(temp,0,sizeof(temp)); while (scanf("%c",&ch),ch>='0'&&ch<='9') temp[++temp[0]]=ch-'0'; for (i=1; i<=temp[0]; i++) { if (i%DIGITS==1) mask=1; else mask*=10; b[(i+DIGITS-1)/DIGITS]=b[(i+DIGITS-1)/DIGITS]+=temp[temp[0]+1-i]*mask; } b[0]=(temp[0]+DIGITS-1)/DIGITS; } void doit() { print(a); printf("%c",operater); print(b); printf("="); switch (operater) { case '+': Hi_Add(a,b,c); print(c); printf("\n"); break; case '-': Hi_Sub(a,b,c); print(c); printf("\n"); break; case '*': Hi_Mul(a,b,c); print(c); printf("\n"); break; case '/': Hi_Div(a,b,c);//经过除法操作后，a数组剩下的刚好是余数（详见Hi_Div函数定义） print(c); printf("……");//顺便加个余数显示 print(a); printf("\n"); break; } } int main() { init(); doit(); return 0; } void Hi_Add(int a[], int b[], int c[]) { int i; memset(c,0,sizeof(c)); c[0]=a[0]>b[0] ? a[0]:b[0];//c位数初始化
for (i=1; i<=c[0]; i++) { c[i]+=a[i]+b[i]; c[i+1]+=c[i]/UPPERBOUND; c[i]%=UPPERBOUND; } if (c[c[0]+1]) c[0]++;//如最高位有进位 } void Hi_Sub(int a[], int b[], int c[]) { int i; memset(c,0,sizeof(c)); c[0]=a[0]; for (i=1; i<=c[0]; i++) { c[i]+=a[i]-b[i]; if (c[i]<0) { c[i]+=UPPERBOUND; c[i+1]--; } } while (c[c[0]]==0&&c[0]>1) c[0]--;//去掉高位的0，注意，如果结果是0，个位的0要保留（位数至少为1，下同）
}

void Hi_Mul(int a[], int b[], int c[])
{
int i,j;
memset(c,0,sizeof(c));
c[0]=a[0]+b[0]-1;
for (i=1; i<=a[0]; i++) for (j=1; j<=b[0]; j++) { c[i+j-1]+=a[i]*b[j]; c[i+j]+=c[i+j-1]/UPPERBOUND; c[i+j-1]%=UPPERBOUND; } while (c[c[0]+1]!=0)//处理最高位后的进位 { c[0]++; c[c[0]+1]=c[c[0]]/UPPERBOUND; c[c[0]]%=UPPERBOUND; } while (c[c[0]]==0&&c[0]>1) c[0]--;//万一有个乘数是0的情况，位数会减少，去0
}

void Hi_Div(int a[], int b[], int c[])
{
int i;
memset(c,0,sizeof(c));
c[0]=a[0]-b[0]+1;//商最高位不超过a[0]-b[0]+1，c位数初始化一下
for (i=a[0]-b[0]+1; i>0; i--)
while (Hi_Div_Cmp(a+i-1,b)>=0)//用指针，对齐待减的部分和b的个位（联想竖式除法）
{ //其实可以完全不用为试除作乘法，在当前位一直减就可以了，直到减不动为止（时间效率理论上比乘法试除要高）
Hi_Div_Sub(a+i-1,b); //每对a减一次，就在c的对应位+1（a中不断地减去b的倍数，最后剩下的就是余数）
c[i]++;
}
while (c[c[0]]==0&&c[0]>1) c[0]--;
while (a[a[0]]==0&&a[0]>1) a[0]--;//剩下的a作为余数，化为标准大整数形式，以备输出
}

int Hi_Div_Cmp(int a[], int b[])//比较函数，看是否还能再做减法
{
int i;
for (i=b[0]+1; i>0; i--)
{
if (a[i]>b[i]) return 1;
if (a[i]<=b[0]; i++) { a[i]-=b[i]; if (a[i]<0) { a[i]+=UPPERBOUND; a[i+1]--; } } } void print(int a[])//打印大整数 { int i,mask=UPPERBOUND/10,x; for (i=a[0]; i>0; i--)
if (i==a[0]) printf("%i",a[i]);
else //中间部分高位出现0，必须用0补齐
{
x=a[i];
while (mask>0)
{
printf("%i",x/mask);
x%=mask;
mask/=10;
}
}
}
[/code]