高精度算法文库.doc

高 精 度 算 法#include #include #include #include int an,bn,fa=1,fb=1; /* 把an,bn,k设为全局变量,an纪录第一个高精度数组的位数,bn纪录第二个高精度数组的位数,k纪录输出结果的位数*/char b1250, b2250; /*纪录需要计算的两个高精度数据 */-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(b10=45) an-; fa=-1;ai=0; /*判断数组的符号 */ if(b20=45) bn-; fb=-1;bi=0; for (i=0; ian; i+,ai+) a1i=b1an-ai-0; printf(%d,a1i); /*把字符形数据b1转为整数形数据,同样用数组纪录 */ for (i=0; i0|q) if(anbn) k=an; else k=bn; /*用k纪录结果的最小位数*/ for(i=0;ik;i+) ci=ai+bi+ci; ci+1=(int)ci/10; ci=(int)ci%10; /*高精度加法运算过程*/ if(ck) k+; /*判断最后结果的位数*/ if(fa0&q|fa=0;i-) printf(%d,ci); /*输出结果*/ return; else subtraction(a,b,1); return;-subtraction(int a,int b,int q) /*高精度减法运算*/ int i,f=0,c251=0,k; if(fa*fb0|q) if(anbn) k=an; else /*用k纪录结果的最大位数*/ k=bn; for(i=k;ai=0;i-) if(aibi) f=1; /*f纪录结果符号*/ if(!f) /*高精度减法运算过程*/ for(i=0;ik;i+) if(aibi) ai+1-; ai+=10; ci=ai-bi; else /*当ab时的处理*/ for(i=0;ik;i+) if(bi1) k-; /*判断最后结果的位数*/ if(q&(fa0&f|fa0&(fb0&!f|f&!q) printf(-); /*如果f为真是输出负号*/ for(i=k-1;i=0;i-) printf(%d,ci); return; else addition(a,b,1);-void multiplication( int a, int b) /*高精度乘法运算*/ int i, j, c501 = 0,k; k = an + bn - 1; /*用k纪录结果的最大位数*/ for(i = 0; i an; i+) /*高精度乘法运算过程*/ for(j = 0;j bn; j+) ci+j = ai * bj + ci+j; ci+j+1 = ci+j / 10 + ci+j+1; ci+j = ci+j % 10; while(!ck) k-; /*判断最后结果的位数*/ if(fa*fb= 0; i-) printf(%d,ci); /*输出结果*/main() int a250=0,b250=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 #define N 500 main() int aN = 0, cN = 0; int i, k, d, b; char a1N; printf(Input 除数:); scanf(%d, &b); printf(Input 被除数:); scanf(%s, a1); k = strlen(a1); for(i = 0; i = 0 ; i-) d = d * 10 + ai; ci = d / b; d = d % b; while(ck - 1 = 0 & k 1) k-; printf(商=); for(i = k - 1; i = 0; i-) printf(%d, ci); printf(n余数=%d, d); -2、高精度乘以高精度（要求用尽可能少的存储单元）； 算法：用数组保存两个高精度数，然后逐位相乘，注意考虑进位和总位数。源程序如下： #include main() int a240 = 0, b240 = 0, c480 = 0; int i, j, ka, kb, k; char a1240, b1240; gets(a1); ka = strlen(a1); gets(b1); kb = strlen(b1); k = ka + kb; for(i = 0; i ka; i+) ai = a1ka-i-1 - 0; for(i = 0; i kb; i+) bi = b1kb-i-1 - 0; for(i = 0; i ka; i+) for(j = 0; j = 0; i-) printf(%d, ci); -3、高精度除以高精度（要求用尽可能少的存储单元）； 算法：用计算机模拟手算除法，把除法试商转化为连减。 #include #define N 500 int bj(int a, int b, int k1, int k2) /*比较大小函数*/ int i, t, flag; /*flag作标志位*/ if(k1 k2) flag = 1; /*被除数大于除数返回1*/ else /*被除数和除数位数相等则逐位进行比较*/ i = k1; t = 0; while(t = 0 & i 0) if(ai bi) t = 1; flag = 1; else if(ai = bi) 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, dN; for(i = 0; i k2; i+) di = bi; /*把除数赋给数组d*/ for(i = k2; i N; i+) di = 0; /*d数组无数据的高位置0*/ k = k1 - k2 - 1; /*计算减法起始位置*/ if(k 0) for(i = k2 - 1; i = 0; i-) di + k = di; /*移动减数位数与被减数对齐*/ for(i = 0; i k; i+) di = 0; /*移动后的其余位置0*/ for(i = 0; i = di) ai -= di; else ai + 1 = ai + 1 - 1; ai = 10 + ai - di; return k; main() int aN = 0, bN = 0, cN = 0, dN = 0; int i, ka, kb, m, t, t1, t2, k, x, kd, kk; char a1N, b1N; printf(Input 被除数:); scanf(%s, a1); ka = strlen(a1); for(i = 0; i ka; i+) ai = a1ka - i -1 - 0; printf(Input 除数:); scanf(%s, b1); kb = strlen(b1); for(i = 0; i = 1) k = jf(a, b, ka, kb); ck+; if(k m) m = k; t1 = 0; for(i = k; i 0) m+; cm = t1; while(t = 1); if(t2 = 0) printf(商=0); printf(n余数=); for(i = kd - 1; i = 0; i-) printf(%d, ai); exit(1); if(t2 = 2) printf(商 = 1); printf(n余数 = 0); exit(1); kk = kd; while(!ckd - 1) kd-; printf(商 = ); for(i = kd - 1; i = 0; i-) printf(%d, ci); while(!akk) kk-; printf(n余数 = ); if(kk = 0; i-) printf(%d, ai); -4、 N！，要求精确到P位（0P1000。 算法：结果用数组a保存，开始时a0=1，依次乘以数组中各位，注意进位和数组长度的变化。源程序如下： #include #define M 1000 main() int aM, i, n, j, flag = 1; printf(n=); scanf(%d,&n); printf(n!=); a0 = 1; for(i = 1; i M; i+) ai = 0; for(j = 2; j = n; j+) for(i = 0; i flag; i+) ai *= j; for(i = 0; i = 10) ai+1 += ai/10; ai = ai % 10; if(i = flag-1) flag+; for(j = flag - 1; j = 0; j-) printf(%d, aj); 问题1. 麦森数 【问题描述】形如2P-1的素数称为麦森数，这时P一定也是个素数。但反过来不一定，即如果P是个素数，2P-1不一定也是素数。到1998年底，人们已找到了37个麦森数。最大的一个是P=3021377，它有909526位。麦森数有许多重要应用，它与完全数密切相关。 任务：从文件中输入P（1000P3100000），计算2P-1的位数和最后500位数字（用十进制高精度数表示） 【输入格式】 文件中只包含一个整数P（1000P3100000） 【输出格式】 第一行：十进制高精度数2P-1的位数。 第2-11行：十进制高精度数2P-1的最后500位数字。（每行输出50位，共输出10行，不足500位时高位补0） 不必验证2P-1与P是否为素数。 【输入样例】 1279 【输出样例】 386 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000104079321946643990819252403273640855 38615262247266704805319112350403608059673360298012 23944173232418484242161395428100779138356624832346 49081399066056773207629241295093892203457731833496 61583550472959420547689811211693677147548478866962 50138443826029173234888531116082853841658502825560 46662248318909188018470682222031405210266984354887 32958028878050869736186900714720710555703168729087 算法：2的幂可以转化成左移运算，为了提高运算速度，可每次左移10位，即每次乘210。对于个位单独考虑，每次左移一位。源程序如下： #include #include #define MAX 100000 main() int p; int i, j; scanf(%d, &p); printf(%dn, (int)(p * log10(2.0) + 1); long store110 = 0; store0 = 1; int left = p % 10; p /= 10; for(i = 1; i = p; i+) for(j = 0; j = 100; j+) storej = 10; for(j = 0; j = MAX) storej + 1 += storej / MAX; storej %= MAX; for(i = 1; i = left; i+) for(j = 0; j = 100; j+) storej = 1; for(j = 0; j = MAX) storej + 1 += storej / MAX; storej %= MAX; store0 -= 1; for(i = 1; i 100; i+) if(storei - 1 = 0; i-) printf(%05d, storei); if(100 - i) % 10 = 0) printf(n); 问题2. 有一个正整数N（N可能达到120位），它是由若干个不大于65535的正整数相乘而得到的。请把这个数分解成素数因子（质因子）的乘积。 输入：输入文件只有一行为N的值。 输出：（1）素数因子由小到大分行输出； （2）每一行输出一个素数因子和该素数因子的个数，用一个空格分开； （3）如果正整数N的分解中有一个以上的大于65535的素数，请按照（1）、（2）的要求输出分解中的小于65535的素数后，在下一行输出“DATA ERROR！”。 算法：先将2到65535之间的所有素数保存在数组中，用这个数去除数组中的每一个数，得到一个质因数就打印出来。源程序如下： #include #include int length, temp120; int sushu(int a) int i, j, k = 0, m; for(i = 2; i = 65537; i+) m = sqrt(i); for(j = 2; j m) ak = i; k+; return k; int divide(int a, int k) int i, d = 0; for(i = length - 1; i = 0; i-) d = d * 10 + ai; tempi = d / k; d = d % k; if(!d) while(templength - 1 = 0 & length 1) length-; for(i = 0; i length; i+) ai = tempi; tempi = 0; for(i = length; i 120; i+) ai = 0; else for(i = 0; i length; i+) tempi = 0; return d; main() int i, k, s, d; /*s计数器; d余数*/ int a6600, b120 = 0, c120 = 0; char b1120; gets(b1); length = strlen(b1); for(i = 0; i length; i+) bi = b1length - i - 1 - 0; k = sushu(a); for(i = 0; i k; i+) s = 0; d = divide(b, ai); while(!d) s+; d = divide(b, ai); if(i = k - 1) printf(Data Error!); break; 大数的表示用字符串，自己计算进位基本上这个思路这是我以前编号的一个大数计算器。可以计算加减乘除。足够你的大数乘法要求，基本上最后结果不超过1000位应该都可以。不过没有乘方功能#include #include /-/将字符串转化为整形数组void str2int(char *a,char *b,int ia1024,int ib1024,int ir1024)int i,len;/对数组初始化for (i=0;istrlen(b) sg=0;else if (strlen(a)strlen(b)sg=1;elsefor (i=0;i*(b+i)sg=0;break;else if (*(a+i)strlen(b) len=strlen(a);else len=strlen(b);c=0;/加法运算for (i=0;ilen;i+)iri=(iai+ibi+c)%10;c=(iai+ibi+c)/10;if (c=1)irlen=1;len+;for (i=0;ilen;i+)*(a+i)=irlen-i-1+48;/翻转输出*(a+len)=0;return a;/-/减法函数char *sub(char *a,char *b)int len,i,c,sg;int ia1024,ib1024,ir1024;char str1024;char *strrt;str2int(a,b,ia,ib,ir);/符号判断sg=cmp(a,b);if (sg=0) len=strlen(a);else len=strlen(b);c=0;/减法运算for (i=0;i=0)iri=iai-ibi-c;c=0;elseiri=10+iai-ibi-c;c=1;elseif (ibi-iai-c)=0)iri=ibi-iai-c;c=0;elseiri=10+ibi-iai-c;c=1;if (sg=1) str0=-;for (i=0;i1&*strrt=0)strrt+;len-;if (sg=1)strrt+;while(len1&*strrt=0)*strrt=-;strrt+;len-;strrt-;strcpy(a,strrt);return a;/-/乘法函数char *mul(char *a,char *b)int len,lena,lenb,i,j,c,jin;int ma1024,mb1024,mr1024;char stra1024,strb1024;char *strrta,*strrtb;stra0=0;stra1=0;strrta=stra;str2int(a,b,ma,mb,mr);/乘法运算lena=strlen(a);lenb=strlen(b);for (j=0;jlena;j+)c=0;jin=0;for (i=0;i0) strb0=c+48;jin=1;for (i=0;ilen;i+)strbi+jin=mrlen-i-1+48;for (i=len;ilen+j;i+) strbi+jin=0;strblen+j+jin=0;strrtb=strb;add(strrta,strrtb);strcpy(a,strrta);return a;/-/除法函数char *div(char *a,char *b)int len,lena,i,j;char stra1024,strb1024,strc1024,strd1024;char *strbp;strbp=strc;strcpy(stra,a);strcpy(strb,b);strcpy(strd,a);if (cmp(stra,strb)=1)/被除数小于除数*a=0;*(a+1)=0;strcpy(b,stra);else/被除数大于除数mul(strb,10);len=strlen(a)-strlen(b);if (len=0|(len=1&cmp(stra,strb)=1)strcpy(stra,a);strcpy(strb,b);i=1;strc0=1;strc1=0;while(cmp(stra,strc)=0)strc0=i+48;strc1=0;mul(strc,st