DFS—深度优先搜索

这篇具有很好参考价值的文章主要介绍了DFS—深度优先搜索。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

递归函数代码形式

函数类型 函数名(形式参数):
	if(边界条件)
		边界处理
	else
		递推算法

1、斐波那契数列:

1 1 2 3 5 8 13 21 34 55 89 ...
已知前两项为1,之后每一项等于前两项之和。
现输入n,请输出兔子数列的第n项。

#include<bits/stdc++.h>
using namespace std;
int f(int n){
	if(n==1 || n==2)
		return 1;
	else	//else可省略,为什么? 
		return f(n-1)+f(n-2);
}
int main(){
	int n;
	cin>>n;
	cout<<f(n);
	return 0;
}

2、用递归法求n!的值。

F ( n ) = { 1 ( n = 0 ) n ∗ F ( n − 1 ) ( n > 0 ) F(n)=\begin{cases}1(n=0)\\n*F(n-1)(n>0)\end{cases} F(n)={1n=0nF(n1)n>0

不难分析出上题的递推式为 f a c ( n ) = f a c ( n − 1 ) ∗ n fac(n)=fac(n-1)*n fac(n)=fac(n1)n,边界条件为 f a c ( 0 ) = 1 fac(0)=1 fac(0)=1
求解过程如下:

f a c ( 4 ) = 4 ∗ f a c ( 3 ) = 4 ∗ ( 3 ∗ f a c ( 2 ) ) = 4 ∗ ( 3 ∗ ( 2 ∗ f a c ( 1 ) ) ) = 4 ∗ ( 3 ∗ ( 2 ∗ ( 1 ∗ f a c ( 0 ) ) ) ) = 4 ∗ ( 3 ∗ ( 2 ∗ ( 1 ∗ 1 ) ) ) fac(4)\\ =4*fac(3)\\ =4*(3*fac(2))\\ =4*(3*(2*fac(1)))\\ =4*(3*(2*(1*fac(0))))\\ =4*(3*(2*(1*1))) fac(4)=4fac(3)=4(3fac(2))=4(3(2fac(1)))=4(3(2(1fac(0))))=4(3(2(11)))

题解:

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

3、用递归法求f(n)=1+2+3+…+n的值。

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

4、输入两个数,求其最大公约数。

根据上文中所讲的辗转相除法可得公式如下:
g c d ( a , b ) = { ( a % b = 0 ) g c d ( b , a % b ) ( a % b ≠ 0 ) gcd(a,b)=\begin {cases}(a\%b=0)\\gcd(b,a\%b)(a\%b\neq 0)\end{cases} gcd(a,b)={(a%b=0)gcd(b,a%b)a%b=0

#include<bits/stdc++.h>
using namespace std;
int f(int n,int m){
	if(n%m==0)
		return m;
	else
		return f(m,n%m);//该处return去除亦可正常运行,为什么? 
}
int main(){
	int n,m;
	cin>>n>>m;
	cout<<f(n,m);
	return 0;
}

5、跳台阶

花果山上有一洞,小猴每次采取跳1阶或者跳3阶的办法从山下跳跃上台阶进洞,编程输入台阶数,输出有多少种不同的跳法。

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

6、输出全排列

给定N(N<10),按照字典序输出所有的N排列
输入样例:
3
输出样例:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

可以采用1~n循环填每一个空的思路来做,也符合题意的按字典序填数,每填好一个数后继续递归填下一个数

#include<bits/stdc++.h>
using namespace std;
const int N=15;
int n,a[N];

void f(int x){//函数f(x)定义:确定函数的第x个数
	if(x==n+1){
		for(int i=1;i<=n;i++)
			cout<<a[i]<<' ';
		cout<<endl;
		return;
	} else{
		for(int i=1;i<=n;i++){ //枚举第x个数的值 
			bool ok=true;
			for(int j=1;j<x;j++)//判断i是否在前x-1个数中出现过
				if(a[j]==i){ok=false;break;}
			if(ok){
				a[x]=i;
				f(x+1);
				a[x]=0;//执行完f(x+1)后会退回该处,恢复现场,亦可不写,因为新的赋值会把原值覆盖掉 
			}
		}
	}
}

int main(){
	cin>>n;
	f(1);
	return 0;
}

上述代码中“判断i是否在前x-1个数中出现过”使用了枚举法,导致代码效率不高,我们可以采用 used[] 数组来进行优化,i 被使用过则将 used[i] 记为true,否则为false

#include<bits/stdc++.h>
using namespace std;
const int N=15;
int n,a[N];
bool used[N]; 
void f(int x){//函数f(x)定义:确定函数的第x个数
	if(x==n+1){
		for(int i=1;i<=n;i++)
			cout<<a[i]<<' ';
		cout<<endl;
		return;
	} else{
		for(int i=1;i<=n;i++){ //枚举第x个数的值 
			if(!used[i]){
				a[x]=i;
				used[i]=true;
				f(x+1);
				used[i]=false;//执行完f(x+1)后会退回该处,恢复现场,必须得写, 
				a[x]=0;//可写可不写,递归经常会出现类似的对称型代码 
			}
		}
	}
	
}
int main(){
	cin>>n;
	f(1);
	return 0;
}

全排列是一种常见的组合算法,也经常通过不断交换数组中的元素的方式来生成全排列。在每一次递归中,我们将第一个元素与后面的元素进行交换,然后递归生成后面的排列,最后再恢复交换的元素。通过这种方式,我们可以生成所有可能的排列(非字典序)。

#include<bits/stdc++.h>
using namespace std;
int a[15];

// 交换两个元素的值
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 递归生成全排列
void f(int *a, int start, int end) {
    if (start == end) {
        // 打印当前排列
        for (int i=1;i<=end;i++) {
            cout<<a[i]<<' ';
        }
        cout<<endl;
    } else {
        for (int i=start;i<=end;i++) {
            // 交换第一个元素与后面的元素
            swap(&a[start], &a[i]);
            // 递归生成后面的排列
            f(a,start+1,end);
            // 恢复交换的元素
            swap(&a[start], &a[i]);
        }
    }
}

int main() {
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		a[i]=i;
	}
    f(a,1,n);
    return 0;
}

7、汉诺塔

Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时,这n个圆盘由大到小依次套在a柱上,如图所示。 

要求把a柱上n个圆盘按下述规则移到c柱上: 
  (1)一次只能移一个圆盘; 
  (2)圆盘只能在三个柱上存放; 
  (3)在移动过程中,不允许大盘压小盘。 
问将这n个盘子从a柱移动到c柱上,总计需要移动多少个盘次? 

【问题解答】

解:设Hn为n个盘子从a柱移到c柱所需移动的盘次。

    显然,当n=1时,只需把a 柱上的盘子直接移动到c柱就可以了,故:H1=1。

    当n=2时,先将a柱上面的小盘子移动到b柱上去,然后将大盘子从a柱移到c柱,最后,将b柱上的小盘子移到c柱上,共记3个盘次,故:H2=3。

    以此类推,当a柱上有n(n>=2)个盘子时,总是先借助c柱把上面的n-1个盘子移动到b柱上,然后把a柱最下面的盘子移动到c柱上,再借助a柱把b柱上的n-1个盘子移动到c柱上,总共移动H(n-1)+1+H(n-1)个盘次。 

    ∴Hn=2H(n-1)+1,边界条件:H1=1

【递归实现】

#include<stdio.h>
void move(int n, char x, char y, char z)//将n个圆盘从x柱子上借助y柱子移动到z柱子上
{
     if(n == 1)
     	printf("圆盘编号 %d :从 %c 移动到 %c\n",n,x,z);
     else
     {
         move(n-1,x,z,y);
         printf("圆盘编号 %d:从 %c 移动到 %c\n",n,x,z);
         move(n-1,y,x,z);
      }
 }
int main()
{
    int n;//n代表圆盘的个数
    /*A,B,C分别代表三个柱子*/
    char ch1 = 'A';
    char ch2 = 'B';
    char ch3 = 'C';
 
     printf("请输入圆盘的个数:");
     scanf("%d",&n);
     move(n,ch1,ch2,ch3);
     return 0;
}

【递推实现】

#include<stdio.h>
int ct=1;//记录步数,在步骤中输出
void move(int n,char from,char to)
{
    printf("第 %2d 步:把第 %d 个盘子:  %c >>>>>>> %c\n",ct++,n,from,to);
}
int hanoi(int n)//输出步数:
{
    int cnt = 2,ans = 1;
    if(n == 1)
        return 1;
    else
        return 2* hanoi(n-1) +1;
}
void hanoi_tower(int n,char x,char y, char z) //输出步骤
{
    if(n==1)
        move(1,x,z);
    else{
        hanoi_tower(n-1,x,z,y);
        move(n,x,z);
        hanoi_tower(n-1,y,x,z);
    }
}
int main()
{
    int n;//盘子个数
    printf("输入盘子个数:\n");
    scanf("%d",&n);
    char x = 'A',y = 'B',z = 'C';
    int t = hanoi(n);
    printf("一共需要%2d步。\n",t);
    hanoi_tower(n,x,y,z);
    return 0;
}

8、n皇后问题

在N*N(N<=10)的棋盘上放置N个皇后,使得他们不能相互攻击。两个皇后能相互攻击当且仅当他们在同一行,或者同一列,或者同一对角线上。

【题解】来源:WBN

DFS基本格式:

#include<iostream>
using namespace std;
void dfs(int x){//层数
    if(达到目的) 输出(或者方案数+1else{
    	for(遍历所有的算符){
    		if(没有用到){
    			标记
    			dfs(k+1)//下一层递归
    			回溯
    		}
    	}
    }
}

在这道题目中,“层数”可以等于“行”,即第x层递归可以等价于第x行,那么只需要检验对角线以及列数。又因为行数已经可以忽略不考虑(一定符合条件),我们可以用一维数组(p[11])存放皇后.

1.检验列,只需判断p[j]是否与已经放入的“皇后”位置不同,即p[j]!=i;
2.检验对角线,只需要判断“皇后”的行列之差(的绝对值)是否相等

#include<bits/stdc++.h>
using namespace std;
int n,ans,p[11];//一维数组p用来记录列 
 
void Nqueen(int x){ 
	if(x==n+1){//边界条件 即此时已经找完 计算方案数 
		ans++;
		return;//返回函数 
	}
	else{
		for(int i=1;i<=n;i++){
			bool ok=true;
			for(int j=1;j<x;j++){//检查第x列之前 
				if((p[j]==i)||(abs(x-j)==abs(i-p[j]))){//第一部分判断皇后是否在同一列 第二部分判断是否在同一对角线 
					ok =false;
					break;
				}
			}
			if(ok){
				p[x]=i;//放入 
				Nqueen(x+1);//下一列 
				p[x]=0;
			}
		}
	}
}
 
int main(){
	cin>>n;
	Nqueen(1);//从第一行找起 
	cout<<ans;
	
	return 0;
}

9、确定进制

6*9=42对于十进制来说是错误的,但是对于13进制来说是正确的,即6(13)*9(13)=42(13)
现读入三个整数p q r,然后确定一个进制,使得 p *q =r
输入样例:
6 9 42
输出样例:
13

10、最大连续子序列和

给定一个长度为n的序列,求该序列的最大连续子序列和。(n<=100000,|元素值|<=1000)
输入样例:
10
2 5 -3 4 -9 -2 6 1 -8 7
输出样例:
8

【题解】来源:PJD
1.暴力搜索,没什么好说的,纯写了玩

#include<bits/stdc++.h>
using namespace std;
 
int main()
{
	int n,max,op,l=0;
	cin>>n;
	int a[n+1];
	for(int i=1;i<=n;i++)
	cin>>a[i];
	max=a[1];
	for(int i=1;i<=n;i++)
	{
		for(int j=n;j>=i;j--)
		{
			for(int o=i;o<=j;o++)
			{
				op+=a[o];
			}
			if(op>max)
			{
				max=op;
			}
		}
	}
	cout<<max;
	return 0;
}

2.DP

我们以洛谷里的测试样例为例

2 -4 3 -1 2 -4 3
第一个数:2

前两个数最大子段和:显然2-4<2 所以为2

前三:各个子段和分别为1,-1,3(注意,这里的子段是指包含第3个数的子段)

最大为3

在前三个的情况时,我们可以发现,因为前两个数的和为负数,加上第三个数反而没有第三个数大

所以可以很清楚发现状态转移方程为发f(n)=max(f(n-1)+h(n),h(n)) (f(n)指的是第1到n中所有包含第n个数的子段中的最大值,h(n)指的是第n个数的值。

综上,我们可以用简单的DP找出第1到n中所有包含第n个数的子段中的最大值

但很明显,不包括第n个数的子段中可能有字段和更大的情况,例如:

1 2 3 4 -1000 1

如果直接求出f(6),结果为1,但很明显,答案应该是1+2+3+4=10

所以我们可以存储f(1)到f(n),找其中的最值即可

以下是两种编码方式

:第一种,制表递推

#include<bits/stdc++.h>
using namespace std;
 
int o[200005],p[200005];//o存数列,p为表 
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) 
	cin>>o[i];
	int op=o[1];//op来存最大值,自底向上制表递推
	for(int i=1;i<=n;i++)
	{
		p[i]=max(p[i-1]+o[i],o[i]);
	} 
	for(int i=1;i<=n;i++)
	{
		op=max(op,p[i]);
	} 
	cout<<op;
	return 0;
}

可以发现制表,找最值的过程可以合在一个循环里

#include<bits/stdc++.h>
using namespace std;
 
int o[200005],p[200005];//o存数列,p为表 
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) 
	cin>>o[i];
	int op=o[1];//op来存最大值,自底向上制表递推
	for(int i=1;i<=n;i++)
	{
		p[i]=max(p[i-1]+o[i],o[i]);
		op=max(op,p[i]);
	}
	cout<<op;
	return 0;
}

DP第二种,自顶向下递归。其实就是把递推式里东西换了个位置。

#include<bits/stdc++.h>
using namespace std;
 
int o[200005],p[200005],op;//o存数列,p记忆化 
int ys(int bh)
{
	if(bh==1)
	return o[1];
	else
	return max(ys(bh-1)+o[bh],o[bh]);
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) 
	cin>>o[i];
	op=o[1];//op来存最大值
	for(int i=1;i<=n;i++)
	{
		p[i]=ys(i);
		op=max(op,p[i]);
	}
	cout<<op;
	return 0;
}

11、最大子矩阵

已知矩阵的大小等于矩阵中所有元素的和,给定一个nn(n<=300)的矩阵,找到该矩阵的最大非空子矩阵(大小至少为11)。
输入样例:
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
输出样例:
15

【题解】

#include <bits/stdc++.h>
using namespace std;

int n, a[305][305], answer, sum[305][305];

pair<int, int> vis[305][305];

void dfs(const int x, const int y, int s, int px, int py){
	if(px > n || py > n || vis[px][py] == make_pair(x, y)) return;
	vis[px][py] = make_pair(x, y);
	sum[px][py] = s;
	int w = 0;
	for(int t = x; t <= px; t++){
		s += a[t][py + 1];
		w += a[t][py + 1];
	}
	dfs(x, y, s, px, py + 1);
	s -= w;
	w = 0;
	for(int t = y; t <= py; t++){
		s += a[px + 1][t];
		w += a[px + 1][t];
	}
	dfs(x, y, s, px + 1, py);
	s -= w;
	answer = max(s, answer);
}

void dfs2(const int x, const int y, int s, int px, int py){
	if(px > n || py > n || vis[px][py] == make_pair(x, y)) return;
	vis[px][py] = make_pair(x, y);
	dfs2(x, y, sum[px][py + 1] + sum[x - 1][y - 1] - sum[x - 1][py + 1] - sum[px][y - 1], px, py + 1);
	dfs2(x, y, sum[px + 1][py] + sum[x - 1][y - 1] - sum[x - 1][py] - sum[px + 1][y - 1], px + 1, py);
	answer = max(s, answer);
}

int main(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			cin >> a[i][j];
		}
	}
	dfs(1, 1, a[1][1], 1, 1);
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			if(i == 1 && j == 1) continue;
			dfs2(i, j, a[i][j], i, j);
		}
	}
	cout << answer << "\n";
	return 0;
}
/*
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
*/

12、素数环

从1~20一共20个数摆成一个环,要求相邻两个数的和是一个素数。输出一个合法答案。
无输入
输出样例:
一行,20个数,表示一个合法解。

【题解】来源:PWT文章来源地址https://www.toymoban.com/news/detail-831230.html

#include<bits/stdc++.h>//素数环 
using namespace std;
int a[25];
bool f[25];
void print(){//输出函数 
	for(int i=1;i<=20;i++){
		cout<<a[i]<<" ";
	}
	cout<<endl;
}
bool zs(int x){//判断质数 
	if(x==1)return 0;
	for(int i=2;i<=sqrt(x);i++){
		if(x%i==0)return 0;
	}
	return 1; 
}
void dfs(int k){//k是第 k个数字 
	for(int i=1;i<=20;i++){
		if(f[i]==0&&(k==1||zs(i+a[k-1]))){//判断数是否已被占用,如果是第一个数不需要判断和为素数 
			a[k]=i;f[i]=1;//标记数被占用 
			if(k==20&&zs(a[k]+a[1]))print();//20个数已满且首尾相加为素数输出 
			else dfs(k+1);
			f[i]=0;
		}
	}
} 
int main(){
	dfs(1);
    return 0;
}

到了这里,关于DFS—深度优先搜索的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 第一周算法训练(dfs)(深度优先搜索算法)

    dfs: 深度优先搜索算法 ,是一种用于遍历或 搜索树或图的算法 .沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被

    2024年02月20日
    浏览(51)
  • Python 算法基础篇:深度优先搜索( DFS )和广度优先搜索( BFS )

    深度优先搜索( DFS )和广度优先搜索( BFS )是两种常用的图遍历算法,用于在图中搜索目标节点或遍历图的所有节点。本篇博客将介绍 DFS 和 BFS 算法的基本概念,并通过实例代码演示它们的应用。 😃😄 ❤️ ❤️ ❤️ 深度优先搜索( DFS )是一种用于遍历或搜索图或树

    2024年02月07日
    浏览(67)
  • 深度优先搜索(DFS)和广度优先搜索(BFS)两种算法c++

    深度优先搜索(DFS)和广度优先搜索(BFS)是一种用于遍历或搜索树图的一种算法,在这个过程中保证图或数的每个结点被访问且仅被访问一次,再按照每个结点访问的顺序不同分为深搜和广搜。 本文只讨论这两种算法在搜索方面的应用! 深度优先搜索 ( Depth-First-Search,DFS )它 沿

    2024年02月13日
    浏览(51)
  • 图的遍历(搜索)算法(深度优先算法DFS和广度优先算法BFS)

    从图的某个顶点出发访问遍图中所有顶点,且每个顶点仅被访问一次。(连通图与非连通图) 1、访问指定的起始顶点; 2、若当前访问的顶点的邻接顶点有未被访问的,则任选一个访问之;反之,退回到最近访问过的顶点;直到与起始顶点相通的全部顶点都访问完毕; 3、若

    2024年01月17日
    浏览(49)
  • 【数据结构与算法】搜索算法(深度优先搜索 DFS和广度优先搜索 BFS)以及典型算法例题

    【数据结构与算法】系列文章链接: 【数据结构与算法】递推法和递归法解题(递归递推算法典型例题) 【数据结构与算法】系列文章链接: 【数据结构与算法】C++的STL模板(迭代器iterator、容器vector、队列queue、集合set、映射map)以及算法例题 【数据结构与算法】系列文章链

    2024年04月13日
    浏览(78)
  • 如何实现一个简单的深度优先搜索(DFS)算法?

    前端入门之旅:探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何带你启航前端之旅 欢迎来到前端入门之旅!这个专栏是为那些对Web开发感兴趣、刚刚踏入前端领域的朋友们量身打造的。无论你是完全的新手还是有一些基础的开发者,这里都将为你提供一

    2024年02月07日
    浏览(54)
  • 【Python搜索算法】深度优先搜索(DFS)算法原理详解与应用,示例+代码

    目录 1 基本原理 2 DFS算法流程 3 时间复杂度 4 空间复杂度 5 DFS算法应用案例: 5.1 解决路径查找问题  5.2 解决图的连通性问题 5.3  拓扑排序 5.4  在树结构中进行深度遍历 深度优先搜索(DFS)是一种重要的图遍历算法,用于探索图中的节点和边。 DFS 是一种递归或栈(堆栈)

    2024年02月06日
    浏览(61)
  • Python算法:深度优先搜索—DFS(模板及其样例)

    • 沿着一条路径一直搜索下去,在无法搜索时,回退到刚刚访问过的节点。 • 并且每个节点只能访问一次。 • 本质上是持续搜索,遍历了所有可能的情况,必然能得到解。 • 流程是一个树的形式,每次一条路走到黑。 • 目的主要是达到被搜索结构的叶结点直到最后一层

    2024年03月24日
    浏览(49)
  • DFS(深度优先搜索算法)入门保姆级超详解

    如题,本篇创作目的在于更精细化理解DFS的运作,篇幅不长,也只是作者的一家之言,只为提供一个对入门者的更精细的解释。 DFS,深度优先搜索算法,首先我们看中文,可以很清楚的理解到这个算法是指搜索操作中优先进行深度也就是纵向的数据筛查。 看搜索的基本思路

    2024年02月07日
    浏览(48)
  • 【C++算法】dfs深度优先搜索(上) ——【全面深度剖析+经典例题展示】

    💃🏼 本人简介:男 👶🏼 年龄:18 📕 ps:七八天没更新了欸,这几天刚搞完元宇宙,上午一直练🚗,下午背四级单词和刷题来着,还在忙一些学弟学妹录制视频和准备开学一些事,一直没空出时间来,等 20号练完车,也马上开学了QAQ。不过今天倒是空出来一些时间,恰好这

    2024年02月02日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包