首页 > 代码库 > HighAccuracy1047

HighAccuracy1047

 

给定一个数,如果它是N位的,那么从1N乘以这个数,得到的(指得到的N个数都满足条件)都是这个数的回文数。

判断给定的数是否满足条件:

 

大数乘法部分不是难点,本题的难点是怎么判断进行大数乘法之后得到的新数从某个digit开始读就是原数。

 

假设存储原数的字符数组为ori_str,储存进行大数阶乘之后的数的字符数组是num_str,两个ori_str连接成一个新的字符串exp_str,若原数是cyclic的则num_strexp_strsub-string

判断sub-string可以使用c语言string.hstrstr。也可以使用STLstring::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