加法
void add(char a[],char b[],char d[]) { char c[10001]; int lena=strlen(a),lenb=strlen(b); int i,j,len; len=lena>lenb?lena:lenb; len++; c[0]='\0'; for(i=1;i<=len;i++) c[i]='0'; for(i=1;i<=lena;i++) c[i]+=a[lena-i]-48; for(i=1;i<=lenb;i++) c[i]+=b[lenb-i]-48; for(i=0;i<=len;i++) { if(c[i]>57) { c[i]-=10; c[i+1]++; } } for(i=len;i>1;i--) if(c[i]==48) len--; else break; for(i=0;i<=len;i++) d[i]=c[len-i]; }
减法
1 //d2 > d1，如果需要比较大小自己加一个不麻烦。
void dec(char *d1, char *d2, char *out) { int len_min = strlen(d1); int len_max = strlen(d2); int last_j = 0; //最关键的错位 while(len_min > 0) { int dd1 = d1[len_min - 1] - '0'; int dd2 = d2[len_max - 1] - '0'; if (last_j) dd2 = dd2 - 1; last_j = dd2 >= dd1 ? 0 : 1; dd2 = dd2 >= dd1 ? dd2 : dd2 + 10; out[len_max] = (dd2 - dd1) + '0'； len_max -- ; len_min -- ; } while(len_max > 0) { int dd2 = (d2[len_max -1] - '0'); if (last_j) dd2 = dd2 - 1; last_j = dd2 >= 0 ? 0 : 1; dd2 = dd2 >= 0 ? dd2 : dd2 + 10; out[len_max] = dd2 + '0'; len_max --; } if (last_j) out[0] ='1'; else out[0] ='0'; }
乘法
void multiply(char* a,char* b,char* c) { int i,j,ca,cb,*s; ca=strlen(a); cb=strlen(b); s=(int*)malloc(sizeof(int)*(ca+cb)); for (i=0;i<ca+cb;i++) s[i]=0; for (i=0;i<ca;i++) for (j=0;j<cb;j++) s[i+j+1]+=(a[i]-'0')*(b[j]-'0'); for (i=ca+cb-1;i>=0;i--) // 这里实现进位操作 { if (s[i]>=10) { s[i-1]+=s[i]/10; s[i]%=10; } } i=0; while(s[i]==0) // 跳过头部0元素 i++; if(i==ca+cb) //s[i]全为0 i--; for (j=0;i<ca+cb;i++,j++) c[j]=s[i]+'0'; c[j]='\0'; free(s); }
/*高精度除低精度求商模板*/
/*大数除法 ------除数为int范围*/
#include<stdio.h> #include<string.h> #include<stdlib.h> #define Max 1000 #include<iostream> #define N 1000 using namespace std; void division(char * src,int n) { int len=strlen(src),i,k,t=0,s=0; char dest[N]; bool flag=true; //商是否有了第一个有效位，防止商首部一直出现0 for(i=0,k=0;i<len;i++) { t=s*10+(src[i]-48); //新余数 if(t/n>0||t==0) //余数为0要修改商 { dest[k++]=t/n+48,s=t%n,flag=false; } else //不够除，修改余数 { s = t; if(!flag) //商已经有有效位了，补零 dest[k++] = '0'; } } int j=0; while(dest[j]=='0') j++; if(j==k) j--; for(i=j;i<k;i++) cout<<dest[i]; cout<<endl; } int main() { char num[N]; int n; while(scanf("%s%d",num,&n)!=EOF) { division(num,n); } return 0; }
/*大数除法---高精度除高精度*/
/*
1.a.size<b.size 返回-1
2.a.size=b.size && a-b<0 返回-1
3.a.size=b.size && a-b=0 返回0
*/
#include<iostream> #include<cstring> #include<string> #define N 2000 using namespace std; //判断a.size 与b.size 的关系 以及做减法 int judge(char a[],int a1,char b[],int b1) { int i; if(a1<b1)return -1;//a.size<b.size bool flag=false; if(a1==b1) //a.size==b.size && a<b { for(i=a1-1;i>=0;i--) if(a[i]>b[i]) flag=true; else if (a[i]<b[i]) { if(!flag) return -1; } } for(i=0;i<a1;i++)//前提b中b1---a1部分必须为'0' { a[i]=a[i]-b[i]+48;//'0'的ASCII为48 if((a[i]-'0')<0) { a[i]=a[i]+10;a[i+1]=a[i+1]-1; } } for(i=a1-1;i>=0;i--) //返回被除数的长度 if(a[i]!='0') return (i+1); return 0;//a.size==b.size&&a=b的情况 } string division(string a,string b) { char x1[N],x2[N]; int ans[N]; int a_len,b_len,i,j; a_len=a.length(); b_len=b.length(); /*初始化部分*/ /*********************************************/ memset(x1,'0',sizeof(x1)); memset(x2,'0',sizeof(x2)); memset(ans,0,sizeof(ans)); for(i=a_len-1,j=0;i>=0;i--) x1[j++]=a[i]; for(i=b_len-1,j=0;i>=0;i--) x2[j++]=b[i]; /*********************************************/ /*分析部分*/ /*********************************************/ if(a_len<b_len) return "0"; int temp_len=judge(x1,a_len,x2,b_len); if(temp_len<0)return "0"; if(temp_len==0)return "1"; ans[0]++;//减掉一次，商加1 int ntimes=temp_len-b_len; if(ntimes<0) return "1"; else if(ntimes>0) //扩充数位，加快减法。 { for(i=temp_len-1;i>=0;i--) if(i>=ntimes) x2[i]=x2[i-ntimes]; else x2[i]='0'; } b_len=temp_len; /*********************************************/ /*加快除法的部分*/ /********************************************/ for(j=0;j<=ntimes;j++) { int ntemp; while((ntemp=judge(x1,temp_len,x2+j,b_len-j))>=0) { temp_len=ntemp; ans[ntimes-j]++; } } /*********************************************/ /*处理最后结果进位部分*/ /*********************************************/ for(i=0;i<N;i++) if(ans[i]>=10) { ans[i+1]+=ans[i]/10; ans[i]%=10; } /*********************************************/ /*返回string类型*/ /*********************************************/ int k=N-1; string c=""; while(ans[k]==0&&k>0) k--; for(i=k;i>=0;i--) c+=(ans[i]+'0'); /*********************************************/ return c; } int main() { string a,b; while(cin>>a>>b) { cout<<division(a,b)<<endl; } return 0; }