洛谷P1601 P1303 P1009题解-平芜编程栈

洛谷P1601 P1303 P1009题解

作者：爱吃大芒果

个人主页爱吃大芒果

本文所属专栏从0到1自学C++

更多专栏

Ascend C 算子开发教程（进阶）
鸿蒙集成
Flutter

P1601 A+B Problem（高精）

P1601题目链接

题目分析

高精度加法要模拟出我们平时做加法的过程，从个位开始逐位相加，并处理进位问题。由于输入的数字可能非常大，无法用普通的数据类型存储，因此我们使用数组来存储每一位数字。代码要满足将字符串转化为倒序数组，实现加法运算，处理进位问题，最后输出结果的要求。

将字符串转化为倒序数组

for(inti=0;i<s1.size();i++){a1[s1.size()-i-1]=s1[i]-'0';}

处理进位问题

for(inti=0;i<len;i++){if(a3[i]>=10){a3[i+1]=a3[i+1]+a3[i]/10;a3[i]=a3[i]%10;}}

AC代码

#include<bits/stdc++.h>usingnamespacestd;intmain(){string s1,s2;// 定义字符串存储输入的大数inta1[210]={0},a2[210]={0},a3[210]={0};// 定义数组存储大数并初始化为0getline(cin,s1);// 使用getline函数读取整行输入getline(cin,s2);for(inti=0;i<s1.size();i++){a1[s1.size()-i-1]=s1[i]-'0';// 将字符转换为整数并存储在a1数组中}for(inti=0;i<s2.size();i++){a2[s2.size()-i-1]=s2[i]-'0';// 将字符转换为整数并存储在a2数组中}intlen=max(s1.size(),s2.size());// 计算较大数的长度for(inti=0;i<len;i++){a3[i]=a1[i]+a2[i];// 对应位相加}for(inti=0;i<len;i++){if(a3[i]>=10){// 处理进位a3[i+1]=a3[i+1]+a3[i]/10;a3[i]=a3[i]%10;// 取余}}if(a3[len]!=0)len++;// 如果最高位有进位，长度加1for(inti=len-1;i>=0;i--)cout<<a3[i];// 输出结果return0;}

P1303 计算阶乘（高精）

P1303题目链接

题目分析

计算大数阶乘需要模拟乘法运算，并处理进位问题。由于阶乘结果可能非常大，无法用普通的数据类型存储，因此我们和高精度加法一样使用数组来存储每一位数字。代码要满足初始化数组，逐步计算阶乘，处理进位问题，最后输出结果的要求。

AC代码

#include<bits/stdc++.h>usingnamespacestd;intmain(){string s1="",s2="";// 定义字符串存储大数inta[10001]={0},b[10001]={0},c[10001]={0};// 定义数组存储大数并初始化为0cin>>s1>>s2;for(inti=0;i<s1.size();i++){a[s1.size()-i-1]=s1[i]-'0';//和高精度加法一样，将字符转换为整数并倒序存储}for(inti=0;i<s2.size();i++){b[s2.size()-i-1]=s2[i]-'0';}for(inti=0;i<s2.size();i++){for(intj=0;j<s1.size();j++){c[j+i]=c[j+i]+a[j]*b[i];// 逐位相乘并相加if(c[j+i]>=10){c[j+i+1]+=c[j+i]/10;// 处理进位c[j+i]=c[j+i]%10;}}}intindex=0;// 定义index变量存储结果的最高位intlen=s1.size()+s2.size();for(inti=len-1;i>=0;i--){// 从最高位开始寻找非0位if(c[i]!=0){// 如果当前位不为0，则将index设置为当前位，并跳出循环index=i;break;}}for(inti=index;i>=0;i--)// 输出结果cout<<c[i];return0;}

P1009 阶乘之和（高精）

P1009题目链接

题目分析

计算阶乘之和需要用到刚刚完成的高精度加法和乘法，把他们用函数封装起来，然后调用函数即可。

使用 memset 函数在每次函数调用时重置数组,由于a, b, c 是全局数组，它们会保留上一次函数调用的值
如果不清零，上一次计算的结果会干扰当前计算

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

注意去除前导0

while (lenc > 1 && c[lenc - 1] == 0) lenc–;
for (int i = lenc - 1; i >= 0; i–) {
res += char(c[i] + ‘0’);
}

AC代码

#include<bits/stdc++.h>usingnamespacestd;intn,a[10010]={0},b[10010]={0},c[10010]={0};string mul="1",sum="0";// 定义字符串存储阶乘和阶乘之和stringadd(string x,string y){// 高精度加法函数memset(a,0,sizeof(a));// 清零数组memset(b,0,sizeof(b));memset(c,0,sizeof(c));intlena=x.length(),lenb=y.length(),lenc=max(lena,lenb);for(inti=0;i<lena;i++)a[i]=x[lena-1-i]-'0';for(inti=0;i<lenb;i++)b[i]=y[lenb-1-i]-'0';for(inti=0;i<lenc;i++){c[i]+=a[i]+b[i];c[i+1]+=c[i]/10;c[i]=c[i]%10;}string res="";// 构建结果字符串if(c[lenc]>0)lenc++;// 如果最高位有进位，长度加1for(inti=lenc-1;i>=0;i--)res+=c[i]+'0';// 将结果转换为字符串returnres;}stringmulti(string x,string y){// 高精度乘法函数memset(a,0,sizeof(a));memset(b,0,sizeof(b));memset(c,0,sizeof(c));intlena=x.length(),lenb=y.length();for(inti=0;i<lena;i++)a[i]=x[lena-1-i]-'0';for(inti=0;i<lenb;i++)b[i]=y[lenb-1-i]-'0';for(inti=0;i<lena;i++){for(intj=0;j<lenb;j++){c[i+j]+=a[i]*b[j];c[i+j+1]+=c[i+j]/10;c[i+j]=c[i+j]%10;}}string res="";// 构建结果字符串intlenc=lena+lenb;while(lenc>1&&c[lenc-1]==0)lenc--;// 去除高位的0for(inti=lenc-1;i>=0;i--){res+=char(c[i]+'0');}returnres;}intmain(){cin>>n;for(inti=1;i<=n;i++){mul=multi(mul,to_string(i));//to_string(i)将整数i转换为字符串sum=add(sum,mul);}cout<<sum<<endl;return0;}