题解 | #[NOIP1999]回文数#

#include <stdio.h>
#include <string.h>
//最主要注意数组下标位置！！！
void sum_judge_reverse(int judge_arr[], int reverse_arr[], int* lenth, int N)
{
    //从低位开始相加，有进位产生进位
    for (int i = *lenth - 1; i > 0; i--)
    {
        int sum = judge_arr[i] + reverse_arr[i - 1];
        if (sum < N)//不产生进位
            judge_arr[i] = sum;
        else
        {
            judge_arr[i - 1] ++;//进位1
            judge_arr[i] = sum % N;
        }
    }
    //相加完后，判断高位有没有进位，如果有进位，整体再向后移动4个字节
    //一直保持有进位的状态，并且可以直接调用回文判断（judge_palind_num）
    if (judge_arr[0] != 0)
    {
        for (int i = *lenth-1; i >= 0; i--)
        {
            judge_arr[i+1] = judge_arr[i];
        }
        judge_arr[0] = 0;
        (*lenth)++; //judge_arr 扩大4个字节
    }
}

void judge_to_reverse(int judge_arr[], int reverse_arr[], int lenth)
{
    for (int i = 1; i < lenth; i++)
    {
        reverse_arr[i - 1] = judge_arr[lenth-i];//注意judge_arr数组前多了一个judge_arr[0]
    }
}

int judge_palind_num(int judge_arr[], int lenth)//判断回文数
{
    int left = 1;
    int right = lenth - 1;
    while (right > left)
    {
        if (judge_arr[left++] != judge_arr[right--])
        {
            return 0; //前后存在一组不相等，返回0
        }
    }
    return 1;//是回文数返回1
}

void turn_char_to_int(char receive_arr[], int judge_arr[], int* lenth)
{
    for (int i = 1;i <= *lenth;i++)
    {
        //i 从1开始给judge_arr赋值，前面预留一位judge_arr[0] 用作进位
        if (receive_arr[i-1] >= '0' && receive_arr[i-1] <= '9')
            judge_arr[i] = receive_arr[i - 1] - '0';
        else
            judge_arr[i] = receive_arr[i - 1] - 'A' + 10;
    }
    (*lenth)++;//因为多了一位judge_arr[0]
}

int main(void)
{
    int N;//进制
    char receive_arr[100] = { 0 };//把数字当做字符串接收
    int judge_arr[101] = { 0 };//判断是否为回文数数组，字符串转数字存到此数组中
    int reverse_arr[100] = { 0 };//将judge_arr中的数字逆序放入此数组，并于judge_arr中的数相加

    scanf("%d", &N);
    scanf("%s", receive_arr);
    int len = strlen(receive_arr);//计算输入数组的长度
    int step = 0;

    //1.把字符数组转化为数字
    turn_char_to_int(receive_arr, judge_arr, &len);
    for (step = 0; step < 30; step++)//循环判断30次，是否为回文数
    {
        //2.判断judge_arr数组是否为回文数
        int ret = judge_palind_num(judge_arr, len);
        if (ret)
            break;//相等则跳出循环
        else//不相等，则需要逆序相加
        {
            //3.获取逆序数组
            judge_to_reverse(judge_arr, reverse_arr, len);
            //4.将正序数字与逆序数字相加
            sum_judge_reverse(judge_arr, reverse_arr, &len, N);
        }
    }
    if (step < 30)
        printf("STEP=%d\n", step);
    else
        printf("Impossible!\n");

    return 0;
}