如何利用数组实现高精度算法

发布于:2022-11-09 ⋅ 阅读:(488) ⋅ 点赞:(0)

目录

 引言       

原理介绍   

数据的输入        

数字对齐的格式(以加法为例)

小细节tips

代码如下

代码分析与书写过程

第一段:书写结构体。

第二段:将字符串转化为数字输入数组

第三段:进行高精度数据的运算(以加法为例)

最后一步,输出


 引言       

        在C/C++语言中,数据类型的储存空间总是有限的,但是有时候在进行一些实际问题的求解是,往往这些数据类型不能容纳,这时候需要我们自己定义一个数据类型和语法,实现大数据的运算!这里有详细的讲解视频,但是初学者可能要看2~3遍才可能看懂,不喜欢看文章的可以去看视频       高精度算法

原理介绍   

       既然大数据存不了,那我们是否可以将其拆分为一个一个的数字,如123,我拆分为1,2,3在输出时让他们位置靠近也可以输出123。这里我们就要用到数组,每个数组都是0~9的数,如果分别拆解了放在数组里,那我们就可以对其为所欲为的操作的!

数据的输入        

       但是,我们又怎么进行输入?这里将大数字以字符串的形式输入,它仅仅是几个字符,但是字符串是不能进行运算的,所以在输入成字符串后,我们就要将字符串的每个字符拆解了放在数组里!这样就实现了我们的第一步,拆解数字。

数字对齐的格式(以加法为例)

拆解完毕后要进行加法运算,就行列一个竖式计算的过程一样,数字该怎么对齐?

如果我们在拆解过程中是正序放入数组的,那么在进行加法的时候会变成这样。

很显然这个位数并没有对齐,所以我们要做的就是在输入到数组是就倒序输入,在输出时倒序输出即可!这样就自动会为我们对其!

小细节tips

     在开数组的时候,就初始化数值全部为0,这样可以让所有位数对齐,并且在后续的进一操作中也有很大帮助!

代码如下

#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;


struct hugeint {  //由于没有数据类型容得下我们要求的数,故自己定义一个数据类型和执行代码,实现大数据的运算。
	
	int num[5005] = { 0 };//全部赋予初始值0使得补零操作
	int len = 0;//记录字符串长度的变量

};

//模块一:将输入字符串转化为数字存放在数组中,要倒序储存!
hugeint math(string s) {
	hugeint a;
	for (int i = s.size() - 1; i >= 0; i--)
		a.num[++a.len] = s[i] - '0';//字符减去0的ASCLL值就是数字!另外就是,++a.len是用来记录录入字符的长度,len从0开始,注意是前置递增,让其先增再运算!
	return a;//直接以数组头a代表整个数组返回,表示将字符串倒序录入结构体数组!
	   }

//模块二:实现加法
/*要将字符串转换为高精度大数字就是主函数体与结构体和模块一,
模块二主要是实现高精度大数字的运算!*/
hugeint sum(hugeint num1, hugeint num2) {
	hugeint ans;
	ans.len = max(num1.len, num2.len);
	for (int i = 1; i <=ans.len; i++) {
		ans.num[i] = num1.num[i] + num2.num[i];
		ans.num[i + 1] = ans.num[i] / 10;
		ans.num[i] %= 10;
	}
	if (ans.num[ans.len + 1] > 0)
		ans.len += 1;

	return ans;

}
//——————————————————————————————————————————————————————————————————————-——————————
int main() {
	string a, b;
	cin >> a >> b;//主函数输入字符串,两个要进行加法的字符串
	hugeint n1 = math(a);
	hugeint n2 = math(b);//这样实现将a,b从字符串转换为高精度大数字n1,n2
	hugeint sum0 = sum(n1, n2);
	for (int i = sum0.len; i >0; i--)
		cout << sum0.num[i];
	return 0;
}

 代码长这样子,接下来一段一段分析!

代码分析与书写过程

第一段:书写结构体。

#include<iostream>
#include<string.h>
using namespace std;


struct hugeint {  //由于没有数据类型容得下我们要求的数,故自己定义一个数据类型和执行代码,实现大数据的运算。
	
	int num[5005] = { 0 };//全部赋予初始值0使得补零操作
	int len = 0;//记录字符串长度的变量

};

       先将结构体命名出来,然后分别用上两个成员名单,一个是我们要用到数组,另一个是用来计算字符长度的len,方便后续用for循环进行输入作为判断条件!

对于开数组的大小就看你要装几位数的数字,让他们全部开始等于0(赋予一个值,如果别的没赋值会默认为0)。

第二段:将字符串转化为数字输入数组

//模块一:将输入字符串转化为数字存放在数组中,要倒序储存!
hugeint math(string s) {
	hugeint a;
	for (int i = s.size() - 1; i >= 0; i--)
		a.num[++a.len] = s[i] - '0';//字符减去0的ASCLL值就是数字!另外就是,++a.len是用来记录录入字符的长度,len从0开始,注意是前置递增,让其先增再运算!
	return a;
	   }






//主函数体
int main() {
	string a, b;
	cin >> a >> b;//主函数输入字符串,两个要进行加法的字符串
	hugeint n1 = math(a);
	hugeint n2 = math(b);//这样实现将a,b从字符串转换为高精度大数字n1,n2
	return 0;
}

       对于为什么要s.size()-1,是因为我这里让i>=0保证数组第一个(以零为下标那个)能够得到数字,同时又要保证不会让得到数组的个数变多,如果不减去1,那么会有i+1个数组都得到数字,然而最后一位却是0,会导致运算出错,要注意,要是感觉有点绕,可以自己去改了,然后输出看看区别在哪里。

      还有一点要注意的是长度为前置递增,要先让长度加了1后在将值赋给它,不然没有长度为0的字符串,会出错,并且后续的每一次计算,都必须是长度自增1才继续赋值!

      最后就是main函数分解出来的数n1,n2,数据类型是我们规定的hugeint,别定义为int!

第三段:进行高精度数据的运算(以加法为例)

//模块二:实现加法
/*要将字符串转换为高精度大数字就是主函数体与结构体和模块一,
模块二主要是实现高精度大数字的运算!*/
hugeint sum(hugeint num1, hugeint num2) {
	hugeint ans;
	ans.len = max(num1.len, num2.len);
	for (int i = 1; i <=ans.len; i++) {
		ans.num[i] = num1.num[i] + num2.num[i];
		ans.num[i + 1] = ans.num[i] / 10;
		ans.num[i] %= 10;
	}
	if (ans.num[ans.len + 1] > 0)
		ans.len += 1;

	return ans;

}

      这里要注意的第一点:要规定一个ans(名字随便),它是用来记录加起来后的数字总长度的,它的长度必须是你输入的最长的那个(或者大一位(因为可能会进一)),所以开始就进行一个max比较两个数字的长度,让最长的给ans,否则你输出的数字是不完整的!

      第二点:关于运算,这里需要满足满十进一!该如何操作?就是运算的第二三两句话

ans.num[i + 1] = ans.num[i] / 10;
		ans.num[i] %= 10;

        其中ans.num[i+1]是指后一位等于前一个数字除10(及上一个数字的十位,如果上一个数字满十以上,当前这位就会+1,如果不满十位就会+0),所以不能直接用ans.num[i+1]+=1啊,如果前一位不满十呢,你这位还进一不就错了!

       其次就是ans.num[i]%=10,这里是为了保留个位,如果它满十了需要进一,但个位我们仍然要留给它,就算不满十,取模于10值也不会变!

      注意:这里不能先更新进位,再保留个位!顺序不可以颠倒!不可以,否则更新进位的数字一直都是0(好好想想为什么?)

最后一步,输出

int main() {
	string a, b;
	cin >> a >> b;//主函数输入字符串,两个要进行加法的字符串
	hugeint n1 = math(a);
	hugeint n2 = math(b);//这样实现将a,b从字符串转换为高精度大数字n1,n2
	hugeint sum0 = sum(n1, n2);
	for (int i = sum0.len; i >0; i--)
		cout << sum0.num[i];
	return 0;
}

       最后的输出就要用倒序输出,这里用加起来的和的长度作为条件,让其倒序输出即可!

本文含有隐藏内容,请 开通VIP 后查看