C++ 算法 高精度(较详细.)

这篇具有很好参考价值的文章主要介绍了C++ 算法 高精度(较详细.)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

                概念       

        在我们进行计算的过程中,经常会遇到几十位,甚至几百位的数字的计算问题,也有可能会遇到小数点后几十位,几百位的情况,而我们面对这样的情况下,   和 的数据范围显然是不够使用的了。因此这时,我们就需要引入一个新的算法,叫做高精度算法 .

         我们可以利用程序设计的方法去实现这样的高精度计算 . 介绍常用的几种高精度计算的方法 .

思想

        高精度算法本质上是用字符串模拟数字进行计算,再利用类似于数学里的竖式的形式,一位一位进行相关计算 .

处理

高精度计算中需要处理好以下几个问题:

1)数据的接收方法和存储方法

        数据的接收和存储:当输入的数很长时,可采用字符串方式输入,这样可输入位数很长的数,利用字符串函数和操作运算,将每一位取出,存入数组中 .

void init(int a[]) { // 传入数组
    string s;
    cin >> s; 
    len = s.length(); // s.length --> 计算字符串位数
    for(int i=1; i<=len; i++)     
        a[i] = s[len -i] - '0'; //将字符串s转换为数组a, 倒序存储
}

2)进位、借位的处理.

// 加法进位: c[i] = a[i] + b[i]

code:    if(c[i] >= 10) {
            c[i] %= 10;
            ++c[i++];
         }

//减法借位: c[i] = a[i] - b[i]

code:    if(a[i] < b[i]) {
             --a[i+1];
             a[i] += 10;   
         } 

//乘法进位: c[i + j - 1] = a[i] * b[j] + x + c[i + j - 1];
          x = c[i + j - 1] / 10;
          c[i + j - 1] % 10;

高精度加法 +

        输入两个数到变量中,然后用赋值语句求它们的和后输出 . But,我们知道,在 C++ 语言中任何数据类型都有一定表示范围. 当两个加数很大时,以前的算法显然不能求出精确解,因此我们需要寻求另一种方法 .在读小学时,我们做加法都采用竖式方法 . 这样我们方便写出两个整数相加的算法 .

C++ 算法 高精度(较详细.)C++ 算法 高精度(较详细.)

        如果我们用数组分别储存两个加数,用数组 储存结果。则上例有 :

#include <cstdio>
#include <cstring>

using namespace std;

int main() {
    char a1[5005], b1[5005]; //用字符存储数字
    int a[5005], b[5005], c[5005]; //c[i] 用来储存每位相加的结果
    int len_a, len_b, len_c = 1, x, i;

    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    memset(c, 0, sizeof(c));

    scanf("%s%s", a1, b1); //输入两个加数

    len_a = strlen(a1);
    len_b = strlen(b1);

    for(i=0; i<len_a; i++) a[len_a - i] = a1[i] - '0'; // 将加数放进a数组
    for(i=0; i<len_b; i++) b[len_b - i] = b1[i] - '0'; // 将另一个加数放进b数组

    x = 0; // x为进位
    while(len_c <= len_a || len_c <= len_b) {
        c[len_c] = a[len_c] + b[len_c] + x; // 两数相加,再加上前两个数进位的
        x = c[len_c] / 10; // 刷新进位
        c[len_c] %= 10; // 进位后剩下的
        len_c++; //位数加1
    }
    c[len_c] = x;
    if(c[len_c] == 0) { //判断首位是否为0
        len_c--; // 不输出此位
    }

    for(int i=len_c; i>=1; i--) {
        printf("%d", c[i]); //输出每一位的数
    }

    return 0;
}

高精度减法 -

        类似加法,同样使用竖式。在做减法运算时,需要注意的是:需要有借位处理。

#include <iostream>
#include <cstring>

int main() {
    int a[5005], b[5005], c[5005];
    int lena, lenb, lenc, i;
    char n[5005], n1[5005], n2[5005];

    std::memset(a, 0, sizeof(a));
    std::memset(b, 0, sizeof(b));
    std::memset(c, 0, sizeof(c));

    std::cin >> n1 >> n2; //输入被减数和减数

    lena = std::strlen(n1);
    lenb = std::strlen(n2);

    for(i=0; i<lena; i++) a[lena - i] = (int)n1[i] - '0';
    for(i=0; i<lenb; i++) b[lenb - i] = (int)n2[i] - '0'; //逆序存放排列

    i = 1;
    while(i <= lena || i <= lenb) {
        if(a[i] < b[i]) {
            c[i] = a[i] + 10 - b[i];
            a[i+1]--; //借位处理
        }
        else {
            c[i] = a[i] - b[i]; 
        }
        i++;
    }

    lenc = i;
    while(c[lenc] == 0 && lenc > 1) { //如果最后一位是0,是需要输出的
        lenc--;   // 不输出首位0
    }

    for(i=lenc; i>=1; i--) std::cout << c[i];

    return 0;
}

高精度乘法 ×

        类似加法,使用竖式。在做乘法时,同样也有进位。C++ 算法 高精度(较详细.)

        分析 数组的下标变化规律,可以写出以下关系式:          C++ 算法 高精度(较详细.)

       由此可见, 跟 乘积有关,跟上次的进位有关,跟还原 的值有关,分析下标规律,有 :

                                        C++ 算法 高精度(较详细.)

#include <iostream>
#include <cstring>

int main() {
	int a[105], b[105], c[10005];
	char n1[105], n2[105], lena, lenb, lenc, j, i, x;

	std::memset(a, 0, sizeof(a));
	std::memset(b, 0, sizeof(b));
	std::memset(c, 0, sizeof(c));
	
	std::cin >> n1 >> n2;
	
	lena = std::strlen(n1);
	lenb = std::strlen(n2);
	
	for(i=0; i<=lena-1; i++) a[lena - i] = n1[i] - 48; 
	for(i=0; i<=lenb-1; i++) b[lenb - i] = n2[i] - 48; // 倒序储存
	
	for(i=1; i<=lena; i++) {
		x = 0;
		for(j=1; j<=lenb; j++) {
			c[i + j - 1] = c[i + j - 1] + x + a[i] * b[j];
			x = c[i + j - 1] / 10; // 进位
			c[i + j - 1] %= 10; // 剩余
		}
		c[i + lenb] = x; // 进位的数
	}
	
	lenc = lena + lenb;
	while(c[lenc] == 0 && lenc > 1) {
		lenc--; // 删除前导0
	}
	
	for(i=lenc; i>=1; i--) {
		std::cout << c[i];
	}  // 输出每一位
	   
    std::cout << std::endl;
	
	return 0;
} 

除法 ÷

1)高精除以低精

        做除法时,每一次的商值都在 0~9 之间,每次求得的余数连接以后的若干位得到新的被除数,继续做除法。因此,在做高精度除法时,要涉及到乘法运算和减法运算,还有移位处理。当然,为了程序简洁,可以避免高精度乘法,用 0~9 次循环减法取代得到商的值。采用按位相除法

#include <iostream>

int main(){
    char n1[100];
    int a[100], c[100], lena, i, x = 0, lenc, b;
    
    std::memset(a, 0, sizeof(a));
    std::memset(c, 0, sizeof(c));
    
    std::cin >> n1 >> b;  
    lena = strlen(n1);

    for(i=1; i<=lena; i++) {
        a[i] = n1[i - 1] - '0'; //除法不需要逆序存放
    }

//-------------------------初始化------------------------------

    for(i=1; i<=lena; i++) {
        c[i] = (a[i] + x * 10) / b;  // 算上上一位剩下的继续除
        x = (a[i] + 10 * x) % b; // 求余
    }

    lenc = 1;
    while(c[lenc] == 0 && lenc < lena) {
        lenc++;
    }

    for(i=lenc; i<lena; i++) std::cout << c[i];

    return 0;
}

2)高精除以高精

        高精除以低精是对被除数的每一位(这里的"一位"包含前面的余数,以下都是如此)都除以除数,而高精除以高精则使用减法模拟除法,对被除数的每一位都减去除数,一直减到当前位置的数字(包含前面的余数)小于除数(由于每一位的数字小于10,所以对每一位最多进行10次运算),代码如下:

#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;

int a[50005], b[50005], c[50005], d;

void init(int a[]) {
	char s[50005];
	cin >> s;
	a[0] = strlen(s);		// 字符串存储,表示位数	
	for (int i=1; i<=a[0]; i++) {
		a[i] = s[a[0]-i] - 48;	// 正序储存
	} 	
}

void print(int a[]) {			
	if (a[0] == 0) {
		cout << 0 << endl;
		return;  // 位数为0,输出0
	}
	for (int i=a[0]; i>=1; i--) {
		cout << a[i];  // 输出函数
	}
	cout << endl;
	return;
} 

int compare(int a[], int b[]) {	
	if (a[0] > b[0]) {
		return 1; // 被减数大于减数
	} 
	if (a[0] < b[0]) {
		return -1; // 被减数小于减数
	}
	for (int i=a[0]; i>=1; i--) {	
		if (a[i] > b[i]) {
			return 1;
		} 
		if (a[i] < b[i]) {
			return -1;
		}   // 位数相同,找到第一位不同的进行比较
	} 
	return 0;					
}

void numcpy(int p[], int q[], int det) {
	for (int i=1; i<=p[0]; i++) {
		q[i+det-1] = p[i]; //复制p数组到q数组从det开始的地方
	}
	q[0] = p[0] + det - 1;
}

void jian(int a[], int b[]) {		
	int flag = compare(a, b);		 
	if (flag == 0)  {					
		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]]==0) {
			a[0]--;					
		} 
		return; 
	}				 
}  // 高精减法

void chugao(int a[], int b[], int c[]) {
	int tmp[50005];
	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]++;
			jian(a, tmp);	// 用减法模拟		
		} 
	}
	while (c[0] > 0 && c[c[0]] == 0) {
		c[0]--;
	}
	return;
}

int main() {
	memset(a, 0, sizeof(a));
	memset(b, 0, sizeof(b));
	memset(c, 0, sizeof(c));
	
	init(a);
	init(b);
	chugao(a,b,c);
	print(c);	
	
	return 0;
}

如果这篇文章对你有帮助的话,请来个三连~~你们的支持是对我max(鼓 励)🤑文章来源地址https://www.toymoban.com/news/detail-409219.html

到了这里,关于C++ 算法 高精度(较详细.)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【c++】算法:高精度(经典加减乘除){含解析(图解)}

    Hi~ o(* ̄▽ ̄*)ブ,今天来一起看看c++算法之高精度 之后会持续更新有关c++算法系列,欢迎观看!(#^.^#) 目录 前言 使用高精度的目的: 基本方法介绍:   一、A+B problem 基本思路解析: 具体步骤: 代码如下: 二、A-B problem 基本思路解析: ​编辑 具体步骤:  代码如下:  三

    2024年01月23日
    浏览(54)
  • (基础算法)高精度加法,高精度减法

    什么叫做高精度加法呢?包括接下来的高精度减法,高精度乘法与除法都是同一个道理。正常来讲的话加减乘除,四则运算的数字都是整数,也就是需要在int的范围之内,但当这个操作数变得非常\\\"大\\\"的时候( 其实就是一个字符串,比方说有一个数是20位,如果用整数视角来

    2024年02月01日
    浏览(55)
  • C++高精度问题

    C++中int不能超过2^31-1,最长的long long也不能超过2^63-1,所以我们在题目中如果碰到了很长很长的数,并且需要进行大数运算时,就需要高精度存储。 由于int和long long的限制,我们要想存放很长的数就需要利用数组存储,C++中可以利用STL中的vector容器存储 读取:  由于数据很大,

    2024年01月24日
    浏览(51)
  • C++实现高精度减法

    一、问题描述:        高精度算法是处理大数字的数学计算方法。在一般的科学计算中,会经常算到小数点后几百位或者更多,当然也可能是几千亿几百亿的大数字。一般这类数字我们统称为高精度数,高精度算法是用计算机对于超大数据的一种模拟加,减,乘,除,乘方

    2024年02月14日
    浏览(44)
  • 算法笔记——高精度算法(附源码)

    📖作者介绍:22级树莓人(计算机专业),热爱编程<目前在c++阶段, 因为最近参加新星计划算法赛道(白佬),所以加快了脚步,果然急迫感会增加动力 ——目标Windows,MySQL,Qt,数据结构与算法,Linux,多线程,会持续分享学习成果和小项目的 📖作者主页:热爱编程的

    2023年04月08日
    浏览(61)
  • 【算法】模拟,高精度

      P1601 A+B Problem(高精) - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 思路就是模拟,值得注意的就是要用字符串类型输入。存进自己的int数组时要倒着存,因为如果是正着存的话,进位会有点trouble。 时间复杂度O(max(m,n))    P1303 A*B Problem - 洛谷 | 计算机科学教育新生态 (lu

    2024年02月09日
    浏览(49)
  • 高精度算法详解

    首先要知道为什么需要高精度算法: 高精度算法是 处理大数字 的数学计算方法,当数字过大不能用 int 和 long long 存储时,我们就可以 使用string和vector类型 来存储他们的每一位,然后进行计算。 我们可以先把要输入的两个数字放到vector中存储,注意要 反着存(后边做加法

    2024年01月17日
    浏览(56)
  • 高精度算法笔记·····························

    加法 减法 乘法 除法 高精度加法的步骤: 1.高精度数字利用字符串读入 2.把字符串 翻转 存入两个整型数组A、B 3.从低位到高位,逐位求和,进位,存余 4.把数组C从高位到低位依次输出         1.2为准备         3为加法具体实现(0按位取反为-1,即-1时结束等价于=0)  

    2024年01月21日
    浏览(55)
  • 基于matlab的高精度信号峰值检测算法

    目录 1.算法描述 2.仿真效果预览 3.MATLAB核心程序 4.完整MATLAB        峰值检验是示波表中数据采集方式之一, 这种技术起源于存储深度不能满足捕获毛刺的需要。如果用模拟示波器去观察, 只有当毛刺信号是重复性的并且和主信号同步时, 才能看到毛刺信号 。由于毛刺源于其

    2024年02月12日
    浏览(47)
  • 求2的N次幂(C++)解决高精度运算

    ​👻内容专栏:《C/C++专栏》 🐨本文概括: 计算高精度的2的N次方数字。 🐼本文作者:花 碟 🐸发布时间:2023.6.22 为什么不直接利用int、float、double等类型进行存储计算,因为它们是存在有效数据范围的, 比如说 int 的范围是 -2147483648 ~ 2147483647 字节,数值最多占据10位,

    2024年02月10日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包