算法学习(2):分治法(下)

大整数乘法

1.算法原理

如果我们想要计算两个较大的数字相乘的时候,由于计算机硬件限制可能无法计算,因此我们可以将每个乘数用加法和乘法做分解,当分解到每个因子只是一位数的时候,乘法就很简单了,这也是一种分治法。

(1)分解:首先将2个大整数a(n位)、b(m位)分解为两部分:

ah al   bh bl

然后,

其中ah、al为n/2位,bh、bl为m/2位。两个大整数a、b相乘转换成了4个乘法运算,而乘数的位数变为了原来的一半。

(2)求解子问题。继续分解每个乘法运算,直到分解有一个乘数为1位数时停止分解,进行乘法运算并记录结果。

(3)合并。将计算出的结果相加并回溯,求出最终结果。

2.算法设计

(1)数据结构。将两个大数以字符串的形式输入,然后定义结构体Node,其中s[]数组用于存储大数,注意是倒序存储!(因为乘法加法运算中有可能出现进位,倒序存储时可以让进位存储在数组的末尾)。l表示长度,c表示幂次。两个大叔的初始次幂是0.如下所示:

char sa[1000];

char sb[1000];

typedef struct _Node

{

       int s[M];//数组,倒序存储大数

       int l;

       int c;

}Node, *pNode;

 

(2)划分函数。其中,cp()函数用于将一个n位的数分成两个n/2的数并存储,记录它的次幂和长度。

void cp(pNode src, pNode des, int st, int l)

{

       //src表示待分解的数的结点,des表示分解后得到的数结点

       //st表示从src结点数组中取数的开始位置,l表示取数长度

       int i, j;

       for (i = st, j = 0; i<st + l; i++, j++)

       {

              des->s[j] = src->s[i];//从src节点数组中st位置开始取l个数

       }

       des->l = l;

       des->c = st + src->c;//des次幂等于开始取数的位置加上src次幂。

}

 

(3)乘法运算。定义的mul()函数用于将两个数进行相乘,不断进行分解,直到有一个乘数为1位时停止,让这两个数相乘,并记录结果回溯。

ma = pa->l/2;//表示a长度的一半

mb = pb->l/2;//表示b长度的一半

if(!ma || !mb)//如果!ma说明ma=0,即a的长度为1,该乘数为1位数,同理对mb也是

{

       if(!ma)//!ma说明a为1位数,a/b交换,保证a的长度大于b的长度

       {

              temp=pa;

              pa=pb;

              pb=temp;//交换后b的长度为1

       }

       ans->c = pa->c +pb->c;

       w=pb->s[0];//交换后b长度为1,用w记录即可

       cc=0;//初始化进位为0

       for(i=0;i<pa->;i++)

       {//把a中的数依次取出与w相乘,记录结果和进位

              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;

 

(4)合并函数

add()函数将分解得到的数进行相加合并。

void add(pNode pa, pNode pb, pNode ans)

{

       //程序调用时把a、b的地址传递给pa、pb参数,表示待合并的两个数

       //ans记录结果

       int i,cc,k,alen,blen,len;

       int ta,tb;

       pNode temp;

       if(pa->c <pb->c)//交换保证a的次幂大

       {

              temp=pa;

              pa=pb;

              pb=temp;

       }

       ans->c=pb->c;//结果的次幂为两个数中较小数的次幂

       cc=0;//初始化进位为0

       k=pa->c-pb->c;//k为a左侧需要补零的个数

       alen = pa->l + pa->c;//a数加上次幂的总长度

       blen = pb->l + pb->c;//b数加上次幂的总长度

       if(alen>blen)

              len=alen;

       else

              len=blen;

       len=len-pb->c;//结果的长度为a/b之中的最大值减去最低次幂,最低次幂是不进行加法运算的位数

       for(i=0;i<len;i++)

       {

              if(i<k)

                     ta=0;//k为a左侧需要补零的个数,a左侧补零

              else

                     ta=pa->s[i-k];//i=k时,补零结束,从a数组中第0位开始去数字

              if(i<pb->l)

                     tb=pb->s[i];//从b数组中第0位开始取数字

              else

                     tb=0;//b数字先取完,b右侧补零

              if(i>=pa->l+k)///a数字先取完,a右侧补零

                     ta=0;

              ans->s[i]=(ta+tb+cc)%10;

              cc=(ta+tb+cc)/10;

       }

       if(cc)

              ans->s[i++]=cc;//有进位,则存入数组末位

       ans->l=i;



}

 

3.完整代码

#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)

{

       //src表示待分解的数的结点,des表示分解后得到的数结点

       //st表示从src结点数组中取数的开始位置,l表示取数长度

       int i, j;

       for (i = st, j = 0; i<st + l; i++, j++)

       {

              des->s[j] = src->s[i];//从src节点数组中st位置开始取l个数

       }

       des->l = l;

       des->c = st + src->c;//des次幂等于开始取数的位置加上src次幂。

}

//相加

void add(pNode pa, pNode pb, pNode ans)

{

       //程序调用时把a、b的地址传递给pa、pb参数,表示待合并的两个数

       //ans记录结果

       int i, cc, k, palen, pblen, len;

       int ta, tb;

       pNode temp;

       if ((pa->c)<(pb->c))//交换保证a的次幂大

       {

              temp = pa;

              pa = pb;

              pb = temp;

       }

       ans->c = pb->c;//结果的次幂为两个数中较小数的次幂

       cc = 0;//初始化进位为0

       k = pa->c - pb->c;//k为a左侧需要补零的个数

       palen = pa->l + pa->c;//a数加上次幂的总长度

       pblen = pb->l + pb->c;//b数加上次幂的总长度

       if (palen>pblen)

              len = palen;

       else

              len = pblen;

       for (i = 0; i<len - ans->c; i++) //结果的长度最长为pa,pb之中的最大长度减去最低次幂

       {

              if (i<k)

                     ta = 0;

              else

                     ta = pa->s[i - k];//次幂高的补0,大于低的长度后与0进行计算

              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, 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;

              }

              ans->c = pa->c + pb->c;

              w = pb->s[0];

              cc = 0;     //此时的进位为c

              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);  //先分成4部分al,ah,bl,bh

       cp(pa, &al, 0, ma);

       cp(pb, &bh, mb, pb->l - mb);

       cp(pb, &bl, 0, mb);



       mul(&ah, &bh, &t1);     //分成4部分相乘

       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--)

              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];         //ans用来存储结果,倒向存储

       cout << endl;

       system("pause");

       return 0;

}

 

4.复杂度分析

递推可得,T(n)=4x(Tn/2x)+(2x-1)O(n)。地推最终规模为1,令n=2x,则x=logn,那么有:

T(n)=n2

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注