题目描述
若一个数(首位不为零)从左向右读与从右向左读都一样,我们就将其称之为回文数。
例如:给定一个十进制数56,将56加65(即把5656从右向左读),得到121是一个回文数。
又如:对于十进制数8787:
STEP1:87+78 = 165
STEP2:165+561 = 726
STEP3:726+627 = 1353
STEP4:1353+3531 = 4884在这里的一步是指进行了一次N进制的加法,上例最少用了4步得到回文数4884。
写一个程序,给定一个N(2 \le N \le 10,N=16)进制数M(100位之内),求最少经过几步可以得到回文数。如果在30步以内(包含30步)不可能得到回文数,则输出
Impossible!
输入格式
两行,分别是N,M。
输出格式
STEP=ans
输入输出样例
输入 #1复制
10 87输出 #1复制
STEP=4
这个题我刚开始觉得它的sum可能会很大,然后就用的大数,结果发现,用String 字符串就可以了,你说神奇不神奇,然后再进行编码的时候要注意以下几点:
1.先求某个数的逆数(我是这样称呼的);
2.将这两个数全部转化为10进制,然后相加;
3.将和转化为相应的进制进行判断;
这样的结果是正确的;
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
static Scanner sc=new Scanner(System.in);
static int N,S;
static String M;
static char[] ch= {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
static String reverse(String m2) {
String m1="";
String str=m2+"";
for(int i=str.length()-1;i>=0;i--) {
m1+=str.charAt(i);
}
return m1;
}
static String add(String m2) {
// TODO Auto-generated method stub
String m1=reverse(m2);
long sum1=0;
long sum2=0;
long sum=0;
for(int i=0;i<m2.length();i++) {
sum1=sum1*N+(m2.charAt(i)>64?m2.charAt(i)-55:Long.parseLong(m2.charAt(i)+""));
}
for(int i=0;i<m1.length();i++) {
sum2=sum2*N+(m1.charAt(i)>64?m1.charAt(i)-55:Long.parseLong(m1.charAt(i)+""));
}
sum=sum1+sum2;
String str="";
while(sum>0) {
long dig=sum%N;
str+=ch[(int) dig];
sum/=N;
}
return reverse(str);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
N=sc.nextInt();
S=N;
M=sc.next();
int ans=0;
while(!isH(M)) {
if(ans>30) {
System.out.println("Impossible!");
return;
}
M=add(M);
ans++;
}
if(ans==0) {
ans=1;
}
System.out.println("STEP="+ans);
}
static boolean isH(String m2) {
// TODO Auto-generated method stub
String str=m2+"";
boolean flag=true;
for(int i=0;i<((str.length()-1)/2+1);i++) {
if(!(str.charAt(i)==str.charAt(str.length()-1-i))) {
flag=false;
}
}
return flag;
}
}