acm.rar_高精度算法

高 精 度 算 法 #include <stdio.h> #include <string.h> #include <math.h> #include <malloc.h> int an,bn,fa=1,fb=1; /* 把an,bn,k设为全局变量,an纪录第一个高精度数组的位数,bn纪录第二个高精度数组的位数,k纪录输出结果的位数*/ char b1[250], b2[250]; /*纪录需要计算的两个高精度数据 */ void input(int a1[],int a2[]) /*函数input为输入函数,用来纪录两个待计算的高精度数据,以数组首地址为参数.以实现返回两个高精度数据*/ { int i,ai=1,bi=1; scanf ( "%s%s", b1, b2 ); /*输入两个高精度数据 */ an = strlen( b1 ); /*an纪录b1的位数 */ bn = strlen( b2 ); /*bn纪录b2的位数 */ if(b1[0]==45) { an--; fa=-1;ai=0;} /*判断数组的符号 */ if(b2[0]==45) { bn--; fb=-1;bi=0;} for (i=0; i<an; i++,ai++) {a1[i]=b1[an-ai]-'0'; printf("%d",a1[i]);} /*把字符形数据b1转为整数形数据,同样用数组纪录 */ for (i=0; i<bn; i++,bi++) a2[i]=b2[bn-bi]-'0'; /* 同上 */ return; } void addition(int a[],int b[],int q) /*高精度加法运算*/ { int i,c[251]={0},k; if(fa*fb>0||q) { if(an>bn) k=an; else k=bn; /*用k纪录结果的最小位数*/ for(i=0;i<k;i++) { c[i]=a[i]+b[i]+c[i]; c[i+1]=(int)c[i]/10; c[i]=(int)c[i]%10; } /*高精度加法运算过程*/ if(c[k]) k++; /*判断最后结果的位数*/ if(fa<0&&q||fa<0) printf("-"); for(i=k-1;i>=0;i--) printf("%d",c[i]); /*输出结果*/ return; } else subtraction(a,b,1); return; } subtraction(int a[],int b[],int q) /*高精度减法运算*/ { int i,f=0,c[251]={0},k; if(fa*fb>0||q) { if(an>bn) k=an; else /*用k纪录结果的最大位数*/ { k=bn; for(i=k;a[i]<=b[i]&&i>=0;i--) if(a[i]<b[i]) f=1; /*f纪录结果符号*/ } if(!f) /*高精度减法运算过程*/ for(i=0;i<k;i++) { if(a[i]<b[i]) { a[i+1]--; a[i]+=10; } c[i]=a[i]-b[i]; } else /*当a<b时的处理*/ for(i=0;i<k;i++) { if(b[i]<a[i]) { b[i+1]--; b[i]+=10; } c[i]=b[i]-a[i]; } while(!c[k-1]&&k>1) k--; /*判断最后结果的位数*/ if(q&&(fa>0&&f||fa<0&&!f)||fa>0&&(fb>0&&!f||f&&!q)) printf("-"); /*如果f为真是输出负号*/ for(i=k-1;i>=0;i--) printf("%d",c[i]); return; } else addition(a,b,1); } void multiplication( int a[], int b[]) /*高精度乘法运算*/ { int i, j, c[501] = {0},k; k = an + bn - 1; /*用k纪录结果的最大位数*/ for(i = 0; i < an; i++) /*高精度乘法运算过程*/ for(j = 0;j < bn; j++) { c[i+j] = a[i] * b[j] + c[i+j]; c[i+j+1] = c[i+j] / 10 + c[i+j+1]; c[i+j] = c[i+j] % 10; } while(!c[k]) k--; /*判断最后结果的位数*/ if(fa*fb<0) printf("-"); for(i = k; i >= 0; i--) printf("%d",c[i]); /*输出结果*/ } main() { int a[250]={0},b[250]={0}; input(a,b); printf("\n%s+%s=",b1,b2);addition(a,b,0); printf("\n%s-%s=",b1,b2);subtraction(a,b,0); printf("\n%s*%s=",b1,b2);multiplication(a,b); getch(); } 1、 高精度除以低精度； 算法：按照从高位到低位的顺序，逐位相除。在除到第j位时，该位在接受了来自第j+1位的余数后与除数相除，如果最高位为零，则商的长度减一。源程序如下： #include <stdio.h> #define N 500 main() { int a[N] = {0}, c[N] = {0}; int i, k, d, b; char a1[N]; printf("Input 除数:"); scanf("%d", &b); printf("Input 被除数:"); scanf("%s", a1); k = strlen(a1); for(i = 0; i < k; i++) a[i] = a1[k - i - 1] - '0'; d = 0; for(i = k - 1; i >= 0 ; i--) { d = d * 10 + a[i]; c[i] = d / b; d = d % b; } while(c[k - 1] == 0 && k > 1) k--; printf("商="); for(i = k - 1; i >= 0; i--) printf("%d", c[i]); printf("\n余数=%d", d); } 2、高精度乘以高精度（要求用尽可能少的存储单元）； 算法：用数组保存两个高精度数，然后逐位相乘，注意考虑进位和总位数。源程序如下： #include <stdio.h> main() { int a[240] = {0}, b[240] = {0}, c[480] = {0}; int i, j, ka, kb, k; char a1[240], b1[240]; gets(a1); ka = strlen(a1); gets(b1); kb = strlen(b1); k = ka + kb; for(i = 0; i < ka; i++) a[i] = a1[ka-i-1] - '0'; for(i = 0; i < kb; i++) b[i] = b1[kb-i-1] - '0'; for(i = 0; i < ka; i++) for(j = 0; j < kb; j++) { c[i + j] = c[i + j] + a[i] * b[j]; c[i + j +1] = c[i + j +1] + c[i + j]/10; c[i + j] = c[i + j] % 10; } if(!c[k]) k--; for(i = k-1; i >= 0; i--) printf("%d", c[i]); } 3、高精度除以高精度（要求用尽可能少的存储单元）； 算法：用计算机模拟手算除法，把除法试商转化为连减。 #include <stdio.h> #define N 500 int bj(int a[], int b[], int k1, int k2) /*比较大小函数*/ { int i, t, flag; /*flag作标志位*/ if(k1 < k2) flag = 0; /*被除数小于除数返回0*/ else if(k1 > k2) flag = 1; /*被除数大于除数返回1*/ else { /*被除数和除数位数相等则逐位进行比较*/ i = k1; t = 0; while(t == 0 && i > 0) { if(a[i] > b[i]) {t = 1; flag = 1;} else if(a[i] == b[i]) i--; else {t = 1; flag = 0;} } if(i == 0 && t == 0) flag = 2; /*被除数等于除数返回2*/ } return flag; } int jf(int a[], int b[], int k1, int k2) /*减法运算*/ { int i, k, d[N]; for(i = 0; i < k2; i++) d[i] = b[i]; /*把除数赋给数组d*/ for(i = k2; i < N; i++) d[i] = 0; /*d数组无数据的高位置0*/ k = k1 - k2 - 1; /*计算减法起始位置*/ if(k < 0) k = 0; if(k > 0) { for(i = k2 - 1; i >= 0; i--) d[i + k] = d[i]; /*移动减数位数与被减数对齐*/ for(i = 0; i < k; i++) d[i] = 0; /*移动后的其余位置0*/ } for(i = 0; i < k1; i++) { if(a[i] >= d[i]) a[i] -= d[i]; else { a[i + 1] = a[i + 1] - 1; a[i] = 10 + a[i] - d[i]; } } return k; } main() { int a[N] = {0}, b[N] = {0}, c[N] = {0}, d[N] = {0}; int i, ka, kb, m, t, t1, t2, k, x, kd, kk; char a1[N], b1[N]; printf("Input 被除数:"); scanf("%s", a1); ka = strlen(a1); for(i = 0; i < ka; i++) a[i] = a1[ka - i -1] - '0'; printf("Input 除数:"); scanf("%s", b1); kb = strlen(b1); for(i = 0; i < kb; i++) b[i] = b1[kb - i -1] - '0'; kd = ka; /*保存被除数位数 */ t2 = bj(a, b, ka, kb); m = 0; do { while(a[ka - 1] == 0) ka--; t = bj(a, b, ka, kb); if(t >= 1) { k = jf(a, b, ka, kb); c[k]++; if(k > m) m = k; t1 = 0; for(i = k; i <= m; i++) { x = c[i] + t1; c[i] = x % 10; t1 = x / 10; } if(t1 > 0) {m++; c[m] = t1; } } }while(t == 1); if(t2 == 0) { printf("商=0"); printf("\n余数="); for(i = kd - 1; i >= 0; i--) printf("%d", a[i]); exit(1); } if(t2 == 2) { printf("商 = 1"); printf("\n余数 = 0"); exit(1); } kk = kd; while(!c[kd - 1]) kd--; printf("商 = "); for(i