【回文数(二)】 （C++代码）

解题思路:

注意事项:

参考代码:

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>
#include <set>

#define N 25

using namespace std;

char nums[] = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};

//任意进制转化为10进制
int toDec(char c, int type)
{
	int ans = 0;
	//int len = s.length();
	if (c >= '0' && c <= '9')
		ans += c - '0';
	else if (c >= 'A' && c <= 'Z')
		ans += c - 'A' + 10;
	else if (c >= 'a' && c <= 'z')
		ans += c - 'a' + 10;
	return ans;
}

//10进制转化为任意进制
void toOther(int n, int type, string& s)
{
	if (n)
	{
		toOther(n / type, type, s);
		s += n % type > 9 ? n % type - 10 + 'A' : n % type + '0';
	}
}

//自行实现任意进制加法
string add(string a, string b,int base)
{
	string ans;
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	char temp = '0';
	int carry = 0;
	for (int i = 0; i < a.length() || i < b.length(); i++)
	{
		int aNum = toDec(a[i], base);
		int bNum = toDec(b[i], base);
		temp = nums[(aNum + bNum + carry) % base];
		carry = (aNum + bNum + carry) / base;
		ans += temp;
	}
	if (carry)
	{
		string lastCarry;
		toOther(carry, base, lastCarry);
		ans += lastCarry;
	}
	reverse(ans.begin(), ans.end());
	return ans;
}

void getPaliNum(int step, string num, const int base, int& ansStep)
{
	if (step > 30)
		return;
	else
	{
		bool isPaliNum = true;
		for (int i = 0; i < num.length()/2; i++)
		{
			if (num[i] != num[num.length() -i -1])
			{
				isPaliNum = false;
				break;
			}
		}
		if (isPaliNum)
		{
			ansStep = step;
			return;
		}
		else
		{
			string revNum = num;
			reverse(revNum.begin(), revNum.end());
			getPaliNum(step + 1, add(num, revNum, base), base, ansStep);
			return;
		}
	}
}

int main(int argc, char** argv)
{
	int n = 0;
	string m;
	cin >> n >> m;

	int ansStep = 0;
	getPaliNum(0, m, n, ansStep);

	if (ansStep <= 30)
		cout << "STEP=" << ansStep << endl;
	else
		cout << "Impossible!" << endl;
	system("pause");
	return 0;
}