求回文数的三种算法的c语言描述

栏目: C · 发布时间: 5年前

内容简介:*请问: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

求回文数的三种算法的 <a href='https://www.codercto.com/topics/20720.html'>c语言</a> 描述

输入:

3

输出:

90

输入:

5

输出:

900

**输入:

10

输出:

90000**

输入:

8

输出:

9000

输入:

1

输出:

10

思路分析

  1. 通过for循环读入这个数, 通过/和%操作 将这个数据逆转,然后再对比逆转后的数字是否和原数字相等

求回文数的三种算法的c语言描述

  1. 通过for循环读入这个数, 每次取头位一个数字和末位一个数字,依次比较这两个数字是否相等 ,再去掉这两个数字,直到剩下一个数字(位数为奇数)或者剩下两个数字(位数为偶数)

求回文数的三种算法的c语言描述

. 通过 数学关系 ,直接判断位数,算出这个位数内的回文数个数;

  • 例如: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),需要特殊处理

代码描述

  1. 第一种思路:
#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;
}
  1. 第二种思路:
#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;
}
  1. 第三种思路:
#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语言描述》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

像计算机科学家一样思考Python (第2版)

像计算机科学家一样思考Python (第2版)

[美] 艾伦 B. 唐尼 / 赵普明 / 人民邮电出版社 / 2016-7 / 49.00

本书以培养读者以计算机科学家一样的思维方式来理解Python语言编程。贯穿全书的主体是如何思考、设计、开发的方法,而具体的编程语言,只是提供了一个具体场景方便介绍的媒介。 全书共21章,详细介绍Python语言编程的方方面面。本书从基本的编程概念开始讲起,包括语言的语法和语义,而且每个编程概念都有清晰的定义,引领读者循序渐进地学习变量、表达式、语句、函数和数据结构。书中还探讨了如何处理文件和......一起来看看 《像计算机科学家一样思考Python (第2版)》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器