Java系列文章目錄
Write once,Runanywhere.??????
本派文章詳細(xì)斐波那契數(shù)列、青蛙跳臺(tái)階、漢諾塔(C語(yǔ)言Java通用)、遞歸練習(xí)題。
?? ?? ??如果你覺(jué)得我的文章有幫助到你，還請(qǐng)【關(guān)注?點(diǎn)贊?收藏】，得到你們支持就是我最大的動(dòng)力!!!
?? ?? ??
?版權(quán)聲明：本文由【馬上回來(lái)了】原創(chuàng)、在CSDN首發(fā)、需要轉(zhuǎn)載請(qǐng)聯(lián)系博主。
版權(quán)聲明：本文為CSDN博主「馬上回來(lái)了」的原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請(qǐng)附上原文出處鏈接及本聲明。
?????? 新的知識(shí)開(kāi)始嘍??????
1.斐波那契數(shù)列
斐波那契數(shù)列（Fibonacci sequence），又稱黃金分割數(shù)列，因數(shù)學(xué)家萊昂納多·斐波那契（Leonardo Fibonacci）以兔子繁殖為例子而引入，故又稱為“兔子數(shù)列”，指的是這樣一個(gè)數(shù)列：1、1、2、3、5、8、13、21、34、……在數(shù)學(xué)上，斐波那契數(shù)列以如下被以遞推的方法定義：F(0)=0，F(xiàn)(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）。
1.1 遞歸實(shí)現(xiàn)斐波那契數(shù)列
//遞歸實(shí)現(xiàn)斐波那契數(shù)列
//1 1 2 3 5 8 13 21 34 55 89
public static void main(String[] args) {
int n = 11;//求第十一個(gè)斐波那契數(shù)
int ret = fabonacci(n);
System.out.println(ret);
}
public static int fabonacci(int n){
if(n==1 || n==2){//遞歸的初始條件
return 1;
}else {
return fabonacci(n-1)+fabonacci(n-2);//遞歸的遞推公式
}
}
但是用遞歸來(lái)實(shí)現(xiàn)斐波那契數(shù)列并不高效，因?yàn)橛?jì)算n時(shí)每一個(gè)數(shù)字都要往前遞推，看下面代碼：
//遞歸實(shí)現(xiàn)斐波那契數(shù)列
//1 1 2 3 5 8 13 21 34 55 89
public static void main(String[] args) {
int n = 39;//求第39個(gè)斐波那契數(shù)
int ret = fabonacci(n);
System.out.println(ret);
System.out.println("n = 3被計(jì)算的次數(shù):"+count);
}
public static int count = 0;
public static int fabonacci(int n){
if(n==1 || n==2){
return 1;
}else {
if(n == 3){
count++;
}
return fabonacci(n-1)+fabonacci(n-2);
}
}
}
1.2 循環(huán)實(shí)現(xiàn)斐波那契數(shù)列
上面的代碼在計(jì)算第39個(gè)斐波那契數(shù)時(shí)，n=3被計(jì)算了太多次，效率不高，因此我們一般用循環(huán)(迭代)來(lái)實(shí)現(xiàn)斐波那契數(shù)列，看下面代碼：
//循環(huán)實(shí)現(xiàn)斐波那契數(shù)列
// 1 1 2 3 5 8 13 21 34 55 89
public static void main(String[] args) {
int f1 = 1;
int f2 = 1;
int fn = 0;
Scanner in = new Scanner(System.in);
int n = in.nextInt();//輸入n=8
while (n>2){
fn = f1+f2;
f1 = f2;
f2 = fn;
n--;
}
System.out.println(fn);
}
2.青蛙跳臺(tái)階
2.1問(wèn)題敘述
青蛙每次跳臺(tái)階都有兩種方式，一步跳一階樓梯，一步跳兩階樓梯，問(wèn)現(xiàn)在有n階樓梯，青蛙跳完這n階樓梯有幾種方法？
2.2 .問(wèn)題分析
當(dāng)n=1時(shí)，一步跳一階只有1種跳。
當(dāng)n=2時(shí)，可以一步先只跳一階，還剩下一階，則剩下的跳法就是剩下這一個(gè)臺(tái)階的跳法；或者直接一步跳兩階，因此只有2種跳法。
當(dāng)n=3時(shí)，先第一步跳一階，還剩兩階，因此把這個(gè)臺(tái)階跳完的方法取決于這剩下的兩個(gè)階的跳法，也就是n=2的跳法，因此第一步跳一階的跳法有2種；然后第一步跳兩階，還剩下一階，也就是還剩下n=1的臺(tái)階的跳法，因此第一步跳兩階的跳法只有一種，總共有3中跳法。
當(dāng)n=4時(shí)，第一步先跳一階，還剩下三階，把這個(gè)臺(tái)階跳完的方法取決于剩下的這三個(gè)臺(tái)階即n=3的跳法；第一步跳兩階，還剩下兩階即n=2的跳法，所以總的跳法=(n=2)+(n=3)=5種。
當(dāng)n=5時(shí)，以此類推。
我們可以得出以下規(guī)律：
| 臺(tái)階數(shù)n | 跳法f |
|---|---|
| 1 | f(1)=1 |
| 2 | f(2)=2 |
| 3 | f(3)=f(3-1)(第一步跳一階，剩下兩階)+f(3-2)(第一步跳l兩階，剩下一階)=1+2=3 |
| 4 | f(4)=f(4-1)+f(4-2)=f(3)+f(2)=3+2=5 |
| n | f(n-1)+f(n-2) |
通過(guò)對(duì)結(jié)果的觀察不能發(fā)現(xiàn)其實(shí)青蛙跳臺(tái)階問(wèn)題就是一個(gè)斐波那契數(shù)列，因此代碼實(shí)現(xiàn)斐波那契數(shù)列一樣。
2.3 青蛙跳臺(tái)階進(jìn)階
現(xiàn)在青蛙每一步有三種跳法：
1.一步一階
2.一步兩階
3.一步三階
求青蛙跳n階臺(tái)階有幾種跳法？
分析：
n=1時(shí)，一步一階1種；
n=2時(shí)，先一步一階，還剩一階，因此有1種跳法；先一步兩階，跳完，2種；
n=3時(shí)，先一步一階，還剩兩階，剩下的兩階的跳法總數(shù)，就是第一步只跳一階跳完整個(gè)臺(tái)階的方法，n=2有2種；先一步兩階，還剩一階，n=1有1種；直接一步階，跳完，有4種。
n=4時(shí)，以此類推,先一步一階，還剩三階，n=3有4種；先一步兩階，還剩兩階，n=2有2種；先一步三階，n=1有1種，總共有4+2+1=7種。
n=5……
通過(guò)觀察可以得出遞推公式：
n<=3時(shí)，f(1) = 1,f(2) = 2,f(3)=4
n>3時(shí)，f(n)=f(n-1)+f(n-2)+f(n-3)
與原斐波那契數(shù)列相比，這里變成了從第四個(gè)數(shù)開(kāi)始，每一位等于前面的三個(gè)數(shù)之和。原因在于增加了n=3時(shí)的初始條件。
1 2 4 7 13……
所以在弄懂了上面的原理之后，現(xiàn)在又給你出一道題：
現(xiàn)在青蛙每一步有k種跳法：
1.一步一階
2.一步兩階
3.一步三階
……
k.一步k階
求青蛙跳n階臺(tái)階有幾種跳法？
我們很快就能得出，只是將初始條件由n=3改成了n=k，所以很快就能得出遞推公式：
n<=k時(shí)，f(1) = 1,f(2) = 2,f(3)=4，……f(k)=假設(shè)K種
n>k時(shí)，f(n)=f(n-1)+f(n-2)+f(n-3)+……+f(n-k)
3.漢諾塔
漢諾塔C語(yǔ)言實(shí)現(xiàn)
之前我已經(jīng)講解過(guò)了C語(yǔ)言實(shí)現(xiàn)漢諾塔，可以點(diǎn)進(jìn)去觀看一下。
關(guān)鍵在于：
將每次都將n個(gè)盤(pán)子看做(n-1)+1,然后將(n-1)個(gè)盤(pán)子移到中間柱子y上，然后將剩下的一個(gè)盤(pán)子移到目標(biāo)柱子z上，然后又將在y柱上的(n-1)個(gè)盤(pán)子又看做是(n-2)+1,將(n-2)個(gè)盤(pán)子移到中間柱子x上，然后將剩下的1個(gè)盤(pán)移到目標(biāo)柱z上，以此類推，直到n=1為止。。代碼讓人難理解的地方就是因?yàn)?，起始柱，中間柱，目標(biāo)柱在每次遞歸的時(shí)候都在發(fā)生變化。
這里再用java實(shí)現(xiàn)一遍，看代碼：
//漢諾塔
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();//輸入你要移動(dòng)的盤(pán)子數(shù) n=3
hanoi(n,'X','Y','Z');
}
//移動(dòng)
public static void move(char pos1,char pos2){
System.out.println(pos1+"->"+pos2);
}
public static void hanoi(int n,char pos1,char pos2,char pos3){
if(n==1){//只有1個(gè)盤(pán)子
move(pos1,pos3);//直接x->z
}else{
hanoi(n-1,pos1,pos3,pos2);//將n-1個(gè)盤(pán)子借助Z移到Y(jié)上
move(pos1,pos3);//將剩下的1個(gè)盤(pán)子從X移到Z上
hanoi(n-1,pos2,pos1,pos3);//將Y上的n-1個(gè)盤(pán)子再移到Z上
}
}
運(yùn)行結(jié)果：
4 遞歸練習(xí)題
4.1按順序打印一個(gè)數(shù)字的每一位(例如 1234 打印出 1 2 3 4) （遞歸）
//寫(xiě)一個(gè)遞歸方法，輸入一個(gè)非負(fù)整數(shù)，返回組成它的數(shù)字之和
// 1921
public static void main(String[] args) {
int year = 1921;
print(year);
}
public static void print(int n){
if(n < 10){
System.out.print(n+" ");
}else{
print(n/10);
System.out.print(n%10+" ");
}
}
4.2 寫(xiě)一個(gè)遞歸方法，輸入一個(gè)非負(fù)整數(shù)，返回組成它的數(shù)字之和
//寫(xiě)一個(gè)遞歸方法，輸入一個(gè)非負(fù)整數(shù)，返回組成它的數(shù)字之和
// 1234=1+2+3+4=10
public static void main(String[] args) {
int n = 1234;
int ret = seadd(n);
System.out.println(ret);
}
public static int seadd(int n){
if(n<10){//起始條件
return n;//直接返回n的值
}else{
return n%10+seadd(n/10);//遞推公式 假設(shè)n=12 則這里返回的值：12%10+1=3
}
}
4.3 遞歸求 1 + 2 + 3 + … + 10
//遞歸求 1 + 2 + 3 + ... + 10
public static void main(String[] args) {
int n = 10;
int ret = add(n);
System.out.println(ret);
}
public static int add(int n){
if(n==1){//起始條件
return 1;
}else{
return n+add(n-1);//遞推公式 當(dāng)n=2時(shí)，return 2+1 =3
}
}
4. 4遞歸求 N 的階乘
//遞歸求 N 的階乘
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();//輸入你要求的階乘 n=5
int ret = fac(n);
System.out.println(ret);
}
public static int fac(int n){
if(n == 1){//初始條件
return 1;
}else {
return n*fac(n-1);//遞推公式：當(dāng)n=2時(shí)，return: 2*1=2
}
}
??????今天的你看懂這里又學(xué)到了很多東西吧??????文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-401254.html
?? ?? ??下次見(jiàn)嘍?? ?? ??
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-401254.html
到了這里，關(guān)于斐波那契數(shù)列、青蛙跳臺(tái)階、漢諾塔(C語(yǔ)言Java通用)、遞歸練習(xí)題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
