【字符串相乘】

每天都要进步呀

发布于 2023-03-28 11:21:30

3030

发布于 2023-03-28 11:21:30

文章被收录于专栏：C++/Linux

每一个不曾起舞的日子，都是对生命的辜负。

文章目录

前言

我们已经知道，正常的两位整形数据通过*相乘，C语言中int为4字节，
32bit（字节），其机器码第一位为符号位，余下31位表示数字，表示范围：
-2^31(-2147483648)~2^31-1(2147483647),但超过了这个范围我们该如何
做呢？

提示：将数字以字符串的形式进行操作

一. 分析思路

示例：

我们把每一个数都看成是一个字符串，每一个元素为十进制数字所对应的字符，由于是后面的元素先进行运算，故我们应当把末尾的字符赋值给a[0],以此类推。如下所示：（s1,s2分别表示两个相乘的字符串）

for(i=0; i<n; i++)
            a[i]=s1[n-i-1]-'0';
        for(i=0; i<m; i++)
            b[i]=s2[m-1-i]-'0';

当我们把需要操作的前后顺序弄清之后，接下来就是核心的算法部分了（看了几篇关于这个的博文，都没有详细的去解释这个问题）。其实上一张图片已经展示了将要做的算法步骤，但是说实话也不是说得很清楚，接下来看一下这张图片：

当我们把需要做的元素具体化之后，我们看到了其中的一个规律，上下能够进行相加的数字（通过-‘0’已经变成了数字）他们的因数的角标和是相等的，那么，我们就知道如何进行计算：

/* 乘运算*/
        for(i=0; i<n; i++)
            for(j=0; j<m; j++)
                c[i+j]+=a[i]*b[j];

n,m分别代表字符串的长度，也就是相乘元素的个数。解决了这个问题，剩下的问题便不是问题

二、使用步骤

1.代码如下

代码如下（示例）：

//大数乘法（字符串相乘）
#include<stdio.h>
#include<math.h>
#include<string.h>
#define M 10005
char s1[M],s2[M],s[M];
int a[M],b[M],c[M];
int main()
{
    int i,j,m,n,k;
    while(~scanf("%s%s",s1,s2))
    {
        memset(c,0,sizeof(c));
        n=strlen(s1);
        m=strlen(s2);
        k=n+m;//保证相乘后的位数不会大于k
        printf("s1的长度=%d s2的长度=%d\n",n,m);
 /*把字符串s1和s2逆序用数字排列*/
        for(i=0; i<n; i++)
            a[i]=s1[n-i-1]-'0';
        for(i=0; i<m; i++)
            b[i]=s2[m-1-i]-'0';
          /* 乘运算*/
        for(i=0; i<n; i++)
            for(j=0; j<m; j++)
                c[i+j]+=a[i]*b[j];
        for(i=0; i<=k; i++)//进行进位操作
        {
            if(c[i]>=10)
            {
                c[i+1]+=c[i]/10;
                c[i]%=10;
            }
        }
 /*去除前导0*/
        i=k;
        while(c[i]==0) i--;
 /*判断两个非负数之积是否为0，以及逆序打印c[]*/
        if(i<0) printf("0");
        else
        {
            for(; i>=0; i--)
                printf("%d",c[i]);
        }
        printf("\n");
    }
    return 0;
}