C++基础算法①——高精度加减法计算

高精度算法

• 1.导论
• 2.高精度+低精度
• 3.高精度+高精度
• 4.高精度减法

  1.导论

  当我们利用计算机进行数值计算，有时候会遇到这样的问题： n！的精确结果是多少？

  当n小于30的时候，我们当然可以通过电脑自带的计算器计算出来。但是当我们遇到 100! 的时候就没有办法直接计算出精确的结果。再比如，求两个20000位的数的和。

  那怎么解决精度缺失的问题？

  高精度算法（High Accuracy Algorithm） 是处理大数字的数学计算方法。

  • 在一般的科学计算中，会经常算到小数点后几百位或者更多，当然也可能是几千亿几百亿的大数字。一般这类数字我们统称为高精度数，高精度算法是用计算机对于超大数据的一种模拟加，减，乘，除，乘方，阶乘，开方等运算。对于非常庞大的数字无法在计算机中正常存储。
  • 于是，将这个数字拆开，拆成一位一位的，或者是四位四位的存储到一个数组中， 用一个数组去表示一个数字，这样这个数字就被称为是高精度数。
  • 高精度算法就是能处理高精度数各种运算的算法，但又因其特殊性，故从普通数的算法中分离，自成一家。
  • 高精度处理，实际上就是模拟法，模拟手算，它的原理与我们用竖式计算时一样的，不过在处理过程中要注意高精度数据的读入、转换储存、数据的计算、结果位数的计算、输出等几个问题。

    ---

    2.高精度+低精度

    有一个很大的数，例如 99999999999999999；一个小的数6666。如何把这两个数加起来呢？

    高精度的加法思想

    1. 把大数存到字符串;

    2. 字符串的每个字符数字都通过ASCII转换存到数组,

       注意的是要低位存在数组开头:a[i] = s[len-i-1]-‘0’;

    3. 加法进位的算式:

       ① a[i+1] += a[i]/10;

       ② a[i] %= 10;

    4. 数字溢出，长度+1;

    5. 反向输出结果;

    来看下我们怎么做的，以C++语言编程为例子。

    #include
    #include
    using namespace std;
    string s1;
    int a[1000],b; 
    int main(){
    	cin>>s1>>b; // 1.输入数值 
    

    代码中，s1数组存的是大数，b整数存小数。

    ① 1234 + 66

    ② 123456 + 99

    按照数学加法运算，是先个位数与个位数相加，也就是

    ① s1[3] + 6

    ② s1[5] + 9

    由上面可知，个位数+个位数的索引下标不一致，会增加编程难度。那可以考虑把数组倒序存储！个位数放到数组开头位置也就是s1[0]，那无论数值多大，数组下标都是s1[0] 开始进行加法的。

    //	s1存到数组a里面，记得转为整数
    	int len1 = s1.size(); //获取长度
    	for(int i=0;i
    		a[i] = s1[len1-i-1]-'0';
    	} 
    
    		a[i+1] += a[i] / 10;
    		a[i] = a[i] % 10;
    	}
    
    		a[len1+1] += a[len1]/10;
    		a[len1] %= 10;
    		len1++;
    	} 
    
    		cout
    	cins1>b;
    //	s1存到数组a里面，记得转为整数
    	int len1 = s1.size();
    	for(int i=0;i
    		a[i] = s1[len1-i-1]-'0';
    	} 
    	//3.进行加法运算。
    	a[0]+=b; // 5+9999 10004
    	//4.进位操作
    	for(int i=0;i
    		a[i+1] += a[i] / 10;
    		a[i] = a[i] % 10;
    	}
    	//5.考虑到数字溢出 
    	if(a[len]){
    		len++;
    	} 
    	//6.反向输出
    	for(int i=len1-1;i=0;i--){
    		cout
    //	1.输入值，长度 
    	cins1>s2;  
    	int len1 = s1.size();
    	int len2 = s2.size(); 
    //	2.把字符转为整数存到数组
    //  注意要个位存到数组开头 
    	for(int i=0;i
    		a[i] = s1[len1-i-1]-'0';
    	} 
    	for(int i=0;i
    		b[i] = s2[len2-i-1]-'0';
    	}
    
    		c[i]=a[i]+b[i];
    	}
    
    		c[i+1] += c[i]/10;
    		c[i] %= 10; 
    	}
    
    		len++;
    	} 
    	//7.反向输出 
    	for(int i=len-1;i=0;i--){
    		cout
    //	1.输入值，长度 
    	cins1s2;  
    	int len1 = s1.size();
    	int len2 = s2.size(); 
    //	2.把字符转为整数存到数组
    //  注意要个位存到数组开头 
    	for(int i=0;i
    		a[i] = s1[len1-i-1]-'0';
    	} 
    	for(int i=0;i
    		b[i] = s2[len2-i-1]-'0';
    	}
    //	3.获取最大的数。 
    	int len = max(len1,len2);
    	// 对各个位数进行相加 
    	for(int i=0;i
    		c[i]=a[i]+b[i];
    	}
    	//4.进位
    	for(int i=0;i
    		c[i+1] += c[i]/10;
    		c[i] %= 10; 
    	}
    	//5.溢出
    	while(c[len]==0 && len0){
    		len--;
    	} 
    	if(c[len]0){
    		len++;
    	} 
    	//6.反向输出 
    	for(int i=len-1;i=0;i--){
    		cout
    //	1.输入值
    	cins1s2;
    //	2.判断大小,固定s1恒大于s2 
    	if(s1.size()
    		swap(s1,s2); //交换值
    		cout
    		a[i] = s1[len1-i-1]-'0';
    	} 
    	for(int i=0;i
    		b[i] = s2[len2-i-1]-'0';
    	} 
    
    		if(a[i]
    			a[i+1]--; //被借位-- 
    			a[i]+=10; // 本位+10 
    		}
    		c[i] = a[i]-b[i];  //相减结果存到数组c
    	} 
    
    		len1--;
    	} 
    	//7.反向输出
    	for(int i=len1-1;i=0;i--){
    		cout
    //	1.输入值
    	cins1s2;
    //	2.判断大小,固定s1恒大于s2 
    	if(s1.size()
    		swap(s1,s2); //交换值
    		cout
    		a[i] = s1[len1-i-1]-'0';
    	} 
    	for(int i=0;i
    		b[i] = s2[len2-i-1]-'0';
    	} 
    	//5.减法运算 
    	for(int i=0;i
    		if(a[i]
    			a[i+1]--; //上位-- 
    			a[i]+=10; // 本位+10 
    		}
    		c[i] = a[i]-b[i]; 
    	} 
    	//6去除前导零
    	while(c[len1-1]==0 && len11){
    		len1--;
    	} 
    	//7.反向输出
    	for(int i=len1-1;i=0;i--){
    		cout