有关C/C++语言实现大整数乘法的算法

标签: C/C++  计算机算法  程序设计

最近一个月的月底特别忙,一个是忙于学校的课程设计,老师要我们做一个类似于Visio的工具,除了画点函数以外,不能调用任何底层函数,算法图形全部纯手工敲代码写,所以实现起来真的好复杂,好在月底检查的时候顺利过关验收,老师给我的是最高分24分,满分25分,有时间我会分享源代码和程序。另外一件事是五月底的一篇我和导师的论文投稿,投的是CCF C类的一个会议(CoNLL 2019 Proceedings),所以也在加紧翻译和改稿子,挺头疼的改下来,但愿可以中吧,毕竟以后是真心想读博的。最后一件事是参加了华中科技大学武汉光电国家研究中心的开放日活动,中间找到了一位老师把自己的简历给了他,最后通知我去进行综合的机式和面试,所以在积极准备机式,最后机式的时候发挥一般般吧,主要是有些忘了,一直在搞机器学习的算法,基础算法有些都忘了,面试表现还不错,我的paper比较多,把自己家底的CCF系列的高质量文章做成Poster给了老师看,老师还是很满意的,最后那个团队的boss在我走的时候还特意问我是否想读他的博士,晚上问老师面试结果,老师说我的直博希望很大,也但愿我能够顺利找到自己的研究生归宿吧。
下面的一篇文章是我在准备机式的时候把以前写过的代码翻出来看看,去年的时候我就开始准备程序竞赛,中间遇到一道解决大整数乘法的问题,也就是C/C++语言支持的最大整形是long long int类型(visual c++ 6.0中不支持long long int类型的,是在vc99中添加此功能的,所以我们在vc6.0中编译有long long 的数据时,会出错,但是在VS更高的版本中,是能通过的。),但是不管你的编译器给你的long long int分配多少空间,那些上亿的整数乘法你还是没办法解决,怎么办,写代码用算法解决呗。
这道题是算法题当中比较经典的一道题目,就是让你输入两串数字,求解他们的乘积大小,例如输入:7382748923和8921489234,输出他们的乘积大小,结果为65865115033869594982,因此想要用C/C++自带的标识符和运算符进行显然是不可能实现的,因此需要另想办法。
思路是这样的,我们考虑一下小学的时候计算乘法是怎么计算的。
13625乘以4526的手工计算结果
这里我就直接手算拍照显示直接些,所以我们的算法就和以上类似,两个for循环进行遍历计算每一层的数,然后再将所有的这些数相加求和,因此问题就变成了如何求解两个整数的和了。
求和我们也可以类比我们手工计算的方法,从低位加到高位,计算到某一位的时候我们用求余的方式确定该位的数字,而产生的进位用整形的除法获得,例如某一位为9和另外一位为6,那么这一位相加后该位的数字(假设上一次计算产生的进位为c)是(9 + 6 + c)% 10,而产生的进位为(9 + 6 + c)/ 10,这一位计算后再接着下一位,直到全部计算完毕。
然后乘法的每一位的产生和上面类似,只是把+换成*,即(9 * 6 + c)% 10,而产生的进位为(9 * 6 + c)/ 10。
因此实现起来就是for循环进行操作,其实不难,但是一定要注意for循环的初始值和对应的终止值。以下给出我写的代码。

#include <iostream>
#include <stdio.h>
#include <cstring> 

using namespace std;

//  默认输出为10进制,也可以改为8进制或者二进制 
const int Dec=10;

void Add(string obj1, string obj2)
{
	//  一个为m位的数与一个为n位的数相加的数的位数最大不可超过max(m, n) + 1 
	int N = (obj1.length() > obj2.length() ? obj1.length() : obj2.length()) + 1;
	char a[N], b[N], obj[N];
	//  数组的统一初始化操作 
	memset(a, '0', sizeof(a));
	memset(b, '0', sizeof(b));
	memset(obj, '0', sizeof(obj));
	//  倒序存储便于计算 
	for (int i = obj1.length() - 1, j = 0; i >= 0; i--, j++)
		a[j] = obj1[i];
	for (int i = obj2.length() - 1, j = 0; i >= 0; i--, j++)
		b[j] = obj2[i];
	for (int i = 0, c = 0; i < N; i++)
	{
		//  相加后的余数 
		obj[i] = ((a[i] - '0') + (b[i] - '0') + c) % Dec + '0';
		//  相加后的进位 
		c = ((a[i] - '0') + (b[i] - '0') + c) / Dec;
	}
	//  检查最后一位是否为0,如果是则不输出 
	if (obj[N - 1] == '0')
	{
		char temp[N - 1];
		for (int i = N - 2, j = 0; i >= 0; i--, j++)
			cout<<obj[i];
	}
	else
	{
		char temp[N - 1];
		for (int i = N - 1, j = 0; i >= 0; i--, j++)
			cout<<obj[i];
	}
}

void Mul(string obj1, string obj2)
{
	//  一个为m位的数与一个为n位的数相乘后的数的位数最大不可超过max(m, n) * 2 
	int N = (obj1.length() > obj2.length() ? obj1.length() : obj2.length()) * 2;
	char a[N], b[N], obj[N];
	memset(a, '0', sizeof(a));
	memset(b, '0', sizeof(b));
	memset(obj, '0', sizeof(obj));
	//  倒序存储便于计算和理解 
	for (int i = obj1.length() - 1, j = 0; i >= 0; i--, j++)
		a[j] = obj1[i];
	for (int i = obj2.length() - 1, j = 0; i >= 0; i--, j++)
		b[j] = obj2[i];
	//  双重for循环,每次进行一次乘法后再进行加法运算 
	for (int i = 0; i < obj1.length(); i++)
	{
		char temp[N];
		memset(temp, '0', sizeof(temp));
		for (int j = 0, c = 0; j < obj2.length() + 1; j++)
		{
			temp[i + j] = ((a[i] - '0') * (b[j] - '0') + c) % Dec + '0';
			c = ((a[i] - '0') * (b[j] - '0') + c) / Dec;
		}
		char temp2[N];
		for (int k = 0; k < N; k++)
			temp2[k] = obj[k];
		for (int k = 0, c = 0; k < N; k++)
		{
			obj[k] = ((temp[k] - '0') + (temp2[k] - '0') + c) % Dec + '0';
			c = ((temp[k] - '0') + (temp2[k] - '0') + c) / Dec;
		}
	}
	//  输出 
	int num = 0;
	for (int i = N - 1; i >= 0; i--)
		if (obj[i] == '0') num++;
		else break;
	for (int i = N - num - 1; i >= 0; i--)
		cout<<obj[i];
}


int main(void)
{
	string obj1, obj2;
	cin>>obj1>>obj2;
	cout<<obj1<<"+"<<obj2<<"=";
	Add(obj1, obj2);
	cout<<endl;
	cout<<obj1<<"*"<<obj2<<"=";
	Mul(obj1, obj2);	
	return 0;
} 

我们输入几个数看看,比如输出232384728后回车一次,再输入4294892,最后再回车,结果如下:
232384728*4294892的计算结果
计算正确,符合我们的要求。
还有一种计算方法是用二分法进行计算,就是如果我们可以计算a * b(a和b都是一位数字),那么我们就可以递归计算二位的乘法,就这样一直下去,递归得到结果,但是递归的过程和上面相反,我们是将整数分为两部分然后进行递归,直到达到我们可以很方面处理的计算范围,代码列出如下,我就不详细写过程了。

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

const int N = 100;
const int Decimal = 10;

void print(char *add)
{
    bool flag = false;
    for (int i = N - 1; i >= 0; i--)
        if (add[i] != '0' && flag == false) flag = true, cout<<add[i];
        else if (flag) cout<<add[i];
        else {}
}

void Add(char *add, char *temp)
{
    int n = 0, m = 0, c = 0, s = 0;
    for (int i = 0; i < N; i++)
    {
        n = (add[i] - '0'), m = (temp[i] - '0');
        s = (n + m + c) % Decimal, c = (n + m + c) / Decimal;
        add[i] = s + '0';
    }
}

void f(char *p, int headp, int tailp, int lengthp,
       char *q, int headq, int tailq, int lengthq,
       char *add)
{
    if (tailq - headq!=0)
    {
        f(p, headp, tailp, lengthp, q, headq, (headq + tailq) / 2, lengthq, add);
        f(p, headp, tailp, lengthp, q, (headq + tailq) / 2 + 1, tailq, lengthq, add);
        return;
    }
    if (tailp - headp != 0)
    {
        f(p, headp, (headp + tailp) / 2, lengthp, q, headq, tailq, lengthq, add);
        f(p, (headp + tailp) / 2 + 1, tailp, lengthp, q, headq, tailq, lengthq, add);
        return;
    }
    int mul = (p[headp] - '0') * (q[headq] - '0'), num = headp + headq;
    char temp[N];
    for (int i = 0; i < N; i++)
        temp[i] = '0';
    temp[num] = mul % Decimal + '0', temp[num + 1] = mul / Decimal + '0';
    Add(add, temp);
}

int main(void)
{
    string s1 = "", s2 = "";
    cin>>s1>>s2;
    char p[N], q[N];
    char temp[N], add[N];
    int length = 0;
    for (int i = 0; i < N; i++)
        p[i] = q[i] = add[i] = temp[i] = '0';
    for (int i = s1.length() - 1, j = 0; i >= 0; i--, j++)
		p[j] = s1[i];
	for (int i = s2.length() - 1, j = 0; i >= 0; i--, j++)
		q[j] = s2[i];
    f(p, 0, s1.length(), s1.length(), q, 0, s2.length(), s2.length(), add);
    cout<<s1<<"*"<<s2<<"=";
    print(add);
    return 0;
}

我们也计算一次
在这里插入图片描述
计算正确,代码就分享在这里了,如果代码用的过程当中有问题可以给我留言,我会及时更正错误,谢谢大家。
也欢迎大家访问我的主页,我会分享一些自己学习过程当中的技术和想法,谢谢支持。

版权声明:本文为qq_43549752原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_43549752/article/details/90717554