洛谷 [NOIP1999 普及组] 回文数

文章目录

目录

文章目录

题目

一、基本思路

二、相关代码

1.判断是否是回文数

2.字符串的初始化

3.反转

4.反转相加

三.总

题目

若一个数(首位不为零)从左向右读与从右向左读都一样,我们就将其称之为回文数。

例如:给定一个十进制数 5656,将 5656 加 6565(即把 5656 从右向左读),得到 121121 是一个回文数。

又如:对于十进制数 8787:

STEP1:87+78=16587+78=165
STEP2:165+561=726165+561=726
STEP3:726+627=1353726+627=1353
STEP4:1353+3531=48841353+3531=4884

在这里的一步是指进行了一次 NN 进制的加法,上例最少用了 44 步得到回文数 48844884。

写一个程序,给定一个 NN(2 \le N \le 102≤N≤10 或 N=16N=16)进制数 MM(100100 位之内),求最少经过几步可以得到回文数。如果在 3030 步以内(包含 3030 步)不可能得到回文数,则输出 Impossible!


提示:以下是本篇文章正文内容,下面案例可供参考

一、基本思路

1.输入M,N(进制数)

2.判断N是否是回文数

  2.1如果是结束操作

  2.2如果不是进行反转相加,回到步骤2重复操作

       2.2.1如果反转相加次数大于30次,结束操作输出“Impossible”

       2.2.2如果反转相加次数小于30次,输出 次数

二、相关代码

1.字符串的初始化

void init()
{
    int j=0;
    for(int i=s.length()-1;i>=0;i--)
    {
        if(s[i]>='0'&&s[i]<='9')//判断是否是数字 
        {
            q[++j]=s[i]-'0';//将字符转换成数字 
        }
        else{
            q[++j]=s[i]-'A'+10;//将十六进制的字母转换为数值 
        }
    }
}

2.判断是否是回文数

bool hw(int a[])
{
    int q=slong;
    int i=1;
    int j=slong;
    while(q--)
    {
        if(q<(slong/2)) break;
        if(a[i]!=a[j]) return false;
        i++;
        j--;
    }
    return true;
} 

3.反转

void turn(int a[])
{
	int j=0;
	for(int i=slong;i>=1;i--)
	w[++j]=a[i];
}

4.反转后高精度相加

void add(int a[],int b[])
{
	for(int i=1;i<=slong;i++)
	{
		a[i]+=b[i];
		a[i+1]+=a[i]/n;
		a[i]%=n;
	}
	if(a[slong+1]>0) slong++;
} 

三.总结

首先输入字符串后要将字符串转化为数值;判断回文数时可以利用最后一位等于第一位循环;因为进行相加的次数很多数值范围大大超出了标准数据类型能表示的范围的运算要用高精度加法


版权声明:本文为m0_73732212原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。