一道C语言面试题:大整数乘法

栏目: C · 发布时间: 5年前

内容简介:题目:输入两个数字字符串,如“1234567890”和“987654321”,返回二者相乘的结果字符串,如本例返回为“1219326311126352690”。来源:某500强企业面试题目思路:从尾部到头部,对两个字串的每个数字分别相乘,并放入结果字符串相应的位置。

题目:输入两个数字字符串,如“1234567890”和“987654321”,返回二者相乘的结果字符串,如本例返回为“1219326311126352690”。

来源:某500强企业面试题目

思路:从尾部到头部,对两个字串的每个数字分别相乘,并放入结果字符串相应的位置。

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

char *BigNumMultiply(const char *n1, const char *n2)
{
    // quit if n1 or n2 is invalid
    if (!n1 || !n2) {
        return NULL;
    }

    // get length
    int Len1 = strlen(n1);
    int Len2 = strlen(n2);
    int Len = Len1 + Len2;

    // allocate result buffer
    char *ret = (char *)malloc(Len + 1);
    if (!ret) {
        return NULL;
    }
    memset(ret, 0, Len + 1);

    // multiply
    for (int i = Len1 - 1; i >= 0; --i) {
        for (int j = Len2 - 1; j >= 0; --j) {
            int k = i + j + 1;
            // multiply digit by digit
            ret[k] += (n1[i] - '0') * (n2[j] - '0');

            // add to upper position
            if (ret[k] >= 10){
                ret[k - 1] += ret[k] / 10;
                ret[k] = ret[k] % 10;
            }
        }
    }

    // handle first 0
    int d = ret[0] == 0 ? 1 : 0;
    for (int i = 0; i < Len - d; ++i) {
        ret[i] = ret[i + d] + '0';
    }
    ret[Len - d] = '\0';

    return ret;
}

int main(int argc, char* argv[])
{
    char n1[] = "1234567890";
    char n2[] = "987654321";
    char *ret = BigNumMultiply(n1, n2);
    printf("%s * %s = %s\n", n1, n2, ret);
    free(ret);
    ret = NULL;

    getchar();
    return 0;
}

如下:

一道 <a href='https://www.codercto.com/topics/20720.html'>C语言</a> 面试题:大整数乘法

从工程化角度考虑,有几点需要注意:

1、输入的字符串是否有效?

上面的代码只判断了是否为空,实际上还有可能输入的字符串并非有效的数字字符串,如“12gh34”,这种也需要返回NULL。

2、前导0的处理

a位数与b位数相乘,结果长度可能为a+b,如9*99=891;也可能a+b-1是如 10*100=1000。

在代码的最后部分,对a+b-1的类型进行了移位处理,压缩掉了前导的0。

从编程角度考虑,有几点需要注意:

1、字符串下标从小到大,是从高位到低位。如n=“123”,最高位n[0]=1,最低位n[2]=3。

2、字符ASCII码与字符的转换,如n[3]=5这是纯数字,而+'0'后有n[3]='5'这就是字符了。

3、数字交叉相乘的进位处理,通过 >=10来判断进位,此处注意不要写成>10;另外注意多次叠加,所以使用 +=

4、malloc()的返回值是(void *),为了让编译器happy,需要强制转为(char *),而且最后需要free来释放它申请的内存。

5、字符'0'和字符串“0”的区别

Linux公社的RSS地址https://www.linuxidc.com/rssFeed.aspx

本文永久更新链接地址: https://www.linuxidc.com/Linux/2019-05/158424.htm


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

文明之光(第四册)

文明之光(第四册)

吴军 / 人民邮电出版社 / 2017-3 / 69.00元

计算机科学家吴军博士继创作《浪潮之巅》、《数学之美》之后,将视角拉回到人类文明史,以他独具的观点从对人类文明产生了重大影响却在过去被忽略的历史故事里,选择了有意思的几十个片段特写,有机地展现了一幅人类文明发展的画卷。《文明之光》系列创作历经整整四年,本书为其第四卷。 作者所选的创作素材来自于十几年来在世界各地的所见所闻,对其内容都有着深刻的体会和认识。《文明之光》系列第四册每个章节依然相对独......一起来看看 《文明之光(第四册)》 这本书的介绍吧!

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具