C++实现大数乘法

2024-08-30 05:20
文章标签 c++ 实现 大数 乘法

本文主要是介绍C++实现大数乘法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

先来看一下原题目:

在编程的过程中,我们可能会遇到两个很大的数相乘的情况,此时计算的结果很有可能会超过整型的最大值,如果我们继续采取常规的方法对两个数相乘的话可能就会出现问题,此时我们就需要以字符串的形式来读取两个数字,并且编写一个函数计算他们的乘积

首先我们需要判断两个操作数是否含0,因为0乘任何数字都是0,所以只要两个数中出现过0,那么计算出来的结果也为0

        if (s == "0" || t == "0"){return "0";}

接下来我们就需要知道s和t有几个数字:

        int m = s.size();int n = t.size();

我们知道m*n的结果的数字个数不可能大于m+n,所以我们初始化一个大小为m+n的数组pos来存放每一位的乘积结果:

        vector<int> pos(m + n, 0);

接下来我们正式进入大数的运算环节:

我们先从个位数开始运算:

首先我们需要把相乘数位上面的数字转换为整型,然后创建一个新的变量mul用来保存计算结果,再设置两个p1和p2分别用来保存乘积要放在位置的数和进位位置的数,最后再创建一个sum变量用于计算当前位上的总和。

sum除以10的余数就是当前位上应该存的数,sum除以十的整数部分就是进位数:

        for (int i = m - 1; i >= 0; i--){for (int j = n - 1; j >= 0; j--){int mul = (s[i] - '0') * (t[j] - '0');int p1 = i + j;int p2 = i + j + 1;int sum = mul + pos[p2];pos[p2] = sum % 10;pos[p1] += sum / 10;}}

最后我们用string类来保存运算结果并且返回:

        string result;for (int num : pos){           result.push_back(num + '0');}

到这里程序就差不多完成了,我们来测试一下看看有没有问题:

我们可以看到这一组用例出现了问题,我们来寻找一下问题:

可以看到,因为我们一开始创建的数组初始化都为0,因为不一定两个数相乘出来的数可以占全m+n个数位,如果两数相乘没有占满时,最高位就会多出一个0,我们此时就需要把0去除:

        string result;for (int num : pos){if (!(result.empty() && num == 0)){result.push_back(num + '0');}}return result.empty() ? "0" : result;

我们把所有的代码整合一下:

class Solution
{
public:string solve(string s, string t){if (s == "0" || t == "0"){return "0";}int m = s.size();int n = t.size();vector<int> pos(m + n, 0);for (int i = m - 1; i >= 0; i--){for (int j = n - 1; j >= 0; j--){int mul = (s[i] - '0') * (t[j] - '0');int p1 = i + j;int p2 = i + j + 1;int sum = mul + pos[p2];pos[p2] = sum % 10;pos[p1] += sum / 10;}}string result;for (int num : pos){if (!(result.empty() && num == 0)){result.push_back(num + '0');}}return result.empty() ? "0" : result;}
};

修改以后代码成功运行:

这篇关于C++实现大数乘法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1119912

相关文章

Linux下删除乱码文件和目录的实现方式

《Linux下删除乱码文件和目录的实现方式》:本文主要介绍Linux下删除乱码文件和目录的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux下删除乱码文件和目录方法1方法2总结Linux下删除乱码文件和目录方法1使用ls -i命令找到文件或目录

SpringBoot+EasyExcel实现自定义复杂样式导入导出

《SpringBoot+EasyExcel实现自定义复杂样式导入导出》这篇文章主要为大家详细介绍了SpringBoot如何结果EasyExcel实现自定义复杂样式导入导出功能,文中的示例代码讲解详细,... 目录安装处理自定义导出复杂场景1、列不固定,动态列2、动态下拉3、自定义锁定行/列,添加密码4、合并

mybatis执行insert返回id实现详解

《mybatis执行insert返回id实现详解》MyBatis插入操作默认返回受影响行数,需通过useGeneratedKeys+keyProperty或selectKey获取主键ID,确保主键为自... 目录 两种方式获取自增 ID:1. ​​useGeneratedKeys+keyProperty(推

Spring Boot集成Druid实现数据源管理与监控的详细步骤

《SpringBoot集成Druid实现数据源管理与监控的详细步骤》本文介绍如何在SpringBoot项目中集成Druid数据库连接池,包括环境搭建、Maven依赖配置、SpringBoot配置文件... 目录1. 引言1.1 环境准备1.2 Druid介绍2. 配置Druid连接池3. 查看Druid监控

Linux在线解压jar包的实现方式

《Linux在线解压jar包的实现方式》:本文主要介绍Linux在线解压jar包的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux在线解压jar包解压 jar包的步骤总结Linux在线解压jar包在 Centos 中解压 jar 包可以使用 u

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中,如果使用类成员变量时未给定其初始值,那么它将被

C++中NULL与nullptr的区别小结

《C++中NULL与nullptr的区别小结》本文介绍了C++编程中NULL与nullptr的区别,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编... 目录C++98空值——NULLC++11空值——nullptr区别对比示例 C++98空值——NUL

C++ Log4cpp跨平台日志库的使用小结

《C++Log4cpp跨平台日志库的使用小结》Log4cpp是c++类库,本文详细介绍了C++日志库log4cpp的使用方法,及设置日志输出格式和优先级,具有一定的参考价值,感兴趣的可以了解一下... 目录一、介绍1. log4cpp的日志方式2.设置日志输出的格式3. 设置日志的输出优先级二、Window

Qt使用QSqlDatabase连接MySQL实现增删改查功能

《Qt使用QSqlDatabase连接MySQL实现增删改查功能》这篇文章主要为大家详细介绍了Qt如何使用QSqlDatabase连接MySQL实现增删改查功能,文中的示例代码讲解详细,感兴趣的小伙伴... 目录一、创建数据表二、连接mysql数据库三、封装成一个完整的轻量级 ORM 风格类3.1 表结构

基于Python实现一个图片拆分工具

《基于Python实现一个图片拆分工具》这篇文章主要为大家详细介绍了如何基于Python实现一个图片拆分工具,可以根据需要的行数和列数进行拆分,感兴趣的小伙伴可以跟随小编一起学习一下... 简单介绍先自己选择输入的图片,默认是输出到项目文件夹中,可以自己选择其他的文件夹,选择需要拆分的行数和列数,可以通过