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

jiezi

5 年前

注意：（这些回文数都没有前导 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 了或者爆递归了?

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

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

题目描述

思路分析

代码描述

额外疑问