• C++高精度算法

    C++高精度算法

    描述

    如果要计算的数超过了long long怎么解决? —>使用高精度加减乘除，简单理解就是 很大的数进行加减乘除。

    1. 高精度加法

    1. 思路

    1. 创建对应的数组变量及其他变量
    2. 输入字符串
    3. 将读入的数据转化为整数类型，并逆序（反转）存储到数组中
    4. 将两个数组做累加(注意进位)
    5. 判断最高位是否为0，大于0代表进位了，则让长度加1
    6. 倒序输出

    2. 代码

    #include
using namespace std;

int a[510], b[510], c[510];//a:被加数  b:加数  c:和 
int main(){
	// 1. 输入字符串 
    string str1,str2;
    cin >> str1 >> str2;
    // 2. "1,2,3,4"转换为{1,2,3,4},并且反转 {4,3,2,1}
    for (int i = 0; i < str1.size(); i ++)
        a[str1.size()-1 - i] = str1[i] - '0';
    for (int i = 0; i < str2.size(); i ++)
        b[str2.size()-1 - i] = str2[i] - '0';  
	// 3. 找两个字符串最大的个数，目的是为了将每一位计算完 
    int ans = max(str1.size(), str2.size());
    // 4. 相加(a+b) 
    for (int i = 0; i < ans; i ++){//遍历至最大长度，避免有的数字没计算 
        c[i] += a[i] + b[i];//相加 
        c[i+1] = c[i] / 10;// 进位 
        c[i] %= 10;//将加的结果求余10 得出第i位 
    }
    //4. 如果结果数组第ans位的数大于0(大于0代表进位了)，则让长度增加1 
    while(c[ans]>0) ans++;  
    //5. 倒序输出 
    for (int i = ans-1; i >= 0; i--)
        cout << c[i];
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    #include
using namespace std;

int a[500],b[500],c[501],ans[501],len_a,len_b,len_ans;//a:加数1  b:加数2  c:进位数组  ans:结果数组 

int main(){
	// 1. 输入字符串 
    string str1,str2;
    cin >> str1 >> str2;
	len_a = str1.length();
	len_b = str2.length();
    // 2. "1,2,3,4"转换为{1,2,3,4},并且反转 {4,3,2,1}
    for (int i = 0; i < str1.size(); i ++)
        a[str1.size()-1 - i] = str1[i] - '0';
    for (int i = 0; i < str2.size(); i ++)
        b[str2.size()-1 - i] = str2[i] - '0';  
	// 3. 找两个字符串最大的个数，目的是为了将每一位计算完 
	len_ans = max(len_a,len_b);
	// 4. 相加(a+b) 
	for(int i=0;i<=len_ans;i++){
		ans[i] = a[i] + b[i] + c[i];//结果数组 =（等于） 被加数 加上  加数 加上 进位的数  
		if(ans[i] > 9){//如果结果数组大于9，则进位 
			c[i+1] = ans[i] / 10;//给进位数组赋值 
			ans[i] %= 10; // 让结果数组大于9的数求余10，变成个位数 
		}
	} 
	//5. 如果结果数组len_ans位的数大于0，则让长度增加1 
	while(ans[len_ans]>0) len_ans++;
	//6. 倒叙输出 
	for(int i=len_ans-1;i>=0;i--) cout<<ans[i];
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32

    2. 高精度减法

    1. 思路

    1. 定义被减数a，减数b，结果c数组
    2. 输入被减数和减数，并且将数据倒叙存入数组中。
    3. 找两个字符串最大的个数，目的是为了将每一位计算完
    4. 将两个数组做相减（遍历至最大长度，避免有的数字没计算 ）。
    5. 去掉前导 0 。例如结果为：089，不需要0
    6. 循环遍历输出

    2. 代码

    #include
using namespace std;

int a[510], b[510], c[510];//a:被减数  b:减数  c:结果 
int main(){
	// 1. 输入字符串 
    string str1,str2;
    cin >> str1 >> str2;
    // 2. "1,2,3,4"转换为{1,2,3,4},并且反转 {4,3,2,1}
    for (int i = 0; i < str1.size(); i ++)
        a[str1.size()-1 - i] = str1[i] - '0';
    for (int i = 0; i < str2.size(); i ++)
        b[str2.size()-1 - i] = str2[i] - '0';  
	// 3. 找两个字符串最大的个数，目的是为了将每一位计算完 
    int ans = max(str1.size(), str2.size());
    // 4. 相减(a-b) 
    for (int i = 0; i < ans; i ++){//遍历至最大长度，避免有的数字没计算 
    	if(a[i] < b[i]){
        	a[i+1] -= 1;//向前借一位 
        	a[i] += 10;// 借一位以后加10 
		} 
        c[i] = a[i] - b[i]; 
    }
    //5. 如去掉前导 0 。例如结果为：089，不需要0
    while(c[ans-1]==0 && ans>1) ans--;  
    //6. 倒序输出 
    for (int i = ans-1; i >= 0; i--)
        cout << c[i];
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    #include
using namespace std;

int a[500],b[500],c[501],ans[501],len_a,len_b,len_ans;//a:被减数  b:减数  c:进位  ans:结果 

int main(){
	// 1. 输入字符串 
    string str1,str2;
    cin >> str1 >> str2;
	len_a = str1.length();
	len_b = str2.length(); 
    // 2. "1,2,3,4"转换为{1,2,3,4},并且反转 {4,3,2,1}
    for (int i = 0; i < str1.size(); i ++)
        a[str1.size()-1 - i] = str1[i] - '0';
    for (int i = 0; i < str2.size(); i ++)
        b[str2.size()-1 - i] = str2[i] - '0';  
	// 3. 找两个字符串最大的个数，目的是为了将每一位计算完 
	len_ans = max(len_a,len_b);
	// 4. 相减(a-b)
	for(int i=0;i<=len_ans;i++){
		ans[i] = a[i] - b[i] - c[i];//结果数组 =（等于） 被减数 减去  减数  减去 进位的数  
		if(ans[i] < 0){//如果结果数组小于0，则借位 
			ans[i] += 10;// 借1位，加上10 
			c[i+1]++;    // 进位数组加1 
		}
	} 
	//5. 如去掉前导 0 。例如结果为：089，不需要0
	while(len_ans>1 && ans[len_ans-1]==0) len_ans--;
	//6. 倒序输出 
	for(int i=len_ans-1;i>=0;i--) cout<<ans[i];
	return 0;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33

    3. 如果出现被减数的位数小于减数时呢？

    #include
using namespace std;

int a[510], b[510], c[510];//a:被减数  b:减数   c:结果 
int flag = 0;
int main(){
	// 1. 输入字符串 
    string str1,str2;
    cin >> str1 >> str2;
    //2. str1.size() < str2.size() 或者 两个数一样长并且被减数的数值小于减数时，才需要交换两数位置
    if(str1.size() < str2.size() || str1.size() == str2.size() && str1 < str2) {
    	string t = str1;
    	str1 = str2;
    	str2 = t;
    	flag = 1;
	}
    // 3. "1,2,3,4"转换为{1,2,3,4},并且反转 {4,3,2,1}
    for (int i = 0; i < str1.size(); i ++)
        a[str1.size()-1 - i] = str1[i] - '0';
    for (int i = 0; i < str2.size(); i ++)
        b[str2.size()-1 - i] = str2[i] - '0';  
	// 4. 找两个字符串最大的个数，目的是为了将每一位计算完 
    int ans = max(str1.size(), str2.size());
    // 5. 相减(a-b) 
    for (int i = 0; i < ans; i ++){//遍历至最大长度，避免有的数字没计算 
    	if(a[i] < b[i]){
        	a[i+1] -= 1;//向前借一位 
        	a[i] += 10;// 借一位以后加10 
    	}
		c[i] = a[i] - b[i]; 
    }
    //6.如去掉前导 0 。例如结果为：089，不需要0
    while(c[ans-1]==0 && ans>1) ans--;  
    //7. 倒叙输出 
    if(flag == 1) cout<<"-";
    for (int i = ans-1; i >= 0; i--)
        cout << c[i];
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39

    3. 高精度乘法

    1. 解法1

    1. 思路

    1. 输入字符串
    2. 将输入的字符串转化为int类型，并且反转
    3. 相乘(a*b),需要将每个数都乘一遍(乘法分配律)
    4. 去0
    5. 倒叙输出

    2. 代码

    #include
using namespace std;

int a[510], b[510], c[510];a:数1  b:数2   c:结果  
int main(){
	// 1. 输入字符串 
    string str1,str2;
    cin >> str1 >> str2;
    // 2. "1,2,3,4"转换为{1,2,3,4},并且反转 {4,3,2,1}
    for (int i = 0; i < str1.size(); i ++)
        a[str1.size()-1 - i] = str1[i] - '0';
    for (int i = 0; i < str2.size(); i ++)
        b[str2.size()-1 - i] = str2[i] - '0';  
        
    // 3. 相乘(a*b),需要将每个数都乘一遍
    for (int i = 0; i < str1.size(); i ++){ //a[i]  a数组每一位要进行乘法运算 
    	for(int j=0;j<str2.size();j++){		//b[j]  b数组每一项也要进行乘法运算 
    		c[i+j] += a[i]*b[j];//将a*b的结果放入c结果数组中，i=0,j=0 它们相乘结果放在c[0]中，i=0 j=1时  它们相乘结果放在c[1]中 
	    	c[i+j+1] += c[i+j]/10;//加法进位，因为两个数有可能会大于10 
	    	c[i+j] %= 10;//将乘的结果求余10 得出第i位  
		}
    }
    // 4. 去前导零，如果结果数组第ans-1位的数等于0，则让长度减1 
    int ans = str1.size() + str2.size();// 两个数相乘不会超过 这两个数的长度 
    while(c[ans-1]==0 && ans>1) ans--;    
    //5. 倒序输出
    for (int i = ans-1; i >= 0; i--)
        cout << c[i];
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

    2. 解法2

    思路：

    1. 输入字符串
    2. 将输入的字符串转化为int类型，并且反转
    3. 相乘(a*b),需要将每个数都乘一遍(乘法分配律)
    4. 处理进位问题
    5. 处理0的问题
    6. 倒叙输出
    #include
using namespace std;

int a[500],b[500],c[501],ans[501],len_a,len_b,len_ans; 

int main(){
	// 1. 输入字符串 
    string str1,str2;
    cin >> str1 >> str2;
	len_a = str1.length();
	len_b = str2.length();
    // 2. "1,2,3,4"转换为{1,2,3,4},并且反转 {4,3,2,1}
    for (int i = 0; i < str1.size(); i ++)
        a[str1.size()-1 - i] = str1[i] - '0';
    for (int i = 0; i < str2.size(); i ++)
        b[str2.size()-1 - i] = str2[i] - '0';  
	// 3. 相乘(a*b) 
	for(int i=0;i<=len_a;i++){
		for(int j=0;j<len_b;j++){
			ans[i+j] += a[i] * b[j];
		} 
	} 
	// 4. 处理进位问题 
	len_ans = len_a + len_b;
	for(int i=0;i<len_ans;i++){
		if(ans[i]>9){
			ans[i+1] += ans[i]/10;
			ans[i] %=10; 
		}
	}
	//5. 处理0的问题 
	while(ans[len_ans-1]==0 && len_ans>1) len_ans--; //如果结果数组len_ans位的数大于0，则让长度减-  
	//6. 倒叙输出 
	for(int i=len_ans-1;i>=0;i--) cout<<ans[i];
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36

    4. 高精度除法

    思路：

    1. 输入字符串
    2. "1,2,3,4"转换为{1,2,3,4}
    3. 相除(a/b)
    4. 处理0的问题（通过变量将数组前面的0舍掉）
    5. 倒叙输出
    #include
using namespace std;

int a[500],b,c[501]; // a:被除数  b:除数  c:结果 

int main(){
	// 1. 输入字符串 
    string str1;
    cin >> str1 >> b;
	int len = str1.size();
    // 2. "1,2,3,4"转换为{1,2,3,4}
    for (int i = 0; i < len; i ++)
        a[i] = str1[i] - '0';
	// 3. 相除(a/b) 
	int x = 0;//变量x用来存放余数 
	for(int i=0;i<=len;i++){ 
		c[i] = (x * 10 + a[i]) / b; 
		x = (x * 10 + a[i]) % b;
	} 
	//4. 处理0的问题（通过变量将数组前面的0舍掉） 
	int z = 0;//z代表从某个下标开始不是0 
	while(c[z]==0 && z<len) z++; //如果结果数组第z位的数等于0，则让长度加1 
	//5. 倒叙输出(注意：i不能从0开始了，因为第4步就是处理0的问题)
	for(int i=z;i<len;i++) cout<<c[i];
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
  • 相关阅读:
    Linux学习-52-Linux工作管理-后台命令运行管理
    AIX360-CEMExplainer: MNIST Example
    `英语` 2022/8/12
    昨天访问量破记录
    头部品牌集体扑街！2023年9月京东平板电视TOP10品牌排行榜出炉
    mvn deploy tongweb-embed-7.0.E.5_P3 依赖上传
    STM32实战总结：HAL之DMA
    【Qt】从开源项目QCAD中学习如何增强QLineEdit控件
    集成开发环境Pycharm的安装及模板设置
    DH、DHE、ECDHE加密算法
  • 原文地址：https://blog.csdn.net/m0_56945138/article/details/126754569