【马蹄集】第二十四周——高精度计算专题

这篇具有很好参考价值的文章主要介绍了【马蹄集】第二十四周——高精度计算专题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

数论专题:高精度计算






MT2191 整数大小比较

难度:黄金    时间限制:1秒    占用内存:128M
题目描述

给出两个正整数,判断它们的大小。

格式

输入格式:两个正整数。
输出格式:若前者大,输出 >;若后者大,输出 <;若一样大,输出 =

样例 1

输入:1412894619244619891 23762842222

输出:>

备注

保证所有数在 2 100 2^{100} 2100 以内。


相关知识点:高精度计算


题解


虽然这道题是比较数字的大小,但实际上我们不用关心其数字的取值范围(可以从字符串对象的角度出发进行比较)。对于任意两个正整数,它们之间的大小关系可根据以下两步进行比较:

  1. 数字长度。对于正整数而言,显然长度越长的数更大。
  2. 若长度相等,则从数的最高位到最低位依次比较大小,在某位上具有更大数字的数更大。

若 1、2 之后未能找到更大的数,则说明这两个数的取值相同。

基于此,可直接写出求解该题的完整代码(已 AC):

/*
    MT2191 整数大小比较 
*/
#include<bits/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 i=0; i<lenA; 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) cout<<">"<<endl;
    else if(result < 0) cout<<"<"<<endl;
    else cout<<"="<<endl;
}

int main( )
{
    // 获取输入 
    string stra, strb;
    cin>>stra>>strb;
    // 比较两个大数的大小
    int result = compare(stra, strb);
    // 输出比较结果
    printResult(result);
    return 0;
} 



MT2192 A+B problem

难度:黄金    时间限制:1秒    占用内存:128M
题目描述

计算 A + B ( 1 ≤ A , B ≤ 10 10000 ) A+B(1\le A,B\le{10}^{10000}) A+B(1A,B1010000)

格式

输入格式:两行每行一个整数 A , B A,B A,B
输出格式:一个整数 A + B A+B A+B

样例 1

输入:

1
1

输出:

2


相关知识点: 高精度计算


题解


这道题考察的是大数运算(加法)。关于如何实现大数加法运算的分析请见博客 【算法与数据结构】——大数运算 。下面给出多位数加法的执行流程:

【马蹄集】第二十四周——高精度计算专题,马蹄集试题题解,MT2192 A+B,MT2193 A-B,MT2194 大斐列,MT2195 升级版斐波那契,MT2196 2的N次幂,马蹄集试题题解,高精度计算

多位数加法的过程涉及到对各个位的加法运算,因此在处理大数的加法运算时,通常会用一个 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 A+B problem 
*/
#include<bits/stdc++.h> 
using namespace std;

const int N = 1e4+5;
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 i=stra.length()-1; i>=0; i--)
        numa[tmp++] = stra[i] - '0';
    tmp = 0;
    for(int i=strb.length()-1; i>=0; i--)
        numb[tmp++] = strb[i] - '0';
    // 将数组中的每个数按位进行加法运算
    for(int i=0;i<N;i++)
        numa[i] += numb[i];
    // 对存放加法结果的数组执行进位处理
    for(int i=0; i<N; i++){
        numa[i+1] += numa[i] / 10;
        numa[i] %= 10;
    }
}

// 输出大数加法后的结果 
void printBigData()
{
    // 从最高位向后扫描,直到第 1 个非 0 数字出现 
    int p = N-1;
    while(numa[p] == 0) p--;
    while(p >= 0) cout<<numa[p--];
    cout<<"\n";
} 

int main( )
{
    // 获取输入 
    string stra, strb;
    cin>>stra>>strb;
    // 对两个大数进行加法运算 
    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}) AB(1BA1010000)

格式

输入格式:两行每行一个整数 A , B A,B A,B
输出格式:一个整数 A − B A-B AB

样例 1

输入:

2
1

输出:

1

相关知识点: 高精度计算


题解


这道题考察的是大数运算(减法)。关于如何实现大数减法运算的分析请见博客 【算法与数据结构】——大数运算 。下面给出多位数减法的执行流程:

【马蹄集】第二十四周——高精度计算专题,马蹄集试题题解,MT2192 A+B,MT2193 A-B,MT2194 大斐列,MT2195 升级版斐波那契,MT2196 2的N次幂,马蹄集试题题解,高精度计算

多位数减法需要用到 int 型数组来存储大数在各个位上的值,其存储规则和大数加法一致(即低位对应较小的索引,高位对应较大的索引)。接下来,只需要扫描数组,在每个位上按照以上思路进行减法运算即可得到大数减法的结果。

下面直接给出求解本题的完整代码(已 AC):

/*
    MT2193 A-B problem 
*/
#include<bits/stdc++.h> 
using namespace std;

const int N = 1e4+5;
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 i=stra.length()-1; i>=0; i--)
        numa[tmp++] = stra[i] - '0';
    tmp = 0;
    for(int i=strb.length()-1; i>=0; i--)
        numb[tmp++] = strb[i] - '0';
    // 将数组中的每个数按位进行减法运算
    for(int i=0;i<N;i++){
        numa[i] -= numb[i];
        if(numa[i] < 0){
            // 借位 
            numa[i+1]--; 
            numa[i] += 10;
        }
    }
}

// 输出大数减法后的结果 
void printBigData()
{
    // 从最高位向后扫描,直到第 1 个非 0 数字出现 
    int p = N-1;
    while(numa[p] == 0) p--;
    while(p > -1) cout<<numa[p--];
    cout<<"\n";
} 

int main( )
{
    // 获取输入 
    string stra, strb;
    cin>>stra>>strb;
    // 对两个大数进行减法运算 
    getSub(stra, strb);
    // 输出和
    printBigData();
    return 0;
} 


MT2194 大斐列

难度:黄金    时间限制:1秒    占用内存:128M
题目描述

计算斐波那契数列第 n n n 项。
斐波那契数列定义为: F [ 1 ] = 1 , F [ 2 ] = 1 F[1] = 1,F[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[N1]+F[N2]。即: 1 、 1 、 2 、 3 、 5 、 8 、 13 、 21 、 34 、 … … 1、1、2、3、5、8、13、21、34、…… 112358132134……

格式

输入格式:一个整数 n n n
输出格式:一个整数 F [ n ] F[n] F[n]

样例 1

输入:6

输出:8

备注

对于 30% 的数据: 3 ≤ n ≤ 20 3≤n≤20 3n20
对于 100% 的数据: 3 ≤ n ≤ 5000 3≤n≤5000 3n5000


相关知识点:高精度计算


题解


这道题实际上就是求斐波那契数列:即通过迭代公式 F [ N ] = F [ N − 1 ] + F [ N − 2 ] F[N] = F[N-1] + F[N-2] F[N]=F[N1]+F[N2],不断获取下一个值。但是斐波那契数列的增长速度非常快,通过编写 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])))

【马蹄集】第二十四周——高精度计算专题,马蹄集试题题解,MT2192 A+B,MT2193 A-B,MT2194 大斐列,MT2195 升级版斐波那契,MT2196 2的N次幂,马蹄集试题题解,高精度计算

所以这里依然需要用到大数加法。具体的实现方式和前面类似,在此就不赘述。

下面给出基于以上思路写出的完整代码(已 AC):

/*
    MT2194 大斐列 
    通过 python 算出最后数字(即第 5000 项)的长度为 1045
*/
#include<bits/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 i=0;i<N;i++)
            numc[i] = numa[i] + numb[i];
        // 对存放加法结果的数组执行进位处理
        for(int i=0; i<N; i++){
            numc[i+1] += 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) cout<<numc[p--];
    cout<<"\n";
} 

int main( )
{
    // 获取输入 
    int n;
    cin>>n;
    // 求出斐波那契数列 
    getFibonacci(n);
    // 输出指定项 
    printBigData();
    return 0;
} 


MT2195 升级版斐波那契数列

难度:黄金    时间限制:1秒    占用内存:128M
题目描述

我们都知道斐波那契数列一项是前两项的和,现在我们规定一个升级版斐波那契数列,其一项为前三项的和,要求算其前 n n n 项的和。即,定义: F [ 1 ] = 1 , F [ 2 ] = 1 , F [ 3 ] = 1 F[1] = 1,F[2] = 1,F[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[N1]+F[N2]+F[N3]

格式

输入格式:一个整数 n n n
输出格式:前 n n n 项的和。

样例 1

输入:4

输出:6

备注

其中: 4 ≤ n ≤ 1000 4\le n \le 1000 4n1000


相关知识点:高精度计算


题解


这道题依然考察了大数加法,和前面一题类似,下面直接给出求解本题的完整代码(已 AC):

/*
    MT2195 升级版斐波那契数列 
    通过 python 算出最后数字(即第 1000 项)的长度为 265,整个数列的数字之和长度为 265
*/
#include<bits/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 i=0;i<N;i++)
            numd[i] = numa[i] + numb[i] + numc[i];
        // 对存放加法结果的数组执行进位处理
        for(int i=0; i<N; i++){
            numd[i+1] += numd[i] / 10;
            numd[i] %= 10;
        }
        // 将当前项累加至前缀和数组中
        for(int i=0;i<N;i++)
            preSum[i] += numd[i];
        for(int i=0; i<N; i++){
            preSum[i+1] += 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) cout<<preSum[p--];
    cout<<"\n";
} 

int main( )
{
    // 获取输入 
    int n;
    cin>>n;
    // 求出斐波那契数列 
    getFibonacci(n);
    // 输出前缀和 
    printBigData();
    return 0;
} 


MT2196 2的N次幂

难度:黄金    时间限制:1秒    占用内存:128M
题目描述

任意给定一个正整数 N ( N ≤ 100 ) N(N\le100) N(N100) ,计算 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 n1),每遍都执行以下两步:

  • 将存放大数的数组中的每一位都乘以底数;
  • 遍历整个数组执行进位。

算法结束时,即得到了大数乘幂运算的结果。下面给出基于以上思路得到的完整代码:文章来源地址https://www.toymoban.com/news/detail-688124.html

/*
    MT2196 2的N次幂  
*/
#include<bits/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 i=0; i<N; i++)
            num[i] *= base;
        // 对数组执行进位处理
        for(int i=0; i<N; i++){
            num[i+1] += num[i] / 10;
            num[i] %= 10;
        }
    }
}

// 输出高精度运算后的大数
void printBigData()
{
    // 从最高位向后扫描,直到第 1 个非 0 数字出现 
    int p = N-1;
    while(num[p] == 0) p--;
    while(p > -1) cout<<num[p--];
    cout<<"\n";
} 

int main( )
{
    // 获取输入 
    int n;
    cin>>n;
    // 执行乘幂的高精度运算
    getHighPrecision(2, n);
    // 输出 
    printBigData();
    return 0;
} 

END


到了这里,关于【马蹄集】第二十四周——高精度计算专题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C语言 加减乘除模 的 高精度计算 (超详细)

    目录 高精度加法 高精度乘法 高精度减法          高精度除法 高精度模法   高精度计算 是模拟算法的一种,通过字符串和整型数组的使用,将加减乘除的竖式运算 模拟 出来,达到计算的目的。其步骤大致分为:一,将字符串数据存到整型数组中,二,模拟算法,不同的

    2023年04月24日
    浏览(42)
  • (基础算法)高精度加法,高精度减法

    什么叫做高精度加法呢?包括接下来的高精度减法,高精度乘法与除法都是同一个道理。正常来讲的话加减乘除,四则运算的数字都是整数,也就是需要在int的范围之内,但当这个操作数变得非常\\\"大\\\"的时候( 其实就是一个字符串,比方说有一个数是20位,如果用整数视角来

    2024年02月01日
    浏览(60)
  • 深入理解Python中的math和decimal模块:数学基础与高精度计算实战【第104篇—math和decimal模块】

    前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。【点击进入巨牛的人工智能学习网站】。 在Python中, math 和 decimal 模块是处理数学运算的重要工具。 math 提供了一系列常见的数学函数,而 decimal 则专注于高精度的浮点数运算。本文

    2024年03月19日
    浏览(52)
  • 【计算机视觉】不仅能分割一切简单物体,而且还能高精度分割一切复杂物体的SAM升级版本HQ-SAM来了

    相信很多朋友都对Facebook开源的Segement Anything(SAM)算法有很深的印象,当前SAM已经被开发出众多的热门应用,至今为止,可能已经有很多朋友用它来提升自己的工作与生产效率。 虽然SAM算法效果很好,但是当碰到复杂的图像分割任务时,SAM输出的效果并不能满足我们的需求。

    2024年02月06日
    浏览(62)
  • 高精度加法(含代码)

    例如: 1111111111111+9, 列成 竖式 , 先算个位, 1 + 9 = 10 , 满 10 , 向十位进 1 。 接下来, 处理 进位 。 十位: 1+1=2 - 2 百位: 无进位, 直接照抄. 1 - 1 千位: 1 - 1 万位: ... ...: ... 最高位: 1 - 1 最终结果: 所以, 1111111111111+ 9 = 1111111111120 1111111111111+8888888888889, 这个算式变成了 高精度 + 高精度

    2024年02月06日
    浏览(45)
  • 高精度乘法

    高精度加减法讨论的是两个大整数之间的运算。 而这里高精度乘除法讨论的是一个大整数和一个小整数之间的关系。 算法思路: 还是模拟小学的乘法列竖式,只不过此时不太一样,原本的列竖式是一位一位的乘,这里需要改变一下思路。 这里直接把小整数当成一个数,所乘

    2024年02月08日
    浏览(55)
  • 高精度算法详解

    首先要知道为什么需要高精度算法: 高精度算法是 处理大数字 的数学计算方法,当数字过大不能用 int 和 long long 存储时,我们就可以 使用string和vector类型 来存储他们的每一位,然后进行计算。 我们可以先把要输入的两个数字放到vector中存储,注意要 反着存(后边做加法

    2024年01月17日
    浏览(61)
  • 高精度减法

    要实现两个高精度数的减法,和高精度加法一样都是模拟竖式计算的过程,主要就是解决以下两个问题。 谁大谁小? 由于这两个数字都很大,但是不知道谁更大,所以要先判断哪个数更大,思路如下: 判断这两个数谁的位数更大,位数更大的自然更大。 如果位数不相同,从

    2024年02月08日
    浏览(55)
  • C++高精度算法

    目录 前言:  思路: 高精度加法: 高精度减法: 高精度乘法: 高精度除法:  代码: 一、高精度加法 二、高精度减法  三、高精度乘法  四、高精度除法 最后         计算机最初、也是最重要的应用就是数值运算。在编程进行数值运算时,有时会遇到运算的精度要求特

    2024年02月14日
    浏览(54)
  • 【算法】模拟,高精度

      P1601 A+B Problem(高精) - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 思路就是模拟,值得注意的就是要用字符串类型输入。存进自己的int数组时要倒着存,因为如果是正着存的话,进位会有点trouble。 时间复杂度O(max(m,n))    P1303 A*B Problem - 洛谷 | 计算机科学教育新生态 (lu

    2024年02月09日
    浏览(53)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包