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è);
* 請問:n位的回文數(shù)有多少個(gè)?請編寫一個(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),然后再對比逆轉(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)位置對應(yīng),998為3位數(shù)字,**除第一位(不包含前導(dǎo)0)故與后半對應(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ī)模縮小 } 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了或者爆遞歸了?
以上就是本文的全部內(nèi)容,希望對大家的學(xué)習(xí)有所幫助,也希望大家多多支持我們。
上一篇:C語言實(shí)現(xiàn)520表白代碼 祝你表白成功!
欄 目:C語言
下一篇:如何基于C語言socket編程實(shí)現(xiàn)TCP通信
本文標(biāo)題:c語言描述回文數(shù)的三種算法
本文地址:http://mengdiqiu.com.cn/a1/Cyuyan/309.html
您可能感興趣的文章
- 04-02c語言函數(shù)調(diào)用后清空內(nèi)存 c語言調(diào)用函數(shù)刪除字符
- 04-02c語言的正則匹配函數(shù) c語言正則表達(dá)式函數(shù)庫
- 04-02func函數(shù)+在C語言 func函數(shù)在c語言中
- 04-02c語言中對數(shù)函數(shù)的表達(dá)式 c語言中對數(shù)怎么表達(dá)
- 04-02c語言用函數(shù)寫分段 用c語言表示分段函數(shù)
- 04-02c語言編寫函數(shù)冒泡排序 c語言冒泡排序法函數(shù)
- 04-02c語言沒有round函數(shù) round c語言
- 04-02c語言分段函數(shù)怎么求 用c語言求分段函數(shù)
- 04-02C語言中怎么打出三角函數(shù) c語言中怎么打出三角函數(shù)的值
- 04-02c語言調(diào)用函數(shù)求fibo C語言調(diào)用函數(shù)求階乘


閱讀排行
本欄相關(guān)
- 04-02c語言函數(shù)調(diào)用后清空內(nèi)存 c語言調(diào)用
- 04-02func函數(shù)+在C語言 func函數(shù)在c語言中
- 04-02c語言的正則匹配函數(shù) c語言正則表達(dá)
- 04-02c語言用函數(shù)寫分段 用c語言表示分段
- 04-02c語言中對數(shù)函數(shù)的表達(dá)式 c語言中對
- 04-02c語言編寫函數(shù)冒泡排序 c語言冒泡排
- 04-02c語言沒有round函數(shù) round c語言
- 04-02c語言分段函數(shù)怎么求 用c語言求分段
- 04-02C語言中怎么打出三角函數(shù) c語言中怎
- 04-02c語言調(diào)用函數(shù)求fibo C語言調(diào)用函數(shù)求
隨機(jī)閱讀
- 01-11ajax實(shí)現(xiàn)頁面的局部加載
- 01-10delphi制作wav文件的方法
- 08-05織夢dedecms什么時(shí)候用欄目交叉功能?
- 08-05DEDE織夢data目錄下的sessions文件夾有什
- 01-10使用C語言求解撲克牌的順子及n個(gè)骰子
- 01-10C#中split用法實(shí)例總結(jié)
- 01-10SublimeText編譯C開發(fā)環(huán)境設(shè)置
- 08-05dedecms(織夢)副欄目數(shù)量限制代碼修改
- 01-11Mac OSX 打開原生自帶讀寫NTFS功能(圖文
- 04-02jquery與jsp,用jquery