題目描述
* 請問：n位的回文數有多少個？請編寫一個遞歸函數來解決此問題?。?！
輸入：
3
輸出：
90
輸入：
5
輸出：
900
**輸入：
10
輸出：
90000**
輸入：
8
輸出：
9000
輸入：
1
輸出：
10
思路分析
通過for循環讀入這個數,通過/和%操作將這個數據逆轉,然后再對比逆轉后的數字是否和原數字相等
通過for循環讀入這個數,每次取頭位一個數字和末位一個數字,依次比較這兩個數字是否相等,再去掉這兩個數字,直到剩下一個數字(位數為奇數)或者剩下兩個數字(位數為偶數)
通過數學關系,直接判斷位數,算出這個位數內的回文數個數;
代碼描述
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;}2. 第二種思路:
#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;}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;}額外疑問
第一第二種方法當n=10的時候運算不出來,求解為何如此,是時間復雜度太高了嗎?還是爆int了或者爆遞歸了?
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持武林網。
新聞熱點
疑難解答
圖片精選
