C 語言基礎(chǔ)實(shí)現(xiàn)青蛙跳臺(tái)階和漢諾塔問題
一、青蛙跳臺(tái)階
題目
一只青蛙一次可以跳上1級(jí)臺(tái)階,也可以跳上2級(jí)臺(tái)階。求該青蛙跳上一個(gè) n 級(jí)的臺(tái)階總共有多少種跳法
思路
遇見題目我們可以在紙上先動(dòng)手畫畫,把最簡(jiǎn)單的幾種方式列出來,作比較,找規(guī)律。
分析
按照上面表格可以從跳法次數(shù),過程,或者兩者結(jié)合找規(guī)律
1. 從跳法次數(shù)分析
- 觀察表格,可以知道從n>=3時(shí),第n個(gè)數(shù)就是前兩個(gè)數(shù)的和(與斐波那契數(shù)列一樣)
- 我們自己推論,當(dāng)臺(tái)階數(shù)為n時(shí),設(shè)跳法有f(n)次,如果青蛙先跳1階,則剩下的臺(tái)階數(shù)為n-1,即剩余跳法有f(n-1)次;如果青蛙先跳2階,則剩下的臺(tái)階數(shù)為n-2,即剩余跳法有f(n-2)次。
- 故跳法次數(shù)f(n)=f(n-1)+f(n-2),因?yàn)榈忍?hào)右邊有兩個(gè)值,故當(dāng)n=1,n=2時(shí)為最后的特殊限制條件
- 下面代碼為遞歸求法,如果想用非遞歸,可以將遞歸通項(xiàng)改成循環(huán)
代碼1(遞歸)
#include <stdio.h> int jump(int n) { if (n == 1) return 1; if (n == 2) return 2; return jump(n - 1) + jump(n - 2); } int main() { int n; scanf("%d", &n); int ret = jump(n); printf("%d", ret); return 0; }
2. 從過程分析
- 觀察表格,可以知道,跳n階臺(tái)階,跳兩階臺(tái)階次數(shù)可以為0到n/2次,而每一次跳兩階臺(tái)階的順序也是不定的??梢酝ㄟ^計(jì)數(shù)原理的組合數(shù)C(n,m),表示從n個(gè)數(shù)中選m個(gè)數(shù)排列。n表示每次需要跳的次數(shù),m表示一次跳兩階的次數(shù)
- 組合數(shù)C(n,m),可以由n!/(m!*(n-m)!)求得
- 下面代碼為非遞歸求法,如果想要寫成遞歸,可以根據(jù)循環(huán)修改
代碼2(非遞歸)
#include <stdio.h> int fac(int m) { int i = 0; int count = 1; for (i = 1; i <= m; i++) { count *= i; } return count; } int jump(int n) { int i = 0; //i為跳兩階臺(tái)階的次數(shù) int sum = 0; //sum為計(jì)算跳法 for (i = 0; i <= n / 2; i++) { int a = 0; a = n - i * 2 + i; //a為跳到n階臺(tái)階跳的次數(shù) sum += fac(a) / (fac(i)*fac(a - i)); } return sum; } int main() { int n; scanf("%d", &n); int ret = jump(n); printf("%d", ret); return 0; }
二、青蛙跳臺(tái)階變式1
題目
一只青蛙一次可以跳上1級(jí)臺(tái)階,也可以跳上2級(jí)臺(tái)階…也可以跳n級(jí)臺(tái)階。求該青蛙跳上一個(gè) n 級(jí)的臺(tái)階總共有多少種跳法
分析
- 根據(jù)原題推論,當(dāng)臺(tái)階數(shù)為n時(shí),設(shè)跳法有f(n)次,如果青蛙先跳1階,則剩下的臺(tái)階數(shù)為n-1,即剩余跳法有f(n-1)次;如果青蛙先跳2階,則剩下的臺(tái)階數(shù)為n-2,即剩余跳法有f(n-2)次。
- 那么當(dāng)青蛙跳3階臺(tái)階,則剩下的臺(tái)階數(shù)為n-3,即剩余跳法有f(n-3)次…當(dāng)青蛙跳n階臺(tái)階,則剩下的臺(tái)階數(shù)為n-n,即剩余跳法有f(n-n)次
- 故跳法次數(shù)f(n)=f(n-1)+f(n-2)+f(n-3)…+f(n-n)
- 由推論可得f(n-1)=f(n-2)+f(n-3)…+f(n-n),將其代入上面式子
- 故跳法次數(shù)為f(n)=2*f(n-1),因?yàn)榈忍?hào)右邊只有一個(gè)值,故n=1為最后的特殊限制條件
代碼3(遞歸)
#include <stdio.h> int jump(int n) { if (n == 1) return 1; return 2*jump(n - 1); } int main() { int n; scanf("%d", &n); int ret = jump(n); printf("%d", ret); return 0; }
三、青蛙跳臺(tái)階變式2
題目
一只青蛙一次可以跳上1級(jí)臺(tái)階,也可以跳上2級(jí)臺(tái)階…也可以跳m級(jí)臺(tái)階。求該青蛙跳上一個(gè) n 級(jí)的臺(tái)階總共有多少種跳法(m<=n)
分析
- 根據(jù)變式1推論得f(n)=f(n-1)+f(n-2)+f(n-3)…+f(n-n)
- 而這里最多一次只能跳m階,故f(n)=f(n-1)+f(n-2)+f(n-3)…+f(n-m)
- 由推論得f(n-1)=f(n-2)+f(n-3)…+f(n-m)+f(n-m-1),代入上面式子
- 故跳法次數(shù)為f(n)=2*f(n-1)-f(n-m-1)
- 因?yàn)橥ㄟ^遞歸n的值在減少,當(dāng)n<m時(shí),其實(shí)最多就只能跳n階,與變式1就是一樣的問題了
代碼4(遞歸)
#include <stdio.h> int jump(int n,int m) { if (n > m) return 2 * jump(n - 1, m) - jump(n - 1 - m, m); else { if (n == 1) return 1; return 2 * jump(n - 1, n); } } int main() { int n, m; scanf("%d%d", &n, &m); int ret = jump(n,m); printf("%d", ret); return 0; }
四、漢諾塔問題(求步數(shù))
題目
有A,B,C三個(gè)柱子,A柱子上從上到下,從小到大排列著n個(gè)圓盤?,F(xiàn)要求將A柱子上的n個(gè)圓盤全部移動(dòng)到C柱子上,依然按照從上到下,從小到大的順序排列。且對(duì)移動(dòng)過程要求如下:
a)一次只能移動(dòng)一個(gè)盤子。
b)移動(dòng)過程中大盤子不允許出現(xiàn)在小盤子上方。
問:總共需要移動(dòng)的步數(shù)是多少?
思路
因?yàn)榍蟮氖遣綌?shù),我們可以通過找前面幾組數(shù)據(jù),觀察是否有什么規(guī)律
分析
- 通過表格觀察,可以知道盤子數(shù)為n時(shí),步數(shù)為20+21+…+2n-1,即2n-1
- 我們可以通過下面這張圖片來推論:
- 假設(shè)盤子數(shù)量為n,通過化繁為簡(jiǎn)思想,我們可以把盤子分成兩個(gè)部分。上面n-1個(gè)盤子,和最下面一個(gè)盤子。移動(dòng)步驟如下:
- 將最上面的n-1個(gè)盤子移動(dòng)到B柱上
- 將最下面的盤子移動(dòng)到C柱上
- 再將B柱上的n-1個(gè)盤子移動(dòng)到C柱上
- 問題轉(zhuǎn)化成如何移動(dòng)最上面n-1個(gè)盤子。按照上面的思路解決n-1個(gè)盤子移動(dòng)的問題。
- 假設(shè)移動(dòng)n個(gè)盤子需要的步數(shù)為f(n),則移動(dòng)n-1個(gè)盤子需要f(n-1)步。
- 故移動(dòng)步數(shù)為f(n)=f(n-1)+1+f(n-1),即f(n)=2*f(n-1)+1
- 通過等比數(shù)列變形又可以得到f(n)=2n-1
代碼5(非遞歸)
#include <stdio.h> #include <math.h> int main() { int n; scanf("%d", &n); int count =0; count=(int)pow(2,n)-1; printf("%d", count); return 0; }
代碼6(遞歸)
#include <stdio.h> int tower(int n) { if (n == 1) return 1; else return 2 * tower(n - 1) + 1; } int main() { int n; scanf("%d", &n); int ret=tower(n); printf("%d", ret); return 0; }
五、漢諾塔問題(求移動(dòng)過程)
題目
有A,B,C三個(gè)柱子,A柱子上從上到下,從小到大排列著n個(gè)圓盤?,F(xiàn)要求將A柱子上的n個(gè)圓盤全部移動(dòng)到C柱子上,依然按照從上到下,從小到大的順序排列。且對(duì)移動(dòng)過程要求如下:
a)一次只能移動(dòng)一個(gè)盤子。
b)移動(dòng)過程中大盤子不允許出現(xiàn)在小盤子上方。
問:打印移動(dòng)的方案 (例如, 移動(dòng)A柱最上面的圓盤到C柱, 則輸出"A -> C")
思路
因?yàn)榍蟮氖且苿?dòng)方案,所以我們可以將前幾組數(shù)據(jù)列出來,結(jié)合遞歸化簡(jiǎn)為繁的思想找共性和非共性
分析
- 通過觀察得到:除了n=1,n>1時(shí),都是先將A柱上面n-1個(gè)盤子拿到B柱(粗字體為其過程),再將A柱最下面盤子拿到C柱。此時(shí)A柱變成輔助柱,再將B柱上的盤子放到C柱
- 故將A柱最下面盤子移到C柱為中間過程
- 上一步為將初始柱(A柱)上面n-1個(gè)盤子借助輔助柱(C柱)移到目標(biāo)柱(B柱)【其實(shí)可以這里看作單獨(dú)一個(gè)n-1的漢諾塔,將A柱上的盤子移動(dòng)到B柱】
- 下一步為將初始柱(B柱)上面n-1個(gè)盤子借助輔助柱(A柱)移到目標(biāo)柱(C柱)【其實(shí)可以這里看作單獨(dú)一個(gè)n-1的漢諾塔,將B柱上的盤子移動(dòng)到C柱】
- 而上一步,中間過程,下一布就是遞歸的核心思想
- 而當(dāng)n=1時(shí),盤子數(shù)只有一個(gè),我們將其直接放到目標(biāo)柱即可(其為最終的限制條件)
- 初始柱,輔助柱,目標(biāo)柱,其實(shí)就是把該步驟的移動(dòng)過程當(dāng)作一個(gè)單獨(dú)的漢諾塔問題,需要移動(dòng)盤子現(xiàn)在所在的位置為初始柱,要將其放到的位置就是目標(biāo)柱
代碼7(遞歸)
#include <stdio.h> void hanio(int n, char x, char y, char z) { if (n == 1) printf("%c->%c\n",x,z); //當(dāng)盤子只剩一個(gè)時(shí),直接打印初始柱移動(dòng)到目標(biāo)柱的過程 else { hanio(n - 1, x, z, y); //將n-1個(gè)盤子從起始柱放到目標(biāo)柱(第一次A->B,第二次B->A,后面往復(fù)) printf("%c->%c\n", x, z); //打印初始柱移動(dòng)到目標(biāo)柱的過程 hanio(n - 1, y, x, z); //將n-1個(gè)盤子從起始柱放到目標(biāo)柱(第一次B->C,第二次C->B,后面往復(fù)) } } int main() { int n; scanf("%d", &n); hanio(n,'A','B','C'); return 0; }
結(jié)語:
到此這篇關(guān)于C 語言基礎(chǔ)實(shí)現(xiàn)青蛙跳臺(tái)階和漢諾塔問題的文章就介紹到這了,更多相關(guān)C 語言實(shí)現(xiàn)青蛙跳臺(tái)階和漢諾塔內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C語言 OutputDebugString與格式化輸出函數(shù)OutputDebugPrintf案例詳解
這篇文章主要介紹了C語言 OutputDebugString與格式化輸出函數(shù)OutputDebugPrintf案例詳解,本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08淺談C結(jié)構(gòu)和C++結(jié)構(gòu)之間的區(qū)別
這篇文章主要介紹了淺談C結(jié)構(gòu)和C++結(jié)構(gòu)之間的區(qū)別,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-04-04C語言代碼實(shí)現(xiàn)簡(jiǎn)易三子棋游戲
這篇文章主要為大家詳細(xì)介紹了C語言代碼實(shí)現(xiàn)簡(jiǎn)易三子棋游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-05-05關(guān)于win32 gettimeofday替代方案
下面小編就為大家?guī)硪黄P(guān)于win32 gettimeofday替代方案。小編覺得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧2016-12-12C語言結(jié)構(gòu)體鏈表和指針實(shí)現(xiàn)學(xué)生管理系統(tǒng)
這篇文章主要介紹了C語言結(jié)構(gòu)體鏈表和指針實(shí)現(xiàn)學(xué)生管理系統(tǒng),包括學(xué)生檔案管理子系統(tǒng)和學(xué)生成績(jī)管理子系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-06-06C++11/14 線程的創(chuàng)建與分離的實(shí)現(xiàn)
這篇文章主要介紹了C++11/14 線程的創(chuàng)建與分離的實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-01-01