A24196. 回文数
题目描述
回文数
题目描述
若一个数（首位不为零）从左向右读与从右向左读都是一样，我们就将其称之为回文数。例如：给定一个 10进制数 56，将 56加 65（即把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” 。
输入
第1行，给定一个N（2＜N≤10或N=16）表示进制；
第2行，一个N进制数M。
输出
最少几步。如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible”。
输入样例
9
87输出样例
6参考答案
#include<bits/stdc++.h>
using namespace std;
#define N 135
int n, a[N];
char s[N];
void tonum(char s[], int a[])//转为数字数组
{
int len = strlen(s);
for(int i = 1; i <= len; ++i)
{
if(s[len-i] >= '0' && s[len-i] <= '9')
a[i] = s[len-i] - '0';
else
a[i] = s[len-i] - 'A' + 10;
}
a[0] = len;
}
void genOpp(int a[], int b[])//生成a的逆向数字b
{
for(int i = 1; i <= a[0]; ++i)//生成a的逆向数字b
b[i] = a[a[0]+1-i];
b[0] = a[0];
}
void addToA(int a[], int b[])//n进制高精度加法 a += b
{
int c = 0;
for(int i = 1; i <= a[0] || i <= b[0]; ++i)
{
a[i] += b[i] + c;
c = a[i] / n;//n进制
a[i] %= n;
}
if(c > 0)
a[++a[0]] = c;
}
bool isPalin(int a[])//判断数字a是否是回文的
{
for(int i = 1; i <= a[0]/2; ++i)//遍历一半数组
{
if(a[i] != a[a[0]-i+1])
return false;
}
return true;
}
int main()
{
int b[N] = {};//b:a的逆向数字
cin >> n >> s;
tonum(s, a);
for(int i = 0; i <= 30; ++i)
{
if(isPalin(a))
{
cout << i;
return 0;
}
genOpp(a, b);//生成a的逆向数字b
addToA(a, b);//a+=b
}
cout << "Impossible";
return 0;
}答案解析
#include <bits/stdc++.h>
using namespace std;
#define N 155
struct HPN
{
int a[N] = {};
int base;//基数
HPN(){}
int getVal(char c)
{
return c >= '0' && c <= '9' ? c-'0' : c-'A'+10;
}
HPN(string s, int b)
{
a[0] = s.length();
base = b;
for(int i = 1; i <= a[0]; ++i)
a[i] = getVal(s[a[0]-i]);
}
void setLen(int i)
{
while(i > 1 && a[i] == 0)
i--;
a[0] = i;
}
int& operator [] (int i)
{
return a[i];
}
HPN rev() //取本高精度数的倒序数
{
HPN r("0", base);
for(int i = 1; i <= a[0]; ++i)
r[i] = a[a[0]-i+1];
r[0] = a[0];
return r;
}
HPN operator + (HPN b)
{
HPN r("0", base);
int i, c = 0;
for(i = 1; i <= max(a[0], b[0]); ++i)
{
r[i] = a[i]+b[i]+c;
c = r[i]/base;
r[i] %= base;
}
r[i] = c;
r.setLen(i);
return r;
}
bool isPalin()//判断本数是否为回文数
{
for(int i = 1; i <= a[0]/2; ++i)
if(a[i] != a[a[0]+1-i])
return false;
return true;
}
};
int main()
{
int n;
string m;
cin >> n >> m;
HPN num(m, n);
for(int i = 0; i <= 30; ++i)
{
if(num.isPalin())
{
cout << "STEP=" << i;
return 0;
}
num = num+num.rev();
}
cout << "Impossible!";
return 0;
}