高精度除法

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

一、算法描述

高精度除法和乘法讨论的一样,都是一个大整数和一个小整数之间的运算。

算法思路

  • 根据小学除法一样,我们还是模拟这个过程。

  • 注意这里遍历\(A\)数组的时候要按照我们读数字的顺序,也就是从数组尾部到头部遍历。

  • 每一位的计算过程应该是,上一轮的余数\(r\)\(10\)之后加上当前位数上的数A[i],即r = r * 10 + A[i]

  • 然后计算当前位数上的答案并加入答案数组,C.push_back(r / b),然后计算余数进行下一轮的计算,r = r % b

  • 假如答案是\(0084\),那么我们将答案加入数组的顺序也是\(0、0、8、4\),为了方便处理前导\(0\)以及统一输出,我们需要将答案逆序一下。

  • 最后的结果需要将余数带出来,所以参数用一个引用表示余数。

经过优化之后代码如下:

vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> C;
    for (int i = A.size() - 1; i >= 0; --i)
    {
        r = r * 10 + A[i];
        
        C.push_back(r / b);
        r = r % b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0)   C.pop_back();
    
    return C;
}

二、题目描述

给定两个非负整数(不含前导 \(0\)\(A,B\),请你计算 \(A/B\) 的商和余数。

输入格式

共两行,第一行包含整数 \(A\),第二行包含整数 \(B\)

输出格式

共两行,第一行输出所求的商,第二行输出所求余数。

数据范围

\(1≤A的长度≤100000,\)
\(1≤B≤10000,\)
\(B\) 一定不为 \(0\)文章来源地址https://www.toymoban.com/news/detail-711046.html

输入样例:

7
2 

输出样例:

3
1 

三、题目来源

AcWing算法基础课-794.高精度除法

四、源代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 100010;

vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> C;
    for (int i = A.size() - 1; i >= 0; --i)
    {
        r = r * 10 + A[i];
        
        C.push_back(r / b);
        r = r % b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0)   C.pop_back();
    
    return C;
}

int main()
{
    string a;
    int b;
    cin >> a >> b;
    
    vector<int> A;
    for (int i = a.size() - 1; i >= 0; --i) A.push_back(a[i] - '0');
    
    int r = 0;
    vector<int> C = div(A, b, r);
    for (int i = C.size() - 1; i >= 0; --i) cout << C[i];
    cout << endl << r << endl;
    
    return 0;
}

到了这里,关于高精度除法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 高精度除法【c++实现】超详细讲解

    高精度算法分为两种,高精除以低精和高精除以高精。不要看都是除法,就认为原理类似,其实是有很大差距的。让我们一起来学习吧! 有句话说在前面,如果除数等于0,就不要算了,不成立。( 如果你忘了这个知识,小学数学老师饶不了你 ) 高精度除低精度,原理是模

    2024年02月13日
    浏览(44)
  • 高精度乘法

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

    2024年02月08日
    浏览(54)
  • 高精度乘法模板(fft)

     正常高精度复杂度是o(n^2),fft复杂度o(nlogn)

    2024年02月10日
    浏览(46)
  • Acwing793. 高精度乘法

    AcWing 793. 高精度乘法 A x b 和 A x B 的模版(大数相加、大数相乘通用模板)

    2024年02月10日
    浏览(42)
  • (基础算法)高精度加法,高精度减法

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

    2024年02月01日
    浏览(60)
  • 算法笔记——高精度算法(附源码)

    📖作者介绍:22级树莓人(计算机专业),热爱编程<目前在c++阶段, 因为最近参加新星计划算法赛道(白佬),所以加快了脚步,果然急迫感会增加动力 ——目标Windows,MySQL,Qt,数据结构与算法,Linux,多线程,会持续分享学习成果和小项目的 📖作者主页:热爱编程的

    2023年04月08日
    浏览(73)
  • 高精度算法笔记·····························

    加法 减法 乘法 除法 高精度加法的步骤: 1.高精度数字利用字符串读入 2.把字符串 翻转 存入两个整型数组A、B 3.从低位到高位,逐位求和,进位,存余 4.把数组C从高位到低位依次输出         1.2为准备         3为加法具体实现(0按位取反为-1,即-1时结束等价于=0)  

    2024年01月21日
    浏览(60)
  • 【算法】模拟,高精度

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

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

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

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

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

    2024年01月17日
    浏览(60)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包