1052:【回文数(二)】

题目

Description

若一个数&＃xff08;首位不为零&＃xff09;从左向右读与从右向左读都一样&＃xff0c;我们就将其称之为回文数。
例如&＃xff1a;给定一个10进制数56&＃xff0c;将56加65&＃xff08;即把56从右向左读&＃xff09;&＃xff0c;得到121是一个回文数。
又如&＃xff1a;对于10进制数87&＃xff1a;
STEP1&＃xff1a;87&＃43;78 &＃61; 165　　　　　　　　 STEP2&＃xff1a;165&＃43;561 &＃61; 726
STEP3&＃xff1a;726&＃43;627 &＃61; 1353　　　　　　　　STEP4&＃xff1a;1353&＃43;3531 &＃61; 4884
在这里的一步是指进行了一次N进制的加法&＃xff0c;上例最少用了4步得到回文数4884。
写一个程序&＃xff0c;给定一个N&＃xff08;2<&＃61;N<&＃61;16&＃xff09;进制数M&＃xff0c;求最少经过几步可以得到回文数。如果在30步以内&＃xff08;包含30步&＃xff09;不可能得到回文数&＃xff0c;则输出“Impossible!”

Input

共两行
第一行为进制数N&＃xff08;2<&＃61;N<&＃61;16&＃xff09;
第二行为N进制数M&＃xff08;0<&＃61;M<&＃61;maxlongint&＃xff09;

Output

共一行&＃xff0c;为“STEP&＃61;经过的步数”或“Impossible!”

Sample Input

9
87
Sample Output

STEP&＃61;6

代码块


import java.util.Arrays;//java包
import java.util.Scanner;public class Main {static int[] a &＃61; new int[10000];//定义全局数组static int[] b &＃61; new int[10000];static int[] s &＃61; new int[10001];public static void main(String[] args) {Scanner cn &＃61; new Scanner(System.in);//输入流int n &＃61; cn.nextInt();String m &＃61; cn.next();//因为根据题目的要求会有16进制的&＃xff0c;所以要用字符串来存储。int l &＃61; m.length();int count &＃61;0;for(int i &＃61;0;iif(m.charAt(i)>&＃61;&＃39;A&＃39;&&m.charAt(i)<&＃61;&＃39;Z&＃39;){//获取字符串的每一个字符进行判断a[i]&＃61;m.charAt(i)-&＃39;A&＃39;&＃43;10;}else{a[i] &＃61; m.charAt(i)-&＃39;0&＃39;;}s[i] &＃61; a[i];b[l-i-1]&＃61;a[i];}while(!huiwen(s,l)&&count<&＃61;30){//用while判断是不是回文数count&＃43;&＃43;;Arrays.fill(s, 0);for(int i&＃61;0;i1]&＃43;&＃61;s[i]/n;s[i] &＃61; s[i]%n;}if(s[l]!&＃61;0)l&＃61; l&＃43;1;inverse(s,l);}if(count<&＃61;30){System.out.println("STEP&＃61;"&＃43;count);}else{System.out.println("Impossible!");}}private static void inverse(int[] s2, int l) {//将一个数的正序和倒序存入到两个数组中int i;Arrays.fill(a, 0);Arrays.fill(b, 0);for(i&＃61;0;i1]&＃61; a[i];}}//用来判断是不是回文数private static boolean huiwen(int[] s2, int l) {int k &＃61; (l-1)/2;int i;for(i&＃61;0;i<&＃61;k;i&＃43;&＃43;){//如果是回文数&＃xff0c;就说明是对称的if(s[i]!&＃61;s[l-i-1]) break;}if(i&＃61;&＃61;k&＃43;1)return true;elsereturn false;}
}