題目描述
對于一個自然數 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;
}轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/43017.html
標籤：C
上一篇：運算子