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

前言：

之所以取题目的前部分为自定义API函数（不断更新中），是因为笔者想形成一套算法良好、接口清晰、方便编写程序的算法之意，也是为了日后更好调用算法，遇到相似的问题直接调用即可，以及方便大家使用，开发出更高效率的程序。其中的效率不敢说最好，还希望大家互相交流，共同进步！下面进入正题。

普通的乘法计算用int、long、double都可以解决，但有时候需要处理的数字过大，从而产生溢出，以下是实现任意长度的正整数A*B的算法，即大数相乘，这个算法比较简单易懂，思路如下：

1、在主函数用char型数组a和b分别保存输入的数字A和B；

2、对字符串数组a和b每一位互相相乘，像小学时候学的竖式乘法，结果保存在字符串数组s，但是不进行进位处理；
3、对字符串数组s每一位进行进位处理；

4、将字符串数组s赋给char型数组c，返回结果。

char版本：

//大数相乘，实现大数A*B
char* getMultiplyValue(char a[],char b[]) //参数a：char型数组a的数组名；参数b：char型数组b的数组名；
{
  int i,j,ca,cb,*s,cs;
 char *c;

 ca=strlen(a); //求字符串数组a的长度
  cb=strlen(b); //求字符串数组b的长度
 cs=ca+cb;
 s=new int[cs];
 c=new char[cs];

 //初始化
 for(i=0;i<cs;i++)
 s[i]=0;

 //直接纵向求和，不处理进位
 for(i=0;i<ca;i++)
 for(j=0;j<cb;j++)
  s[i+j+1]+=(a[i]-'0')*(b[j]-'0'); //因为s[0]用来后面保存最高位进位，所以从s[1]开始

 //对求和后的数处理进位
 for(i=cs-1;i>=0;i--)
 if(s[i]>=10)
 {
  s[i-1]+=s[i]/10;
  s[i]%=10;
 }

 //如果最高位没有进位，则舍弃开头0
  i=0;
 while(s[i]==0)
 i++;

 //保存结果到字符串
 for(j=0;i<cs;i++,j++)
 c[j]=s[i]+'0';
 c[j]='\0'; 

 return c;

}

另外，附上string版本的，

#include <string>
using namespace std;

//大数相乘，实现大数A*B
string getMultiplyValue(string a,string b) //参数a：string型a的变量名；参数b：string型b的变量名；
{
  int i,j,ca,cb,cs,*s;
 string sum;

 ca=a.length(); //求字符串a的长度
  cb=b.length(); //求字符串b的长度
 s=new int[cs=ca+cb];

 //初始化
 for(i=0;i<cs;i++)
 s[i]=0;

 //直接纵向求和，不处理进位
 for(i=0;i<ca;i++)
 for(j=0;j<cb;j++)
  s[i+j+1]+=(a[i]-'0')*(b[j]-'0'); //因为s[0]用来后面保存最高位进位，所以从s[1]开始

 //对求和后的数处理进位
 for(i=cs-1;i>=0;i--)
 if(s[i]>=10)
 {
  s[i-1]+=s[i]/10;
  s[i]%=10;
 }

 //如果最高位没有进位，则舍弃开头0
  i=0;
 while(s[i]==0)
 i++;

 //保存结果到字符串
 for(j=0;i<cs;i++,j++)
 sum+=s[i]+'0';

 return sum;

}

下面给出的是char版本的运行实例（string版本同理），更彻底教会大家如何使用，

#include <iostream>
using namespace std;
int main()
{
 char a[255],b[255];

 cin>>a>>b;          //输入数字a,b

 cout<<getMultiplyValue(a,b)<<endl;  //输出a*b

 return 0;
}

希望对大家有所帮助。

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

赞 (0)

相关推荐

  • 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++实现大整数乘法

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

  • C++实现大整数乘法（字符串乘法）

    本文实例为大家分享了C++实现大整数乘法的具体代码,供大家参考,具体内容如下 #include<iostream> #include<algorithm> #include<string> using namespace std; string add(string a,string b) { if(a.length()==0) return b; if(b.length()==0) return a; a.length()<b.length()?a.swap(b

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

    C++实现大数相乘算法

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

  • 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() << " " &

  • 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++自定义API函数实现大数相乘算法

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

  • javascript数组对象常用api函数小结(连接,插入,删除,反转,排序等)

    本文实例讲述了javascript数组对象常用api函数.分享给大家供大家参考,具体如下: 1. concat() 连接两个或多个数组,并返回结果 var a = [1,2,3]; var b = a.concat(6,7); console.log(a); //[1,2,3] console.log(b); //[1,2,3,6,7] 2. join(str) 把数组的所有元素用str分隔,默认逗号分隔 var a = [1,2,3] var b = a.join('|'); console.

  • php自定义hash函数实例

    本文实例讲述了php自定义hash函数实现方法.分享给大家供大家参考.具体分析如下: 这里演示php实现的一个简单hash算法,可以用来加密,不过这个函数过于简单,不能用来解密 function SimpleHash($str){ $n = 0; // The magic happens here: // I just loop trough all letters and add the // ASCII value to a integer variable. for ($c=0; $c <

  • javascript字符串对象常用api函数小结(连接,替换,分割,转换等)

    本文实例讲述了javascript字符串对象常用api函数.分享给大家供大家参考,具体如下: 1. concat(str1,str2,···) 连接字符串 2. indexOf(str,start) 返回 str 在字符串中首次出现的位置 var str = "hello world"; str.indexOf("hello"); // 0 str.indexOf("o",5); // 7 str.indexOf("World"

  • jQuery自定义动画函数实例详解(附demo源码)

    jQuery自定义动画函数实例详解(附demo源码)

    本文实例讲述了jQuery自定义动画函数完整实现技巧.分享给大家供大家参考,具体如下: 运行效果截图如下: 在线演示地址如下: http://demo.jb51.net/js/2015/jquery-zdy-dh-move-style-demo/ 具体代码如下: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.d

  • PHP实现的自定义数组排序函数与排序类示例

    本文实例讲述了PHP实现的自定义数组排序函数与排序类.分享给大家供大家参考,具体如下: /* * 二维数组自定义排序函数 * uasort($arr,function_name) * **/ $arr = array( array('a'=>1,'b'=>'c'), array('a'=>4,'b'=>'a'), array('a'=>5,'b'=>'g'), array('a'=>7,'b'=>'f'), array('a'=>6,'b'=>'

  • js自定义trim函数实现删除两端空格功能

    本文实例讲述了js自定义trim函数实现删除两端空格功能.分享给大家供大家参考,具体如下: 兼容IE低版本浏览器,以及其他一些低版本脚本的浏览器 js中本身是没有trim函数的 //删除左右两端的空格 function trim(str){ return str.replace(/(^\s*)|(\s*$)/g, ""); } //删除左边的空格 function ltrim(str){ return str.replace(/(^\s*)/g,""); } //删

随机推荐