【NOIP提高组】回文数

若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。

例如：给定一个10进制数56，将56加65（即把56从右向左读），得到121是一个回文数。

又如：对于10进制数87：
STEP1：87+78 = 165 STEP2：165+561 = 726
STEP3：726+627 = 1353 STEP4：1353+3531 = 4884
在这里的一步是指进行了一次N进制的加法，上例最少用了4步得到回文数4884。

写一个程序，给定一个N（2<=N<=10或N=16）进制数M，其中16进制数字为0-9与A-F，求最少经过几步可以得到回文数。如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible!”

输入

共两行
第一行为进制数N（2<=N<=10或N=16）
第二行为N进制数M（0<=M<=maxlongint

输出

共一行
第一行为“STEP=”加上经过的步数或“Impossible!”

样例输入

9
87

样例输出

STEP=6

C语言代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

// 将字符形式的数字（十六进制下可能是字母）转换为对应的整型值（对应进制下）
int charToInt(char c, int n) {
    if (isdigit(c)) {
        return c - '0';
    } else if (n == 16 && (c >= 'A' && c <= 'F')) {
        return c - 'A' + 10;
    }
    return -1;  // 表示输入不合法
}

// 将整型值转换为对应进制下的字符形式（十六进制下可能是字母）
char intToChar(int num, int n) {
    if (num < 10) {
        return num + '0';
    } else if (n == 16) {
        return num - 10 + 'A';
    }
    return '\0';  // 表示输入不合法
}

// 判断一个字符串表示的数在给定进制下是否是回文数
int isPalindrome(char *num, int n) {
    int len = strlen(num);
    for (int i = 0; i < len / 2; i++) {
        if (charToInt(num[i], n)!= charToInt(num[len - 1 - i], n)) {
            return 0;
        }
    }
    return 1;
}

// 给定进制下两个数相加（用字符串表示数）
void add(char *a, char *b, char *result, int n) {
    int len_a = strlen(a);
    int len_b = strlen(b);
    int carry = 0;  // 进位标志
    int i = len_a - 1, j = len_b - 1, k = 0;
    while (i >= 0 || j >= 0 || carry) {
        int sum = carry;
        if (i >= 0) {
            sum += charToInt(a[i], n);
            i--;
        }
        if (j >= 0) {
            sum += charToInt(b[j], n);
            j--;
        }
        result[k++] = intToChar(sum % n, n);
        carry = sum / n;
    }
    result[k] = '\0';
    // 反转结果字符串，使其变为正常顺序
    for (int p = 0; p < k / 2; p++) {
        char temp = result[p];
        result[p] = result[k - 1 - p];
        result[k - 1 - p] = temp;
    }
}

int main() {
    int n;
    scanf("%d", &n);
    char m[100];
    scanf("%s", m);

    for (int step = 0; step <= 30; step++) {
        if (isPalindrome(m, n)) {
            printf("STEP=%d\n", step);
            return 0;
        }
        char reversed[100];
        strcpy(reversed, m);
        // 反转原数字字符串得到另一个加数
        for (int p = 0; p < strlen(reversed) / 2; p++) {
            char temp = reversed[p];
            reversed[p] = reversed[strlen(reversed) - 1 - p];
            reversed[strlen(reversed) - 1 - p] = temp;
        }
        char sum[100];
        add(m, reversed, sum, n);
        strcpy(m, sum);
    }
    printf("Impossible!\n");
    return 0;
}

C++ 代码

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

// 将字符形式的数字（十六进制下可能是字母）转换为对应的整型值（对应进制下）
int charToInt(char c, int n) {
    if (isdigit(c)) {
        return c - '0';
    } else if (n == 16 && (c >= 'A' && c <= 'F')) {
        return c - 'A' + 10;
    }
    return -1;  // 表示输入不合法
}

// 将整型值转换为对应进制下的字符形式（十六进制下可能是字母）
char intToChar(int num, int n) {
    if (num < 10) {
        return num + '0';
    } else if (n == 16) {
        return num - 10 + 'A';
    }
    return '\0';  // 表示输入不合法
}

// 判断一个字符串表示的数在给定进制下是否是回文数
bool isPalindrome(const string& num, int n) {
    int len = num.size();
    for (int i = 0; i < len / 2; i++) {
        if (charToInt(num[i], n)!= charToInt(num[len - 1 - i], n)) {
            return false;
        }
    }
    return true;
}

// 给定进制下两个数相加（用字符串表示数）
string add(const string& a, const string& b, int n) {
    string result = "";
    int carry = 0;  // 进位标志
    int i = a.size() - 1, j = b.size() - 1;
    while (i >= 0 || j >= 0 || carry) {
        int sum = carry;
        if (i >= 0) {
            sum += charToInt(a[i], n);
            i--;
        }
        if (j >= 0) {
            sum += charToInt(b[j], n);
            j--;
        }
        result += intToChar(sum % n, n);
        carry = sum / n;
    }
    reverse(result.begin(), result.end());
    return result;
}

int main() {
    int n;
    cin >> n;
    string m;
    cin >> m;

    for (int step = 0; step <= 30; step++) {
        if (isPalindrome(m, n)) {
            cout << "STEP=" << step << endl;
            return 0;
        }
        string reversed = m;
        reverse(reversed.begin(), reversed.end());
        m = add(m, reversed, n);
    }
    cout << "Impossible!" << endl;
    return 0;
}

Java代码

import java.util.Scanner;

public class Main {
    // 将字符形式的数字（十六进制下可能是字母）转换为对应的整型值（对应进制下）
    static int charToInt(char c, int n) {
        if (Character.isDigit(c)) {
            return c - '0';
        } else if (n == 16 && (c >= 'A' && c <= 'F')) {
            return c - 'A' + 10;
        }
        return -1;  // 表示输入不合法
    }

    // 将整型值转换为对应进制下的字符形式（十六进制下可能是字母）
    static char intToChar(int num, int n) {
        if (num < 10) {
            return (char) (num + '0');
        } else if (n == 16) {
            return (char) (num - 10 + 'A');
        }
        return '\0';  // 表示输入不合法
    }

    // 判断一个字符串表示的数在给定进制下是否是回文数
    static boolean isPalindrome(String num, int n) {
        int len = num.length();
        for (int i = 0; i < len / 2; i++) {
            if (charToInt(num.charAt(i), n)!= charToInt(num.charAt(len - 1 - i), n)) {
                return false;
            }
        }
        return true;
    }

    // 给定进制下两个数相加（用字符串表示数）
    static String add(String a, String b, int n) {
        StringBuilder result = new StringBuilder();
        int carry = 0;  // 进位标志
        int i = a.length() - 1, j = b.length() - 1;
        while (i >= 0 || j >= 0 || carry > 0) {
            int sum = carry;
            if (i >= 0) {
                sum += charToInt(a.charAt(i), n);
                i--;
            }
            if (j >= 0) {
                sum += charToInt(b.charAt(j), n);
                j--;
            }
            result.append(intToChar(sum % n, n));
            carry = sum / n;
        }
        return result.reverse().toString();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        String m = scanner.next();

        for (int step = 0; step <= 30; step++) {
            if (isPalindrome(m, n)) {
                System.out.println("STEP=" + step);
                return;
            }
            String reversed = new StringBuilder(m).reverse().toString();
            m = add(m, reversed, n);
        }
        System.out.println("Impossible!");
    }
}

Python代码

def char_to_int(c, n):
    """将字符形式的数字（十六进制下可能是字母）转换为对应的整型值（对应进制下）"""
    if c.isdigit():
        return int(c)
    elif n == 16 and 'A' <= c <= 'F':
        return ord(c) - ord('A') + 10
    return -1  # 表示输入不合法

def int_to_char(num, n):
    """将整型值转换为对应进制下的字符形式（十六进制下可能是字母）"""
    if num < 10:
        return str(num)
    elif n == 16:
        return chr(num - 10 + ord('A'))
    return ''  # 表示输入不合法

def is_palindrome(num, n):
    """判断一个字符串表示的数在给定进制下是否是回文数"""
    return num == num[::-1]

def add(a, b, n):
    """给定进制下两个数相加（用字符串表示数）"""
    result = ""
    carry = 0
    i, j = len(a) - 1, len(b) - 1
    while i >= 0 or j >= 0 or carry:
        sum_ = carry
        if i >= 0:
            sum_ += char_to_int(a[i], n)
            i -= 1
        if j >= 0:
            sum_ += char_to_int(b[j], n)
            j -= 1
        result += int_to_char(sum_ % n, n)
        carry = sum_ // n
    return result[::-1]

n = int(input())
m = input()
for step in range(31):
    if is_palindrome(m, n):
        print("STEP=" + str(step))
        break
    reversed_m = m[::-1]
    m = add(m, reversed_m, n)
else:
    print("Impossible!")