T1最大数max(x,y,z)
题目描述：已知: m=max(a,b,c)/(max(a+b,b,c)max(a,b,b+c))
输入a,b,c，求m。把求三个数的最大数max(x,y,z)分别定义成函数和过程来做。
思路：a，b，c定义成double类型的数，用一个double类型的函数判断大小。
代码：
#include<bits/stdc++.h>
using namespace std;
double a,b,c,d;
double maxn(double a,double b,double c){
if(a<b){
swap(a,b);
}
if(a<c){
swap(a,c);
}
return a;
}
int main(){
cin>>a>>b>>c;
d=maxn(a,b,c)/(maxn(a+b,b,c)*maxn(a,b,b+c));
cout<<fixed<<setprecision(3)<<d;
return 0;
}
考察点：考察递归的应用是否正确。
T2斐波那契数列
题目描述：使用递归算法输出斐波那契数列第n(n<=33)项。0，1，1，2，3，5，8，13……。
思路：先判断如果n=0,输出0，如果n=2，输出1，再执行(n-1)+(n-2)的命令。
代码：
#include<bits/stdc++.h>
using namespace std;
int n;
int fie(int n){
if(n==1){
return 0;
}
if(n==2){
return 1;
}
return fie(n-2)+fie(n-1);
}
int main(){
cin>>n;
cout<<fie(n);
return 0;
}
考察点：考察递归的使用。
T3汉诺塔
题目描述：1.有三根杆子A,B,C。A杆上有若干碟子。
2.每次移动一块碟子,小的只能叠在大的上面。
3.把所有碟子从A杆全部移到C杆上。
思路：判断特殊条件，n==1，直接把这个移到c杆上。
代码：
#include<bits/stdc++.h>
using namespace std;
int n;
void hano(int n,char a,char b,char c){
if(n==1){
cout<<a<<" "<<"To"<<" "<<c<<endl;
}else{
hano(n-1,a,c,b);
cout<<a<<" "<<"To"<<" "<<c<<endl;
hano(n-1,b,a,c);
}
}
int main(){
cin>>n;
hano(n,'A','B','C');
return 0;
}
考察点：考察递归的应用。
T4小木块
题目描述：
判断有多少个小木块。输入n，代表层数。
思路：ans代表所有木块的和，sum代表一层木块的和。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,ans;
void s(int n){
int sum=0;
for(int i=1;i<=n;i++){
sum+=i;
ans+=sum;
}
cout<<ans;
}
int main(){
cin>>n;
s(n);
return 0;
}
考察点：累加求和的理解和对函数的调用。
T5递归实现指数型枚举
题目描述：从 1∼n 这 n个整数中随机选取任意多个，输出所有可能的选择方案。
思路：用vector定义一个动态数组，ans代表最终结果，每一次递归后记录选项后还原现场。
代码：
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int>ans;
void dfs(int u){
if(u==n+1){
for(int i=0;i<ans.size();i++){
cout<<ans[i]<<" ";
}
cout<<endl;
return;
}
dfs(u+1);
ans.push_back(u);
dfs(u+1);
ans.pop_back();
}
int main(){
cin>>n;
dfs(1);
return 0;
}
考察点：考察深度优先搜索算法的使用，动态数组的使用。
T6递归实现组合型枚举
题目描述：从 1∼n这 n个整数中随机选出m个，输出所有可能的选择方案。
思路：从n个整数里选出m个数，判断ans的长度>m或者ans的长度加n-u-i的长度大于m的话，输出ans，停止运行，否则进行保存元素，还原现场的操作。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int>ans;
void dfs(int u){
if(ans.size()>m||ans.size()+(n-u+1)<m){
return;
}
if(u==n+1){
for(int i=0;i<ans.size();i++){
cout<<ans[i]<<" ";
}
cout<<endl;
return;
}
ans.push_back(u);
dfs(u+1);
ans.pop_back();
dfs(u+1);
}
int main(){
cin>>n>>m;
dfs(1);
return 0;
}
考察点：考察深度优先搜索的使用。
T7递归实现排列型枚举
题目描述：把 1∼n 这 n个整数排成一行后随机打乱顺序，输出所有可能的次序。
思路：用深搜寻找1-n的所有排序可能，bool类型数组vis用来标记被选择的整数。
代码：
#include<bits/stdc++.h>
using namespace std;
int m;
bool vis[15];
vector<int>ans;
void dfs(int u){
if(u==m+1){
for(int i=0;i<ans.size();i++){
cout<<ans[i]<<" ";
}
cout<<endl;
return;
}
for(int i=1;i<=m;i++){
if(!vis[i]){
ans.push_back(i);
vis[i]=1;
dfs(u+1);
ans.pop_back();
vis[i]=0;
}
}
}
int main(){
cin>>m;
dfs(1);
return 0;
}
考察点：考察深搜的使用。
T8数池塘
题目描述：农夫约翰的农场可以表示成N*M（1≤N≤100≤M≤100）个方格组成的矩形。由于近日的降雨，在约翰农场上的不同地方形成了池塘。每一个方格或者有积水（'W'）或者没有积水（'.'）。农夫约翰打算数出他的农场上共形成了多少池塘。一个池塘是一系列相连的有积水的方格，每一个方格周围的四个方格都被认为是与这个方格相连的。现给出约翰农场的图样，要求输出农场上的池塘数。
思路：用深搜来判断鱼塘的个数，用dx，dy来代表上下左右四个方位，x,y定义为nx，ny，cnt累加求和。
代码：
#include<bits/stdc++.h>
using namespace std;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0},n,m,sum;
char a[101][101];
void dfs(int x,int y){
a[x][y]='.';
for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(nx<=n&&ny<=m&&a[nx][ny]=='W'){
dfs(nx,ny);
}
}
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>a[i][j];
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(a[i][j]=='W'){
dfs(i,j);
sum++;
}
}
}
cout<<sum;
return 0;
}
考察点：考察深搜的使用，上下左右四个方向的判断。
深度优先搜索模板
1.回溯算法模板
void dfs(int u) // u指的是填数的第几个位置或者递归层数
{
if (所有空填完了)
{
记录答案/输出答案/更新最优答案;
return;
}
for (枚举当前位置能填的选项)
{
if (判断当前选项是否合法)
{
记录下这个选项（保存答案）
dfs(u+1); // 递归填下一个位置
取消这个选项，还原现场
}
}
}
2.连通块问题模板
int dx[] = {0,1,0,-1}, dy[] = {1,0,-1,0}; // 4个方向
void dfs(int x, int y) // x，y搜索的起点坐标
{
// 枚举4个方向
for (int i = 0; i < 4; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (check(nx, ny)) // 检查是否满足继续搜索的条件
{
// 记录答案 ans
// 添加标记 vis[nx][ny] = true;
dfs(nx, ny); // 继续搜索
}
}
}
