【算法基础】高精度乘法（C++描述）

Fivk

2021 年 03 月 20 日

1251 次浏览

暂无评论

707字数

算法基础

【算法分析】

类似加法，可以用竖式乘法。在做乘法运算时同样也有进位，同时对每一位进行乘法运算时，必须进行错位相加。如图：

![](https://blog.fivk.cn/usr/uploads/2021/03/3113439865.png)

分析c数组下标的变化规律，可以写出如下关系式：c[i]=c'[i]+c''[i]+...由此可见,c[i]跟a[i]*b[i]乘积有关，跟上次的进位有关，还跟原c[i]的值有关，分析下标规律，有

c[i+j-1]=a[i]*b[j]+x+c[i+j-1]

x=c[i+j-1]/10;

c[i+j-1]%=10;

</div>

* 高精度乘法的参考程序：

```C
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

int main(int argc, char* argv[])
{
	char a1[101], b1[101];
	int a[101], b[101], c[10001], lena, lenb, lenc, i, j, x;

memset(a, 0, sizeof(a));
	memset(b, 0, sizeof(b));
	memset(c, 0, sizeof(c));

gets_s(a1);
	gets_s(b1);

lena = strlen(a1);
	lenb = strlen(b1);

for (i = 0; i <= lena - 1; i++)	a[lena - i] = a1[i] - '0';
	for (i = 0; i <= lenb - 1; i++)	b[lenb - i] = b1[i] - '0';

for (i = 1; i <= lena; i++)
	{
		x = 0;							//用于存放进位
		for (j = 1; j <= lenb; j++)		//对乘数的每一位进行处理
		{
			c[i + j - 1] = a[i] * b[j] + x + c[i + j - 1];
										//当前乘积+上次乘积进位+原数
			x = c[i + j - 1] / 10;
			c[i + j - 1] %= 10;
		}
		c[i + lenb] = x;				//进位
	}
	lenc = lena + lenb;					//设为最大长度
	while (c[lenc] == 0 && lenc > 0)	lenc--;

for (i = lenc; i >= 1; i--)
		cout << c[i];
	cout << endl;
	return 0;
}
```

<div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-6d917203a37921dbb867a805a8e4e85194" aria-expanded="true"><div class="accordion-toggle"><span style="">例题：高精度阶乘</span>
<i class="pull-right fontello icon-fw fontello-angle-right"></i>
</div>
</div>
<div class="panel-body collapse-panel-body">
<div id="collapse-6d917203a37921dbb867a805a8e4e85194" class="collapse collapse-content"><p></p>

用高精度方法，求n！的精确值（n以一般整数输入）。

**输入格式:**

一个整数

**输出格式:**

一个整数

**输入样例:**

```in
10
```

**输出样例:**

```out
3628800
```

```cpp
#include <stdio.h>
int ans[100001];
int jw[100001];
int count = 1;
int n;
int main()
{
	scanf("%d",&n);
	ans[1] = 1;
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= count; j++)
		{
			ans[j] = ans[j]*i + jw[j];
			jw[j] = 0;

if(ans[j]>=10)
			{
				jw[j+1] += ans[j]/10;
				ans[j] %= 10;
	
				if(j == count) count++;
			}
		}
	}

for(int i = count; i >= 1; i--) printf("%d",ans[i]);

return 0;
}
```

最后修改：2023 年 09 月 14 日