c語言描述回文數(shù)的三種算法
題目描述
- 注意:(這些回文數(shù)都沒有前導(dǎo)0)
- 1位的回文數(shù)有0,1,2,3,4,5,6,7,8,9 共10個(gè);
- 2位的回文數(shù)有11,22,33,44,55,66,77,88,99 共9個(gè);
* 請(qǐng)問:n位的回文數(shù)有多少個(gè)?請(qǐng)編寫一個(gè)遞歸函數(shù)來解決此問題!??!
- 【輸入形式】一行一個(gè)正整數(shù),代表多少位
- 【輸出形式】一行一個(gè)正整數(shù),代表回文詩的個(gè)數(shù)
- 【樣例輸入】2
- 【樣例輸出】9

輸入:
3
輸出:
90
輸入:
5
輸出:
900
**輸入:
10
輸出:
90000**
輸入:
8
輸出:
9000
輸入:
1
輸出:
10
思路分析
通過for循環(huán)讀入這個(gè)數(shù),通過/和%操作將這個(gè)數(shù)據(jù)逆轉(zhuǎn),然后再對(duì)比逆轉(zhuǎn)后的數(shù)字是否和原數(shù)字相等

通過for循環(huán)讀入這個(gè)數(shù),每次取頭位一個(gè)數(shù)字和末位一個(gè)數(shù)字,依次比較這兩個(gè)數(shù)字是否相等,再去掉這兩個(gè)數(shù)字,直到剩下一個(gè)數(shù)字(位數(shù)為奇數(shù))或者剩下兩個(gè)數(shù)字(位數(shù)為偶數(shù))

通過數(shù)學(xué)關(guān)系,直接判斷位數(shù),算出這個(gè)位數(shù)內(nèi)的回文數(shù)個(gè)數(shù);
- 例如:99899
- 可以把它分為兩半,取前面一半998,如果是回文數(shù),其后面一半一定是與其相應(yīng)位置對(duì)應(yīng),998為3位數(shù)字,**除第一位(不包含前導(dǎo)0)故與后半對(duì)應(yīng)的位置那個(gè)數(shù)有9種選擇(1-9)外,其他位都與相應(yīng)的位置有10種選擇(0-9)**,例如第二位和倒數(shù)第二位(0-9)
- 所以可以總結(jié)出來相同的位數(shù),位數(shù)為奇數(shù)奇數(shù)其回文數(shù)有9*10^(n/2)個(gè),注意n/2是整數(shù),位數(shù)為偶數(shù)的為910^(n/2-1)個(gè),所以5位數(shù)字的的回文數(shù)有910*10=900個(gè)
- 注意位數(shù)為1有10個(gè)(0-9),需要特殊處理
代碼描述
1. 第一種思路:
#include <stdio.h>
#include <math.h>
int reverse(long int i,long int *terminate) //遞歸函數(shù)求數(shù)值的逆序
{
if (i<=0){ //遞歸出口
return 1;
}
else{
*terminate*=10; //每次乘10升位數(shù)
*terminate+=i%10; //加上個(gè)位
reverse(i/10,terminate); //遞歸每次規(guī)??s小
}
return 1;
}
int main ()
{
int n;
scanf ("%d",&n); //讀入一個(gè)n,表示n位整數(shù)
long int i;
int count=0;
if (n==1){ //如果等于1,則有10個(gè)(0-9都是),特殊處理;
printf ("10");
return 0;
}
for (i=pow(10,n-1);i<pow(10,n);i++){ //從第一個(gè)n位數(shù)開始(10^(n-1)),到(10^n)-1
long int terminate=0; //定義一個(gè)逆序目標(biāo)數(shù)
reverse(i,&terminate); //把i和逆序目標(biāo)數(shù)傳入
if (terminate==i){ //逆序后還和原數(shù)相等,則可計(jì)數(shù)
count++;
}
}
printf ("%d",count); //輸出個(gè)數(shù)
return 0;
}
2. 第二種思路:
#include <stdio.h>
#include <math.h>
int judge(int i,int n)
{
int first,last;
if (n<=1){ //規(guī)模減小,直到n為1(偶數(shù))或者0
return 1;
}
else{
first=i/pow(10,n-1); //頭位數(shù)字
last=i%10; //末位數(shù)字
if (first!=last){ //頭位末尾不一樣直接退出
return 0;
}
int tem=pow(10,n-1);
judge(i%tem/10,n-2); //剔除頭尾剩下中間,位數(shù)減二
}
}
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); //循環(huán)入口
long long high=pow(10,n); //循環(huán)出口
for (i=low;i<high;i++){
if ( judge(i,n)==1){ //判斷i是否為回文,計(jì)數(shù)
count++;
}
}
printf ("%d",count);
return 0;
}
3. 第三種思路:
#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;
}
額外疑問
第一第二種方法當(dāng)n=10的時(shí)候運(yùn)算不出來,求解為何如此,是時(shí)間復(fù)雜度太高了嗎?還是爆int了或者爆遞歸了?
以上就是本文的全部?jī)?nèi)容,希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
解決Microsoft?Visual?C++?2010?Express?運(yùn)行及調(diào)試問題
這篇文章主要介紹了解決Microsoft?Visual?C++?2010?Express?運(yùn)行及調(diào)試問題,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2022-01-01
c實(shí)現(xiàn)linux下的數(shù)據(jù)庫備份
本文給大家簡(jiǎn)單介紹下c實(shí)現(xiàn)linux下的數(shù)據(jù)庫備份的方法和具體的源碼,十分的實(shí)用,有需要的小伙伴可以參考下。2015-07-07
visual studio2019的安裝以及使用圖文步驟詳解
這篇文章主要介紹了visual studio2019的安裝以及使用圖文步驟詳解,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-03-03
C語言實(shí)現(xiàn)簡(jiǎn)易通訊錄實(shí)例
大家好,本篇文章主要講的是C語言實(shí)現(xiàn)簡(jiǎn)易通訊錄實(shí)例,感興趣的同學(xué)趕快來看一看吧,對(duì)你有幫助的話記得收藏一下2022-02-02
C語言進(jìn)程程序替換的實(shí)現(xiàn)詳解
為什么要進(jìn)程替換?因?yàn)楦高M(jìn)程創(chuàng)建出來的子進(jìn)程和父進(jìn)程擁有相同的代碼段,所以,子進(jìn)程看到的代碼和父進(jìn)程是一樣的。當(dāng)我們想要讓子進(jìn)程執(zhí)行不同的程序時(shí)候,就需要讓子進(jìn)程調(diào)用進(jìn)程程序替換的接口,從而讓子進(jìn)程執(zhí)行不一樣的代碼2022-08-08
基于Qt開發(fā)獲取CTP量化交易接口測(cè)試數(shù)據(jù)工具
這篇文章主要為大家詳細(xì)介紹了如何使用Qt軟件開發(fā)K線股P相關(guān)軟件,先開發(fā)一個(gè)通過CTP量化交易的sdk獲取相關(guān)推送數(shù)據(jù)的工具,需要的可以參考下2024-04-04

