当前位置：首页 > news >正文

C语言入门算法——回文数

news 2025/7/28 2:48:18

题目描述：

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

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

又如：对于十进制数 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（100 位之内），求最少经过几步可以得到回文数。如果在 30 步以内（包含 30 步）不可能得到回文数，则输出 Impossible!。

输入格式

两行，分别是 N，M。

输出格式

如果能在 3030 步以内得到回文数，输出格式形如 STEP=ans，其中 ansans 为最少得到回文数的步数。

否则输出 Impossible!。

输入输出样例

输入 #1

10
87

输出 #1

STEP=4

题目来源

P1015 [NOIP1999 普及组] 回文数

思路及部分代码：

1. 将字符解析成数字

//将字符解成数字
int char_number(char c){if(c >= '0' && c <= '9')return c-'0';else if(c >= 'A' && c <= 'F')return (c - 'A' + 10); else if(c >= 'a' && c <= 'f')return (c - 'a' + 10);elsereturn 0;
}

2. 各进制加运算法

//进行进制运算      2-10 || 16   
//返回值表示是否有进位
int operation(int x,int n){int a;int i = 0;number[0] = 0;for(i =0;i < n;i++){a = number_z[i] + number_z[n-i-1] + number[i];if(a >= x){number[i] = a - x;number[i+1] = 1; }else{number[i] = a;number[i+1] = 0;}}return number[n];
}

3. 判断数字是否满足实验要求

//传入number的位数，判定是否 是 同位数
int number_pd(int n){for(int i = 0; i<n;i++){if(number[i] != number[n-i-1])  return 0;   //不满足同位数要求}return 1;
}

4. 依次计算到题目要求的结束

    while(1){//将数值传入临时保存for(int i=0; i <cnt_n; i++){number_z[i] = number[i];}//超出计算次数if(cnt > 30){printf("Impossible!\r\n");return 0;}cnt_n = cnt_n + operation(n, cnt_n);cnt++;//如果满足同位数if(number_pd(cnt_n) == 1){printf("STEP=%d\r\n", cnt);break;}}

总代码：

#include <stdio.h>
#include <string.h>char M[100];
int number_z[10000];
int number  [10000] = {0};//将字符解成数字
int char_number(char c){if(c >= '0' && c <= '9')return c-'0';else if(c >= 'A' && c <= 'F')return (c - 'A' + 10); else if(c >= 'a' && c <= 'f')return (c - 'a' + 10);elsereturn 0;
}//将数字转换成字符
/*
char number_char(int n){if(n >= 0 && n<=9)return '0'+n;else if(n >= 10 && n<=15)return ('A'+n-10);
}*///进行进制运算      2-10 || 16   
//返回值表示是否有进位
int operation(int x,int n){int a;int i = 0;number[0] = 0;for(i =0;i < n;i++){a = number_z[i] + number_z[n-i-1] + number[i];if(a >= x){number[i] = a - x;number[i+1] = 1; }else{number[i] = a;number[i+1] = 0;}}return number[n];
}//传入number的位数，判定是否 是 同位数
int number_pd(int n){for(int i = 0; i<n;i++){if(number[i] != number[n-i-1])  return 0;   //不满足同位数要求}return 1;
}int main (){int n;scanf("%d",&n);scanf("%s",M);//将接收的字符串for(int i=0;i<strlen(M);i++){number[i] = char_number(M[i]);  }int cnt_n = strlen(M);int cnt = 0;    //用于计算步数while(1){//将数值传入临时保存for(int i=0; i <cnt_n; i++){number_z[i] = number[i];}//超出计算次数if(cnt > 30){printf("Impossible!\r\n");return 0;}cnt_n = cnt_n + operation(n, cnt_n);cnt++;//如果满足同位数if(number_pd(cnt_n) == 1){printf("STEP=%d\r\n", cnt);break;}}return 0;
}

总结：

代码实现了进制转换和同位数判断的功能，并且在实现过程中使用了数组、循环、条件语句等基本的编程知识。

不足之处：

变量名不够直观，例如 M、number_z、number 等变量名不够清晰，不便于阅读和理解。
函数和变量的注释不够详细，没有说明其作用、输入和输出等信息，不便于阅读和理解。
在进行进制运算时，代码中使用了 number 数组来保存结果，但是没有清空该数组，可能会导致计算结果错误。

改进意见：

变量名应该更加直观，例如 M 可以改为 input_string，number_z 可以改为 temp_number，number 可以改为 result_number 等。
在代码中添加注释，说明函数和变量的作用、输入和输出等信息，方便阅读和理解。
在进行进制运算时，应该在每次运算前清空 number 数组，避免出现错误的计算结果。可以在每次运算前使用 memset 函数将 number 数组清空。