在线购物网站设计_微信怎么制作微电影网站_营销策划的六个步骤_百度手机版

【NOIP提高组】回文数

- - C语言代码
  - C++ 代码
  - Java代码
  - Python代码

💐The Begin💐点点关注，收藏不迷路💐

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

例如：给定一个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') + 10return -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 = 0i, j = len(a) - 1, len(b) - 1while i >= 0 or j >= 0 or carry:sum_ = carryif i >= 0:sum_ += char_to_int(a[i], n)i -= 1if j >= 0:sum_ += char_to_int(b[j], n)j -= 1result += int_to_char(sum_ % n, n)carry = sum_ // nreturn result[::-1]n = int(input())
m = input()
for step in range(31):if is_palindrome(m, n):print("STEP=" + str(step))breakreversed_m = m[::-1]m = add(m, reversed_m, n)
else:print("Impossible!")

在这里插入图片描述

💐The End💐点点关注，收藏不迷路💐