• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    迪恩网络公众号

大整数乘法(高精度乘法)的实现源码(原创)

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

问题描述:给定两个正整数A,B(A和B可能超出计算机中国INT32,INT64的范围,高达几百甚至上千位),

求A和B相乘的积。

解决方案:

用计算机模拟手算的乘法,假设A和B都用字符串表示,

时间复杂度为:O(strlen(A) * strlen(B));

空间复杂度为:O(strlen(A) + strlen(B));

源码实现如下:


#include 
#include 
#include 

//大整数的乘法
//时间复杂度O(strlen(a) * strlen(b))
//空间复杂度O(strlen(a) + strlen(b))
//a,b都是用字符串表示的正的整数
//例如:a=12345678910, b=10987654321
char* mul(const char *a, const char *b)
{
    //略去对大整数a,b的合法性判断

    int len1 = strlen(a);
    int len2 = strlen(b);
    int len = len1 + len2;
    int i,j,k;
    int *c = (int*)malloc(sizeof(int) * (len - 1));
    memset(c, 0, sizeof(int) * (len - 1));

    //[PS:一个数字减去'0'就是它对应的数值]
    //模拟手算乘法
    for(i = 0; i < len1; ++i)
        for(j = 0; j < len2; ++j)
            c[i + j] += (a[i] - '0') * (b[j] - '0');

    char* r = (char*)malloc(sizeof(char) * (len + 1));
    memset(r, 0, sizeof(char) * (len + 1));

    int carry = 0;
    //按从低位到高位的顺序将每一位的结果存到r中
    for(i = len - 2, k = 0; i >= 0; --i, k++)
    {
        r[k] = (c[i] + carry) % 10 + '0';
        carry = (c[i] + carry) / 10;
    }
    if(carry) r[k++] = carry + '0';

    //将结果r倒置
    for(i = 0, j = k - 1; i < j; i++,j--)
    {
        int tmp = r[i];
        r[i] = r[j];
        r[j] = tmp;
    }

    free(c);
    return r;

}

int main()
{
    const char* a = "12345678910";
    const char* b = "10987654321";
    char * r = mul(a, b);
    printf("%s\n", r);
    free(r);
    system("pause");
    return 0;
}

鲜花

握手

雷人

路过

鸡蛋
专题导读
上一篇:
拓扑排序算法(邻接矩阵版)(C++实现)发布时间:2022-05-14
下一篇:
top-k算法的二分实现(修正版)(C++实现)发布时间:2022-05-14
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap