題目描述
注意：(這些回文數都沒有前導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是整數,位數為偶數的為910^(n/2-1)個,是以5位數字的的回文數有910*10=900個
注意位數為1有10個(0-9),需要特殊處理
代碼描述
1. 第一種思路:
#include
#include
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
long int terminate=0; //定義一個逆序目标數
reverse(i,&terminate); //把i和逆序目标數傳入
if (terminate==i){ //逆序後還和原數相等,則可計數
count++;
}
}
printf ("%d",count); //輸出個數
return 0;
}
2. 第二種思路:
#include
#include
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
if ( judge(i,n)==1){ //判斷i是否為回文,計數
count++;
}
}
printf ("%d",count);
return 0;
}
3. 第三種思路:
#include
#include
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了或者爆遞歸了?
以上就是本文的全部内容，希望對大家的學習有所幫助，也希望大家多多支援找一找教程網。