分治法求大整数乘法的具体算法思想及其C语言实现

分治法求大整数乘法的算法思想是将大整数按一定规则分割成小的整数段，对每一段进行相乘运算，并将结果相加得到最终结果。具体实现中，采用递归调用函数的方式将原问题不断划分成子问题，直至最小子问题可以直接求解为止。C语言实现如下：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define N 10000

void strnozero(char *);//去除开头的"0"
void makeno(char *,int);//在字符串前面补0
void mul(char*,char*,int,char*);//大整数乘法
void Split_Str(char*,char*,char*);//将字符串分割
int Max(int,int);//比较大小
char a[N],b[N],c[N],d[N];

int main() {
    memset(a,0,N);
    memset(b,0,N);
    memset(c,0,N);
    memset(d,0,N);
    printf("请输入两个大整数:\n");
    scanf("%s %s",a,b); //输入两个大整数
    strnozero(a);
    strnozero(b);
    if(strcmp(a,"0")==0||strcmp(b,"0")==0)//如果输入的数有一个是0，则直接输出0
        printf("0");
    else {
        int lena=strlen(a),lenb=strlen(b);
        int lenc,len,k=0;
        lenc=lena+lenb;
        len=Max(lena,lenb);
        if(len%2==1)++len; //如果len是奇数，加1变成偶数
        makeno(a,len);
        makeno(b,len);
        for(int i=0;i<lenc;i++)
            c[i]='0';
        mul(a,b,len,c); //调用函数求解
        strnozero(c);
        printf("%s",c);
    }
    return 0;
}

void makeno(char *a,int len) {
    int l=strlen(a),k=len-l;
    for(int i=len-1;i>=k;--i)
        a[i]=a[i-k];
    for(int i=0;i<k;i++)
        a[i]='0';
}

int Max(int x,int y) {
    if(x>y)return x;
    else return y;
}

void mul(char *a,char *b,int len,char *ans) {
    if(len==1) { //递归结束条件
        int num=(a[0]-'0')*(b[0]-'0');
        ans[0]=num%10+'0';
        ans[1]=num/10+'0';
        ans[2]='\0';
        return;
    }
    memset(c,0,sizeof(c));
    memset(d,0,sizeof(d));
    int len1=len/2;
    int len2=len-len1;
    Split_Str(a,c,d); //将a,c,d各自分割成2段
    mul(c,b,len1,ans);
    mul(d,b,len2,ans+len1*2);
    makeno(c,len1+len2);
    makeno(d,len1+len2);
    strnozero(c);
    strnozero(d);
    strnozero(ans);
    ans[len]=0;
    strnozero(ans);
    mul(c,b,len1,ans+len1);
    mul(d,b,len2,c);
    for(int i=0; i<len; i++) {
        ans[i]+=(c[i]+d[i]-'0');
        if(ans[i]>'9') {
            ans[i]+=1-'0';
            ans[i+1]++;
        }
    }
    ans[len]='\0';
    strnozero(ans);
}

void strnozero(char *a) {
    int len=strlen(a);
    int i,j;
    for(i=0;a[i]=='0';i++);
    if(i>0) {
        for(j=i;j<=len;j++)
            a[j-i]=a[j];
    }
}

void Split_Str(char *a,char *c,char *d) {
    int len1=strlen(a)/2;
    int len2=strlen(a)-len1;
    for(int i=0; i<len1; i++)
        c[i]=a[i];
    c[len1]='\0';
    for(int i=len1; i<len1+len2; i++)
        d[i-len1]=a[i];
    d[len2]='\0';
}

希望能够解决您的问题。