C语言高精度算法(已更新加,减,乘,阶乘)

2024-01-07 20:20:18

前言

问:为什么会有高精度呢?
答:int表示的范围有限,int 占4个字节,32位,大概能表示10的9次方的数据范围,超过此范围,int型无法表示。
ps:本文知识来源于b站麦克老师讲算法、信息学万老师等,每个会尽量附上例子o(╥﹏╥)o。
目前只写了加法减法乘法,后面等我几天哈哈哈o(╥﹏╥)o

高精度加法

  1. 原理
    简单来说就是将数拆分,一个一个对应相加,往高位进一,看图
    在这里插入图片描述
	c[i] += a[i] + b[i];
	c[i+1] = c[i] / 10;
	c[i] = c[i] % 10;
  1. 注意事项
    事先定义:数组a,b存的是两个加数,数组c存的是和。
    (1) 先定义两个 char 类型的数组存储要输入的元素,再将其转换成 int 类型的进行相加(一开始就定义成 int 类型的无法准确赋值)
    原因事例:
#include <stdio.h>
#include <string.h>

int main () {
	char s[510];
	int a[510], len;
	scanf("%s", s);
	len = strlen(s);
	
	//转换成int
	for (int i = 0; i < len; i++) {
		a[i] = s[i] - '0';
	}
	printf("看一下转换后的样子:\n");
	for (int i = 0; i < len; i++) {
		printf("%d", a[i]);
	}
	
	printf("\n");
	//如果不转化,是这样的:
	printf("如果不转化,是这样的:\n");
	for (int i = 0; i < len; i++) {
		a[i] = s[i];
		printf("%d", a[i]);
	}
}

运行结果:(主要是因为不转换存的是ASCII值)
在这里插入图片描述
(2)数组c的长度是数组a、b中长度最大的加1,因为可能会进位,看图
在这里插入图片描述
(3)为了方便操作,我们可以将数据反转过来,到时候输出的时候从后往前输出就可以了,注意前导0,看图
在这里插入图片描述
(我也试过不翻转直接加,发现太麻烦了,还是翻转省事)
3. 例子(洛谷P1601

高精度减法

  1. 与高精度加法类似,核心还是把数字拆开,一个一个的处理,类比小学减法;

  2. 事先说明:定义2个 char 类型的数组 s1,s2,分别存存储减数和被减数;定义2个 int 型的数组 a 和 b ,分别存储将 char 型数字转成 int 型数字,用 int 型数组c存储最终结果;

  3. 为了方便操作,可将减数和被减数都逆转,结果逆着输出就可以了;

  4. 由于被减数可能比减数小,也是为了方便操作,如果出现这种情况,我们可以将两个操作数互换一下,最后单独输出符号就行了;

  5. 与加法一样要处理前导0;

  6. 图示:(千言万语尽在图里)
    在这里插入图片描述
    核心代码:

for (int i = 0; i < lenc; i++) {
		if (a[i] < b[i]){
			a[i] = a[i] + 10;
			a[i+1] -= 1;
		}
		c[i] = a[i] - b[i];
	}

(让我偷个懒,没错这个分析就是我的例子里面的分析,O(∩_∩)O哈哈~)
7. 例子在这里

高精度乘法

高精度×高精度

  1. 与高精度加法一样啦,还是拆开一个一个对应相乘,在相加,类比小学乘法
  2. 事先说明:定义两个 char 类型的数组 s1 和 s2,分别存放两个乘数,定义两个 int 型的数组 a 和 b 存放转换后的乘数(将 char 型的 ‘1’ 转成 int 型的 ‘1’),int 型数组c 存放相乘的结果,数组c的长度是数组a与数组b长度之和(这是最长的情况),可以写几个数据试一下:
    (这个排版可能在手机上可能有问题,可以用电脑看)
      1 2 3 4   长度为4      |         1 2 3 4     长度为4
x       1 1 1   长度为3      |  x          9 9     长度2
———————————————              | ————————————————
  1 3 6 9 7 4   长度为6      |     1 2 2 1 6 6     长度为6
  1. 与加法一样,乘法也要将两个操作数翻转一下,结果也是逆着输出即可,在这里也要处理前导0,处理前导0的代码我改进了一下,在详细说明一下我这个处理前导0的细节(主要是0 * 0 = 0 的情况)
lenc = lenc - 1;
	if (lenc >= 1) {
		while (c[lenc] == 0 && lenc >= 1) {
			lenc--;
		}
	}
看一下 0 * 0 = 0 的情况,此时lenc = lena + lenb = 2,数组c的是00
即c[0]=0,c[1]=0,所以有lenc = lenc - 1;因为while循环里的判断是c[lenc] == 0while循环往后,lenc可以当成数组下标来看了,抱歉我写的可能有点绕了
  1. 核心代码是这个
for (int i = 0; i < lenb; i++) {
		for (int j = 0; j < lena; j++) {
			c[i+j] += b[i] * a[j];
			c[i+j+1] += c[i+j] / 10;
			c[i+j] = c[i+j] % 10;
		}
	}
  1. 图示理解(千言万语唯有图示能表达出我的想法)
    在这里插入图片描述
  2. 例子(洛谷P1303

高精度×低精度 + 高精度阶乘

  1. 高精度×低精度原理
    (1)将高精度的数拆开用数组存储,具体方法为定义 char 类型数组s存储要输入的值,再将其转化成 int 型存入 int 型数组a中,为了方便操作,再将其转置(以上步骤都与我最初写的高精度加法一样);
    (2)低精度看题目要求是用 int 还是 long long;
    (3)拆开存入数组a后,逐位与低精度相乘,再进位,此处进位与加法进位不同,最后可能有多位进位,需单独处理;
    (4)核心代码:
int jinWei = 0;
	for (int i = 0; i < lena; i++) {
		a[i] = a[i]*n + jinWei;
		jinWei = a[i] / 10;
		a[i] = a[i] % 10;
	}
	
	//处理进位
	while (jinWei) {
		a[lena++] = jinWei % 10;
		jinWei = jinWei / 10;
	}

(5)别忘了处理前导0和逆着输出;
(6)图示理解(千言万语尽在图中):
在这里插入图片描述
2. 高精度阶乘与高精度×低精度原理很类似,没有太大的区别,就是多乘几次;
3. 那啥,我没找到高精度×低精度的题目,所以下面的代码只是参考,我会贴几个样例,暂时没发现错误,这几个样例运行都是对的哦
完整代码:

#include <stdio.h>
#include <string.h>

//翻转函数
void reverse (int d[510], int len) {
	int temp, mid = len/2;
	for (int i = 0, j = len - 1; i < mid, j >= mid; i++, j--) {
		temp = d[i];
		d[i] = d[j];
		d[j] = temp;
	}
}

int main () {
	char s[10000];
	int a[10000], n;//数组a存的是高精度数,n存的是低精度数
	scanf("%s%d", s, &n);
	int lena = strlen(s);
	
	for (int i = 0; i < lena; i++) 
		a[i] = s[i] - '0';
	
	reverse(a, lena);
	
	int jinWei = 0;
	for (int i = 0; i < lena; i++) {
		a[i] = a[i]*n + jinWei;
		jinWei = a[i] / 10;
		a[i] = a[i] % 10;
	}
	
	//处理进位
	while (jinWei) {
		a[lena++] = jinWei % 10;
		jinWei = jinWei / 10;
	}
	
	//处理前导0
	lena = lena - 1;
	while (a[lena] == 0 && lena >= 1){
		lena--;
	}
	
	//输出
	for (int i = lena; i>=0; i--) {
		printf("%d", a[i]);
	}
	
}

样例1:
输入:123456789 56
运行结果:
在这里插入图片描述

样例2:
输入:46572937942 567
运行结果:
在这里插入图片描述
4. 高精度阶乘,其实阶乘的核心代码也是上面的那个,只不过阶乘是 1×2×3×…×n,可以当成是高精度数 ×1×2×…×n,把高精度数初值设为1,即a[1] = 1,lena = 1,然后 ×1×2×…×n,×n个低精度的数而已,每次在乘的时候处理进位的同时,lena也会变。
5. 高精度阶乘例子(洛谷[NOIP1998 普及组] 阶乘之和),此例子隐含高精度×低精度。

文章来源:https://blog.csdn.net/qq_65265649/article/details/135380428
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。