一、青蛙跳臺(tái)階
題目
一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)臺(tái)階。求該青蛙跳上一個(gè) n 級(jí)的臺(tái)階總共有多少種跳法
思路
遇見(jiàn)題目我們可以在紙上先動(dòng)手畫(huà)畫(huà)，把最簡(jiǎn)單的幾種方式列出來(lái)，作比較，找規(guī)律。
分析
按照上面表格可以從跳法次數(shù)，過(guò)程，或者兩者結(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. 從過(guò)程分析
- 觀察表格，可以知道，跳n階臺(tái)階，跳兩階臺(tái)階次數(shù)可以為0到n/2次，而每一次跳兩階臺(tái)階的順序也是不定的。可以通過(guò)計(jì)數(shù)原理的組合數(shù)C(n，m)，表示從n個(gè)數(shù)中選m個(gè)數(shù)排列。n表示每次需要跳的次數(shù)，m表示一次跳兩階的次數(shù)
- 組合數(shù)C(n，m)，可以由n！/(m！*(n-m)！)求得
- 下面代碼為非遞歸求法，如果想要寫(xiě)成遞歸，可以根據(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)橥ㄟ^(guò)遞歸n的值在減少，當(dāng)n<m時(shí)，其實(shí)最多就只能跳n階，與變式1就是一樣的問(wèn)題了
代碼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;
}
四、漢諾塔問(wèn)題（求步數(shù)）
題目
有A，B，C三個(gè)柱子，A柱子上從上到下，從小到大排列著n個(gè)圓盤(pán)。現(xiàn)要求將A柱子上的n個(gè)圓盤(pán)全部移動(dòng)到C柱子上，依然按照從上到下，從小到大的順序排列。且對(duì)移動(dòng)過(guò)程要求如下：
a）一次只能移動(dòng)一個(gè)盤(pán)子。
b）移動(dòng)過(guò)程中大盤(pán)子不允許出現(xiàn)在小盤(pán)子上方。
問(wèn)：總共需要移動(dòng)的步數(shù)是多少？
思路
因?yàn)榍蟮氖遣綌?shù)，我們可以通過(guò)找前面幾組數(shù)據(jù)，觀察是否有什么規(guī)律
分析
- 通過(guò)表格觀察，可以知道盤(pán)子數(shù)為n時(shí)，步數(shù)為20+21+…+2n-1，即2n-1
- 我們可以通過(guò)下面這張圖片來(lái)推論：
- 假設(shè)盤(pán)子數(shù)量為n，通過(guò)化繁為簡(jiǎn)思想，我們可以把盤(pán)子分成兩個(gè)部分。上面n-1個(gè)盤(pán)子，和最下面一個(gè)盤(pán)子。移動(dòng)步驟如下：
- 將最上面的n-1個(gè)盤(pán)子移動(dòng)到B柱上
- 將最下面的盤(pán)子移動(dòng)到C柱上
- 再將B柱上的n-1個(gè)盤(pán)子移動(dòng)到C柱上
- 問(wèn)題轉(zhuǎn)化成如何移動(dòng)最上面n-1個(gè)盤(pán)子。按照上面的思路解決n-1個(gè)盤(pán)子移動(dòng)的問(wèn)題。
- 假設(shè)移動(dòng)n個(gè)盤(pán)子需要的步數(shù)為f(n)，則移動(dòng)n-1個(gè)盤(pán)子需要f(n-1)步。
- 故移動(dòng)步數(shù)為f(n)=f(n-1)+1+f(n-1)，即f(n)=2*f(n-1)+1
- 通過(guò)等比數(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;
}
五、漢諾塔問(wèn)題（求移動(dòng)過(guò)程）
題目
有A，B，C三個(gè)柱子，A柱子上從上到下，從小到大排列著n個(gè)圓盤(pán)。現(xiàn)要求將A柱子上的n個(gè)圓盤(pán)全部移動(dòng)到C柱子上，依然按照從上到下，從小到大的順序排列。且對(duì)移動(dòng)過(guò)程要求如下：
a）一次只能移動(dòng)一個(gè)盤(pán)子。
b）移動(dòng)過(guò)程中大盤(pán)子不允許出現(xiàn)在小盤(pán)子上方。
問(wèn)：打印移動(dòng)的方案 (例如, 移動(dòng)A柱最上面的圓盤(pán)到C柱, 則輸出"A -> C")
思路
因?yàn)榍蟮氖且苿?dòng)方案，所以我們可以將前幾組數(shù)據(jù)列出來(lái)，結(jié)合遞歸化簡(jiǎn)為繁的思想找共性和非共性
分析
- 通過(guò)觀察得到：除了n=1，n>1時(shí)，都是先將A柱上面n-1個(gè)盤(pán)子拿到B柱（粗字體為其過(guò)程），再將A柱最下面盤(pán)子拿到C柱。此時(shí)A柱變成輔助柱，再將B柱上的盤(pán)子放到C柱
- 故將A柱最下面盤(pán)子移到C柱為中間過(guò)程
- 上一步為將初始柱（A柱）上面n-1個(gè)盤(pán)子借助輔助柱（C柱）移到目標(biāo)柱（B柱）【其實(shí)可以這里看作單獨(dú)一個(gè)n-1的漢諾塔，將A柱上的盤(pán)子移動(dòng)到B柱】
- 下一步為將初始柱（B柱）上面n-1個(gè)盤(pán)子借助輔助柱（A柱）移到目標(biāo)柱（C柱）【其實(shí)可以這里看作單獨(dú)一個(gè)n-1的漢諾塔，將B柱上的盤(pán)子移動(dòng)到C柱】
- 而上一步，中間過(guò)程，下一布就是遞歸的核心思想
- 而當(dāng)n=1時(shí)，盤(pán)子數(shù)只有一個(gè)，我們將其直接放到目標(biāo)柱即可（其為最終的限制條件）
- 初始柱，輔助柱，目標(biāo)柱，其實(shí)就是把該步驟的移動(dòng)過(guò)程當(dāng)作一個(gè)單獨(dú)的漢諾塔問(wèn)題，需要移動(dòng)盤(pán)子現(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)盤(pán)子只剩一個(gè)時(shí)，直接打印初始柱移動(dòng)到目標(biāo)柱的過(guò)程
else
{
hanio(n - 1, x, z, y); //將n-1個(gè)盤(pán)子從起始柱放到目標(biāo)柱(第一次A->B，第二次B->A，后面往復(fù))
printf("%c->%c\n", x, z); //打印初始柱移動(dòng)到目標(biāo)柱的過(guò)程
hanio(n - 1, y, x, z); //將n-1個(gè)盤(pán)子從起始柱放到目標(biāo)柱(第一次B->C，第二次C->B，后面往復(fù))
}
}
int main()
{
int n;
scanf("%d", &n);
hanio(n,'A','B','C');
return 0;
}
結(jié)語(yǔ)：
到此這篇關(guān)于C 語(yǔ)言基礎(chǔ)實(shí)現(xiàn)青蛙跳臺(tái)階和漢諾塔問(wèn)題的文章就介紹到這了,更多相關(guān)C 語(yǔ)言實(shí)現(xiàn)青蛙跳臺(tái)階和漢諾塔內(nèi)容請(qǐng)搜索服務(wù)器之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持服務(wù)器之家！
原文鏈接：https://blog.csdn.net/weixin_51367845/article/details/116136835
