关于蓝桥杯官网ADV-197 P1001试题分析与strlen函数疑问

最近忙于学习PHP,对C有所懈怠,今天心血来潮,打开了官网,发现又多了好几道题,于是挑了一道高精度的问题尝试着做做,做了好久,发现了些小问题(也许并不小),今天总结一下。
题如下:
当两个比较大的整数相乘时,可能会出现数据溢出的情形。为避免溢出,可以采用字符串的方法来实现两个大数之间的乘法。具体来说,首先以字符串的形式输入两个整数,每个整数的长度不会超过8位,然后把它们相乘的结果存储在另一个字符串当中(长度不会超过16位),最后把这个字符串打印出来。例如,假设用户输入为:62773417和12345678,则输出结果为:774980393241726.

输入:
  62773417 12345678
输出:
  774980393241726

本身就这道题而言,感觉是那种有点难度,但是关键还是考验人耐心和细心的问题,所以我一拿到题就有了大致的思路框架。核心问题是如何相乘,如何进位。相乘我采取的是将字符数字强制转换成整型数字,然后稍微处理相乘,并保存在对应的乘积位置,进位考虑难道一次可能不进位、进一位或者多位,所以我才用的是递归,如此一来,核心问题就解决了。
代码如下:
#include <stdio.h>
#include <string.h>

void Carrying(int tag,int i,int j,int *p);
int main(int argc, const char * argv[])
{
    int product[16],i=0,j=0,numOneLen,numTwoLen,tag;
    char numOne[8],numTwo[8];                        //这句代码有问题,详情请看下面解析
    memset(product, 0, sizeof(int)*16);                    //初始化product数据为0
    scanf("%s %s",numOne,numTwo);                    //存数据

    //测数据长度(这里存在bug,应该是系统函数的问题,可以通过放大数组空间来避免bug的触发)
    numOneLen=(int)strlen(numOne);               
    numTwoLen=(int)strlen(numTwo);

    //数据逆序
    for (i=0; i<numOneLen/2; i++)
    {
        tag=numOne[i];
        numOne[i]=numOne[numOneLen-1-i];
        numOne[numOneLen-1-i]=tag;
    }
    for (i=0; i<numTwoLen/2; i++)
    {
        tag=numTwo[i];
        numTwo[i]=numTwo[numTwoLen-1-i];
        numTwo[numTwoLen-1-i]=tag;
    }

    //逐位相乘
    for (i=0; i<numOneLen; i++)
    {
        for (j=0; j<numTwoLen; j++)
        {
            tag=((int)numOne[i]-48)*((int)numTwo[j]-48);
            Carrying(tag, i, j, product);                          //递归
        }
    }

    //倒序输出结果
    for (i=15; i>=0; i--)
    {
        if (product[i]!=0)
        {
            break;                                                          //查找到第一个不等于0的跳出
        }
    }
    for (j=i; j>=0; j--)
    {
        printf("%d",product[j]);
    }
    printf("\n");
    return 0;
}

//递归进位函数
void Carrying(int tag,int i,int j,int *p)
{
    p[i+j]+=tag;
    if (p[i+j]>9)
    {
        tag=p[i+j]/10;
        p[i+j] %=10;
        Carrying(tag, i+1, j, p);                                //写成Carrying(tag, i, j+1, p);也成立,为了让i+j递增而已
    }
    return ;
}
理论上,我自认为我的这串代码是可行的,能够正确通过,可是当我尝试输入题中给的数据时,却发现没有答案输出。这是让我感觉匪夷所思的情况,于是我开始尝试多输入几次,发现都是这样,当我输入的第二个数组长度为八时,结果均无法输出。
于是我决定拆开步骤了尝试,终于在我分别检查过递归进位、逐位相乘、倒序输出、数据逆序等过程后,我发现问题出在了我以为最不可能出现的地方,测试数据长度这个过程,于是我在测试过程后加了一个输出numOneLen和numTwoLen的语句,经过反复测试,发现,只要第二个数组的数据长度为8,则第一个数组长度无论为几,numOneLen均为0,这就导致了最后无结果输出的情况。仔细分析会发现,这两个测试的代码(使用strlen()系统函数)根本没有关联,不存在第一个会影响第二个测试,所以我无法理解为什么会出现这个系统函数测试数据异常的情况。经过反复思考,个人认为,这是系统函数的问题,无法完美的处理边界问题,所以我讲数组开的稍微大了一点点,即:"char numOne[8],numTwo[8];"改为了"char numOne[9],numTwo[9];",然后再尝试了好几组数据,均通过了。
就这样,我认为我的问题解决了,并初步认定为系统函数对边界问题无法完美处理而导致的错误结果,于是我就去将代码上交至蓝桥杯官网,然而,,,,,,挨千刀的,六组数据我只通过了五组,给了我83分,我没有vip,所以无法得知这最下边的一组测试数据,但是由于蓝桥杯官网经常出现错题或者是错误测试数据,所以我并不能肯定自己做的是否正确,但是对于这个strlen()系统函数,我觉得的确有些许问题,希望以后随着自己知识的增多,可以解决今天遗留的这个问题!
另外,考虑到自己对系统函数的不了解,并且竞赛的根本目的也是为了考算法,所以以后在竞赛题中,可以不使用系统函数的话,我决定不再使用,一方面锻炼自己,另一方面,自己写的代码自己心里有底……所存在的bug自己也可以动手找出来……Fighting!!!
好久没写博客,不能再这么懈怠了……
全部评论

相关推荐

点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务