题解 | 回文数

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<math.h>
void reverse(int arr[], int vein_arr[], int n) {//交换数组位置，达到将一个数反过来
    int i = 0;
    for (i = 0; i < n; i++) {
        *(vein_arr + n - 1 - i) = *(arr + i);
    }
}
int judge(int arr[], int n) {//判断是否为回文数
    int right = n - 1;
    int left = 0;
    while (left <= right) {
        if (*(arr + right) != *(arr + left)) {
            return 0;
        }
        left++;
        right--;
    }
    return 1;
}
int cut(int arr[], long long M, int N) {//将十进制的数转换为N进制，每一位储存在数组中(从左到右权值越来越大)
    long long new_M;
    int j = 0;
    new_M = M;
    while (1) {
        if (new_M < N) {
            *(arr + j) = new_M;
            j++;
            break;
        }
        *(arr + j) = new_M % N;
        new_M = new_M / N;
        j++;
    }
    return j;// 返回的是数组中有几个数
}
long long ten_transform(int arr[], int n, int N) {//将数组元素乘以对应权值，得出换算后的十进制数
    long long ten_form = 0;
    int i = 0;
    for (i = 0; i < n; i++) {
        ten_form += *(arr + i) * pow(N, i);
    }
    return ten_form;
}

int main() {
    char ch;
    int flag = 0;
    int i = 0;
    int n = 0;
    int N = 0;
    long long M = 0;
    int arr[1024] = {0};
    int first_arr[1024] = {0};
    int vein_arr[1024] = {0};
    scanf("%d", &N);
    getchar();
    while((ch=getchar())!=EOF&&ch!='\n'){//处理字符串
        if(ch>='A'&&ch<='G'){
            first_arr[n] = ch - 55;
        }
        if(ch>='0'&&ch<='9'){
            first_arr[n] = ch - 48;
        }
        n++;
    }
    reverse(first_arr,arr,n);
    for (i = 1; i <= 30; i++) {
        reverse(arr,vein_arr,n);
        M = ten_transform(arr,n,N)+ten_transform(vein_arr,n,N);
        n = cut(arr,M,N);
        if(judge(arr,n)){
            printf("STEP=%d",i);
            flag = 1;
            break;
        }
    }
    if(0==flag){
        printf("Impossible!");
    }
    return 0;
}