总结

递归：

回溯算法模板：

// dfs 回溯算法模板
void dfs(int u) // u指的是填数的第几个位置或者递归层
{  
    if (所有空填完了)
    {
    记录答案/输出答案/更新最优答案;
    return;
    }
    for (枚举当前位置能填的选项)
    {
        if (判断当前选项是否合法)
        {
        记录下这个选项（保存答案）
        dfs(u+1);   // 递归填下一个位置
        取消这个选项，还原现场
        }
    }
}

连通块问题模板

// 连通性问题搜索模板
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); // 继续搜索 
		}
	}
}

T1 最大数max(x,y,z)

题目描述

已知: 𝑚=𝑚𝑎𝑥(𝑎,𝑏,𝑐)÷[𝑚𝑎𝑥(𝑎+𝑏,𝑏,𝑐)×𝑚𝑎𝑥(𝑎,𝑏,𝑏+𝑐)]

输入𝑎,𝑏,𝑐a,b,c，求𝑚m。把求三个数的最大数𝑚𝑎𝑥(𝑥,𝑦,𝑧)max(x,y,z)分别定义成函数和过程来做。

声明一个int类型的函数，返回值为𝑚𝑎𝑥(𝑎,𝑏,𝑐)÷[𝑚𝑎𝑥(𝑎+𝑏,𝑏,𝑐)×𝑚𝑎𝑥(𝑎,𝑏,𝑏+𝑐)]

#include<bits/stdc++.h>
using namespace std;
double m(double x,double y,double z)
{
	return max(max(x,y),z)/(max(max(x,x+y),z)*max(max(x,y),y+z));
}
int main()
{
	double a,b,c;
	cin>>a>>b>>c;
	printf("%.3lf",m(a,b,c));
return 0;
}

T2 斐波那契数列 （简单版）

使用递归算法输出斐波那契数列第n(n<=33)项。0，1，1，2，3，5，8，13……

之所以叫简单版是因为这题的数据范围很小(n<=33)。

声明一个递归函数，1为0，2为1。根据递推公式可以得知，n=n-1+n-2。

#include<bits/stdc++.h>
using namespace std;
int rabbit(int x)
{
	if(x==1)
	{
		return 0;
	}
	if(x==2)
	{
		return 1;
	}
	return rabbit(x-1)+rabbit(x-2);
}
int main()
{
	int n;
	cin>>n;
	cout<<rabbit(n);
return 0;
}

T3 汉诺塔

1.有三根杆子A,B,C。A杆上有若干碟子

2.每次移动一块碟子,小的只能叠在大的上面

3.把所有碟子从A杆全部移到C杆上

经过研究发现，汉诺塔的破解很简单，就是按照移动规则向一个方向移动金片：

如3阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C此外，汉诺塔问题也是程序设计中的经典递归问题。

算法思路：

1.如果只有一个金片，则把该金片从源移动到目标棒，结束。

2.如果有n个金片，则把前n-1个金片移动到辅助的棒，然后把自己移动到目标棒，最后再把前n-1个移动到目标棒.

这题题目里面已经说了：算法思路是什么，那么我们可以直接根据思路写出递归函数。

#include<bits/stdc++.h>
using namespace std;
void hnt(int n,char a,char b,char c)
{
	if(n==1)
	{
		cout<<a<<' '<<"To"<<' '<<c<<endl;
	}
	else
	{
		hnt(n-1,a,c,b);
		cout<<a<<' '<<"To"<<' '<<c<<endl;
		hnt(n-1,b,a,c);
	}
	
}
int main()
{
	int n;
	cin>>n;
	hnt(n,'A','B','C');
return 0;
}

T4 数数小木块

根据上图我们可以得知递归公式：

1：1=1

2：3=1+2

3：6=3+3

. . .

4：n=f(n-1)+n

那么我们可以直接写题了。

#include<bits/stdc++.h>
using namespace std;
int ans[110]={0,1};
int m(int x)
{
	if(x==1)
	{
		return ans[x];
	}
	return ans[x]=m(x-1)+x;
}
int main()
{
	int n,s=0;
	cin>>n;
	m(n);
	for(int i=1;i<=n;i++)
	{
		s=s+ans[i];
	}
	cout<<s;
return 0;
}

T5 递归实现指数型枚举

枚举：第一位输出1的有几种，第二位输出2还是3，第三位又输出几. . . 以此类推

#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> chosen;
void dfs(int x)
{
	if(x==n+1)
	{
		for(int i=0;i<chosen.size();i++)
		{
			cout<<chosen[i]<<' ';
		}
		cout<<endl;
		return;
	}
	dfs(x+1);
	chosen.push_back(x);
	dfs(x+1);
	chosen.pop_back();
}
int main()
{
	cin>>n;
	dfs(1);
return 0;
}

T6 递归实现组合型枚举

这题是一道排列题 1在第一位的话第二位有几种，第三位呢？

#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> chosen;
void dfs(int x)
{
	if(chosen.size()>m||chosen.size()+(n-x+1)<m)
	{
		return;
	}
	if(x==n+1)
	{
		for(int i=0;i<chosen.size();i++)
		{
			cout<<chosen[i]<<' ';
		}
		cout<<endl;
		return;
	}
	chosen.push_back(x);
	dfs(x+1);
	chosen.pop_back();
	dfs(x+1);
}
int main()
{
	cin>>n>>m;
	dfs(1);
return 0;
}

T7 数池塘

这题用dfs深度搜索来找，如果是'W'那么判断上下左右有没有'W'。那么数++，如果不是变成'.'，直到上下左右全是'.'，数++。

#include<bits/stdc++.h>
using namespace std;
char s[110][110];
int n,m,cut=0;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
void dfs(int x,int y)
{
	s[x][y]='.';
	for(int i=0;i<4;i++)
	{
		int nx=x+dx[i];
		int ny=y+dy[i];
		if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&s[nx][ny]=='W')
		{
			dfs(nx,ny);
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>s[i][j];
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(s[i][j]=='W')
			{
				cut++;
				dfs(i,j);
			}
		}
	}
	cout<<cut;
return 0;
}