歡迎回到：遇見藍橋遇見你，不負代碼不負卿！

【前言】：鐵汁們在看這篇文章之前，先將遞回上半部分大致看一下，再次加深認識，

https://blog.csdn.net/weixin_57544072/article/details/120836167utm_source=app&app_version=4.16.0

目錄

一、精選題講解

1、斐波那契數列

三段論

代碼執行

2、青蛙跳臺階

三段論

代碼執行

3、最大公約數

輾轉相除法

代碼執行

遞回代碼

4、漢諾塔問題

解題思路

代碼執行

二、思考題：放蘋果

三、藍橋結語：遇見代碼遇見你，不負代碼不負卿

一、精選題講解

1、斐波那契數列

題目描述：求斐波那契數列的第N項，1 1 2 3 5 8 13 21...

三段論

找重復：求前兩項是原問題的重復，規模更小，是其子問題

找變化：很明顯，只有n在變化

找邊界：當n == 1 || n == 2時結束

代碼執行

#include<stdio.h>

int fac(int n)
{
	//找邊界
	if (n == 1 || n == 2)
	{
		return 1;
	}
	//找重復
	return fac(n - 1) + fac(n - 2);
}

int main()
{
	int ret = fac(7);

	printf("%d\n", ret);

	return 0;
}

這里筆者要補充另外一種遞回解題思維，所以請鐵汁們先回顧一下，看看筆者在遞回上篇講了什么

https://blog.csdn.net/weixin_57544072/article/details/120836167utm_source=app&app_version=4.16.0

我在遞回（上）里面講到一種“切蛋糕思維”式的解題方法，它能夠解決很多平常我們遇到的遞回類的題目，但是就本題而言，單單是“切一刀”是解決不了問題的

求斐波那契數列的第N項，即求f(N), 這里如果只是“劃一刀”，則變成了f(N - 1),很顯然，只劃一刀是解決不了本題的，但是不難看出，f(N) = f(N - 1) + f(N - 2),也就可以理解為上篇中提到的把蛋糕比作“專案”，在上一篇中，小高這個人比較懶，他呢，只做了一丟丟，剩下的很大一部分都委派給了另外一個人用遞回的方式去完成， 但是在這里，他更懶了，懶到那一丟丟都不想做，直接全權委派給了另外兩個人用遞回的方式去解決，

所以：上篇博文都是"劃一刀“就解決問題了，現在可就不行了噢，所以鐵汁們，當你們以后遇到遞回的題目，先看看”劃一刀”能不能解決，不能解決時也別忙轉換思路，先看看自己是不是形參寫少了，實在沒找出毛病，再想想是不是需要轉化思維，

總結：上一篇博文都是利用“切蛋糕思維” ，f (N) = x + f(N + 1)

其存在變體是：f(N) = f(N / 2) + f(N / 2)-->兩次規模湊起來是一個規模，后面可能遇到，

而今天博文中提到的斐波那契數列比較特殊：f(N) = f(N - 1) + f(N - 2)

所以：遞回可以分解為：直接量 + 小規模子問題；也可以分解為：多個小規模子問題

其實在實際運用當中，我們不會采用遞回的方式去求斐波那契數列，因為它進行了大量的重復運算，至于為什么，后面講到二叉樹的時候會詳細介紹，這里就不過多贅述了，

所以為了避免進行大量多余的計算，我們會選用迭代去求斐波那契數列問題，也就是常說的回圈，

#include<stdio.h>
int fib(int n)
{
	int last2 = 1;
	int last1 = 1;
	int cur = 1;
	for (int i = 3; i <= n; i++)
	{
		cur = last1 + last2;
		last2 = last1;
		last1 = cur;
	}
	return cur;
}
int main()
{
	printf("%d\n", fib(7));
	return 0;
}

2、青蛙跳臺階

題目描述：一只青蛙一次可以跳上1級臺階，也可以跳上兩級，求：該青蛙跳上一個n級的臺階總共有多少種跳法？

注意：注意這個題目問的是什么？

問的不是青蛙能跳多少次，而是有多少種跳法能到最后一個臺階，

問題分析：當n > 2時，第一次跳就有兩種不同的選擇：一是第一次只跳一級，此時跳法數目等于后面剩下的（n - 1）級臺階的跳法數目，即為f(n - 1); 還有一種選擇是第一次跳兩級，此時跳法數目等于后面剩下的（n - 2）級臺階的跳法數目，即為f(n - 2).

所以有：f(n) = f(n - 1) + f(n - 2)

當n == 1時，有1種跳法；

當n == 2時，有2種跳法；

當n == 3時，有3種跳法；

當n == 4時，有5種跳法，

是呀，這題跟斐波那契數列基本上一樣，不過這道題目需要思考一下，沒有斐波那契這么明顯，

三段論

找重復：求（n - 1）和（n - 2）個臺階的跳法，是原問題的重復，規模更小，是其子問題

找變化：很顯然，n一直在變化

找邊界:當n == 1時或者n == 2時，就找到出口了

代碼執行

#include<stdio.h>
int jumpfloor(int n)
{
	//找邊界
	if (n == 1)
	{
		return 1;
	}
	if (n == 2)
	{
		return 2;
	}
	//找重復
	return jumpfloor(n - 1) + jumpfloor(n - 2);
}

int main()
{
	printf("%d\n", jumpfloor(5));
	return 0;
}

3、最大公約數

輾轉相除法

可能我們求最大公約數的時候多采用“輾轉相除法” ，其實也可以采用遞回的方式去求最大公約數，首先補充輾轉相除法求最大公約數：

代碼執行

#include<stdio.h>

int main()
{
	int m = 24;
	int n = 18;
	int r = m % n;
	while (r != 0)
	{
		r = m % n;
		m = n;
		n = r;
	}

	printf("最大公約數為：%d\n", m);

	return 0;
}

遞回代碼

#include<stdio.h>

int gcd(int m, int n)
{
	if (n == 0)
	{
		return m;
	}
	return gcd(n, m % n);
}

int main()
{
	printf("%d\n",gcd(24,42));
	return 0;
}

所以：當“切蛋糕思維”解決不了問題時，想想有沒有遞回公式，有沒有等價轉換，看看能不能將范圍縮小，這都是需要經過大量訓練才能掌握的規律，加油加油，看完筆者的博文，要把里面的題目全都掌握哦，都是基礎題，之后再去牛客網，力扣里面刷題，聽的再多都不如自己用代碼實作出來！

4、漢諾塔問題

題目描述：漢諾塔問題是一個很經典的問題，有三根柱子，在一根柱子上，從下往上按照大小順序摞著64個圓盤，現需要將圓盤全部擺放到另一根柱子上去，并且規定，任何時候，在小圓盤上面都不能放大圓盤，也就是始終要保證大盤在底下，小盤在上面，

解題思路

將A柱上面的4個圓盤放到C柱上，可以先通過B、C將4個盤子上面的3個移動到B上去，然后將大盤放到C上，最后通過A、B重復操作將那3個盤子放到C上，

代碼執行

public class Recursion {

    //從pos1位置移動到pos2位置
    public static void move(char pos1, char pos2) {
        System.out.print(pos1 + "->" + pos2 + " ");
    }
    //形參分別代表盤子個數、起始位置、中途位置、目的地位置
    public static void hanoi(int n, char pos1, char pos2, char pos3) {
        //終止條件
        if(n == 1) {
            move(pos1, pos3);
            return;
        }
        //先將(n - 1)個盤子通過B、C移動到B上去
        hanoi(n - 1, pos1, pos3, pos2);
        //再將大盤放到C上
        move(pos1,pos3);
        //再將B柱上的盤子通過A、C放到C上
        hanoi(n - 1, pos2,pos1,pos3);
    }
    public static void main(String[] args) {

        hanoi(4,'A','B','C');
    }
}

注意事項：一定不要想著去展開代碼，做遞回題目要學著橫向思考，還是那句話，多做，多練，多敲，這道題目為了讓大家理解怎么拿，怎么放，所以就沒有真正去實作，否則還會用到后面一個模塊的知識，在后面的博文中會做詳細介紹，

二、思考題：放蘋果

題目描述：把m個相同的蘋果放到n個相同的盤子里，允許有的盤子空著不放，問可以有多少種不同的方法？注意：5 1 1 和 1 5 1是同一種分法

由于這道題目對于沒有遇到過的鐵汁們可能有點繞，所以我先將大致思路說一下，注意哦，解開本題的話一定要留意今天主要講的是什么哦，

大致思路：設i個蘋果放在k個盤子里的放法總數是：f(i, k), 則：

1、當k > i時，說明盤子比蘋果要多，必然有盤子是空的（k - i）個，所以將（k - i）個盤子放在一邊不用，剩下的問題就變成了將i個蘋果放到i個盤子里

2、當k <= i時，將放法分為有盤子為空和無盤子為空兩類，所以它的總放法 = 有盤子為空的方法 + 沒盤子為空的放法

好咯，鐵汁們，大致思路就說這么多哦，要嘗試著自己做出來哦，等到該系列的下一篇博文發出，筆者會詳細講解的，

三、藍橋結語：遇見代碼遇見你，不負代碼不負卿

說到這里，藍橋杯演算法競賽系列第二章遞回基礎知識部分結束了，哈哈，沒錯，后面還有的，等到筆者把剩下的幾個基礎演算法的基礎知識部分講完之后，還會附加大量的練習，以及歷年的藍橋真題，遞回這么重要當然跑不掉，正好那個時候順便再復習這里的基礎知識，

說到這里，請鐵汁們，再將遞回這兩篇博文好好看一遍，沖沖沖，

https://blog.csdn.net/weixin_57544072/article/details/120836167?utm_source=app&app_version=4.16.0

又到結尾咯，筆者再次請求鐵汁們如果覺得有所識訓的話，給筆者來個一鍵三連，捧個人場就行了哈，你們的支持就是筆者最大的動力哦，蟹蟹鐵汁們，