C++实现大数相乘算法

本文实例为大家分享了C++实现大数相乘的具体代码，供大家参考，具体内容如下

首先说一下乘法计算的算法：同样是模拟人工计算时的方法。

从低位向高位乘，在竖式计算中，我们是将乘数第一位与被乘数的每一位相乘，记录结果之后，用第二位相乘，记录结果并且左移一位，以此类推，直到计算完最后一位，再将各项结果相加，得出最后结果。
计算的过程基本上和小学生列竖式做乘法相同。为编程方便，并不急于处理进位，而将进位问题留待最后统一处理。
我们以125*53为例来说明计算过程：

1、先算125*3，3*5得到15个1，3*2得到6个10，3*1得到3个100，下面是存储结果的数组的形式

2、接下来算125*5，5*5得到25个10，2*5得到10个100，5*1得到5个1000；

3、乘法过程完毕。接下来从 a[0]开始向高位逐位处理进位问题。a[0]留下5，把1 加到a[1]上，a[1]变为32 后，应留下2，把3 加到a[2]上……最终使得a里的每个元素都是1 位数，结果就算出来了

结果就是6625。

总结一个规律：即一个数的第i 位和另一个数的第j 位相乘所得的数，一定是要累加到结果的第i+j 位上。这里i， j 都是从右往左，从0 开始数。
即：ans[i+j] = a[i]*b[j];

另外进位时要处理，当前的值加上进位的值再看本位数字是否又有进位；前导清零。

下面是C++代码实现：

#include<iostream>
#include<string>
#include<cstdio>

using namespace std;
#define MAX 1010 

int main()
{
string std1, std2;
cin>>std1>>std2;
int length1 = std1.length();
int length2 = std2.length();
int a[MAX] = {0};
int b[MAX] = {0};
int result[2 * MAX] = {0};
int i = 0, j = 0;
//将字符串转移到数组中，以方便计算 ，注意是倒叙存储
//即字符串123存为321，为的是将低位放在前面方便计算
for(i = length1 - 1, j = 0; i >= 0; i--, j++)
{
a[j] = std1[i] - '0';
}
for(i = length2 - 1, j = 0; i >= 0; i--, j++)
{
b[j] = std2[i] - '0';
}
//将结果储存在 resullt中，result[i + j] = a[i] * b[j]是关键算法
for(i = 0; i < length1; i++)
{
for(j = 0; j < length2; j++)
{
result[i + j] += a[i] * b[j];
}
}

//从低位到高位进行进位

for(i = 0; i < (length1+length2); i++)
{
if(result[i] > 9)
{
result[i+1] += result[i]/10;
result[i] %= 10;
}
}
//将前导0全部剔掉，比如我们结果是236，在result中
//是这样存储的63200……我们需要定位到第一个不为零的数，它的位置也就是i ，两数相乘，位数最多是两数位数之和

for(i = length1 + lengrh2; i >= 0 ; i--)
{
if(result[i] == 0) continue;
else break;
}
//接着i继续输出，就是我们的结果
for(; i >=0; i--)
cout<<result[i];
return 0;
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • C++实现的大数相乘算法示例

    本文实例讲述了C++实现的大数相乘算法.分享给大家供大家参考,具体如下: 昨晚校招笔试,虐的没脸睡觉,能力太渣了,但我还在码农的坑里前行,希望早日跳坑,解决衣食住行之忧. 大数相乘,是指那些相乘结果或是乘数本身用long long类型都会溢出的数字,通常这些数字都通过string类型进行表示,借助于可动态调整大小的数据结构(vector,string,deque)模拟实现数字的乘法操作.对于普通的乘法,我们知道m位数和n位数相乘,最后的结果位数在区间内[m+n-1,m+n].例如34*56,我们

  • 深入分析C++中两个大数相乘结果不正确的问题

    在编写代码做测试时发现两个大数相乘结果不正确的问题,测试代码如下: #include "stdafx.h"#include<stdlib.h>#include<time.h>int _tmain(int argc, _TCHAR* argv[]){      time_t temp1=1345172428000000;    time_t temp2=1345172428*1000000;   ::system("pause");    re

  • C++实现大整数乘法

    算法竞赛入门经典 这本书并没有对大数乘法实现,所以自己补充了一下,乘法的实现很简单,就是再其数据结构基础上把每宽为8位的十进制数看成多项式的系数,vector的下标看成多项式的指数,然后再对应相乘相加就可以了,注意系数超过8位 将超八位的补分进位. 我这里是笛卡尔相乘.一般来说是够用的. 但其实多项式乘法算法还有很多更高效的. #include <iostream> #include <vector> #include <cstring> #include <cs

  • C++实现大数相乘算法

    C++实现大数相乘算法

    本文实例为大家分享了C++实现大数相乘的具体代码,供大家参考,具体内容如下 首先说一下乘法计算的算法:同样是模拟人工计算时的方法. 从低位向高位乘,在竖式计算中,我们是将乘数第一位与被乘数的每一位相乘,记录结果之后,用第二位相乘,记录结果并且左移一位,以此类推,直到计算完最后一位,再将各项结果相加,得出最后结果. 计算的过程基本上和小学生列竖式做乘法相同.为编程方便,并不急于处理进位,而将进位问题留待最后统一处理. 我们以125*53为例来说明计算过程: 1.先算125*3,3*5得到15个1,

  • C++自定义API函数实现大数相乘算法

    前言: 之所以取题目的前部分为自定义API函数(不断更新中),是因为笔者想形成一套算法良好.接口清晰.方便编写程序的算法之意,也是为了日后更好调用算法,遇到相似的问题直接调用即可,以及方便大家使用,开发出更高效率的程序.其中的效率不敢说最好,还希望大家互相交流,共同进步!下面进入正题. 普通的乘法计算用int.long.double都可以解决,但有时候需要处理的数字过大,从而产生溢出,以下是实现任意长度的正整数A*B的算法,即大数相乘,这个算法比较简单易懂,思路如下: 1.在主函数用char型数

  • C++实现大数相乘的算法

    由于数字无法用一个整形变量存储,很自然的想到用字符串来表示一串数字.然后按照乘法的运算规则,用一个乘数的每一位乘以另一个乘数,然后将所有中间结果按正确位置相加得到最终结果.可以分析得出如果乘数为A和B,A的位数为m,B的位数为n,则乘积结果为m+n-1位(最高位无进位)或m+n位(最高位有进位).因此可以分配一个m+n的辅存来存储最终结果.为了节约空间,所有的中间结果直接在m+n的辅存上进行累加. C++实现大数相乘代码如下: #include<iostream> #include<st

  • C++实现大数乘法算法代码

    C++实现大数乘法算法代码 复制代码 代码如下: //大数乘法算法 #include<iostream> #include<string> #include<cstring> using namespace std; int main() {     string num1,num2;     cin >> num1 >> num2;     //cout << num1.size() << " " &

  • JS实现大数相加大数相乘示例详解

    目录 JS大数相加.大数相乘 一.实现两个大数相加 二.实现两个大数相乘 JS大数相加.大数相乘 JavaScript 只有一种数字类型,可以使用也可以不使用小数点来书写数字. 在 JavaScript 中,数字不分为整数类型和浮点数类型,所有的数字都是浮点数类型.JavaScript 采用 IEEE754 标准定义的 64 位浮点格式表示数字,此格式用 64 位存储数值.其中 0~51存储数字片段,52~62存储指数,63 位存储符号. 来看看 JavaScript 中数字的最大值和最小值:

  • JS实现两个大数(整数)相乘

    大数,即超出语言所能表示的数字最大范围的数字,此时的数字只能用字符串来表示.那么如何实现两个大数相乘呢?我用JS实现了一下,代码如下: 复制代码 代码如下: console.log(bigMut("567", "1234")); // 699678 function bigMut(big, common) { big += ""; common += ""; if (big.length < common.length)

  • 基于C++的拼多多算法在线笔试题示例

    本文实例讲述了基于C++的拼多多算法在线笔试题.分享给大家供大家参考,具体如下: 最近在狼厂实习中,很久没做题了.秋招第一发, 拼多多...  四个简单题,看到有些人竟然觉得难? 我来降一发自己的RP,这题目觉得难的,如果你拿到比我好的Offer,我是不服气的.. 四个题...其实我也就写了40分钟吧..不过最后也没有满分, 390/400, 第三题不知道为嘛一直有10分过不了.. 更一下, 刚刚好像发现第三题...这个>号, 我写的是>= ....? 可是我看题目好像是 >= 呀...

  • C#实现分治算法求解股票问题

    C#实现分治算法求解股票问题

    目录 分治策略是: 可使用分治法求解的一些经典问题 分治算法 - 最大子数组问题 (1)暴力求解 (2)分治法 分治法实现大数相乘 C#实现 分治策略是: 对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解.这种算法设计策略叫做分治法. 可使用分治法求解的一些经典问题 (1)二分搜索 (2)大整数乘法 (3)Strassen矩阵乘法 (4)

随机推荐