做视频自媒体要投稿几个网站,广州工程承包总公司,永久免费的移动建站平台,鑫迪一键建站系统高精度计算专题 目录 MT2191 整数大小比较MT2192 AB problemMT2193 A-B problemMT2194 大斐列MT2195 升级版斐波那契数列MT2196 2的N次幂 MT2191 整数大小比较 难度#xff1a;黄金 时间限制#xff1a;1秒 占用内存#xff1a;128M 题目描述 给出两个正整数…高精度计算专题 目录 MT2191 整数大小比较MT2192 AB problemMT2193 A-B problemMT2194 大斐列MT2195 升级版斐波那契数列MT2196 2的N次幂 MT2191 整数大小比较 难度黄金 时间限制1秒 占用内存128M 题目描述 给出两个正整数判断它们的大小。 格式 输入格式两个正整数。 输出格式若前者大输出 若后者大输出 若一样大输出 。 样例 1 输入1412894619244619891 23762842222 输出 备注 保证所有数在 2 100 2^{100} 2100 以内。 相关知识点高精度计算 题解 虽然这道题是比较数字的大小但实际上我们不用关心其数字的取值范围可以从字符串对象的角度出发进行比较。对于任意两个正整数它们之间的大小关系可根据以下两步进行比较
数字长度。对于正整数而言显然长度越长的数更大。若长度相等则从数的最高位到最低位依次比较大小在某位上具有更大数字的数更大。
若 1、2 之后未能找到更大的数则说明这两个数的取值相同。
基于此可直接写出求解该题的完整代码已 AC
/*MT2191 整数大小比较
*/
#includebits/stdc.h
using namespace std;// 比较两个大数的大小
int compare(string stra, string strb)
{// 根据长度判断大小关系 int lenA stra.length();int lenB strb.length();if(lenA lenB) return 1;if(lenA lenB) return -1;// 长度相等需要进一步判断for(int i0; ilenA; i){if(stra[i] - strb[i] 0) return 1;if(stra[i] - strb[i] 0) return -1;}// 或者直接比较字符串大小// if(stra strb) return 1;// else if(stra strb) return -1;// else return return 0;
}// 打印结果
void printResult(int result)
{if(result 0) coutendl;else if(result 0) coutendl;else coutendl;
}int main( )
{// 获取输入 string stra, strb;cinstrastrb;// 比较两个大数的大小int result compare(stra, strb);// 输出比较结果printResult(result);return 0;
} MT2192 AB problem 难度黄金 时间限制1秒 占用内存128M 题目描述 计算 A B ( 1 ≤ A , B ≤ 10 10000 ) AB(1\le A,B\le{10}^{10000}) AB(1≤A,B≤1010000)。 格式 输入格式两行每行一个整数 A , B A,B A,B。 输出格式一个整数 A B AB AB。 样例 1 输入 1 1 输出 2 相关知识点 高精度计算 题解 这道题考察的是大数运算加法。关于如何实现大数加法运算的分析请见博客 【算法与数据结构】——大数运算 。下面给出多位数加法的执行流程 多位数加法的过程涉及到对各个位的加法运算因此在处理大数的加法运算时通常会用一个 int 型数组来存储大数在各个位上的值。例如数122333444455555666666可通过一个足够长的数组 a r y [ ] ary[\ ] ary[ ] 使 a r y [ 0 ] 1 , a r y [ 1 ] 2 , a r y [ 3 ] 2 , … , a r y [ 20 ] 6 ary\left[0\right]1,ary\left[1\right]2,ary\left[3\right]2,\ldots,ary\left[20\right]6 ary[0]1,ary[1]2,ary[3]2,…,ary[20]6 进行存储。采取数位与索引大小相对应的存储方式即数的低位对应较小的索引高位对应较大的索引是为了便于大数在执行加法运算时的进位可直接在数组中向后拓展。接下来就能按照以上思路扫描数组并对各个位进行加法运算。最后单独用一层循环处理进位即可。
下面直接给出求解本题的完整代码已 AC
/*MT2192 AB problem
*/
#includebits/stdc.h
using namespace std;const int N 1e45;
int numa[N], numb[N];// 计算两个大数之和输入为字符串
void getSum(string stra, string strb)
{// 赋初值memset(numa, 0, sizeof(numa));memset(numb, 0, sizeof(numb));int tmp 0;// 将两个字符串保存至 int 型数组中注意逆序 for(int istra.length()-1; i0; i--)numa[tmp] stra[i] - 0;tmp 0;for(int istrb.length()-1; i0; i--)numb[tmp] strb[i] - 0;// 将数组中的每个数按位进行加法运算for(int i0;iN;i)numa[i] numb[i];// 对存放加法结果的数组执行进位处理for(int i0; iN; i){numa[i1] numa[i] / 10;numa[i] % 10;}
}// 输出大数加法后的结果
void printBigData()
{// 从最高位向后扫描直到第 1 个非 0 数字出现 int p N-1;while(numa[p] 0) p--;while(p 0) coutnuma[p--];cout\n;
} int main( )
{// 获取输入 string stra, strb;cinstrastrb;// 对两个大数进行加法运算 getSum(stra, strb);// 输出和printBigData();return 0;
} MT2193 A-B problem 难度黄金 时间限制1秒 占用内存128M 题目描述 计算 A − B ( 1 ≤ B ≤ A ≤ 10 10000 ) A-B(1\le B\le A\le{10}^{10000}) A−B(1≤B≤A≤1010000)。 格式 输入格式两行每行一个整数 A , B A,B A,B。 输出格式一个整数 A − B A-B A−B。 样例 1 输入 2 1 输出 1 相关知识点 高精度计算 题解 这道题考察的是大数运算减法。关于如何实现大数减法运算的分析请见博客 【算法与数据结构】——大数运算 。下面给出多位数减法的执行流程 多位数减法需要用到 int 型数组来存储大数在各个位上的值其存储规则和大数加法一致即低位对应较小的索引高位对应较大的索引。接下来只需要扫描数组在每个位上按照以上思路进行减法运算即可得到大数减法的结果。
下面直接给出求解本题的完整代码已 AC
/*MT2193 A-B problem
*/
#includebits/stdc.h
using namespace std;const int N 1e45;
int numa[N], numb[N];// 计算两个大数之差输入为字符串
void getSub(string stra, string strb)
{// 赋初值memset(numa, 0, sizeof(numa));memset(numb, 0, sizeof(numb));int tmp 0;// 将两个字符串保存至 int 型数组中注意逆序 for(int istra.length()-1; i0; i--)numa[tmp] stra[i] - 0;tmp 0;for(int istrb.length()-1; i0; i--)numb[tmp] strb[i] - 0;// 将数组中的每个数按位进行减法运算for(int i0;iN;i){numa[i] - numb[i];if(numa[i] 0){// 借位 numa[i1]--; numa[i] 10;}}
}// 输出大数减法后的结果
void printBigData()
{// 从最高位向后扫描直到第 1 个非 0 数字出现 int p N-1;while(numa[p] 0) p--;while(p -1) coutnuma[p--];cout\n;
} int main( )
{// 获取输入 string stra, strb;cinstrastrb;// 对两个大数进行减法运算 getSub(stra, strb);// 输出和printBigData();return 0;
} MT2194 大斐列 难度黄金 时间限制1秒 占用内存128M 题目描述 计算斐波那契数列第 n n n 项。 斐波那契数列定义为 F [ 1 ] 1 F [ 2 ] 1 F[1] 1F[2] 1 F[1]1F[2]1递推关系为 F [ N ] F [ N − 1 ] F [ N − 2 ] F[N] F[N-1] F[N-2] F[N]F[N−1]F[N−2]。即 1 、 1 、 2 、 3 、 5 、 8 、 13 、 21 、 34 、 … … 1、1、2、3、5、8、13、21、34、…… 1、1、2、3、5、8、13、21、34、…… 格式 输入格式一个整数 n n n。 输出格式一个整数 F [ n ] F[n] F[n]。 样例 1 输入6 输出8 备注 对于 30% 的数据 3 ≤ n ≤ 20 3≤n≤20 3≤n≤20。 对于 100% 的数据 3 ≤ n ≤ 5000 3≤n≤5000 3≤n≤5000。 相关知识点高精度计算 题解 这道题实际上就是求斐波那契数列即通过迭代公式 F [ N ] F [ N − 1 ] F [ N − 2 ] F[N] F[N-1] F[N-2] F[N]F[N−1]F[N−2]不断获取下一个值。但是斐波那契数列的增长速度非常快通过编写 Python 代码可知代码如下斐波那契数列的第 5000 个数的长度达到了 1045。因此这道题是一道妥妥的大数加法问题。
# 求斐波那契的第 5000 项
ary [1,1]
for i in range(2,5000):ary.append(ary[i-1]ary[i-2])
print(ary[4999])
print(len(str(ary[4999])))所以这里依然需要用到大数加法。具体的实现方式和前面类似在此就不赘述。
下面给出基于以上思路写出的完整代码已 AC
/*MT2194 大斐列 通过 python 算出最后数字即第 5000 项的长度为 1045
*/
#includebits/stdc.h
using namespace std;const int N 1100;
int numa[N], numb[N], numc[N];// 计算斐波那契数列
void getFibonacci(int n)
{// 赋初值memset(numa, 0, sizeof(numa));memset(numb, 0, sizeof(numb));memset(numc, 0, sizeof(numc));numa[0] numb[0] 1;n - 2;// 递推求解斐波那契数列并统计前缀和 while(n--){// 将数组中的每个数按位进行加法运算 for(int i0;iN;i)numc[i] numa[i] numb[i];// 对存放加法结果的数组执行进位处理for(int i0; iN; i){numc[i1] numc[i] / 10;numc[i] % 10;}// 将数组进行前向赋值从而实现递推memcpy(numa, numb, sizeof(numb));memcpy(numb, numc, sizeof(numc));}
}// 输出大数加法后的结果
void printBigData()
{// 从最高位向后扫描直到第 1 个非 0 数字出现 int p N-1;while(numc[p] 0) p--;while(p -1) coutnumc[p--];cout\n;
} int main( )
{// 获取输入 int n;cinn;// 求出斐波那契数列 getFibonacci(n);// 输出指定项 printBigData();return 0;
} MT2195 升级版斐波那契数列 难度黄金 时间限制1秒 占用内存128M 题目描述 我们都知道斐波那契数列一项是前两项的和现在我们规定一个升级版斐波那契数列其一项为前三项的和要求算其前 n n n 项的和。即定义 F [ 1 ] 1 F [ 2 ] 1 F [ 3 ] 1 F[1] 1F[2] 1F[3] 1 F[1]1F[2]1F[3]1递推关系为 F [ N ] F [ N − 1 ] F [ N − 2 ] F [ N − 3 ] F[N] F[N-1] F[N-2] F[N-3] F[N]F[N−1]F[N−2]F[N−3]。 格式 输入格式一个整数 n n n 输出格式前 n n n 项的和。 样例 1 输入4 输出6 备注 其中 4 ≤ n ≤ 1000 4\le n \le 1000 4≤n≤1000。 相关知识点高精度计算 题解 这道题依然考察了大数加法和前面一题类似下面直接给出求解本题的完整代码已 AC
/*MT2195 升级版斐波那契数列 通过 python 算出最后数字即第 1000 项的长度为 265整个数列的数字之和长度为 265
*/
#includebits/stdc.h
using namespace std;const int N 300;
int numa[N], numb[N], numc[N], numd[N], preSum[N];// 计算斐波那契数列
void getFibonacci(int n)
{// 赋初值memset(numa, 0, sizeof(numa));memset(numb, 0, sizeof(numb));memset(numc, 0, sizeof(numc));memset(numd, 0, sizeof(numd));memset(preSum, 0, sizeof(preSum));numa[0] numb[0] numc[0] 1;preSum[0] 3;n - 3;// 递推求解斐波那契数列并统计前缀和 while(n--){// 将数组中的每个数按位进行加法运算 for(int i0;iN;i)numd[i] numa[i] numb[i] numc[i];// 对存放加法结果的数组执行进位处理for(int i0; iN; i){numd[i1] numd[i] / 10;numd[i] % 10;}// 将当前项累加至前缀和数组中for(int i0;iN;i)preSum[i] numd[i];for(int i0; iN; i){preSum[i1] preSum[i] / 10;preSum[i] % 10;}// 将数组进行前向赋值memcpy(numa, numb, sizeof(numb));memcpy(numb, numc, sizeof(numc));memcpy(numc, numd, sizeof(numd));}
}// 输出大数加法后的结果
void printBigData()
{// 从最高位向后扫描直到第 1 个非 0 数字出现 int p N-1;while(preSum[p] 0) p--;while(p -1) coutpreSum[p--];cout\n;
} int main( )
{// 获取输入 int n;cinn;// 求出斐波那契数列 getFibonacci(n);// 输出前缀和 printBigData();return 0;
} MT2196 2的N次幂 难度黄金 时间限制1秒 占用内存128M 题目描述 任意给定一个正整数 N ( N ≤ 100 ) N(N\le100) N(N≤100) 计算 2 的 N N N 次方的值。 格式 输入格式一个正整数 N N N 输出格式输出 2 N 2^N 2N 的值。 样例 1 输入5 输出32 相关知识点高精度计算 题解 2 n 2^n 2n 在 n n n 取 100 时是一个长度为 31 的大数因此也是一道高精度题。与前面不同的是这道题要求的是乘幂运算。但实际上数的乘幂运算就等于进行 “幂” 次乘法运算叠乘乘数为底数。所以求解该题的关键实际是基于乘法运算的高精度计算问题关于如何实现大数乘法运算的分析请见博客 【算法与数据结构】——大数运算 。
这里选用的数据结构依然是 int 型数组其存储规则和大数加法一致即低位对应较小的索引高位对应较大的索引。不过在算法一开始需要将该数组的最低位置为底数即 2。接下来定义一重循环循环次数为 n − 1 n-1 n−1每遍都执行以下两步
将存放大数的数组中的每一位都乘以底数遍历整个数组执行进位。
算法结束时即得到了大数乘幂运算的结果。下面给出基于以上思路得到的完整代码
/*MT2196 2的N次幂
*/
#includebits/stdc.h
using namespace std;// 题目给的数据范围保证了结果不超过 32 位
const int N 32;
int num[N];// 高精度乘幂运算
void getHighPrecision(int base, int power)
{// 初始化存放运算结果的数组 memset(num, 0, sizeof(num));// 给数组赋初值 num[0] base;// 执行乘幂运算 while(--power){// 将数组中的每个数进行乘法运算 for(int i0; iN; i)num[i] * base;// 对数组执行进位处理for(int i0; iN; i){num[i1] num[i] / 10;num[i] % 10;}}
}// 输出高精度运算后的大数
void printBigData()
{// 从最高位向后扫描直到第 1 个非 0 数字出现 int p N-1;while(num[p] 0) p--;while(p -1) coutnum[p--];cout\n;
} int main( )
{// 获取输入 int n;cinn;// 执行乘幂的高精度运算getHighPrecision(2, n);// 输出 printBigData();return 0;
} END
