C語言超詳細講解字串相乘

2022-03-29 19:00:19

前言

我們已經知道，正常的兩位整形資料通過*相乘，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的長度=%dn",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;
}