题目描述
若一个数(首位不为零)从左向右读与从右向左读都一样,我们就将其称之为回文数。
例如:给定一个10进制数56,将56加56(即把56从右向左读),得到121是一个回文数。
又如:对于10进制数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,求最少经过几步可以得到回文数。如果在30步以内(包含30步)不可能得到回文数,则输出“Impossible!”
输入描述:
两行,分别是N,M。输出描述:
STEP=ans(ans表示答案)示例1
输入9
87
输出
STEP=6
题解
本题在回文串的基础上增加了进制转换,没有什么高深的算法,模拟。
1、 回文判断
stl里提供的string类容器可以很好的判断两个字符串的大小关系,那么将串A复制到串B,再将串B头尾反转判断两串大小:若相等则为回文串。
2、 进制转换
周围同学都是严格的使用A~F表示10进制表示不了的数,在此题中也不断进行着进制转换的操作,这样很繁琐,干脆使用数值对应的ASCII码代替A~F,在对应进制上进行操作。
#include<iostream> #include<bits/stdc++.h> #include<iomanip> #include<string> #include<cstring> #include<stack> #include<map> #include<list> #include<vector> #include<queue> #include<deque> #include<set> #include<functional> #include<time.h> #include<fstream> #include<algorithm> #define pi 3.14159265358979323846264338327950288419716939937510582097494 using namespace std; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; #define _for(i, a, b) for(ll i = (a); i < (b); ++i) #define _rep(i, a, b) for(ll i = (a); i <= (b); ++i) #define _re_for(i, a, b) for(ll i = (a); i > (b); --i) #define _re_rep(i, a, b) for(ll i = (a); i >= (b); --i) const int INF1 = 0x3f3f3f3f; const int INF0 = 0xc0c0c0c0; const int MAX = 100010; string ad(string &a, string &b, int n) { int r = 0; _for(i, 0, a.size()) { int sum = a[i] + b[i] - 48 - 48 + r;// 使用ASCII吗计算 a[i] = sum % n + 48;// n进制下取余 r = sum / n; } char c = r + 48; if (r + 48 != '0') a += c;// 末尾余位 return a; } string a, b; char flag[200]; int main() { _rep(i, 0, 9) flag['0' + i] = i + 48; _rep(i, 'A', 'Z') flag[i] = '9' + (i - 'A' + 1);// 构建码值表 int n; cin >> n >> a; _for(i, 0, a.size()) a[i] = flag[a[i]];// 以ASCII码替换原码值 b = a; // while (b.size() && b.back() == '0') b.pop_back(); reverse(b.begin(), b.end());// 字符串翻转 int cnt = 0; while (cnt <= 30) { if (a == b) { cout << "STEP="<< cnt; return 0; } cnt ++; a = ad(a, b, n);// 得到两串相加的结果 b = a; // while (b.size() && b.back() == '0') b.pop_back(); reverse(b.begin(), b.end()); } cout << "Impossible!"; return 0; }