（趣学算法）分治算法：大整数乘法

╰半橙微兮° 2022-05-16 15:59 162阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 2][]

#include<stdlib.h>
    #include<cstring>
    #include<iostream>
    using namespace std;
    #define M 100
    char sa[1000];
    char sb[1000];
    typedef struct _Node{
    	int s[M];
    	int l;//代表字符串长度 
    	int c;//幂 
    } Node, *pNode;
    
    void cp(pNode src, pNode des, int st, int l)
    {
    	int i, j;
    	for(i = st, j = 0; i <= st+l; i++, j++)
    	{
    		des->s[j] = src->s[i];
    	}
    	des->l = l;
    	des->c = st + src->c;//次幂 
    }
    
    void add(pNode pa, pNode pb, pNode ans)
    {
    	int i, cc, k, palen, pblen, len;
    	int ta, tb;
    	pNode temp;
    	if((pa->c < pb->c)) //保证pa的次幂大
    	{
    		temp = pa;
    		pa = pb;
    		pb = temp;
    	} 
    	ans->c = pb->c;
    	cc = 0;
    	palen = pa->l + pa->c;
    	pblen = pb->l + pb->c;
    	if(palen > pblen)
    		len = palen;
    	else
    		len = pblen;
    	k = pa->c - pb->c;//k为左侧需要补零的个数 
    	for(i = 0; i <len - ans->c; i++)//结果的长度为pa pb的最大长度-最低次幂 
    	{
    		if(i < k) 
    			ta = 0;
    		else
    			ta = pa->s[i-k];
    		if(i < pb->l)
    			tb = pb->s[i];
    		else
    			tb = 0; 
    		if(i >= pa->l + k)
    			ta = 0;
    		ans->s[i] = (ta+tb+cc)%10;
    		cc = (ta + tb +cc)/10;
    	}
    	if(cc)
    		ans->s[i++] = cc;
    	ans->l = i;
    } 
    
    void mul(pNode pa, pNode pb, pNode ans)
    {
    	int i, cc, w;
    	int ma = pa->l >> 1;
    	int mb = pb->l >> 1;//长度除以2
    	Node ah, al, bh, bl;
    	Node t1, t2, t3, t4, z;
    	pNode temp;
    	if(!ma || !mb)//边界条件，如果其中一个数为1 
    	{
    		if(!ma)//如果a串的长度为1，pa,pb交换，pa的长度大于等于pb的长度
    		{
    			temp = pa;
    			pa = pb;
    			pb = temp;
    		} //交换后pb的长度为1 
    		ans->c = pa->c + pb->c;
    		w = pb->s[0];//用w记录pb的长度，pb的长度为1
    		cc = 0;//初始化进位为0
    		for(i = 0; i < pa->l; ++i)
    		{
    			ans->s[i] = (w*pa->s[i] + cc) %10;
    			cc = (w*pa->s[i] + cc)/10;
    		} 
    		if(cc)
    		{
    			ans->s[i++] = cc;
    		}
    		ans -> l = i;//记录结果的长度
    		return ; 
    	} 
    	
    	//分治的核心
    	cp(pa, &ah, ma, pa->l - ma);
    	cp(pa, &al, 0, ma);
    	cp(pb, &bh, mb, pb->l - mb);
    	cp(pb, &bl, 0, mb);
    	
    	mul(&ah, &bh, &t1);
    	mul(&ah, &bl, &t2);
    	mul(&al, &bh, &t3);
    	mul(&al, &bl, &t4);
    	
    	add(&t3, &t4, ans);
    	add(&t2, ans, &z);
    	add(&t1, &z, ans); 
    } 
    
    
    int main()
    {
    	Node ans,a,b;
    	cout << "输入大整数a: " << endl;
    	cin >> sa;
    	cout << "输入大整数b: " << endl;
    	cin >> sb;
    	a.l = strlen(sa);//sa,sb以字符串进行处理 
    	b.l = strlen(sb);
    	int z = 0, i;
    	for(i = a.l - 1; i >= 0; --i)//将sa,sb字符串转为数字 
    	{
    		a.s[z++] = sa[i] - '0';
    	} 
    	a.c = 0;
    	z = 0;
    	for(i = b.l - 1; i >= 0; --i)
    	{
    		b.s[z++] = sb[i] - '0';
    	}
    	b.c = 0;
    	mul(&a,&b,&ans);//乘法运算，将两个数进行相乘，不断的分解
    	cout << "最终结果为： ";
    	for(i = ans.l - 1; i >= 0; --i)//将最终结果逆序输出 
    		cout << ans.s[i];
    	cout << endl;
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70]: /images/20220503/151a18116f0c416ba8a9aeb9dead1e2d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 1]: /images/20220503/244c8e1cdb4d444bad91238e1002ee92.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 2]: /images/20220503/43dcb9034e4b4785a33a040d08b11b24.png