首页 > 代码库 > 【算法:1】高精度除法
【算法:1】高精度除法
高精度除法,我用高精度减法来模拟
#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#include<algorithm>#include<cmath>#include<string>using namespace std;inline int read(){ int x=0,f=1;char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch==‘-‘) f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-‘0‘; return x*f;}const int maxn=10000;int a[maxn],b[maxn],c[maxn];void in(int a[]) //这个函数用来输入,输入时将字符串转化为int数组,角标为0的为长度。并倒序存储。 { string s; cin>>s; a[0]=s.length(); for(int i=1;i<=a[0];i++) a[i]=s[a[0]-i]-‘0‘; return ;}void print(int a[]) // 输出{ if( !a[0] ) puts("0"); else { for(int i=a[0];i>0;i--) printf("%d",a[i]); puts(""); } return ;}int compare( int a[], int b[]) // 比较函数,如果a<b,返回-1,如果a>b,返回1,如果a=b,返回0 { if( a[0] > b[0] ) return 1; if( a[0] < b[0] ) return -1; for(int i=a[0];i>0;i--) { if(a[i] > b[i]) return 1; else if( a[i] < b[i] ) return -1; } return 0;}void sub(int a[], int b[])//高精度减法 { int flag=compare(a,b); if( !flag) {a[0]=0;return ;} if( flag == 1 ) { for(int i=1;i<=a[0];i++) { if( a[i] < b[i] ) { a[i+1]--; a[i]+=10; } a[i]-=b[i]; } while( a[0] > 0 && !a[a[0]] ) a[0]--; } return ;}void numcpy(int p[], int q[],int det) //复制p数组到q数组从det开始的地方 { for(int i=1;i<=p[0];i++) q[i+det-1]=p[i]; q[0]=p[0]+det-1; return ;}void div(int a[], int b[], int c[]){ int tmp[maxn]; c[0]=a[0]-b[0]+1; for(int i=c[0];i>0;i--) { memset(tmp,0,sizeof(tmp)); numcpy(b,tmp,i); while( compare(a,tmp) >= 0) {c[i]++;sub(a,tmp);} //用减法模拟除法 } while(c[0] > 0 && !c[c[0]]) c[0]--; return ;}int main(){ in(a),in(b),div(a,b,c),print(c),print(a);}
【算法:1】高精度除法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。