共计 1965 个字符,预计需要花费 5 分钟才能阅读完成。
c 语言求回文数的三种算法的描述
题目描述
- 注意:(这些回文数都没有前导 0 )
- 1 位的回文数有 0,1,2,3,4,5,6,7,8,9 共 10 个;
- 2 位的回文数有 11,22,33,44,55,66,77,88,99 共 9 个;
* 请问:n 位的回文数有多少个?请编写一个递归函数来解决此问题!!!
- 【输入形式】一行一个正整数,代表多少位
- 【输出形式】一行一个正整数,代表回文诗的个数
- 【样例输入】2
- 【样例输出】9
输入:
3
输出:
90
输入:
5
输出:
900
** 输入:
10
输出:
90000**
输入:
8
输出:
9000
输入:
1
输出:
10
思路分析
- 通过 for 循环读入这个数,通过 / 和 % 操作 将这个数据逆转, 然后再对比逆转后的数字是否和原数字相等
- 通过 for 循环读入这个数,每次取头位一个数字和末位一个数字, 依次比较这两个数字是否相等 , 再去掉这两个数字, 直到剩下一个数字(位数为奇数) 或者剩下两个数字(位数为偶数)
. 通过 数学关系, 直接判断位数, 算出这个位数内的回文数个数;
- 例如:99899
- 可以把它分为两半, 取前面一半 998, 如果是回文数, 其后面一半一定是与其相应位置对应,998 为 3 位数字,除第一位 (不包含前导 0) 故与后半对应的位置那个数有 9 种选择 (1-9) 外, 其他位都与相应的位置有 10 种选择(0-9), 例如第二位和倒数第二位(0-9)
- 所以可以总结出来相同的位数, 位数为奇数奇数其回文数有 9 10^(n/2)个, 注意 n / 2 是整数, 位数为偶数的为 9 10^(n/2-1)个, 所以 5 位数字的的回文数有 9 1010=900 个
- 注意位数为 1 有 10 个(0-9), 需要特殊处理
代码描述
- 第一种思路:
#include <stdio.h>
#include <math.h>
int reverse(long int i,long int *terminate) // 递归函数求数值的逆序
{if (i<=0){ // 递归出口
return 1;
}
else{
*terminate*=10; // 每次乘 10 升位数
*terminate+=i%10; // 加上个位
reverse(i/10,terminate); // 递归每次规模缩小
}
return 1;
}
int main ()
{
int n;
scanf ("%d",&n); // 读入一个 n, 表示 n 位整数
long int i;
int count=0;
if (n==1){// 如果等于 1, 则有 10 个(0- 9 都是), 特殊处理;
printf ("10");
return 0;
}
for (i=pow(10,n-1);i<pow(10,n);i++){// 从第一个 n 位数开始(10^(n-1)), 到(10^n)-1
long int terminate=0; // 定义一个逆序目标数
reverse(i,&terminate); // 把 i 和逆序目标数传入
if (terminate==i){ // 逆序后还和原数相等, 则可计数
count++;
}
}
printf ("%d",count); // 输出个数
return 0;
}
- 第二种思路:
#include <stdio.h>
#include <math.h>
int judge(int i,int n)
{
int first,last;
if (n<=1){// 规模减小, 直到 n 为 1(偶数)或者 0
return 1;
}
else{first=i/pow(10,n-1); // 头位数字
last=i%10; // 末位数字
if (first!=last){ // 头位末尾不一样直接退出
return 0;
}
int tem=pow(10,n-1);
judge(i%tem/10,n-2); // 剔除头尾剩下中间, 位数减二
}
}
int main ()
{
int n;
scanf("%d",&n);
if (1==n){printf ("10");
return 0;
}
int i;
int count=0;
long long low=pow(10,n-1); // 循环入口
long long high=pow(10,n); // 循环出口
for (i=low;i<high;i++){if ( judge(i,n)==1){ // 判断 i 是否为回文, 计数
count++;
}
}
printf ("%d",count);
return 0;
}
- 第三种思路:
#include <stdio.h>
#include <math.h>
int main (){
int n;
scanf ("%d",&n);
int ji=9*pow(10,n/2),ou=9*pow(10,n/2-1);
if (n==1){printf ("10");
}
else if (n==2){printf ("%d",9);
}
else if (n%2==1){printf ("%d",ji);
}
else if (n%2==0){printf("%d",ou);
}
return 0;
}
额外疑问
- 第一第二种方法当 n =10 的时候运算不出来, 求解为何如此, 是时间复杂度太高了吗? 还是爆 int 了或者爆递归了?
正文完