关于蓝桥杯官网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!!!
好久没写博客,不能再这么懈怠了……