回文数题解

题目描述

对于一个自然数 n，若将 n 的各位数字反向排列所得的数 n1 与 n 相等，则称 n 为回文数，例如 2332。
若给定一个 N( 2<=N<=16) 进制数 M（M 的长度在一百位以内），如果 M 不是回文数，可以对其进行 N 进制加法，最终得到回文数。
例如对于十进制数 79
STEP1 : 79 + 97 = 176
STEP2 : 176 + 671 = 847
STEP3 : 847 + 748 = 1595
STEP4 : 1595 +5951 = 7546
STEP5 : 7546 + 6457 = 14003
STEP6 : 14003 + 30041 = 44044
那么对于给定的 N 进制数 M，请判断其能否在 30 步以内（包括 30 步）得到回文数。

输入格式:
第一行包括一个正整数 N（2<=N<=16）。
第二行包括一个正整数M（一百位以内）。

输出格式:
如果可以在n步内得到回文数，输出“STEP=n”，否则输出“NO”。

解题思路

1.将高精度数储存在数组中（对十六进制数特判）
2.反向排列，判断是否为回文数
3.若非回文数，则进行高精度 n 进制加法
4.循环2-3步，直到满足条件

完整代码

#include<stdio.h>
#include<string.h>
#define MAX_LEN 1000
char num[MAX_LEN + 10];
int sz1[MAX_LEN + 10];
int sz2[MAX_LEN + 10];

void reverse(int a[], int b[]) {
	int i;
	for (i = 1; i <= a[0]; i++) {
		b[i] = a[a[0] - i + 1];
	}
	b[0] = a[0];
}/*功能：反向排列*/

int cmp(int a[], int b[]) {
	int i;
	for (i = 1; i <= a[0] / 2; i++) {
		if (a[i] != b[i]) {
			return 0;
		}
	}
	return 1;
}/*功能：判断回文数
   返回值：返回0表示非回文数，返回1表示回文数*/

void plus(int a[], int b[], int n) {
	int i;
	for (i = 1; i <= a[0]; i++) {
		a[i] += b[i];
		a[i + 1] += a[i] / n;
		a[i] %= n;
	}
	if (a[a[0] + 1] > 0) {
		a[0]++;
	}
}/*功能：高精度n进制加法*/

int main()
{
	int N, i;
	scanf("%d", &N);
	scanf("%s", num);
	
	sz1[0] = strlen(num);
	for (i = 1; i <= sz1[0]; i++) {
		if (num[sz1[0] - i] >= 'A' && num[sz1[0] - i] <= 'F') {
			sz1[i] = num[sz1[0] - i] - 'A' + 10;
		}
		else if (num[sz1[0] - i] >= 'a' && num[sz1[0] - i] <= 'f') {
			sz1[i] = num[sz1[0] - i] - 'a' + 10;
		}/*对十六进制数特判*/
		else {
			sz1[i] = num[sz1[0] - i] - '0';
		}
	}
	for (i = 0; i <= 30; i++) {
		reverse(sz1, sz2);
		if (cmp(sz1, sz2) == 1) {
			break;
		}
		plus(sz1, sz2, N);
	}
	
	if (i <= 30) {
		printf("STEP=%d", i);
	}
	else {
		printf("NO");
	}
	return 0;
}