精华内容
参与话题
问答
  • 「学习笔记」C++ 高精度算法

    万次阅读 多人点赞 2017-09-03 16:30:17
    高精度算法解决long long也解决不了的计算   高精度的存储是把每一位单独存储,且是倒序存储,数组num[1]是这个数的个位,num[2]是这个数的十位,以此类推;     (一)高精度加法   #include <...

    高精度算法解决long long也解决不了的计算

     

    高精度的存储是把每一位单独存储,且是倒序存储,数组num[1]是这个数的个位,num[2]是这个数的十位,以此类推;

     

     

    (一)高精度加法

     

    #include <iostream>
    #include <cstring>
    using namespace std;
    
    struct HugeInt{
    	int len;
    	int num[100001];
    }; 
    
    HugeInt a, b, w;        //w为结果 
    char c[100001], d[100001];
    
    void Scan_HugeInt() {   //读入两个大整数 
    	cin >> c;
    	cin >> d;
    	a.len = strlen(c); //strlen求串长 
    	b.len = strlen(d);
    	for(int i=0; i<a.len; i++) a.num[a.len - i] = c[i] - '0'; //逆序存储 
    	for(int i=0; i<b.len; i++) b.num[b.len - i] = d[i] - '0';
    }
    
    void Plus() {
    	w.len = max(a.len, b.len);           //num每一位是0,长度取max不影响加法 
    	for(int i=1; i<=w.len; i++) {
    		w.num[i] += a.num[i] + b.num[i]; 
    		w.num[i+1] += w.num[i] / 10;    //处理进位
    		w.num[i] %= 10;                 //处理当前位 保证<10 
    	}
    	if(w.num[w.len + 1] != 0) w.len ++;  //加法最多有可能会多出一位 
    }
    
    int main() {
    	Scan_HugeInt();
    	Plus();
    	for(int i=w.len; i>=1; i--) cout << w.num[i]; //倒序存储 倒序输出 
    	cout << endl;
    	return 0;
    }
    

     

     

     

    (二)高精度减法

     

    #include <iostream>
    #include <cstring>
    using namespace std;
    
    struct HugeInt {
    	int len;
    	int num[100001];
    };
    
    HugeInt a, b, w;         //w为结果
    char c[100001], d[100001];
    bool negative;           //负数标记 
    
    void Scan_HugeInt() {    //读入两个大整数
    	cin >> c;
    	cin >> d;
    	if((strlen(c) < strlen(d)) || (strlen(c) == strlen(d) && strcmp(c, d) < 0)) { //若被减数小 交换 记为负数 
    		negative = true;
    		swap(c, d);
    	}
    	a.len = strlen(c);
    	b.len = strlen(d);
    	for(int i=0; i<a.len; i++) a.num[a.len - i] = c[i] - '0'; 
    	for(int i=0; i<b.len; i++) b.num[b.len - i] = d[i] - '0';
    }
    
    void Minus() {
    	w.len = a.len;                //a更大 
    	for(int i=1; i<=w.len; i++) {
    		if(a.num[i] < b.num[i]) {  
    			a.num[i+1] --;      //num[i+1]减成负数也不影响 
    			a.num[i] += 10;     //借位 
    		}
    		w.num[i] += a.num[i] - b.num[i];
    	}
    	while(w.num[w.len] == 0 && (w.len != 1)) w.len --; //多余的不是个位的0去掉 
    }
    
    int main() {
    	Scan_HugeInt();
    	Minus();
    	if(negative == true) cout << "-";             //负数加负号 
    	for(int i=w.len; i>=1; i--) cout << w.num[i]; //倒序存储 倒序输出
    	cout << endl;
    	return 0;
    }

     

     

     

     

     

    (三)高精度乘法

     

    #include <iostream>
    #include <cstring>
    using namespace std;
    
    struct HugeInt {
    	int len;
    	int num[100001];
    };
    
    HugeInt a, b, w; 
    char c[10001], d[10001];
    
    void Scan_HugeInt() {    //读入两个大整数
    	cin >> c;
    	cin >> d;
    	a.len = strlen(c);
    	b.len = strlen(d);
    	for(int i=0; i<a.len; i++) a.num[a.len - i] = c[i] - '0';
    	for(int i=0; i<b.len; i++) b.num[b.len - i] = d[i] - '0';
    }
    
    void Multiply() {
    	int x;              //处理每次进位的变量 
    	for(int i=1; i<=a.len; i++) {      //a的第i位 
    		x = 0;
    		for(int j=1; j<=b.len; j++) { //b的第j位 
    			w.num[i+j-1] += a.num[i] * b.num[j] + x; //用 +=:结果与上次乘的结果相加 
    			x = w.num[i+j-1] / 10;
    			w.num[i+j-1] %= 10;          //进位处理 
    		} 
    		w.num[i+b.len] = x;  //多出的最高位 
    	}
    	w.len = a.len + b.len;
    	while(w.num[w.len] == 0 && (w.len != 1)) w.len --; //多余的0 
    }
    
    int main() {
    	Scan_HugeInt();
    	Multiply();
    	for(int i=w.len; i>=1; i--) cout << w.num[i];
    	cout << endl;
    	return 0;
    }

     

    (四)高精度除法

    除以高精时,直接枚举每一位.

    除以低精时,可以使用另种模拟更快

    
    Int1000 operator / (const int &b) { //除以低精
    	if(*this < Int1000(b)) return Int1000(0);
    	Int1000 ans;
    	ans.len = len;
    	int r = 0;
    	for(int i=ans.len; i>=1; i--) {
    		r = r * 10 + a[i];
    		ans.a[i] = r / b;
    		r %= b;
    	}
    	while(ans.len > 1 && !ans.a[ans.len]) ans.len --;
    	return ans;
    }
    Int1000 operator / (Int1000 b) {
    	if(*this < b) return Int1000(0);
    	Int1000 ans; ans.len = len - b.len + 1;
    	for(int i=ans.len; i>=1; i--) {
    		for(int j=1; j<=9; j++) {
    			ans.a[i] ++;
    			if((*this) < (ans * b)) {
    				ans.a[i] --;
    				break;
    			}
    		}
    	        if(ans.a[ans.len] == 0) ans.len --;
            }
    	while(ans.len > 1 && !ans.a[ans.len]) ans.len --;
    	return ans;
    }

     

    高精度模版:

    PS:常数较大,谨慎使用

     

    const int MAX_SIZE = 1010;
    
    struct Int {
    	int len, n[MAX_SIZE];
    	void Set(int l) {
    		len = l;
    		for(int i = 1; i <= len; i ++) n[i] = 0;
    	}
    	Int(char *s) {
    		len = strlen(s);
    		for(int i = len - 1; ~i; i --) {
    			if(s[i] <= '9' && s[i] >= '0') {
    				len = i + 1;
    				break;
    			}
    		}
    		for(int i = len; i >= 1; i --) n[i] = s[len - i] - '0';
    	}
    	Int(long long x = 0) {
    		len = 0;
    		do {
    			n[++ len] = x % 10;
    			x /= 10;
    		} while(x);
    	}
    	bool operator < (const Int b) {
    		if(len != b.len) return len < b.len;
    		for(int i = len; i; i --)
    			if(n[i] != b.n[i]) return n[i] < b.n[i];
    		return false;
    	}
    	Int operator + (const Int b) const {
    		Int ans; ans.Set(max(len, b.len) + 1);
    		for(int i = 1; i <= ans.len; i ++) {
    			if(i <= len) ans.n[i] += n[i];
    			if(i <= b.len) ans.n[i] += b.n[i];
    			ans.n[i + 1] += ans.n[i] / 10;
    			ans.n[i] %= 10;
    		}
    		while(!ans.n[ans.len] && ans.len > 1) ans.len --;
    		return ans;
    	}
    	Int operator - (const Int b) {
    		Int ans, a = *(this); ans.Set(len);
    		for(int i = 1; i <= ans.len; i ++) {
    			if(a.n[i] < b.n[i]) a.n[i + 1] --, a.n[i] += 10;
    			ans.n[i] += a.n[i] - (i > b.len ? 0 : b.n[i]);
    		}
    		while(!ans.n[ans.len] && ans.len > 1) ans.len --;
    		return ans;
    	}
    	Int operator * (Int b) {
    		Int ans; ans.Set(len + b.len);
    		for(int i = 1; i <= len; i ++) {
    			for(int j = 1; j <= b.len; j ++) {
    				ans.n[i + j - 1] += n[i] * b.n[j];
    				ans.n[i + j] += ans.n[i + j - 1] / 10;
    				ans.n[i + j - 1] %= 10;
    			}
    		}
    		while(!ans.n[ans.len] && ans.len > 1) ans.len --;
    		return ans;
    	}
    	Int operator / (const int &b) { //除以低精  
         	    if(*this < Int(b)) return Int(0LL);  
         	    Int ans; ans.len = len;  
         	    int r = 0;  
         	    for(int i = ans.len; i; i --) {  
         		r = r * 10 + n[i];  
         		ans.n[i] = r / b;  
              	r %= b;  
            }  
                while(ans.len > 1 && !ans.a[ans.len]) ans.len --;  
                return ans;  
            }  
    	Int operator / (const Int b) {
    		if((*this) < b) return Int(0LL);
    		Int ans; ans.Set(len - b.len + 1);
    		for(int i = ans.len; i; i --) {
    			for(int j = 1; j <= 9; j ++) {
    				ans.n[i] ++;
    				if((*this) < (ans * b)) {
    					ans.n[i] --;
    					break;
    				}
    			}
    		}
    		while(ans.len > 1 && !ans.n[ans.len]) ans.len --;
    		return ans;
    	}
    	void print() {
    		for(int i = len; i; i --) 
    			printf("%d", n[i]);
    		printf("\n");
    	}
    };

     

    黑科技:两个long long实现高精度

    typedef long long LL;
    const LL Base = (LL)1e9;
    
    struct Long {
        LL high, low;
        Long(LL x = 0) : low(x) {high = 0;}
        friend Long operator + (const Long &a, const Long &b) {
            Long c; c.high = a.high + b.high, c.low = a.low + b.low;
            if (c.high >= 0 && c.low >= Base) c.high += c.low / Base, c.low = c.low % Base;
            if (c.high <= 0 && c.low <= -Base) c.high += c.low / Base, c.low = c.low % Base;
            if (c.high > 0 && c.low < 0) c.high --, c.low += Base;
            if (c.high < 0 && c.low >= Base) c.high ++, c.low -= Base;
            return c;
        }
        friend bool operator <(const Long &a, const Long &b) {
            return a.high == b.high ? a.low < b.low : a.high < b.high;
        }
        friend Long max(const Long &a, const Long &b) {return a < b ? b : a;}
    };

     

    展开全文
  • 高精度算法

    2018-10-26 20:15:38
    高精度算法,属于处理大数字的数学计算方法。在一般的科学计算中,会经常算到小数点后几百位或者更多,当然也可能是几千亿几百亿的大数字。一般这类数字我们统称为高精度数,高精度算法是用计算机对于超大数据的一种...

    高精度

    1.什么是高精度

    高精度算法,属于处理大数字的数学计算方法。在一般的科学计算中,会经常算到小数点后几百位或者更多,当然也可能是几千亿几百亿的大数字。一般这类数字我们统称为高精度数,高精度算法是用计算机对于超大数据的一种模拟加,减,乘,除,乘方,阶乘,开方等运算。对于非常庞大的数字无法在计算机中正常存储,于是,我们可以将这个数字拆开,拆成一位一位的,或者是几位几位的存储到一个数组中, 用一个数组去表示一个数字,这样这个数字就被称为是高精度数。高精度算法就是能处理高精度数各种运算的算法,但又因其特殊性,故从普通数的算法中分离,自成一家。

    对于这类问题,不要指望long double这些东西了,基本数据类型不可能存的下。我们可以把这两个数当成字符串输入到数组中,然后模拟手动的竖式运算(不会的话,回去上小学)得出结果。

    说白了,高精度计算就是解决long long也解决不了的问题。

    2.高精度的作用

    正如上面所说的,高精度的作用就是对于一些异常之大的数字进行加减乘除乘方阶乘开方等运算。比如给你一道a+b的题目,读入a和b,让你输出它们的和,但a和b的范围都是小于等于10的6666次方,这个时候你就只能用高精度了。

    3.高精度读入处理数据

    当一个数据很大的时候,我们用一个整数类型是存不下的,所以我们可以先用一个字符串输入,这样就可以输入很长的数,然后再利用字符串函数和操作运算,将每一位数取出,存入一个数组里,我们用数组里的每一位表示这个数的每一个数位。

    例如:998244353用数组储存下来,a{3,5,3,4,4,2,8,9,9},一般是倒着存(从低位到高位,因为整数没有除个位以下的数位,但你的最高位还可以进位,那么你就又要开一个位置来存这个新的最高位)。

    高精度读入Code

    char s[6666];
    int a[6666];
     
    int main(){
        scanf("%s",s+1);//用字符串读入
        len=strlen(s+1);//这个数的长度为len
        for(int i=1;i<=len;i++){
            a[i]=s[len-i+1]-'0';//倒叙储存,每一位存一个数
        }
        return 0;
    }
    

    高精度输出Code

    
    int a[6666]
     
    void write(int a[]){
        for(int i=lena;i>0;i--){
            printf("%d",a[i]);//一位一位输出这个数
        }
    }
    

    4.高精度比较大小

    处理完数据之后,假设我们要比较两个数那个大怎么办呢?

    我们先模拟比较1314520和1314530,首先我们看两个数的长度(即len1和len2)如果哪个数的len更长一点,那么这个数肯定要比另一个数大,否则我们才继续比较下去,这里两个数的长度是一样的,所以接下来我们就看这两个数的最高位(即1和1),相等,则继续比较下一位(3和3),也一样,继续比较下一位…直到比到十位的时候(2和3),因为2<3,所以第一个数<第二个数,直接退出。

    所以,高精度比较大小的步骤大致如下:

    1、比较两个数的长度,长度更长的数越大。

    2、如果两个数长度相等,那么就从高位到低位一位一位比较,如果某一位数字不同时,较大的数大。否则继续比较下一位。

    3、如果比到最后都没有比出谁大谁小,就说明这两个数一样大。

    高精度比较大小Code

    //比较a和b的大小,如果a>b则返回真,否则返回假
    int a[6666],b[6666];
     
    int compare(){
        if(lena>lenb) return 1;//lena表示a这个数的长度,lenb则表示b的长度
        if(lenb>lena) return 0;//步骤1
        for(int i=lena;i>0;i--){//从高位到底位一位一位比较
            if(a[i]>b[i]) return 1;
            if(b[i]>a[i]) return 0;
        }//步骤2
        return 0;//步骤3,a=b,即a不大于b
    }
    

    5.高精度处理进位与借位

    一、那么我们怎么处理进位呢?

    其实也很简单,我们再来模拟一下(模拟大法好,不会也得会),1439+887的时候,首先我们最低位相加,得到16,那么答案最低位就是6,再进个1,然后两数的十位相加,3+8=11,然后再加上进位的1,就是11+1=12,所以答案十位就是2,再进1,4+8+1=13,答案百位是3,进1,1+0+1=2,答案千位是2。所以结果就是6232!哦,不对反了,是2326,呵呵,这里要注意一下,输出的时候是倒着输出的,千万不要忘了。

    总结一下,进位的步骤大致如下:

    1、将当前位置的数相加,当前位的结果就是当前结果除以10的余数。

    2、再讲当前结果除以10加到高位,表示进位。

    注意:有同学可能会有疑问,为什么一定要倒着储存这个数呢?顺着存不是更好吗?这里我举一个非常简单的例子,比如10+90,谁都知道答案是100,那么我们来看看顺着储存和倒着储存有什么区别:

    1.顺着存:a={1,0},b={9,0},当a的最高位(即数组第1位)加上b的最高位(即数组第2位)时我们是不是得进位?!?但是a的最高位是数组的第一位,那么我们要进位到a数组的第几个位置呢?第0个位置?太复杂了。还是存在第一个位置并把所有的数往数组右边移动一位?那更不行,时间复杂度又太高,所以不好办。

    2.倒着存:a={0,1},b={0,9},当a的最高位(即数组第2位)加上b的最高位(即数组第2位)时我们同样要进位,这个时候就好办了,直接进位到数组的第三位就好了,所以答案的数组就是{0,0,1},倒过来输出答案100。

    高精度进位Code

    int a[6666],b[6666],c[6666];
    int lena,lenb,lenc;
     
    int main(){
        lenc=max(lena,lenb);
        for(int i=1;i<=lenc;i++){
            c[i]=c[i]+a[i]+b[i];
            c[i+1]=c[i]/10;
            c[i]=c[i]%10;
        }
        while(c[lenc+1]>0) lenc++;//答案的长度有时还会增加
    }
    

    二、接下来讲讲当减法的时候如何借位

    1、将当前位置的数向减。

    2、如果结果大于或等于0就直接作为当前位的答案。

    3、否则将结果加10作为当前位的答案,在将高位的数-1即可。

    高精度借位Code

    int a[6666],b[6666],c[6666];
    int lena,lenb,lenc;
     
    int main(){
        lenc=max(lena,lenb);
        for(int i=1;i<=lenc;i++){
            c[i]=c[i]+a[i]-b[i];
            if(c[i]<0) c[i]=c[i]+10,c[i+1]=-1;
        }
        while(c[lenc]==0&&lenc>1) lenc--;//细节,如果a-b结果为0,那么也要输出一个0
    }
    

    6.高精度加法
    至此,就可以进行任意你想进行的运算了,首先我们来看看加法,其实上面的代码已经差不多写出来了。

    高精度加法Code

    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    int a[6666],b[6666],c[6666];
    int lena,lenb,lenc;
    char s1[6666],s2[6666];
     
    int main(){
        scanf("%s %s",s1+1,s2+1);
        lena=strlen(s1+1);
        lenb=strlen(s2+1);
        for(int i=1;i<=lena;i++) a[i]=s1[lena-i+1]-'0';
        for(int i=1;i<=lenb;i++) b[i]=s2[lenb-i+1]-'0';
        lenc=max(lena,lenb);
        for(int i=1;i<=lenc;i++){
            c[i]=c[i]+a[i]+b[i];
            c[i+1]=c[i]/10;
            c[i]=c[i]%10;
        }
        while(c[lenc+1]>0) lenc++;
        for(int i=lenc;i>0;i--) printf("%d",c[i]);
    }
    

    7.高精度减法
    高精度减法Code

    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    int a[6666],b[6666],c[6666];
    int lena,lenb,lenc;
    char s1[6666],s2[6666];
     
    int main(){
        scanf("%s %s",s1+1,s2+1);
        lena=strlen(s1+1);
        lenb=strlen(s2+1);
        if(lenb>lena||(lena==lenb&&s2>s1)){//如果第二个数比第一个数大,那么结果是负数
        	printf("-");
        	swap(s1,s2);//swap是C++自带函数可以直接调用
        	swap(lena,lenb);//别忘了交换长度
        }
        for(int i=1;i<=lena;i++) a[i]=s1[lena-i+1]-'0';
        for(int i=1;i<=lenb;i++) b[i]=s2[lenb-i+1]-'0';
        lenc=max(lena,lenb);
        for(int i=1;i<=lenc;i++){
            c[i]=c[i]+a[i]-b[i];
            if(c[i]<0) c[i]=c[i]+10,c[i+1]=-1;
        }
        while(c[lenc]==0&&lenc>1) lenc--;
        for(int i=lenc;i>0;i--) printf("%d",c[i]);
    }
    

    8.高精度乘法
    1.高精度乘以单精度
    高精度乘以单精度Code

    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    int a[6666],b;
    int lena;
    char s1[6666];
     
    int main(){
        scanf("%s %d",s1+1,&b);
        lena=strlen(s1+1);
        for(int i=1;i<=lena;i++) a[i]=s1[lena-i+1]-'0';
        for(int i=1;i<=lena;i++) a[i]*=b;
        for(int i=1;i<=lena;i++){
        	a[i+1]+=a[i]/10;
        	a[i]%=10;
        }
        while(a[lena+1]>0) lena++;
        for(int i=lena;i>0;i--) printf("%d",a[i]);
    }
    

    2.高精度乘以高精度
    高精度乘以高精度Code

    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    int a[6666],b[6666],c[6666];
    int lena,lenb,lenc;
    char s1[6666],s2[6666];
     
    int main(){
        scanf("%s %s",s1+1,s2+1);
        lena=strlen(s1+1);
        lenb=strlen(s2+1);
        for(int i=1;i<=lena;i++) a[i]=s1[lena-i+1]-'0';
        for(int i=1;i<=lenb;i++) b[i]=s2[lenb-i+1]-'0';
        lenc=lena+lenb-1;
        for(int i=1;i<=lena;i++){
        	for(int j=1;j<=lenb;j++){
        		c[i+j-1]+=a[i]*b[j];
        		c[i+j]+=c[i+j-1]/10;
        		c[i+j-1]%=10;
    		}
    	}
        while(c[lenc+1]>0) lenc++;
        for(int i=lenc;i>0;i--) printf("%d",c[i]);
    }
    

    9.高精度除法

    1.高精度除以单精度
    手动模拟一下,我们只要记录一个r,表示当前的余数,然后不断除就可以了。

    高精度除以单精度Code

    
    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    int a[6666],b,r;
    int lena;
    char s1[6666];
     
    int main(){
        scanf("%s %d",s1+1,&b);
        lena=strlen(s1+1);
        for(int i=1;i<=lena;i++) a[i]=s1[lena-i+1]-'0';
        for(int i=lena;i>0;i--){
        	r=r*10+a[i];
        	a[i]=r/b;
        	r=r%b;
        }
        while(a[lena]==0&&lena>1) lena--;
        for(int i=lena;i>0;i--) printf("%d",a[i]);
    }
    

    2.高精度除以高精度
    很多人都不知道高精度如何整除以一个高精度,那么这里我就讲一下我的方法吧,可能不是最优的。

    我们知道除法是乘法的逆运算,那么我们为什么不可以看做是我们现在要求一个数乘以除数等于被除数呢?那么枚举肯定是不行的,这个时候我们就要用到二分啦(二分大发好啊~),没错高精度二分商,实际上就是一个高精度加法(mid=l+r),然后高精度除以单精度(mid/2),最后再高精度减法(r=mid-1)就可以实现二分了,我们二分出来的数直接高精度乘以高精度判断一下就可以了(代码中数组中的第0个位置表示此数的长度,瞬间暴露PC党…)。

    高精度除以高精度Code

    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    int a[6666],b[6666],ans[6666],t[6666],l[6666],r[6666],mid[6666];
    char s1[6666],s2[6666];
     
    int compare(int a[],int b[]){
        if(a[0]>b[0]) return 0;
        if(a[0]<b[0]) return 1;
        for(int i=a[0];i>0;i--){
            if(a[i]>b[i]) return 0;
            if(a[i]<b[i]) return 1;
        }
        return 1;
    }
     
    void add(){
        mid[0]=max(l[0],r[0]);
        for(int i=1;i<=mid[0];i++) mid[i]=l[i]+r[i];
        while(mid[mid[0]+1]>0) mid[0]++;
        for(int i=1;i<=mid[0];i++){
            mid[i+1]+=mid[i]/10;
            mid[i]%=10;
        }
        while(mid[mid[0]+1]>0) mid[0]++;
    }
     
    void times(){
        memset(t,0,sizeof(t));
        t[0]=b[0]+mid[0]-1;
        for(int i=1;i<=b[0];i++){
            for(int j=1;j<=mid[0];j++){
                t[i+j-1]+=b[i]*mid[j];
                t[i+j]+=t[i+j-1]/10;
                t[i+j-1]%=10;
            }
        }
        while(t[t[0]+1]>0) t[0]++;
    }
     
    void div(){
        int r=0;
        for(int i=mid[0];i>0;i--){
            r=r*10+mid[i];
            mid[i]=r/2;
            r%=2;
        }
        while(mid[mid[0]]==0) mid[0]--;
    }
     
    void left(){
        for(int i=0;i<=mid[0];i++) l[i]=ans[i]=mid[i];
        l[1]++;
        for(int i=1;i<=l[0];i++){
            l[i+1]+=l[i]/10;
            l[i]%=10;
        }
    }
     
    void right(){
        for(int i=0;i<=mid[0];i++) r[i]=mid[i];
        r[1]--;
        for(int i=1;i<=r[0];i++){
            if(r[i]<0){
                r[i+1]--;
                r[i]+=10;
            }
        }
    }
     
    int main(){
        scanf("%s %s",s1+1,s2+1);
        a[0]=r[0]=strlen(s1+1);
        b[0]=strlen(s2+1);
        for(int i=1;i<=a[0];i++) a[i]=r[i]=s1[a[0]-i+1]-'0';
        for(int i=1;i<=b[0];i++) b[i]=s2[b[0]-i+1]-'0';
        l[0]=ans[0]=1;
        while(compare(l,r)){
            add();
            div();
            times();
            if(compare(t,a)) left();
            else right();
        }
        for(int i=ans[0];i>0;i--) printf("%d",ans[i]);
        return 0;
    }
    

    码打的有点丑,不要介意…

    10.高精度开平方
    高精度开平方其实也还算比较简单,有一次考试就有一道原题,我一怒之下把它给切了。

    没错,还是二分。二分答案。利用高精度加法和高精度除以单精度可以实现二分的效果,然后直接高精度乘法乘起来再高精度比较一下大小,再用高精度减法移动一下l和r就可以了。其实这也算是高精度比较综合的做法了。码量虽然惊人,但其实高精度除以高精度改一改就好了

    高精度开平方Code

    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    int a[6666],b[6666],ans[6666],t[6666],l[6666],r[6666],mid[6666];
    char s1[6666],s2[6666];
     
    int compare(int a[],int b[]){
        if(a[0]>b[0]) return 0;
        if(a[0]<b[0]) return 1;
        for(int i=a[0];i>0;i--){
            if(a[i]>b[i]) return 0;
            if(a[i]<b[i]) return 1;
        }
        return 1;
    }
     
    void add(){
        mid[0]=max(l[0],r[0]);
        for(int i=1;i<=mid[0];i++) mid[i]=l[i]+r[i];
        while(mid[mid[0]+1]>0) mid[0]++;
        for(int i=1;i<=mid[0];i++){
            mid[i+1]+=mid[i]/10;
            mid[i]%=10;
        }
        while(mid[mid[0]+1]>0) mid[0]++;
    }
     
    void times(){
        memset(t,0,sizeof(t));
        t[0]=mid[0]+mid[0]-1;
        for(int i=1;i<=mid[0];i++){
            for(int j=1;j<=mid[0];j++){
                t[i+j-1]+=mid[i]*mid[j];
                t[i+j]+=t[i+j-1]/10;
                t[i+j-1]%=10;
            }
        }
        while(t[t[0]+1]>0) t[0]++;
    }
     
    void div(){
        int r=0;
        for(int i=mid[0];i>0;i--){
            r=r*10+mid[i];
            mid[i]=r/2;
            r%=2;
        }
        while(mid[mid[0]]==0) mid[0]--;
    }
     
    void left(){
        for(int i=0;i<=mid[0];i++) l[i]=ans[i]=mid[i];
        l[1]++;
        for(int i=1;i<=l[0];i++){
            l[i+1]+=l[i]/10;
            l[i]%=10;
        }
    }
     
    void right(){
        for(int i=0;i<=mid[0];i++) r[i]=mid[i];
        r[1]--;
        for(int i=1;i<=r[0];i++){
            if(r[i]<0){
                r[i+1]--;
                r[i]+=10;
            }
        }
    }
     
    int main(){
        scanf("%s",s1+1);
        a[0]=r[0]=strlen(s1+1);
        for(int i=1;i<=a[0];i++) a[i]=r[i]=s1[a[0]-i+1]-'0';
        l[0]=ans[0]=1;
        while(compare(l,r)){
            add();
            div();
            times();
            if(compare(t,a)) left();
            else right();
        }
        for(int i=ans[0];i>0;i--) printf("%d",ans[i]);
        return 0;
    }
    

    11.高精度开n次方
    稍加处理即可:开平方时将二分的答案乘两次,那么开n次方不就是将二分出来的答案乘n次吗?

    高精度开n次方Code

    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    int n,a[6666],b[6666],ans[6666],t[6666],l[6666],r[6666],mid[6666];
    char s1[6666];
     
    int compare(int a[],int b[]){
        if(a[0]>b[0]) return 0;
        if(a[0]<b[0]) return 1;
        for(int i=a[0];i>0;i--){
            if(a[i]>b[i]) return 0;
            if(a[i]<b[i]) return 1;
        }
        return 1;
    }
     
    void add(){
        mid[0]=max(l[0],r[0]);
        for(int i=1;i<=mid[0];i++) mid[i]=l[i]+r[i];
        while(mid[mid[0]+1]>0) mid[0]++;
        for(int i=1;i<=mid[0];i++){
            mid[i+1]+=mid[i]/10;
            mid[i]%=10;
        }
        while(mid[mid[0]+1]>0) mid[0]++;
    }
     
    void times(){
        for(int i=0;i<=mid[0];i++) b[i]=mid[i];
        for(int k=1;k<=n-1;k++){
            memset(t,0,sizeof(t));
            t[0]=b[0]+mid[0]-1;
            for(int i=1;i<=b[0];i++){
                for(int j=1;j<=mid[0];j++){
                    t[i+j-1]+=b[i]*mid[j];
                    t[i+j]+=t[i+j-1]/10;
                    t[i+j-1]%=10;
                }
            }
            while(t[t[0]+1]>0) t[0]++;
            for(int i=0;i<=t[0];i++) b[i]=t[i];
        }
    }
     
    void div(){
        int r=0;
        for(int i=mid[0];i>0;i--){
            r=r*10+mid[i];
            mid[i]=r/2;
            r%=2;
        }
        while(mid[mid[0]]==0) mid[0]--;
    }
     
    void left(){
        for(int i=0;i<=mid[0];i++) l[i]=ans[i]=mid[i];
        l[1]++;
        for(int i=1;i<=l[0];i++){
            l[i+1]+=l[i]/10;
            l[i]%=10;
        }
    }
     
    void right(){
        for(int i=0;i<=mid[0];i++) r[i]=mid[i];
        r[1]--;
        for(int i=1;i<=r[0];i++){
            if(r[i]<0){
                r[i+1]--;			
                r[i]+=10;
            }
        }
    }
     
    int main(){
        scanf("%d\n",&n);
        scanf("%s",s1+1);
        a[0]=r[0]=strlen(s1+1);
        for(int i=1;i<=a[0];i++) a[i]=r[i]=s1[a[0]-i+1]-'0';
        l[0]=ans[0]=1;
        while(compare(l,r)){
            add();
            div();
            times();
            if(compare(t,a)) left();
            else right();
        }
        for(int i=ans[0];i>0;i--) printf("%d",ans[i]);
        return 0;
    }
    

    12.高精度小技巧——压位
    当我们学完所有高精度运算的时候,我们依然会发现一个问题,就是它的数会给你很大,以至于当你一位一位进行运算的时候时间会超时!那怎么办呢?难道真的没有解决的办法了吗?那你就太小看高精度了,其实解决这个问题的方法就是——压位。压位是什么?听我慢慢道来。我们可以发现导致高精度时间慢的原因是我们一位一位将这个数存了下来,那么我们可不可以在数组中的一个位置不止存一个数位呢?答案是肯定的。你可以存两位,三位,四位…其实我们压位的时候最少都要压十几位,因为你才压几位跟不压位的时间有什么区别呢?当我们压位的时候,如果你要压比如16位,那么一定要记得开long long或int64类型,这样你才存的下这个十几位的数,还要注意,当我们输出这个数的时候,当一个位置的数不满你压的位数时,比如你压了16位,但是数组当前的位置的这个数只有1位!!!这说明了什么?说明这个数是由前面的15个0和最后一位构成的,也就是说原来这个数是000000000000000X,但是你只输出了X,明显答案是不对的,比如说一个数是5200000000000000001314,那么你存的是a{ 1314,520000 },当输出的时候如果你只是按照数组中的数字输出,那么你的答案是5200001314,发现了吗?你少了中间的0!!!所以当我们输出的时候,我们要判断这个数是否是满你压的位数,如果不足,那么就要补0,但是最高位除外。这就是压位的基本思路了。

    1.高精度压位读入处理
    高精度压位读入处理Code

    const int mod=1000000000000000;
    char s[6666];
    int a[6666];
     
     
    int main(){
        scanf("%s",s+1);
        int len=strlen(s+1),st=1;
        for(int i=len;i>0;i--){
            x=x+(s[i]-'0')*st;
            st*=10;
            if(st==mod){
                st=1;x=0;
                a[++a[0]]=x;
            }
        }
    }
    

    2.高精度压位输出处理
    高精度压位输出处理Code

    
    const int mod=10000000000000000;
    char s[6666];
    int a[6666];
     
    int main(){
     
        printf("%d",a[a[0]]);
        for(i=a[0];i>0;i--){
            t=a[i],l=0;
            while(t>0){
                t/=10;l++;
            }
            for(j=1;j<=15-l;j++) printf("0");
            printf("%d",a[i]);
        }
    }
     
    

    更多的题目实现需要用已有的知识灵活变通。
    以上为高精度算法大部分内容。希望你能有所收获。

    展开全文
  • 高精度运算

    2020-11-17 09:18:14
    高精度算法(High Accuracy Algorithm)是处理大数字的数学计算方法。在一般的科学计算中,会经常算到小数点后几百位或者更多,当然也可能是几千亿几百亿的大数字。一般这类数字我们统称为高精度数,高精度算法是用...

    前言

    高精度算法(High Accuracy Algorithm)是处理大数字的数学计算方法。在一般的科学计算中,会经常算到小数点后几百位或者更多,当然也可能是几千亿几百亿的大数字。一般这类数字我们统称为高精度数,高精度算法是用计算机对于超大数据的一种模拟加,减,乘,除,乘方,阶乘,开方等运算。对于非常庞大的数字无法在计算机中正常存储,于是,将这个数字拆开,拆成一位一位的,或者是四位四位的存储到一个数组中, 用一个数组去表示一个数字,这样这个数字就被称为是高精度数。高精度算法就是能处理高精度数各种运算的算法,但又因其特殊性,故从普通数的算法中分离,自成一家。
                                                                                                                                          ________百度百科
    不知道是谁发明的,应该是因为数据太为毒瘤而发明的,不管了,直接进入正题

    高精度加法

    相信各位读者一定学过竖式,而高精度算法就是结合了我们学过的竖式而发明的算法。
    所以高精度加法就是直接模拟竖式加法。在这里插入图片描述
    注意有几个要点:
    1、做的时候可以把数字反着存,因为做竖式的时候我们要把做加法的数字往右移,也就相当于把这个数字翻过来往左对齐,也就是这样:
    在这里插入图片描述
    2、注意进位
    3、注意如果是最高位进了位,要更新答案的长度,比如说:99+1=100
    在这里插入图片描述

    反过来,
    在这里插入图片描述

    像这样在最高位的进位,答案的长度就变成三了。
    4、注意去掉前导零,有些毒瘤出题人会这样出数据:
    在这里插入图片描述
    但是我们的程序跑出来是这样的:
    在这里插入图片描述
    所以输出来是这样的:
    0000000000000000000245
    完美错掉,于是我们需要处理前导零
    所以代码就这样写:

    #include <bits/stdc++.h>
    using namespace std;
    char s1[505], s2[505];
    int a[505], b[505], c[505];
    int main()
    {
    	int la, lb, lc;
    	scanf("%s %s", s1, s2);
    	la = strlen(s1), lb = strlen(s2);
    	
    	
    	for(int i = 0; i < la; i++)
    		a[la - i] = s1[i] - '0';
    	for(int i = 0; i < lb; i++)
    		b[lb - i] = s2[i] - '0';
    
    
    	lc = max(la, lb) + 1;
    	for(int i = 1; i <= lc; i++)
    	{
    		c[i] += a[i] + b[i];
    		c[i + 1] = c[i] / 10;
    		c[i] = c[i] % 10;
    	}
    	if(c[lc] == 0 && lc > 0)
    		lc--;
    	for(int i = lc; i > 0; i--)
    		printf("%d", c[i]);
    	return 0;
    }
    

    高精度减法

    跟高精度加法一样,我们也是模拟竖式减法:

    同样有几个注意点:
    1、注意借位
    2、做的时候先判断哪个大哪个小,比如我要求A-B
          如果A>B那就可以直接做
          如果A<B,则AB交换,输出-,然后再求A-B
          如果A=B,则直接输出0就行了

    #include <bits/stdc++.h>
    using namespace std;
    #define MAXN 1005
    int len1, len2;
    char s1[MAXN], s2[MAXN], ans[MAXN];
    int cmp(char s1[], char s2[])
    {
    	int len1 = strlen(s1), len2 = strlen(s2);
    	if(len1 > len2)
            return 1;
    	else if(len1 < len2)
            return -1;
    	else
            return strcmp(s1, s2);
    }
    void sub(char s1[], char s2[])
    {
    	memset(ans,0, sizeof ans);
    	int len = max(len1, len2);
        int lens1 = strlen(s1);
    	for(int i = lens1 - 1, j = MAXN - 1; i >= 0; i--, j--)
    	{
    		s1[j] = s1[i] - '0';
    		s1[i] = 0;
    	}
        int lens2 = strlen(s2);
        for(int i = lens2 - 1, j = MAXN - 1; i >= 0; i--, j--)
    	{
    		s2[j] = s2[i] - '0';
    		s2[i] = 0;
    	}
    	for(int i = MAXN - 1; i >= MAXN - len; i--)
    	{
    		ans[i] += s1[i] - s2[i];
    		if(ans[i] < 0)
    		{
                ans[i - 1]--;
    			ans[i] += 10;
    		}
    	}
    	int anslen = 0;
    	while(ans[anslen] == 0)
            anslen++;
    	for(int j = 0; anslen < MAXN;)
    	{
    		ans[j++] = ans[anslen++] + 48;
    		ans[anslen - 1] = 0;
    	}
        return ;
    }
    int main()
    {
    	scanf("%s %s", s1, s2);
        len1 = strlen(s1);
        len2 = strlen(s2);
    	if(cmp(s1, s2) == 1)
    	{
    		sub(s1, s2);
    		printf("%s\n", ans);
    	}
    	else if(cmp(s1, s2) == -1)
    	{
            sub(s2, s1);
            printf("-%s\n", ans);
    	}
        else
    	    printf("0\n");
        return 0;
    }
    
    

    高精度乘法

    模拟竖式乘法,注意点和加法差不多

    #include <bits/stdc++.h>
    using namespace std;
    #define MAXN 1000005
    char num1[MAXN], num2[MAXN], res[MAXN];
    void multi(char *s1, char *s2, char *s3)
    {
        int len1 = strlen(s1), len2 = strlen(s2);
        for(register int i = 0; i < len1; i++)
        {
            for(register int j = 0; j < len2; j++)
            	s3[i + j + 1] += (s1[i] - 48) * (s2[j] - 48);
            for(register int k = len1 + len2 - 1; k > 0; k--)
    		{
                s3[k - 1] += s3[k] / 10;
                s3[k] = s3[k] % 10;
            }
        }
        return ;
    }
    int main()
    {
    	scanf("%s",num1);
    	scanf("%s",num2);
    	int len1 = strlen(num1), len2 = strlen(num2);
    	multi(num1, num2, res);
    	int i = 0;
    	while(res[i] == 0 && i < len1 + len2)
            i++;
    	if(i == len1 + len2)
            printf("0");                                       //结果为0的情况
    	else
    	{
    		for(; i < strlen(num1) + strlen(num2); i++)
    		printf("%c", res[i] + 48);
    	}
        return 0;
    }
    

    高精度除法

    高精度除法是这四个中最难的,考虑的点很多
    先举个例子:
    173÷23173 ÷ 23
    在这里插入图片描述
    23有两位,所以先和173的前两位比较,小了,于是加上后面的一位一起比较
    在这里插入图片描述
    好,比23大了,于是直接算173÷23173÷23,答案是7,没有数了结束
    还有一种情况,就是结果中间有0。在这里插入图片描述
    这种情况要注意处理,剩下的直接模拟就行了。

    直接加一位算一次就行了,注意答案为0的情况

    #include<bits/stdc++.h>
    using namespace std;
    char a[1005],z[1005];
    long long b, len, l1, cnt = 0, s;
    void w(char a[])
    {
        for(int i = 0; i < len; i++)
            a[i] -= '0';
        return ;
    }
    int main()
    {
        cin>>a;
        cin>>b;
        len=strlen(a);
        w(a);
        bool flag = false;
        int i = 0;
        while(i < len)
        {
            s = s * 10 + a[i];
            if(s / b)
                flag = true;
            if(flag)
            {
                z[cnt++] = s / b + '0';
                s %= b;
            }
            i++;
        }
        // if(cnt == 0)
        //     cout << 0 << endl << s << endl;
        // else
            cout << z << endl << s << endl;
        return 0;
    }
    
    
    展开全文
  • 高精度加、减、乘、除算法实现详解

    万次阅读 多人点赞 2018-04-16 22:52:47
    在说高精度加减乘除运算之前,我们先搞明白什么是高精度运算? 实际上高精度就是说参与运算的数据和运算结果的范围,超出标准数据类型能表示的数据大小范围的运算。...这时就要用到高精度算法了。 ...

           在说高精度加减乘除运算之前,我们先搞明白什么是高精度运算?

           实际上高精度就是说参与运算的数据和运算结果的范围,超出标准数据类型能表示的数据大小范围的运算。这个时候,如果要得到正确的计算结果,显然不能依靠普通方法实现了。而要在普通运算原理的基础上,加以辅助算法来实现超大数据的计算。例如:求两个100位的数据的和,或者计算两个100位的数字乘积。这时就要用到高精度算法了。

        一、高精度加法:

        高精度加法的实现原理:

    1、计算结果的位数
    358934760892734899共18位
    38960302975237462共17位
    故结果不会超过19位。
    2、将要计算的数字分割成多段,按照顺序排列(这里以0-32767作为每一存储单位存储的数的限制):

    (为提高空间利用效率,可以一个存储单位存储多位数。)
    3、将两数相加。

    4、输出结果。
    从高位到低位依次输出。除最高位以外,其他低位上不足4位的要在前面补上0。

    5.代码实现如下

    #include<iostream>  
    #include<cstring>  
    using namespace std;  
    int main()  
    {  
      string str1,str2;  
      int a[250],b[250],len;   //数组的大小决定了计算的高精度最大位数  
      int i;  
      memset(a,0,sizeof(a));  
      memset(b,0,sizeof(b));  
      cin>>str1>>str2;   //输入两个字符串  
      a[0]=str1.length();  //取得第一个字符串的长度  
      for(i=1;i<=a[0];i++)  //把第一个字符串转换为整数,存放在数组a中  
        a[i]=str1[a[0]-i]-'0';  
      b[0]=str2.length();   //取得第二个字符串长度  
      for(i=1;i<=b[0];i++)   //把第二个字符串中的每一位转换为整数,存放在数组B中  
        b[i]=str2[b[0]-i]-'0';  
      len=(a[0]>b[0]?a[0]:b[0]);   //取两个字符串最大的长度  
      for(i=1;i<=len;i++)   //做按位加法,同时处理进位  
      {  
        a[i]+=b[i];  
        a[i+1]+=a[i]/10;  
        a[i]%=10;     
      }  
      len++;    //下面是去掉最高位的0,然后输出。  
      while((a[len]==0)&&(len>1)) len--;  
      for(i=len;i>=1;i--)  
        cout<<a[i];  
      return 0;   
    }  
       
    //注意:两个数相加,结果的位数,应该比两个数中大的那个数多一位。 

    二、高精度减法:

      高精度减法的实现原理:

       1.高精度减法相比高精度加法来说,稍微复杂一点,因为减法在差为负数时处理的细节更多一点:当被减数小于减数时,差为负数,差的绝对值是减数减去被减数;在程序实现上用一个变量来存储符号位,用另一个数组存差的绝对值。

       2.实现流程

    (1).先比较大小

    (2).决定输出符号,为正还是为负

    (3).按位减法,并注意处理借位

       3.代码实现如下:

    #include<iostream>  
    using namespace std;  
    int compare(string s1,string s2);  
    int main()  
    {  
      string str1,str2;  
      int a[250],b[250],len;  
      int i;  
      memset(a,0,sizeof(a));  
      memset(b,0,sizeof(b));  
      cin>>str1>>str2;  
      a[0]=str1.length();  
      for(i=1;i<=a[0];i++)  
        a[i]=str1[a[0]-i]-'0';  
      b[0]=str2.length();  
      for(i=1;i<=b[0];i++)  
        b[i]=str2[b[0]-i]-'0';  
      if((compare(str1,str2))==0)  //大于等于,做按位减,并处理借位。  
      {  
        for(i=1;i<=a[0];i++)  
          {a[i]-=b[i];  
           if (a[i]<0) {a[i+1]--;a[i]+=10;}  
          }  
        a[0]++;  
        while((a[a[0]]==0)&&(a[0]>1)) a[0]--;  
        for(i=a[0];i>=1;i--)  
          cout<<a[i];  
        cout<<endl;   
      }                            
      else  
      {  
        cout<<'-';  //小于就输出负号  
        for(i=1;i<=b[0];i++)  //做按位减,大的减小的  
          {b[i]-=a[i];  
           if (b[i]<0) {b[i+1]--;b[i]+=10;}  
          }  
        b[0]++;  
        while((b[b[0]]==0)&&(b[0]>1)) b[0]--;  
        for(i=b[0];i>=1;i--)  
          cout<<b[i];  
        cout<<endl;          
      }  
      return 0;   
    }  
    int compare(string s1,string s2)  //比较字符串(两个数)数字的大小,大于等于返回0,小于返回1。  
    {  
      if(s1.length()>s2.length()) return 0;  //先比较长度,哪个字符串长,对应的那个数就大  
      if(s1.length()<s2.length()) return 1;  
      for(int i=0;i<=s1.length();i++)  //长度相同时,就一位一位比较。  
      {  
        if(s1[i]>s2[i]) return 0;  
        if(s1[i]<s2[i]) return 1;                            
      }  
      return 0;   //如果长度相同,每一位也一样,就返回0,说明相等  
    }  

    三、高精度乘法实现

        高精度乘法实现原理:

       1.由于数字较大,无法使用简单的数据结构进行存储,选用数组和字符串来存储数字,字符串方便我们对于高位整数的输入,而整形数组的简便有利于每个位数的计算,结合两者优点便可实现高精度乘法。

        2.实现过程:

    (1).通过两个字符串输入两个整数

    (2).引入两个数组,将每个整数切割存储到数组里面

    (3).进行每一位的运算

    (4).处理进位

    (5).输出结果

      3.代码实现如下:

    #include<iostream>  
    #include<cstring>  
    using namespace std;  
    int main()  
    {  
      string str1,str2;  
      int a[250],b[250],c[500],len;    //250位以内的两个数相乘  
      int i,j;  
      memset(a,0,sizeof(a));  
      memset(b,0,sizeof(b));  
      cin>>str1>>str2;  
      a[0]=str1.length();  
      for(i=1;i<=a[0];i++)  
        a[i]=str1[a[0]-i]-'0';  
      b[0]=str2.length();  
      for(i=1;i<=b[0];i++)  
        b[i]=str2[b[0]-i]-'0';  
      memset(c,0,sizeof(c));  
      for(i=1;i<=a[0];i++)   //做按位乘法同时处理进位,注意循环内语句的写法。  
        for(j=1;j<=b[0];j++)  
        {  
        c[i+j-1]+=a[i]*b[j];  
        c[i+j]+=c[i+j-1]/10;  
        c[i+j-1]%=10;     
        }  
      len=a[0]+b[0]+1;  //去掉最高位的0,然后输出  
      while((c[len]==0)&&(len>1)) len--;   //为什么此处要len>1??  
      for(i=len;i>=1;i--)  
        cout<<c[i];  
      return 0;   
    }  

    四、高精度除法实现

    高精度除法实现原理:高精度除法这一块比较复杂,它可以分为两种情况:

    第一种情况:高精除以低精,实际上就是对被除的每一位,包括前面的余数都除以除数。

    代码实现如下:

    #include<iostream>
    #include<cstring>
    #include<cstdio>
    using namespace std;
    int main()
    {
        char a1[100],c1[100];
        int a[100],c[100],lena,i,x=0,lenc,b;
        memset(a,0,sizeof(a));
        memset(c,0,sizeof(c));
        gets(a1);  //输入高精度被除数 
        cin>>b;    //输入低精度除数 
        lena=strlen(a1);
        for (i=0;i<=lena-1;i++)
            a[i+1]=a1[i]-48;   //将高精度被除数放入a数组 
        for (i=1;i<=lena;i++)            //按位相除
            {
                c[i]=(x*10+a[i])/b;
                    x=(x*10+a[i])%b;
            }
        lenc=1;
        while (c[lenc]==0&&lenc<lena) 
        lenc++;       //删除前导0
        for (i=lenc;i<=lena;i++) 
        cout<<c[i];
        cout<<endl;
        return 0;
    }

    第二种情况:高精除以高精

    代码实现如下:

    #include<iostream>
    #include<cstring>
    using namespace std;
    int a[100],b[100],c[100];
    int compare(int a[],int b[])//比较a、b,若a>b为1;若a<b为-1;若a=b为0
    {
        int i;
        if(a[0]>b[0])
            return 1;
        if(a[0]<b[0])
            return -1;
        for(i=a[0];i>0;i--)//从高位到低位比较
        {
            if(a[i]>b[i])
                return 1;
            if(a[i]<b[i])
                return -1;
        }
        return 0;
    }
    
    void subduction(int a[],int b[])//计算a=a-b
    {
        int flag;
        int i;
    
        flag=compare(a,b);
        if(flag==0)//相等
        {
            a[0]=0;
            return;
        }
        if(flag==1)//大于
        {
            for(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]]==0)//删除前导0
                a[0]--;
            return;
        }
    }
    int main()
    {
        char str1[100],str2[100];
        int i,j;
    
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(c,0,sizeof(c));
    
        cin>>str1>>str2;
        a[0]=strlen(str1);//a[0]存储串1的位数
        b[0]=strlen(str2);//b[0]存储串2的位数
        for(i=1;i<=a[0];i++)
            a[i]=str1[a[0]-i]-'0';
        for(i=1;i<=b[0];i++)
            b[i]=str2[b[0]-i]-'0';
    
    
        int temp[100];
        c[0]=a[0]-b[0]+1;
        for(i=c[0];i>0;i--)
        {
            memset(temp,0,sizeof(temp));
    
            for(j=1;j<=b[0];j++)//从i开始的地方,复制数组b到数组temp
                temp[j+i-1]=b[j];
            temp[0]=b[0]+i-1;
    
            while(compare(a,temp)>=0)//用减法模拟
            {
                c[i]++;
                subduction(a,temp);
            }
        }
    
        while(c[0]>0&&c[c[0]]==0)//删除前导0
            c[0]--;
    
        cout<<"商为:";
        if(c[0]==0)//输出结果
            cout<<0<<endl;
        else
        {
            for(i=c[0];i>0;i--)
                cout<<c[i];
            cout<<endl;
        }
    
        cout<<"余数为:";
        if(a[0]==0)//输出余数
            cout<<0<<endl;
        else
        {
            for(i=a[0];i>0;i--)
                cout<<a[i];
            cout<<endl;
        }
    
        return 0;
    }
    展开全文
  • 【算法】高精度算法讲解

    万次阅读 2015-03-16 16:33:11
    这时,就要用到高精度算法了 高精度使用数组来存储整数,模拟手算进行四则运算 2.高精度运算涉及到的问题 (1) 数据的输入 (2) 数据的存储 (3)数据的运算:进位和借位  (4)结果的输出:小数点的位置和处于...
  • 高精度算法-压位

    千次阅读 2018-07-31 07:12:18
    我们之前做过大整数类的运算的题目 大整数乘法 大整数加法 这个方法看似是无敌的,,, 但是那么如果是一个10000^10000位的数据呢? 数组根本开不到这么大的。。。 有这样的题目吗?...实际上我们一个数组空间...
  • C语言 高精度算法

    万次阅读 多人点赞 2014-08-18 12:30:07
    笔者笔者去年总结了Pascal里有关高精度计算的问题,首先高精度计算可以解决以下四个问题:    1. 加数,减数,运算结果的输入和存储:  运算因子超出了整型、实型能表示的范围,肯定不能直接用一个数的形式来...
  • C++高精度算法之高精度加法

    千次阅读 2017-06-04 09:26:50
    高精度加法 题目描述: 高精度加法 输入: 两个自然数a,b 输出: 结果 样例输入: 1  1
  • 高精度算法(C++)

    2019-07-13 13:21:24
    我们利用计算机进行数值计算,有时候会遇到这样的问题: n!① 的精确结果是多少? 当n小于30的时候,我们...这是由于计算机的特点是运算速度超级快,精确度高,因此利用计算机进行高精度的计算和处理是计算机的一...
  • 原地址:http://blog.sina.com.cn/s/blog_4fdb102b010087ng.html特别赞的一篇关于高精度的文章,特别感谢原作者!前言:由于计算机运算是有模运算,数据范围的表示有一定限制,如整型int(C++中int 与long相同)表达范围...
  • 高精度算法的两个基本问题:高精度数的表示和高精度数的基本运算 1.高精度数的表示: 首先我想到的是do while 循环逆序存放在数组之中,但书中用string接受并且将其转化成数字,存放在数组之中int arr[100]; ...
  • #include #include #include #include char s[10010]; int a[50001],sth[50001],p[10]; long long b,c; int main(){ gets(s); scanf("%d",&b); int len=strlen(s),th=0,xs,bbb=0; for(int i=0;i<len
  • 高精度算法(一)高精度加法

    千次阅读 2019-03-17 11:02:10
    学过编程的大家一定对int long 不陌生吧,那么自然是知道它们各自能表达的数范围,比如int能表示范围为2^32,这看起来很大,但在大数据时代的如今,不说是int 哪怕是long long也是不够的,那么为了使用或计算这些...
  • 高精度算法(加法)

    千次阅读 2009-07-05 00:19:00
    以前总是零零散散的写的高精度算法,现在想好好整理下,以后就不要再写了。 模拟整数相加过程,从个数相加。输入两个整数(当成字符串输入)然后把字符串倒置过来,方便从个位相加。用e来存放进位。d表示两个数相加的...
  • 蓝桥杯:高精度算法

    2017-04-19 10:55:33
    算法描述 由于a和b都比较大,所以不能直接使用语言中的标准数据类型来存储。对于这种问题,一般使用数组来处理。定义一个数组A,A[0]用于存储a的个位,A[1]用于存储a的十位,依此类推。同样可以用一个数组B来存储b。...
  • 这时,就要用到高精度算法了。 百度词条 高精度算法主要需要解决的问题: 1、超大数据的存储; 2、超大数据的计算。 运用的思想: 1、运用ascll码进行字符与数字之间的转换; 例如: (int)‘0’-48=0 2、...
  • C++高精度算法之比大小

    千次阅读 2017-06-08 13:50:21
    比大小 描述 给你两个很大的正数,你能不能判断出他们两个数的大小呢? 比如123456789123456789要大于123456789 输入 每组数据占一行,输入两个不超过1000位的10...如果a>b则输出“a>b”,如果a
  • C语言高精度算法(阶乘)

    千次阅读 2020-01-15 16:26:57
    高精度算法1 可以表示一个超过计算机数字标准范围的一个数比如1000!早已超过2^32但可以用高精度算法表示。 #include<stdio.h> int main() { int a[10000] = { 1 }, i, up, c, s,n,j; scanf_s("%d", &...
  • C++ 高精度算法及N的阶乘

    千次阅读 2017-03-10 22:27:14
    高精度算法
  • 圆周率高精度算法

    千次阅读 2018-08-11 16:34:45
    #include&lt;stdio.h&gt; #define MAX 1000000 //f数组要足够大,否则计算较多位数时可能会发生数组越界 #define WEI 100 // 小数点后位数(必须是4的倍数) int a,b,c,d,e,f[MAX],g;...
  • 阶乘和(高精度算法

    千次阅读 2018-07-26 20:22:35
    (对于自然数N的阶乘,当N比较小时,可以32位整数int范围内准确表示 。例如12!=479001600(231-1)  而20!=2432902008176640000(263-1)可以在64位整数long long int范围内准确表示 ,但是 N取值更大时,N!...
  • 高精度算法(C/C++)

    2020-01-28 16:28:14
    高精度算法 (C/C++) 做ACM题的时候,经常遇到大数的加减乘除,乘幂,阶乘的计算,这时给定的数据类型往往不够表示最后结果,这时就需要用到高精度算法高精度算法的本质是把大数拆成若干固定长度的块,然后对每...
  • 小白C语言写高精度算法(加法)

    千次阅读 2017-04-15 13:30:34
    基本思路 用字符数组获取两个加数,用两个整形数组分别转存两个加数中的每一位,用手算加法的思路处理进位问题(代码中体现)#include #include #define N 100 int main() { char cNum1[N],cNum2[N];...
  • 目录试题 基础练习 高精度加法要点解题思路思路一:比较A、B数组长度大小,分阶段处理代码思路二:将较短的数组的长度变得和较长数组的长度一样代码 试题 基础练习 高精度加法 资源限制 时间限制:1.0s 内存限制:...
  • 高精度算法之累加

    2019-03-31 17:40:34
    高精度方法,求s=1+2+3+……+n的精确值(n以一般整数输入)。 Input 一行一个整数n(<1000000) Output 输出1到n的累加和,一组数据占一行 Sample Input 10 Sample Output 55 思路:两个大...
  • C++高精度算法之高精度减法

    千次阅读 2017-06-09 18:02:42
    高精度减法 题目描述 高精度减法 输入 两个整数a,b(第二个可能比第一个大) 输出 结果(是负数要输出负号) 样例输入 2 1 样例输出 1 说明 20%数据a,b在long long范围内 100%数据0 题目解析 样例解析: ...
  • C++高精度运算模板

    万次阅读 2014-04-06 17:16:22
    用C++实现大数类

空空如也

1 2 3 4 5 ... 20
收藏数 324,624
精华内容 129,849
关键字:

高精度算法