【藍橋杯速成】| 4.遞歸

遞歸

?題目一：最大公約數

問題描述

1979. 找出數組的最大公約數 - 力扣（LeetCode）

給你一個整數數組?nums?，返回數組中最大數和最小數的?最大公約數?。

兩個數的?最大公約數?是能夠被兩個數整除的最大正整數。

解題步驟

需要返回數組中最大最小值的最大公約數

那么首先需要求出最大最小值

可以使用for循環遍歷得到

int minnum=INT_MAX,maxnum=INT_MIN;
for(int i=0;i<nums.size();i++){if(nums[i]<minnum){minnum=nums[i];}if(nums[i]>maxnum){maxnum=nums[i];}
}

當然也可以使用

求最大值和最小值的函數

最大值：std::max_element
最小值：std::min_element

這些函數返回的是指向最大值或最小值的迭代器，因此需要通過解引用操作符?*?來獲取具體的值。

int maxnum=*max_element(nums.begin(),nums.end());
int minnum=*min_element(nums.begin(),nums.end());

?接下來就是求最大公約數

根據數學知識，我們可以使用輾轉相除法

?那么很明顯這是個遞歸過程，每次要求的是較大值除以較小值的余數，

終止條件就是余數為零，代表整除

所以求最大公倍數的函數應該是

int GCD(int maxnum,int minnum){if(maxnum%minnum == 0)return minnum;else return GCD(minnum,maxnum%minnum);
}

?最后只需要在主函數中調用即可，完整代碼在下面！

補充說明：C++的標準庫中有計算兩個整數最大公約數的函數，就叫gcd，可以直接調用，但此處想強調的是最基礎的遞歸邏輯，故手動實現了一把！

code

class Solution {
public:int GCD(int maxnum,int minnum){if(maxnum%minnum == 0)return minnum;else return GCD(minnum,maxnum%minnum);}int findGCD(vector<int>& nums) {// int minnum=INT_MAX,maxnum=INT_MIN;// for(int i=0;i<nums.size();i++){//     if(nums[i]<minnum){//         minnum=nums[i];//     }//     if(nums[i]>maxnum){//         maxnum=nums[i];//     }// }int maxnum=*max_element(nums.begin(),nums.end());int minnum=*min_element(nums.begin(),nums.end());return GCD(maxnum,minnum);}
};

題目二：FJ的字符串

問題描述

FJ在沙盤上寫了這樣一些字符串：
　　A1 = “A”
　　A2 = “ABA”
　　A3 = “ABACABA”
　　A4 = “ABACABADABACABA”
　　… …
　　你能找出其中的規律并寫所有的數列AN嗎？

輸入格式

僅有一個數：N ≤ 26。

輸出格式

請輸出相應的字符串AN，以一個換行符結束。輸出中不得含有多余的空格或換行、回車符。

樣例輸入

樣例輸出

ABACABA

解題步驟

觀察這些字符串，不難發現

　　A1 = “A”
　　A2 = “ABA”
　　A3 = “ABACABA”
　　A4 = “ABACABADABACABA”

整體規律就是：AN=A(N-1)+第N號字母+A(N-1)

那么也可以用遞歸方法實現

直接利用找到的規律寫出代碼即可，注意字符轉化

code

#include<bits/stdc++.h>
using namespace std;
string FJ(int N){if(N==1){return "A";}else{return FJ(N-1)+(char)('A'+N-1)+FJ(N-1);}
}
int main(){int N;cin>>N;cout<<FJ(N);return 0;
}

題目三：遞歸實現指數型枚舉

問題描述

從?1~n?這?n?個整數中隨機選取任意多個，輸出所有可能的選擇方案。

輸入格式

????????輸入一個整數n。

輸出格式

????????每行輸出一種方案。同一行內的數必須升序排列，相鄰兩個數用恰好1個空格隔開。對于沒有選任何數的方案，輸出空行。各行（不同方案）之間的順序任意。

數據范圍

????????1 ≤ n ≤ 15

示例

????????輸入：3

????????輸出：1，12，13，123，2，23，3

????????輸入：4

????????輸出：1，12，13，14, 123，134, 1234, 2，23，24, 234, 3, 34, 4

解題步驟

觀察題目和示例，可以看到這個n既是輸出的最大長度，也是所取數字的最大值

組合成的每一個數字實際上有重復關系，使用遞歸法

觀察輸出，實際上是對1~n中每個數字的選與不選

即取n時與取n-1時的區別在于增加了n這個數字所組成的組合（單層遞歸）

	dfs(index+1,n,current);//不選擇該數字 ，即n-1產生的所有答案current.push_back(index);//index加入該數字 dfs(index+1,n,current);//生成新的組合

規定同一行的數必須升序排列，那么第一個元素的大小還決定了該行答案出現數字的下界，并且第一個元素是從1，2，3，，，n

那么遞歸的終止條件為

	if(index>n){for(int i=0;i<current.size();i++){cout<<current[i]<<" ";}cout<<endl;return;}

?dfs具備以上兩個主要部分后，只剩下確定參數啦

n作為上界是必須一直使用的，index作為下界需要在傳遞過程中改變，答案數組current也需要傳遞使用

那么整個函數的定義為void dfs(int index,int n,vector<int> current){

在主函數中完善輸入，調用函數即可實現該題

code

#include<bits/stdc++.h>
using namespace std;
void dfs(int index,int n,vector<int> current){if(index>n){for(int i=0;i<current.size();i++){cout<<current[i]<<" ";}cout<<endl;return;}dfs(index+1,n,current);//不選擇該數字 current.push_back(index);//index加入該數字 dfs(index+1,n,current);//生成新的組合 
}int main(){int n;cin>>n;vector<int> current;dfs(1,n,current);return 0;
}

題目四：遞歸實現排列型枚舉

問題描述

1-n個這 n 個整數拍成一排并打亂次序，輸出所有可以選擇的方案。

示例

????????輸入：3

????????輸出：

????????123

? ? ? ? 132

????????213

????????231

????????312

????????321

解題步驟

這個題目如果直接用筆算的話，可以看成是三個格子的填空游戲

從1開始作為第一位，再從余下的數字選擇填入，是全排列

利用遞歸解決還是需要3步走

確定終止條件

如果第一位大于n那么結束，并輸出該序列

    if(i>n){for(int j=1;j<=n;j++){cout<<s[j]<<" ";}cout<<endl;return;}

按順序給1，2，3，4，，，n這n個數字一個當老大的機會，并逐步確定后面的小弟隊伍

注意記錄每一位小弟的排隊情況（即有無使用過）

排進去后進行下一位，

遞歸完畢后會開啟新一輪，需要恢復當前值和當前結果數組的使用情況（下一輪重新開始還得用呢！）

    for(int j=1;j<=n;j++){if(!used[j]){//該數字沒有被使用過 s[i]=j;//記錄該數字 used[j]=true;//更新記錄情況dfs(i+1);//進行下一輪 used[j]=false;//回溯 s[i]=0;//清空 }}

?那么這個dfs的參數就比較簡單了，只需要傳入n即可void dfs(int i)

code

#include<iostream>
using namespace std;const int N=10;
int n;
bool used[N];//記錄數字是否用過 
int s[N];//保存方案 
void dfs(int i){if(i>n){for(int j=1;j<=n;j++){cout<<s[j]<<" ";}cout<<endl;return;}for(int j=1;j<=n;j++){if(!used[j]){//該數字沒有被使用過 s[i]=j;//記錄該數字 used[j]=true;//更新記錄情況dfs(i+1);//進行下一輪 used[j]=false;//回溯 s[i]=0;//清空 }}
}
int main(){cin>>n;dfs(1);return 0;
}

題目五：遞歸實現組合型枚舉

問題描述

1-n個數字中隨機選取?m?個，每種方案按照里的數字按照從小到大的順序排列，按照字典序輸出。

示例

????????輸入：5 3

????????輸出：

????????123

????????124

????????125

????????134......

????????345

解題步驟

這題不一樣之處在于它多了個m，由兩個值決定取值范圍，取值個數

思路還是一樣的

先寫出終止條件，如果當前數大于最大取值個數m，輸出當前序列

	if(now>m){for(int i=1;i<=m;i++){cout<<s[i]<<" ";}cout<<endl;return;}

?單層遞歸呢就是，從當前遍歷到的數字一直到n中，遍歷選擇，存入s中，再取下一位

	for(int i=start;i<=n;i++){//可用范圍內隨意挑選 s[now]=i;dfs(now+1,i+1);s[now]=0;}

?那么函數的參數需要當前值和開始值void dfs(int now,int start)

除此以外該函數可以再加一個剪枝操作，不做無用功

if(now+n-start<m)?? ?return;//不夠用

同樣在主函數中進行輸入和傳參調用即可

code

#include<iostream>
using namespace std;
const int N=35;
int n,m;
int s[N];
void dfs(int now,int start){if(now+n-start<m)	return;//不夠用if(now>m){for(int i=1;i<=m;i++){cout<<s[i]<<" ";}cout<<endl;return;} for(int i=start;i<=n;i++){//可用范圍內隨意挑選 s[now]=i;dfs(now+1,i+1);s[now]=0;}
}
int main(){cin>>n>>m;dfs(1,1);return 0;
}