洛谷千题详解 | P1015 [NOIP1999 普及组] 回文数【C++、Java、Python语言】

博主主页：Yu·仙笙

 

专栏地址：洛谷千题详解

目录

题目描述

输入格式

输出格式

输入输出样例

解析：

C++源码：

C++源码2：

Java源码： 

Python源码：

---

-------------------------------------------------------------------------------------------------------------------------------  

-------------------------------------------------------------------------------------------------------------------------------  

题目描述

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

例如：给定一个十进制数 56，将 56 加 65（即把 56 从右向左读），得到 121 是一个回文数。

又如：对于十进制数 87：

STEP1：87+78=165
STEP2：165+561=726
STEP3：726+627=1353
STEP4：1353+3531=4884

在这里的一步是指进行了一次 N 进制的加法，上例最少用了 4 步得到回文数 4884。

写一个程序，给定一个 N（2≤N≤10 或 N=16）进制数 M（100 位之内），求最少经过几步可以得到回文数。如果在 30 步以内（包含 30 步）不可能得到回文数，则输出 Impossible!。

-------------------------------------------------------------------------------------------------------------------------------  

输入格式

两行，分别是 N，M。

-------------------------------------------------------------------------------------------------------------------------------  

输出格式

如果能在 30 步以内得到回文数，输出格式形如 STEP=ans，其中ans 为最少得到回文数的步数。

否则输出 Impossible!。

-------------------------------------------------------------------------------------------------------------------------------  

输入输出样例

输入 #1 

10
87

输出 #1

STEP=4

-------------------------------------------------------------------------------------------------------------------------------  

解析：

这题是高精度加法和普通模拟的一道好题。

本题按照题目意思模拟即可。我们可以开两个数组来记录高精度数字，这样方便我们处理。判断“该数组是否回文”、“c翻转存入d再做c+d”可以写成两个单独的函数。然后主程序组织一下他们即可。注意好退出循环的条件。

把不同的一些并不小的功能写成不同的函数再在主程序当中组织它们，是属于一种标准化、模块化编程的思维。这种思维在以后编程，尤其是像高精度这样主程序调用频繁的程序当中，可以大大简化思维和代码量。其特点就是函数间独立性较为明显，函数接口较为简单，函数调用方便。一个函数应当干完它所有的任务，如果把某些任务拖延到主程序或者是其他函数当中，将大大复杂编程思维复杂度和代码量。

如果题目是int64整形范围内的话，那么将毫无必要转进制！

一个小技巧：将n进制数反转，在十进制下即可翻转，无需转成字符数组。判断反转后的数（10进制）与原来的数（先把它转成10进制）是否相同即可。

-------------------------------------------------------------------------------------------------------------------------------  

C++源码：

#include 
#include 
const int S=303;//一次加法顶多多一位，所以顶多多30位，也就是130位左右。我开大一点，开到300.
int n,a[S],l;
char c[S],d[S];
inline void add()
{
	for (int i=0;i
		d[l-i-1]=c[i];
	l+=2;//可能有进位，所以我们干脆在前面先多空个两位
	for (int i=0;i
	{
		c[i]+=d[i];
		if (c[i]>=n) c[i+1]++,c[i]-=n;
	}
	while (!c[l-1]) --l;//大不了多余的前导0再减回来嘛~~简化思维~~
}
inline bool pd()
{
	for (int i=0;i
		if (c[i]!=c[l-1-i]) return false;
	return true;
}
int main()
{
	scanf("%d%s",&n,c);l=strlen(c);
	for (int i=0;i
	{
		if (c[i]>='0' && c[i]<='9') c[i]-='0';
		else c[i]=c[i]-'A'+10;
	}
	int step=0;
	while (!pd())
	{
		++step;
		if (step>30) break;
		add();
	}
	if (step<=30) printf("STEP=%d\n",step);
	else puts("Impossible!");
	return 0;
}

------------------------------------------------------------------------------------------------------------------------------- 

C++源码2：

#include
#include
#include
#include
#include
using namespace std;//大家都懂就不说了
int n;//题目中的N进制
string m;//题目中M有100位！！！必须用字符串（不太懂楼下的dalao如何做的用unsigned long long过的？？？求指导qwq）
int ans;
int p;
bool hw(string st)//判断是否回文
{
	int ln=st.size(); 
	for(int i=0;i2;i++)
		if(st[i]!=st[ln-1-i])return 0;//若不了解这条公式，大家可以验证一下
	return 1;
}
int zhuan(char x)//将字符转成数字
{
	if(x>='0'&&x<='9')return int(x-48);
	else//以下判断是因为有16进制
	{
		if(x=='A')return 10;
		if(x=='B')return 11;
		if(x=='C')return 12;
		if(x=='D')return 13;
		if(x=='E')return 14;
		if(x=='F')return 15;
	}
}
char zhuan_h(int x)//将数字转回字符
{
	if(x>=0&&x<=9)return char(x+48);
	else//和上面一样
	{
		if(x==10)return char('A');
		if(x==11)return char('B');
		if(x==12)return char('C');
		if(x==13)return char('D');
		if(x==14)return char('E');
		if(x==15)return char('F');
	}
}
string bian(string a,string b)//做加法
{
	for(int i=0;isize()/2;i++)//进行反转（楼下dalao用reverse(a.begin(), a.end());也是可行的，佩服）
		swap(b[i],b[b.size()-1-i]);
	string c="";//用来记录等会的和
	int jw=0,aw=0,bw=0,cw=0;
	for(int i=a.size()-1;i>=0;i--)
	{
		aw=zhuan(a[i]);//将a[i]转成数字
		bw=zhuan(b[i]);//将b[i]转成数字
		cw=(aw+bw+jw)%n;//看c字符串这一位是几
		if(aw+bw+jw>=n)jw=1;//判断是否进位
		else jw=0;
		c=zhuan_h(cw)+c;//将这一位的数转回字符放在c字符串，注意：要放在在前面，因为是倒着算的
	}
	if(jw==1)c='1'+c;//千万不要忘记了最后一位还会进位
	return c;//返回得出的结果
} 
int main()
{
	cin>>n;
	cin>>m;
	p=hw(m);//判断是否回文
	while(p==0)
	{
		if(ans>30)//如果方案数>30输出“Impossible!”
		{
			cout<<"Impossible!";
			exit(0);
		}
		ans++;//方案数累加
		m=bian(m,m);//将M进行做加法
		p=hw(m);//别忘了判断回文
	}
	cout<<"STEP="<//输出结果
	return 0; //完美结束
}

-------------------------------------------------------------------------------------------------------------------------------  

Java源码： 

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        String number = scanner.next();
        for (int i = 1; i <= 30; ++ i) {
            String reverse = new StringBuilder(number).reverse().toString();
            BigInteger integer = new BigInteger(number, n).add(new BigInteger(reverse, n));
            if (check(number = integer.toString(n))) {
                System.out.println("STEP=" + i);
                return;
            }
        }
        System.out.println("Impossible!");
    }
    private static boolean check(String arg) {
        char[] chars = arg.toCharArray();
        int left = 0, right = chars.length-1;
        while (right-left >= 1)
            if (chars[left ++] != chars[right --])
                return false;
        return true;
    }

------------------------------------------------------------------------------------------------------------------------------- 

Python源码：

N = int(input())
M = input()
n1 = int(M, base=N)  # 将N进制数转为十进制数
n2 = int(M[::-1], base=N)
 
 
def trans(n):
    """将十进制数转化为N进制数,并以列表的形式返回"""
    alist = []
    while n:
        alist.append(n % N)
        n //= N
    alist.reverse()
    return alist
 
 
def dec(M):
    """将N进制数转化为十进制"""
    n = 0
    for i in range(len(M)):
        n += N ** i * int(M[len(M) - i - 1])
    return n
 
 
"""
例：将八进制数转为十进制，计算过程如下：
(3567)8=(3*8*8*8+5*8*8+6*8+7)10
"""
 
count = 0
 
while count <= 30:
    n1 = n1 + n2
    n1 = trans(n1)
    n2 = list(reversed(n1))
    count += 1
    if n1 == n2:
        print("STEP=%d" % count)
        break
    n1 = dec(n1)
    n2 = dec(n2)
 
if count > 30:
    print("Impossible!")
"""
    思路:
        将n进制转换为10进制 然后相加 相加完之后 将10进制转换为n进制再判断是否回文
        1.无论多少进制相加和 都是转换为10进制相加后的和 值不会变
        2.因为有16进制的存在 所以需要自己手写n进制转换10进制的的dec函数 
        3.注意一定要放到列表里面(不要偷懒放到字符串) 因为没法计算的
"""