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

由于数字无法用一个整形变量存储，很自然的想到用字符串来表示一串数字。然后按照乘法的运算规则，用一个乘数的每一位乘以另一个乘数，然后将所有中间结果按正确位置相加得到最终结果。可以分析得出如果乘数为A和B，A的位数为m，B的位数为n，则乘积结果为m+n-1位（最高位无进位）或m+n位（最高位有进位）。因此可以分配一个m+n的辅存来存储最终结果。为了节约空间，所有的中间结果直接在m+n的辅存上进行累加。

C++实现大数相乘代码如下：

#include<iostream>
#include<string>
using namespace std;

  string BigNumMultiply(string str1,string str2)
  {
  int size1=str1.size(),size2=str2.size();
  string str(size1+size2,'0');
  for(int i=size2-1;i>=0;--i)
 {
 int mulflag=0,addflag=0;
 for(int j=size1-1;j>=0;--j)
 {
 int temp1=(str2[i]-'0')*(str1[j]-'0')+mulflag;
 mulflag=temp1/10;
 temp1=temp1%10;
 int temp2=str[i+j+1]-'0'+temp1+addflag;
 str[i+j+1]=temp2%10+48;
 addflag=temp2/10;
 }
 str[i]+=mulflag+addflag;
 }
 if(str[0]=='0')
 str=str.substr(1,str.size());
 return str;
 }

 int main()
 {
 string str1,str2;
 while(cin>>str1>>str2)
 {
 cout<<str1<<"*"<<str2<<"="<<endl;
 cout<<BigNumMultiply(str1,str2)<<endl;
 }
 return 0;
}

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

赞 (0)

相关推荐

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

    C++实现大数相乘算法

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

  • C++实现大整数乘法

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

  • 深入分析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++实现的大数相乘算法示例

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

  • c++大数阶乘的实现方法

    C++代码如下: #include <algorithm>#include <vector>#include <cstdio>using namespace std;typedef  unsigned int Type;enum{ BASE_DATA = 10000, MAX_NUM = 100000 , MAX_SIZE = MAX_NUM+1000};struct MulOpt {Type data1;MulOpt(Type x):data1(x){}inline

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

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

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

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

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

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

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

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

  • C++快速幂与大数取模算法示例

    一.快速幂 其实就是求(a^b)% p ,(其中a,b,p都比较大在int范围内)这类问题. 首先要知道取余的公式: (a*b)%p=(a%p*b%p)%p . 那么幂不就是乘机的累积吗,由此给出代码: int fast(int a,int b,int p) { long long a1=a,t=1; while(b>0) { if(b&1) /如果幂b是奇数多乘一次,因为后边会除2变偶数,(7/2=3) t=(t%p)*(a1%p)%p; a1=(a1%p)*(a1%p)%p; b/=2;

  • 深入第K大数问题以及算法概要的详解

    解法1: 我们可以对这个乱序数组按照从大到小先行排序,然后取出前k大,总的时间复杂度为O(n*logn + k). 解法2: 利用选择排序或交互排序,K次选择后即可得到第k大的数.总的时间复杂度为O(n*k) 解法3: 利用快速排序的思想,从数组S中随机找出一个元素X,把数组分为两部分Sa和Sb.Sa中的元素大于等于X,Sb中元素小于X.这时有两种情况:1. Sa中元素的个数小于k,则Sb中的第k-|Sa|个元素即为第k大数:2. Sa中元素的个数大于等于k,则返回Sa中的第k大数.时间复杂度近

  • 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分过不了.. 更一下, 刚刚好像发现第三题...这个>号, 我写的是>= ....? 可是我看题目好像是 >= 呀...

随机推荐