易知,这个和的数字是非常大的,大到 long long 都装不下,这个时候如果使用 long long 是无法进行运算的。欸!这会高精度算法(即大数运算)就开始发光发热了。
以下是我看资料总结的一些歪瓜裂枣。
对于一位高精度数字,用整数数组存储,数组每一个元素对应一位十进制数,由其下标顺序指明位序号。
1、采用数串形式输入,并将其转化为整数数组。
2、用一个整数变量记录数据的实际长度(即数组的元素个数)
3、该数组的运算规则如同算术运算。
高精度加法的实现首先要注意的是,用数组的一位来存储数字的一位,把两个一位一位的相加,当两位数相加再加进位的数字大于等于10的时候就要进位,同时当前只保留个位数,保证每一位只有一位数字。
下面展示简单的输入和输出
void init(int i[]) //输入
{
string k;
cin>>k;
i[0]=k.length(); //用i[0]计算字符串k的位数
for(int j=0;j<=i[0];j++)
{ i[j]=k[i[0]-j]-'0'; //将输入的字符串k转换为数字i,并倒序存储 }
}
void print(int i[ ]) //输出
{
int j;
if(i[0]==0)
{
cout<<0<<endl;
return;
}
for(j=i[0];j>0;j--) //对应上面要倒序输出
cout<<i[j];
cout<<endl;
return;
}
向量Vector是一个封装了动态大小数组的顺序容器。他和任意容器一样能够存放各种类型的对象。即可以简单的认为向量是一个能够存放任意类型的动态数组。
存储类型:
vector<类型>标识符
vector<类型>标识符(最大容量)
vector<类型>标识符(最大容量,初始所有值)
int i[5]={1,2,3,4,5}
vector<类型>vi(i,i+2);//得到i索引值为3以后的值
vector<vector<int>>v;
二维数组的定义方法如下
#include <bits/stdc++.h>
using namespace std;
int main()
{
int N=5, M=6;
vector<vector<int> > obj(N, vector<int>(M)); //定义二维动态数组5行6列
for(int i=0; i< obj.size(); i++)//输出二维动态数组
{
for(int j=0;j<obj[i].size();j++)
{
cout<<obj[i][j]<<" ";
}
cout<<"\n";
}
return 0;
}
具体代码和思路如下
主要分为大数相加、大数乘法函数和大数幂函数
1.大数相加
大数相加函数add
的作用是将两个大数存储在vector中的数组进行相加。
- 初始化进位
carry
为0,结果数组res
为空。 - 从大数的最低位开始逐位相加,同时考虑进位。
- 将每一位的和取模10得到该位的数值,并将其添加到结果数组
res
中。 - 将进位更新为当前和除以10的商。
- 反转结果数组
res
。 - 返回结果数组
res
。
2.大数乘法函数
大数乘法函数multiply
的作用是将一个大数与一个整数因子相乘。
- 初始化进位
carry
为0,结果数组res
为空。 - 从大数的最高位开始逐位相乘,同时考虑进位。
- 将每一位乘积取模10得到该位的数值,并将其添加到结果数组
res
中。 - 将进位更新为当前乘积除以10的商。
- 当结束循环后,若进位不为0,则将进位的每一位依次添加到结果数组
res
中。 - 反转结果数组
res
。 - 返回结果数组
res
。
3.大数幂函数
大数幂函数power
的作用是计算一个数字的大数幂。
- 初始化结果数组
res
为1(即表示数字1)。 - 进行exponent次循环,每次都将当前结果数组
res
与base相乘得到新的结果。 - 返回结果数组
res
。
#include <iostream>
#include <vector>
using namespace std;
// 大数相加函数
vector<int> add(vector<int>& num1, vector<int>& num2)
{
int carry = 0;
vector<int> res;
int i = num1.size() - 1;
int j = num2.size() - 1;
while (i >= 0 || j >= 0 || carry != 0) {
int sum = carry;
if (i >= 0) {
sum += num1[i];
i--;
}
if (j >= 0) {
sum += num2[j];
j--;
}
res.push_back(sum % 10);
carry = sum / 10;
}
reverse(res.begin(), res.end());
return res;
}
// 大数乘法函数
vector<int> multiply(vector<int>& num, int factor)
{
int carry = 0;
vector<int> res;
for (int i = num.size() - 1; i >= 0; i--) {
int product = num[i] * factor + carry;
res.push_back(product % 10);
carry = product / 10;
}
while (carry != 0) {
res.push_back(carry % 10);
carry /= 10;
}
reverse(res.begin(), res.end());
return res;
}
// 大数幂函数
vector<int> power(int base, int exponent)
{
vector<int> res;
res.push_back(1);
for (int i = 0; i < exponent; i++) {
res = multiply(res, base);
}
return res;
}
// 打印大数
void printNumber(vector<int>& num)
{
for (int i = 0; i < num.size(); i++) {
cout << num[i];
}
cout << endl;
}
int main()
{
vector<int> num1 = power(2, 2023);
vector<int> num2 = power(3, 2023);
vector<int> sum = add(num1, num2);
cout << "2^2023 + 3^2023 = ";
printNumber(sum);
return 0;
}
运行结果如下
2^2023 + 3^2023 = 164550155817497922294838391236299861450073375755268393204821647842390925231027327013362334261121620331320103763309030913468079478876131292912534405287849925398050388086112915948864401074633400938303521438749199299616760709734985020968176706423823045506812125521181906501625126248764139809149859309775005503946205345233873117543877759413080800290663648710104418064091162253163747353098015353006496073835480356649464016840990986871186086363748320458213967890316029657024181388800778492553133247539979368738270897979552321931107295913297764537663273094116306823891621840878523012417042704649200369167527343452009394046433911608627818498610240283001048499399739250672943345292236691272125995018337181697667450665219378815756991606386925778096374338455126384865122296761841414090781569213003224699667342691692380716557987838205129753879602803963110864426892507834007443857214407413528231854495781837278603865482642261573536273486496079316989840792161359098969978812807435
但是显然,结果不是这个,有哪位路过的大神可指点一二。感谢!
标签:数组,大数,int,res,C++,vector,计算,2023,carry From: https://www.cnblogs.com/zongmeijiezuishuai/p/17536419.html