首页 > 试题广场 >

大数乘法

[编程题]大数乘法
  • 热度指数：4055 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
实现大数乘法，输入是两个字符串如
n1 = '340282366920938463463374607431768211456'
n2 = '340282366920938463463374607431768211456'
输出
'115792089237316195423570985008687907853269984665640564039457584007913129639936'
要求：不能使用对大数相乘有内建支持的语言；需要包含对输入字符串的合法性校验

输入描述:
一行，两个非负整数n1,n2，保证|n1|+|n2|<10000，其中|n|是n作为字符串的长度


输出描述:
输出n1*n2的结果
示例1

输入

340282366920938463463374607431768211456 340282366920938463463374607431768211456

输出

115792089237316195423570985008687907853269984665640564039457584007913129639936

备注:
给出的数据均是合法的，但仍建议您对输入的字符串进行合法性校验
算法知识视频讲解
添加回答
C
牛客76165061号头像 牛客76165061号
在遍历过程中递归判断进位，速度比倒数第二慢了一倍...
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void carry_bit(char *res, int k){
    if(res[k]>9){
        res[k-1] += res[k]/10;
        res[k] %=10;
        carry_bit(res, k-1);
    }
}

int main() {
    char s[10000], *n1, *n2;
    n1 = s;
    scanf("%s", n1);
    n2 = n1 + strlen(s) + 1;
    scanf("%s", n2);

    int len_n1 = strlen(n1), len_n2 = strlen(n2);
    int len_s = len_n1 + len_n2, temp_index;
    char *res = (char*)malloc(sizeof(char)*(len_s+1));
    memset(res, 0, sizeof(char)*(len_s+1));
    // for(int i=0;i<len_s;i++) res[i] = 0;
    res[len_s] = '\0';

    for(int i=0; i<len_n1; i++) n1[i]-='0';
    for(int i=0; i<len_n2; i++) n2[i]-='0';

    for(int i=len_n1-1;i>=0;i--){
        for(int j=len_n2-1;j>=0;j--){
            temp_index = i+j+1;
            res[temp_index] += n1[i]*n2[j];
            carry_bit(res, temp_index);
        }
    }
    for(int i=0; i<len_s; i++) res[i] += '0';

    for(int i=0;i<len_s;i++){
        if(res[i]!='0'){
            printf("%s", res+i);
            return 0;
        }
    }
    printf("0");
    return 0;
}

发表于 2024-01-26 19:19:28 回复(0)
提交观点

问题信息

C++工程师 数组 Momenta 模拟 2019 数学 Java工程师
来自：Momenta2019...
上传者：小小
难度：
1条回答 8777浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号