CC++ 高精度乘法

CC++ 高精度乘法,第1张

C/C++ 高精度乘法

实现十进制下100位(设置SIZE)乘法:
时间复杂度:O(k1*k2) (k1表示被乘数位数,k2表示乘数的位数)

# include 
using namespace std;

# define SIZE 100


int main() {
	char A[SIZE], B[SIZE];
	int k1 = 0, k2 = 0;  // length of a, b 
	// input
	do scanf("%c", &A[k1++]);
	while (A[k1-1] != 'n'); k1 --;
	printf("*n");
	do scanf("%c", &B[k2++]);
	while (B[k2-1] != 'n'); k2 --;
	
	// pretreatment
	int a[SIZE], b[SIZE], ans[2*SIZE+5];
	for (int i = k1-1; i+1; i --) a[k1-i-1] = A[i] - '0';
	for (int i = k2-1; i+1; i --) b[k2-i-1] = B[i] - '0';
	// calculate
	memset(ans, 0, sizeof(ans));
	for (int m = 0; m < k2; m ++)
		for (int n = 0; n < k1; n ++)
			ans[n+m] += a[n] * b[m];
	for (int i = 0; i < k1+k2-1; i ++) {  // carry
		ans[i+1] += ans[i]/10;
		ans[i] %= 10;
	}
	
	// output
	char C[2*SIZE+5]; int cnt = 0, t = k1+k2;
	while (!ans[--t] && t);
	for (int i = t; i+1; i --) C[cnt++] = ans[i] + '0';
	C[cnt] = '';  // 不加这句的话,当k1+k2等于9的时候会在c末尾多一个非数字字符(还tm的不固定)??(懵逼)
	// cout << ans[0] << C[cnt];  将上面的语句替换成这句后,字符就消失了??? (不能分开cout,而且也不知道这句给输出哪里去了) 
	printf("=n%sn", C);
	
	return 0;
}

输入输出示例:

>> 250182048980811753
<< *
>> 413715569939057660
<< =
<< 103504208982617773964208926672677980

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5702756.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存