内容简介:*请问:n位的回文数有多少个?请编写一个递归函数来解决此问题!!!输入:
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 10 10=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了或者爆递归了?
以上所述就是小编给大家介绍的《求回文数的三种算法的c语言描述》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 回文算法(JavaScript)
- 让我们一起啃算法----回文数
- java算法题:最长回文串
- 【算法趣题】Q01 回文十进制数
- 高频算法面试题(字符串) leetcode 125. 验证回文串
- 算法 - 找最长回文字符串, 从3s到30ms的解法说明
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
年入10万,17岁草根少年的网赚实战
陶秋丰 / 重庆出版集团 / 2009-3 / 28.00元
《年入10万:17岁草根少年的网赚实战》以一个17岁的在校大学生的真实故事为大家讲述草根少年的网络赚钱之旅。随着网络的普及以及网上应用的日益增多,要在网络上谋生并不难,比如网上写稿、网上兼职、威客赚钱、网上开店等,然而要利用互联网赚大钱,并成就一番事业,那么创建并运营一个独立的网站就是一个绝佳的选择。本书的作者正是经历了“网上写稿一网上各类兼职一策划并创建网站一网站推广与运营一年入10万”这一过程......一起来看看 《年入10万,17岁草根少年的网赚实战》 这本书的介绍吧!