算法篇之完整的大数!!!(我能想到的高精度就这么多了)
发布时间:2020-12-14 03:02:52 所属栏目:大数据 来源:网络整理
导读:这里总结了各种可能遇到的高精度问题。。不过大数除法那一部分还没理解,从队友那里讨来的高精度除法,下一次回来复习大数的时候再好好理解下! #includestdio.h #includestring.hchar c[2000];//全局变量,存储大数运算的结果char arr[1000];//高精度除以高
这里总结了各种可能遇到的高精度问题。。不过大数除法那一部分还没理解,从队友那里讨来的高精度除法,下一次回来复习大数的时候再好好理解下! #include<stdio.h> #include<string.h> char c[2000];//全局变量,存储大数运算的结果 char arr[1000];//高精度除以高精度的余数 long z=0;//高精度除以低精度的余数 int Judge(char ch[]) {//判断字符串ch是否全为0,若全为1,返回,否则返回0 int i,k; k=strlen(ch); for(i=0;i<k;i++) if(ch[i]!='0') return 0; return 1; } int Compare(char a[],char b[]) {//比较字符串的大小,方法不同于strcmp函数,类似于整型常量的比较 int lena,lenb,i; lena=strlen(a),lenb=strlen(b); if(lena<lenb) return -1; else if(lena>lenb) return 1; else { if(strcmp(a,b)==0) return 0; else { for(i=0;i<lena;i++) { if(a[i]>b[i]) return 1; if(a[i]<b[i]) return -1; } return 0; } } } /*算法:先确定a和b中的最大位数k,然后依照由低至高位的顺序进行加法运算。 注意进位,若高位有进位,则c的长度为k+1。*/ //高精度加法 void BigNumberAdd(char a1[],char b1[]) { int i,j,k,lena,lenb; int a[1000]={0},b[1000]={0},d[1000]={0}; lena=strlen(a1),lenb=strlen(b1); for(i=0;i<lena;i++) //将加数与被加数化为整型数组,并且该数组的其他位为0 a[i]=a1[lena-i-1]-'0'; for(i=0;i<lenb;i++) b[i]=b1[lenb-1-i]-'0'; k=lena>lenb?lena:lenb;//当数组除了加数和被加数以外的整型数组元素均为时,无需考虑lena和lenb的大小 for(i=0;i<k;i++) { d[i]=a[i]+b[i]+d[i]; d[i+1]=d[i+1]+d[i]/10; d[i]=d[i]%10; } while(d[k]) //若高位进 k++; while(!d[k-1]) k--;//001+0003=4 for(j=0;j<k;j++) //将整型数组逆着转变并赋值给c字符型数组 c[j]=d[k-j-1]+'0'; if(Judge(c))//若全为0,则只输出一个0 strcpy(c,"0"); } /*算法:依照由低位至高位的顺序进行减法运算。在每次位运算中, 若出现不够减的情况,则向高位借位。在进行了la的减法后,若最高 位为,则a的长度减。若A、B大小未知,则需先判断大小。*/ //高精度减法 void BigNumberSub(char a1[],char b1[]) {//a1为被减数,b1为减数 int lena,i,flag; int a[1000]={0},lenb=strlen(b1); if(Compare(a1,b1)>=0) {//若被减数大于等于减数 for(i=0;i<lena;i++) a[i]=a1[lena-1-i]-'0'; for(i=0;i<lenb;i++) b[i]=b1[lenb-1-i]-'0'; flag=0;//结果正的标志 } else {//若被减数小于减数 for(i=0;i<lenb;i++) a[i]=b1[lenb-1-i]-'0'; for(i=0;i<lena;i++) b[i]=a1[lena-1-i]-'0'; flag=1;//结果负的标志 } k=lena>lenb?lena:lenb; for(i=0;i<k;i++) {//大数减小数 if(a[i]<b[i]) {//若被减数不够减,向高位借一位 a[i+1]--; d[i]=a[i]-b[i]+10; } else d[i]=a[i]-b[i]; } //若较高位已为,并且不止位时 while(!d[i-1]) { k--; i--; } //根据flag,输出有无"-" if(!flag) { for(i=0;i<k;i++) {//将结果转化为字符逆着赋给数组c if(!i&&!d[k-i-1])//若差的第一个字母为,则马上跳过 continue; c[i]=d[k-i-1]+'0'; } } else { c[0]='-'; for(i=1;i<=k;i++) {//将结果转化为字符逆着赋给数组c if(i==1&&!d[k-i])//若差的第一个字母为,则马上跳过 continue; c[i]=d[k-i]+'0';//注意d的下标,不是k-i-1 } } if(Judge(c))//若差全为0,则只输出一个0 strcpy(c,"0"); } /*算法:将多位数存入数组,低位在前、高位在后, 然后用一位数去乘数组的各位,考虑进位,最后按正常顺序输出*/ //高精度乘法--高精度乘以低精度 void BigNumMultiSmall(char a1[],int b1) { int i,t; int a[2000]={0}; //将字符串转化为整型数组,并逆置 t=strlen(a1); for(i=0;i<t;i++) a[i]=a1[t-1-i]-'0'; //整型数组的每个元素乘以b1,然后对其进行求余,整除,使其只有一位数 a[0]=a[0]*b1; for(i=1;i<t;i++) { a[i]*=b1; a[i]+=a[i-1]/10; a[i-1]=a[i-1]%10; } while(a[i-1]>9) {//若最后一个元素大于 a[i]=a[i-1]/10; a[i-1]=a[i-1]%10; i++; } //将得到的整型数组逆置赋给字符串 for(j=0;j<i;j++) c[j]=a[i-j-1]+'0'; if(Judge(c))//若积全为0,则只输出一个0 strcpy(c,"0"); } //高精度乘法--高精度乘以高精度 void BigNumMultiBig(char a1[],char b1[]) { int i,lenb; int a[1000]={0},d[2000]={0}; //将字符串转化为整型数组,并逆置 lena=strlen(a1),lenb=strlen(b1); for(i=0;i<lena;i++) a[i]=a1[lena-i-1]-'0'; for(i=0;i<lenb;i++) b[i]=b1[lenb-i-1]-'0'; //计算乘数从低位到高位以此乘以被乘数的低位到高位 for(i=0;i<lena;i++) for(j=0;j<lenb;j++) { d[i+j]=d[i+j]+a[i]*b[j]; d[i+j+1]+=d[i+j]/10; d[i+j]=d[i+j]%10; } //根据高位是否为判断整型数组的位数 k=lena+lenb; while(!d[k-1]) k--; //积转化为字符型 for(i=0;i<k;i++) c[i]=d[k-1-i]+'0'; if(Judge(c))//若积全为0,则只输出一个0 strcpy(c,"0"); } //整型常量的阶乘 void BigNumFact(int x) { int i,m=0,a[1000]={0}; a[0]=1; for(;x;x--) {//m为在求阶乘过程中a的元素个数 for(k=i=0;i<=m;i++) { k=k+a[i]*x;//数组各个元素均乘以x(x递减),以完成阶乘的运算 a[i]=k%10; k/=10; } while(k) { a[++m]=k%10; k/=10; } } //阶乘的结果转化为字符型 for(i=0;i<=m;i++) c[i]=a[m-i]+'0'; if(Judge(c))//若结果全为0,则只输出一个0 strcpy(c,"0"); } //1-整型常量的阶乘和 void BigNumFactAdd(int t) { int i; char sum[2000],d[2000]; //对字符串进行初始化 memset(d,sizeof(d)),memset(sum,sizeof(sum)); //分别求出相应i的阶乘然后相加 for(i=t;i>0;i--) { BigNumFact(i); strcpy(d,c); memset(c,sizeof(c)); BigNumberAdd(d,sum); strcpy(sum,c); memset(c,sizeof(c)); } strcpy(c,sum);//将结果赋值给全局变量,进行输出 } //高精度的乘方,幂数为整型常量 void BigNumInvol(char a1[],int b1) { int i; char temp[1000]; strcpy(temp,a1);//注意乘方是自己乘自己,而不是结果乘结果 for(i=2;i<b1;i++) { BigNumMultiBig(a1,temp); strcpy(temp,sizeof(c));//将c清空,防止出现错误 } //进行最后一次乘法 BigNumMultiBig(a1,temp); if(Judge(c))//若结果全为0,则只输出一个0 strcpy(c,"0");} //高精度除法--高精度除以低精度,只产生余数 int BigNumDividSmall(char a1[],int b1) { if(!b1) return 0; int i,flag=0,a[1000]={0}; char b[2000]; memset(b,sizeof(b)); k=strlen(a1); for(i=0;i<k;i++) a[i]=a1[i]-'0'; z=0; for(i=0;i<k;i++) { z=a[i]+z*10; b[i]=z/b1+'0'; z=z%b1; } i=j=0; while(b[i++]=='0'); for(i=i-1;i<k;i++) c[j++]=b[i]; return 1; } //高精度除法--高精度除以高精度,只产生余数 void BigNumDividBig(char a1[],char b1[]) { char b[1000],time[1000]; int lena1,lentime,flag=0; memset(arr,sizeof(arr)); //若被除数小于除数,则商为0,余数为被除数 if(Compare(a1,b1)<0) strcpy(arr,a1); //若两数相等,则商为,余数为 else if(!Compare(a1,b1)) c[0]='1'; //若被除数大于除数 else { j=lentime=0; lena1=strlen(a1); memset(b,sizeof(b)); memset(time,sizeof(time)); for(i=0;i<lena1;i++) {//计算得到被除数的前几位,得到整型数组形式的商 //time的一个元素表示一次相除的商 b[j++]=a1[i]; flag=0; while(Compare(b,b1)>=0) { BigNumberSub(b,b1); strcpy(b,c); memset(c,sizeof(c)); time[lentime]++; flag=1;//控制time的元素的位置 } if(flag)//将商转换为字符 time[lentime]+='0'; else//当被除数前几位小于除数,商补 time[lentime]='0'; if(!strcmp(b,"0"))//若b为‘’ j=0; else//继续在b的后面加值 j=strlen(b); lentime++; } k=0; for(i=0;i<lentime;i++) if(time[i]!='0') break;//找到time数组中第一个不为的位置 for(j=i;j<lentime;j++) c[k++]=time[j]; strcpy(arr,b); } if(Judge(c)) strcpy(c,"0"); if(Judge(arr)) strcpy(arr,"0"); } int main() { int flag=0,a3,i; char a2[1000],b2[1000]; printf("说明:该程序适用于正整数的高精度运算,并且运算结果的位数在位以内。n"); while(1) { printf("/************************/n"); printf("1、两数相加n"); printf("2、两数相减n"); printf("3、大数与低精度相乘n"); printf("4、大数与大数相乘n"); printf("5、大数的阶乘n"); printf("6、大数的阶乘和n"); printf("7、大数的乘方n"); printf("8、大数除以低精度n"); printf("9、大数除以大数n"); printf("10、退出n"); printf("/************************/n"); printf("请输入你想要进行的操作数:"); scanf("%d",&k); getchar(); memset(c,sizeof(c)); switch(k) { case 1: printf("请输入您想要进行运算的两个数字:n"); scanf("%s%s",a2,b2); BigNumberAdd(a2,b2); printf("%s+%s=%snn",b2,c); break; case 2: printf("请输入您想要进行运算的两个数字:n");scanf("%s%s",b2); BigNumberSub(a2,b2); printf("%s-%s=%snn",c); break; case 3: printf("请输入您想要进行运算的两个数字:n");scanf("%s%d",&a3); BigNumMultiSmall(a2,a3); printf("%s*%d=%snn",c); break; case 4: printf("请输入您想要进行运算的两个数字:n");scanf("%s%s",b2); BigNumMultiBig(a2,b2); printf("%s*%s=%snn",c); break; case 5: printf("请输入您想要的阶乘数:"); scanf("%d",&a3); BigNumFact(a3);printf("%d!=%snn",c); break; case 6: printf("请输入您想要的阶乘数:"); scanf("%d",&a3); if(!a3) { printf("0!=1nn"); continue; } BigNumFactAdd(a3); for(i=1;i<=a3;i++) { printf("%d!",i); if(i!=a3) printf("+"); } printf("=%snn",c); break; case 7: printf("请输入您想要进行运算的两个数字:n"); scanf("%s%d",&a3); BigNumInvol(a2,a3); printf("%s^%d=%snn",c); break; case 8: printf("请输入您想要进行运算的两个数字:n"); scanf("%s%d",&a3); if(BigNumDividSmall(a2,a3)) { if(!z) printf("%s/%d=%snn",c); else printf("%s/%d=%s……%ldnn",c,z); } else printf("0不能作除数。nn");break; case 9:printf("请输入您想要进行运算的两个数字:n"); scanf("%s%s",b2); if(Judge(b2)) printf("0不能作除数。nn"); else { BigNumDividBig(a2,b2); if(!Judge(arr)) printf("%s/%s=%s……%snn",arr); else printf("%s/%s=%snn",c); }break; case 10:flag=1;printf("感谢您的使用,再见。nn");break; default: printf("对不起,您的输入有误,请重新输入。nn"); } if(flag) break; } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |