首页 > 代码库 > HighAccuracy1047
HighAccuracy1047
给定一个数,如果它是N位的,那么从1到N乘以这个数,得到的(指得到的N个数都满足条件)都是这个数的回文数。
判断给定的数是否满足条件:
大数乘法部分不是难点,本题的难点是怎么判断进行大数乘法之后得到的新数从某个digit开始读就是原数。
假设存储原数的字符数组为ori_str,储存进行大数阶乘之后的数的字符数组是num_str,两个ori_str连接成一个新的字符串exp_str,若原数是cyclic的则num_str是exp_str的sub-string。
判断sub-string可以使用c语言string.h的strstr。也可以使用STL的string::find
#include <stdio.h>
#include <string.h>
int main()
{
int num[60],MulNum[60],i,j,k,len;//num是原数,MulNum是进行乘法之后的数
char ori_str[61],num_str[61],exp_str[121];//ori_str是原数,num_str是进行乘法之后的数,exp_str由
//两个ori_str连接而成
int temp,carry;
int flag;
while(scanf("%s",ori_str)!=EOF)
{
flag=1;
strcpy(exp_str,ori_str);
len=strlen(ori_str);
for(i=0;i<len;i++)
{
exp_str[len+i]=ori_str[i];
num[i]=ori_str[i]-‘0‘;
}
exp_str[len+i]=‘\0‘;
for(i=2;i<=len;i++)
{
carry=0;
for(j=len-1;j>-1;j--)
{
MulNum[j]=num[j]*i+carry;//乘的数比较小,所以不用倒序再乘
if(MulNum[j]>9)
{
temp=MulNum[j];
MulNum[j]%=10;
carry=temp/10;
}
else carry=0;
}
//如果carry不是0,则上面算出来的数位数多于原数,原数不是cyclic
if(carry)
{
flag=0;
break;
}
//判断是否cyclic
else
{
for(j=0;j<len;j++)
{
num_str[j]=MulNum[j]+‘0‘;
}
num_str[len]=‘\0‘;
if(strstr(exp_str,num_str)==NULL)
{
flag=0;
break;
}
}
}//for
if(flag) printf("%s is cyclic\n",ori_str);
else printf("%s is not cyclic\n",ori_str);
}//while
return 0;
}
HighAccuracy1047