C++高精度算法

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

目录:

目录

前言: 

思路:

高精度加法:

高精度减法:

高精度乘法:

高精度除法:

 代码:

一、高精度加法

二、高精度减法 

三、高精度乘法 

四、高精度除法

最后


前言: 

        计算机最初、也是最重要的应用就是数值运算。在编程进行数值运算时,有时会遇到运算的精度要求特别高,远远超过各种数据类型的精度范围;有时数据又特别大,远远超过各种数据类型的极限值。这种情况下,就需要进行“高精度运算”。

        高精度运算首先要处理好数据的接受和存储问题,其次要处理好运算过程中的“进位”和“借位”问题。

引用自百度百科

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

思路:

高精度加法:

        用字符串输入两个数,再导入数组,然后每位相加,如果某位数字>10,则此位模10,下一位加一,最后用while循环去除前导零再输出即可。

高精度减法:

        用字符串输入两个数,再导入数组,判断是否后数比前数,如果是则输出负号再交换数组。然后按位相减不够借1,最后用while循环去除前导零再输出即可。

高精度乘法:

        导入方法与前面一样,导入后按乘法竖式思路相乘,再按常规思路进位。最后去除前导零就行了。

高精度除法:

        比较复杂不做过多解释。 

 代码:

一、高精度加法

#include<bits/stdc++.h>
using namespace std;
#define maxx 1145 //最长值(默认1145位)

char sa[maxx], sb[maxx];
int la, lb, lc, a[maxx], b[maxx], c[maxx];
int main() {
	scanf("%s %s", sa, sb);//读入字符串

	la = strlen(sa);
	lb = strlen(sb);
//	格式化字符串,看情况
//	memset(a, 0, sizeof(a));
//	memset(b, 0, sizeof(b));
//	memset(c, 0, sizeof(c));

//正序将字符串写入到数组A,B中
	for (int i = 0; i < la; i++) {
		a[la - i - 1] = sa[i] - '0';
	}
	for (int i = 0; i < lb; i++) {
		b[lb - i - 1] = sb[i] - '0';
	}

	lc = la > lb ? la : lb;//更新长度数据

	//模拟竖式加法
	for (int i = 0; i < lc; i++) {

		c[i] = a[i] + b[i] + c[i];
		if (c[i] > 10) { //进位
			c[i + 1] = 1;
			c[i] -= 10;
		}
	}
	if (c[lc] > 0)lc++;//更新长度

	//逆序打印输出
	for (int i = lc - 1; i >= 0; i--) {
		printf("%d", c[i]);
	}
	return 0;
}

二、高精度减法 

#include <bits/stdc++.h>
using namespace std;

#define maxx 1145 //最长值(默认1145位)
char sa[maxx], sb[maxx];
char tmp[maxx];//交换字符串
int la, lb, lc, a[maxx], b[maxx], c[maxx];

int main() {
	scanf("%s %s", sa, sb);//读入字符串

	la = strlen(sa);
	lb = strlen(sb);
	//判断最终的结果符号
	if ((la < lb) || (la == lb && strcmp(sa, sb) < 0)) {
		//被减数小于减数,结果为负数
		printf("-");
		//交换数据
		strcpy(tmp, sa);
		strcpy(sa, sb);
		strcpy(sb, tmp);
		//更新长度数据
		la = strlen(sa);
		lb = strlen(sb);
	}
//	格式化字符串,看情况
//	memset(a, 0, sizeof(a));
//	memset(b, 0, sizeof(b));
//	memset(c, 0, sizeof(c));

//倒序将字符串写入到数组A,B中
	for (int i = 0; i < la; i++) {
		a[i] = sa[la - i - 1] - '0';
	}
	for (int i = 0; i < lb; i++) {
		b[i] = sb[lb - i - 1] - '0';
	}

	//模拟竖式减法
	for (int i = 0; i < la; i++) {

		if (a[i] < b[i]) { //借位
			a[i + 1]--;
			a[i] += 10;
		}
		c[i] = a[i] - b[i];
	}

	//删除前导零
	for (int i = la - 1; i >= 0; i--) {
		//因为我们是从索引 0 开始,所以最高位是保存在 len-1
		if (0 == c[i] && la > 1) {
			//注意要有 la>1 这个条件。考虑特殊情况,加法结果为 00,我们实际要输出 0。
			la--;
		} else {
			//第一个不是零的最高位,结束删除
			break;
		}
	}

	//逆序打印输出
	for (int i = la - 1; i >= 0; i--) {
		printf("%d", c[i]);
	}
	return 0;
}

三、高精度乘法 

#include<bits/stdc++.h>
using namespace std;
#define maxx 1145
char sa[maxx], sb[maxx];
int la, lb, lc, jw, f, w, a[maxx], b[maxx], c[maxx * maxx];
int main() {
	scanf("%s", sa);
	scanf("%s", sb);
	la = strlen(sa);
	lb = strlen(sb);
	memset(a, 0, sizeof(a));
	memset(b, 0, sizeof(b));
	memset(c, 0, sizeof(c));
	for (int i = 0; i < la; i++) {
		a[la - i - 1] = sa[i] - '0';
	}
	for (int i = 0; i < lb; i++) {
		b[lb - i - 1] = sb[i] - '0';
	}
	jw = 0;//存储每一次乘法产生的进位
	for (int i = 0; i < la; i++) {
		for (int j = 0; j < lb; j++) {
			f = a[i] * b[j]; //处理逐
			jw = f / 10;    //位乘,记
			f %= 10;       //录乘积
			w = i + j;    //和进位
			c[w] = c[w] + f; //a[i]*b[j]的结果存储到c[i+j]
			c[w + 1] = c[w + 1] + jw + c[w] / 10;//处理进位
			c[w] %= 10;
		}
	}
	lc = la + lb;//找到最高的非0位
	while (c[lc] == 0)lc--;
	if (lc < 0) {
		printf("0\n");
	} else for (int i = lc; i >= 0; i--) {
			printf("%d", c[i]);
		}
	return 0;
}

四、高精度除法

#include<bits/stdc++.h>
using namespace std;
#define maxx 10005
char sa[maxx], sb[maxx];
int la, lb, lc, a[maxx], b[maxx], c[maxx];
int main() {
    scanf("%s", sa);
    scanf("%s", sb);
    la = strlen(sa);
    lb = strlen(sb);
    if (lb > la || (lb == la && strcmp(sa, sb) < 0)) {//特判被除数小于除数的情况
        printf("0\n");
    } else {
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        memset(c, 0, sizeof(c));
        for (int i = 0; i < la; i++) {
            a[la - i - 1] = sa[i] - '0';
        }
        for (int i = 0; i < lb; i++) {
            b[lb - i - 1] = sb[i] - '0';
        }
        lc = la - lb;//计算c的长度
        for (int i = lc; i >= 0; i--) {//从高位到低位枚举c的每一位
            int k = 0;//记录当前位能够减去几个b
            while (k <= 9 && (k * b[0]) <= a[i + lb]) {//二分找到当前位能够减去几个b
                int mid = (k + 1 + 9) >> 1;
                if (mid*b[0] <= a[i + lb] - mid*b[1]) k = mid;
                else break;
            }
            c[i] = k;
            for (int j = 0; j < lb; j++) {
                a[i + j] -= c[i] * b[j];//更新a的值
                if (a[i + j] < 0) {//借位
                    a[i + j] += 10;
                    a[i + j + 1]--;
                }
            }
        }
        while (lc >= 0 && c[lc] == 0)lc--;
        if (lc < 0) {
            printf("0\n");
        } else for (int i = lc; i >= 0; i--) {
            printf("%d", c[i]);
        }
    }
    return 0;
}

最后

祝大家国庆快乐!!!

参考自

https://blog.csdn.net/hejx0412/article/details/123667293

https://baike.baidu.com/item/%E9%AB%98%E7%B2%BE%E5%BA%A6%E7%AE%97%E6%B3%95/1024900?fr=aladdin

https://blog.csdn.net/justidle/article/details/104426323?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522166484827916782395372981%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=166484827916782395372981&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~hot_rank-3-104426323-null-null.142^v51^control,201^v3^control_1&utm_term=%E9%AB%98%E7%B2%BE%E5%BA%A6%E5%87%8F%E6%B3%95&spm=1018.2226.3001.4187文章来源地址https://www.toymoban.com/news/detail-619895.html

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

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

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

相关文章

  • 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)
  • 高精度除法【c++实现】超详细讲解

    高精度算法分为两种,高精除以低精和高精除以高精。不要看都是除法,就认为原理类似,其实是有很大差距的。让我们一起来学习吧! 有句话说在前面,如果除数等于0,就不要算了,不成立。( 如果你忘了这个知识,小学数学老师饶不了你 ) 高精度除低精度,原理是模

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

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

    2024年02月10日
    浏览(35)
  • 双目相机标定及高精度测量方法,含c++和python代码说明

    视觉测量定位中,双面相机高精度标定是一个重要的步骤。下面是关于如何进行双面相机高精度标定的说明和C++和Python代码实现。 1. 双面相机高精度标定的原理 双面相机高精度标定的目的是确定相机内部参数和外部参数。其中,内部参数包括焦距、主点和畸变系数等,外部

    2023年04月08日
    浏览(38)
  • (基础算法)高精度加法,高精度减法

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

    2024年02月01日
    浏览(55)
  • [ACM 学习] 高精度计算

    低位在下标为0的数组那,代码都是用了繁凡的ACM模板。 c = a+b g||ia.len||ib.len 这个设定是直的好,再也不用担心两个数组的长度了,也不用担心c的数组长度。 c = a-b c = a*b 先比长度,长度相同,从高位到低位进行比较。

    2024年01月17日
    浏览(37)
  • 算法笔记——高精度算法(附源码)

    📖作者介绍: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日
    浏览(55)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包