【蓝桥杯-筑基篇】搜索

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

🍓系列专栏:蓝桥杯

🍉个人主页:个人主页

目录

递归树

1.递归构建二进制串 

2.全排列的 DFS 解法

3.全排列的 BFS 解法

4.数的划分法

5.图书推荐


递归树

递归树是一种用于分析递归算法时间复杂度的工具。它可以将递归算法的执行过程可视化,从而更好地理解算法的时间复杂度。

递归树的构造方法如下:

  1. 首先,将递归算法的输入规模表示为根节点。
  2. 然后,将递归算法的每一次递归调用表示为树的一个子节点。
  3. 对于每个子节点,将其表示为一个与父节点相同的问题,但是规模更小的子问题。
  4. 重复上述步骤,直到递归算法的规模为 1 或者 0。

递归树的叶子节点表示递归算法的基本操作,而递归树的深度表示递归算法的递归深度。通过递归树,可以很容易地计算出递归算法的时间复杂度。

以下是一个递归树的例子:

构建二进制串 

【蓝桥杯-筑基篇】搜索,蓝桥杯,算法,蓝桥杯,开发语言

 这个递归树表示的是一个将一个大小为 n 的问题分成两个大小为 n/2 的子问题的递归算法。从根节点到叶子节点的路径长度为 O(log n),因此,这个递归算法的时间复杂度为 O(n log n)。在实际应用中,递归树常常用于分析递归。

1.递归构建二进制串 

public class A {
    public static void main(String[] args) {
   
    	dg(0,"");

    }

	private static void dg(int depth, String bin) {
		if(depth==4) {
			System.out.println(bin);
			return ;
		}
		
		dg(depth+1,bin+"0");
		dg(depth+1,bin+"1");
		
	}

}
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 

修改一下:

public class A {
    public static void main(String[] args) {
   
    	DFS(0,"");

    }

	private static void DFS(int depth, String bin) {
		if(depth==4) {
			System.out.println(bin);
			return ;
		}
		
		for (int i = 0; i <= 1; i++) {
			DFS(depth+1,bin+i);
		}
		
		
		
	}

}

优化:用数组存

在这个例子中,我们使用了一个静态数组arr来存储每个深度的值,当深度达到4时,我们输出这个数组。在DFS函数中,我们使用了一个for循环来遍历每个深度的可能性,即0或1,然后将其存储在数组中,并递归调用DFS函数,直到深度达到4。

public class A {
	public static int[] arr=new int[4];
    public static void main(String[] args) {
   
    	DFS(0);

    }

	private static void DFS(int depth) {
		if(depth==4) {
			System.out.println(Arrays.toString(arr));
			return ;
		}
		
		for (int i = 0; i <= 1; i++) {
			arr[depth]=i;
			DFS(depth+1);
		}
		
		
		
	}

}

 结果:

[0, 0, 0, 0] [0, 0, 0, 1] [0, 0, 1, 0] [0, 0, 1, 1]
[0, 1, 0, 0] [0, 1, 0, 1] [0, 1, 1, 0] [0, 1, 1, 1] 
[1, 0, 0, 0] [1, 0, 0, 1] [1, 0, 1, 0] [1, 0, 1, 1] 
[1, 1, 0, 0] [1, 1, 0, 1] [1, 1, 1, 0] [1, 1, 1, 1] 

2.全排列的 DFS 解法

这段代码是一个全排列的DFS解法。我们使用了递归的方式来生成所有可能的排列。初始时,我们调用DFS函数,初始深度为0,初始答案为空字符串,n为3。在DFS函数中,我们首先判断当前深度是否达到n,如果达到,则输出答案并返回。否则,我们遍历所有可能的下一位数,如果该数未被使用,则将其加入到答案中,并递归调用DFS函数,深度加1。当递归返回时,我们将该数从答案中删除,以便遍历其他可能的下一位数。下面是代码实现:

public class A {
    public static void main(String[] args) {
   
    	DFS(0,"",3);

    }

	private static void DFS(int depth, String ans,int n) {
		if(depth==n) {
			System.out.println(ans);
			return ;
		}
		
		for (int i = 1; i <= n; i++) {
			if(!ans.contains(""+i))
			DFS(depth+1,ans+i,n);
		}
		
	
	}

}
 
123 132 213 231 312 321 

3.全排列的 BFS 解法

这段代码是一个全排列的BFS解法。我们使用了一个队列来存储每个深度的可能性,初始时,队列中包含了所有可能的第一位数。然后,我们遍历队列中的所有元素,将当前深度的可能性加入到队列中。当深度达到n时,队列中的所有元素即为所有可能的排列。

下面是代码实现:

public class A {
    public static void main(String[] args) {
        int n=3;
        Queue<String> q=new LinkedList<String>();
        //将所有可能的第一位数加入队列中
        for (int i = 1; i <= n; i++) q.offer(""+i);
        while(!q.isEmpty()) {
            String head=q.poll();
            for (int i = 1; i <= n; i++) {
                //如果当前深度的可能性中已经包含了i,则跳过
                if(head.contains(""+i)) continue;
                String son=head+i;
                //如果当前深度为n,则输出当前深度的可能性
                if(son.length()==n) System.out.println(son);
                //否则将当前深度的可能性加入到队列中
                else q.offer(son);
            }
        }


    }

}
  
123 132 213 231 312 321 

4.数的划分法

问题描述

将整数n分成k份,且每份不能为空,任意两份不能相同(不考虑顺序)。
例如:n=7,k=3,下面三种分法被认为是相同的:
1,1,5; 

1,5,1;                 

5,1,1;


问有多少种不同的分法。

输入格式
n,k
输出格式
一个整数,即不同的分法
样例输入
7 3
样例输出
4 {四种分法为:1,1,5;1,2,4;1,3,3;2,2,3;}

给定一个正整数n,将其拆分成k个正整数的和,求方案数。这里使用了深度优先搜索的方法,从min开始枚举每个数,递归求解。其中,fanan表示当前的方案,ans表示方案数,cnt表示调用次数。

public class A {
	public static int cnt;//调用次数
	public static int ans;//方案数
    public static void main(String[] args) {
    	int n=7;//给定的正整数
    	int k=3;//将其拆分成k个正整数的和
    	dfs(n,k,1,"");//从1开始枚举每个数
    	System.out.println("方案数:"+ans);//输出方案数
    	System.out.println("调用次数:"+cnt);//输出调用次数
    	


    }

	/**
	 * 深度优先搜索
	 * @param n 给定的正整数
	 * @param k 将其拆分成k个正整数的和
	 * @param min 枚举的最小值
	 * @param fanan 当前的方案
	 */
	private static void dfs(int n, int k, int min, String fanan) {
		cnt++;//调用次数加1
		if(k==1 && min<=n) {//如果k=1且min<=n
			ans++;//方案数加1
			System.out.println(fanan+n);//输出方案
			return ;
		}
		if(min*k>n) return ; //剪枝
		for (int i = min; i < n; i++) {//枚举每个数i
			dfs(n-i,k-1,i,fanan+i+"+");//递归搜索
		}
		
	}

}
1+1+5
1+2+4
1+3+3
2+2+3
方案数:4
调用次数:15

5.图书推荐

你是否发现,购物、短视频、资讯等平台背后的智能推荐算法,不断分析着你的购物偏好和浏览习惯;价格算法时刻计算调整着你能购买到的商品价位;导航算法、网约车平台算法和无人驾驶汽车算法等等,时刻影响着我们的出行……

无论是否愿意,我们的生活已被算法包围。为了帮助大家全面认知我们当前所身处的世界,消弭技术发展过快带来的困扰与隐忧,《人人都离不开的算法——图解算法应用》一方面从人工智能算法的五大核心应用领域—公共、商业、医疗、工业、金融的典型场景出发,以通俗化、故事化和漫画化的具体事例,深入解读算法是如何在各行各业具体发挥作用和对日常生活的影响;另一方面,将从算法的责任监管和立法治理等角度,阐述算法开发与应用者们应该如何守好伦理底线,让科技向善而行。

《人人都离不开的算法——图解算法应用》脉络清晰,图文并茂,无论你是工作中会接触到算法应用的从业人员,还是对算法应用感到好奇的小白,本书都有助于你打开视野,看到算法在实际应用中的波澜壮阔。

【蓝桥杯-筑基篇】搜索,蓝桥杯,算法,蓝桥杯,开发语言文章来源地址https://www.toymoban.com/news/detail-794109.html

到了这里,关于【蓝桥杯-筑基篇】搜索的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 算法修炼之筑基篇——筑基一层中期(解决01背包,完全背包,多重背包)

    ✨ 博主: 命运之光​​​​​​ 🦄 专栏: 算法修炼之练气篇​​​​​ 🍓 专栏: 算法修炼之筑基篇 ✨ 博主的其他文章: 点击进入博主的主页​​​​​​ 前言: 学习了算法修炼之练气篇想必各位蒟蒻们的基础已经非常的扎实了,下来我们进阶到算法修炼之筑基篇的

    2024年02月08日
    浏览(34)
  • MySQL筑基篇之增删改查

    ✅作者简介:C/C++领域新星创作者,为C++和java奋斗中 ✨个人社区:微凉秋意社区 🔥系列专栏:MySql一点通 📃推荐一款模拟面试、刷题神器👉注册免费刷题 🔥前言 本文将承接前两篇MySQL专栏的博文,讲解数据库的 增删改查 操作,这里的查询确切的说应该是初级的查询,不

    2024年02月12日
    浏览(58)
  • 百日筑基篇——python爬虫学习(一)

    百日筑基篇——python爬虫学习(一) 随着学习的深入,有关从各种不同的数据库中以及互联网上的海量信息,如何有选择性的爬取我们所需的数据以方便我们的数据分析工作,爬虫的学习是必要的。 Python爬虫是指使用Python编程语言编写的程序,通过模拟浏览器行为从网页中

    2024年02月13日
    浏览(53)
  • 蓝桥杯算法竞赛系列第五章——拔高篇之深度优先搜索(DFS)

    欢迎回到:遇见蓝桥遇见你,不负代码不负卿!  目录 一、引入:深度优先搜索(DFS)  二、经典例题 例题1.二叉搜索树的范围和 题目描述 题解 代码执行 例题2.岛屿数量  题目描述 题解 代码执行 例题3.背包问题 题目描述 题解 代码执行 三、思考题 四、蓝桥结语:遇见蓝

    2023年04月09日
    浏览(47)
  • C语言算法赛——蓝桥杯(省赛试题)

         

    2024年01月22日
    浏览(35)
  • 音频筑基:算法时延分析

    音频算法中,经常遇到时延分析的问题,刚开始接触大多都比较迷惑,这里将自己对时延的学习思考梳理总结于此。 音频领域中,时延(delay/latency)主要指声音从源端发出,经链路传输,再到对端接收到声音,所经过的总时间延迟。一般人耳无法感知的蓝牙段链路时延是25-30

    2024年01月17日
    浏览(36)
  • 04|硬件语言筑基(二)-代码是怎么生成具体电路的?

    你好,我是LMOS。 上节课,我们学习了硬件描述语言Verilog的基础知识。今天我会带你一起用Verilog设计一个简单的电路模块。通过这节课,你不但能复习巩固上节课学到的硬件语言知识,还能在动手实践中体会代码是怎么生成具体电路的。 如果你学过计算机组成原理的课程或

    2024年02月08日
    浏览(34)
  • C语言实现哈希搜索算法

    哈希搜索,也叫散列查找,是一种通过哈希表(散列表)实现快速查找目标元素的算法。哈希搜索算法通常适用于需要快速查找一组数据中是否存在某个元素的场景,其时间复杂度最高为 O(1),而平均情况下的时间复杂度通常相当接近 O(1),因此在实际应用中具有很高的效率和

    2024年02月12日
    浏览(31)
  • 算法与人生 揭秘C语言中高效搜索的秘诀——二分查找算法详解

    引言,少年们,大家好。在这里祝大家元旦快乐,我是博主 那一脸阳光 ,今天来介绍二分查找 在计算机科学领域,搜索算法是数据处理和问题解决的重要工具之一。其中,**二分查找算法(Binary Search)**以其卓越的时间复杂度和简洁高效的实现,在众多搜索算法中脱颖而出

    2024年01月17日
    浏览(59)
  • 汽车零部件软件开发常用搜索算法

    一、线性搜索(Linear Search) 线性搜索是最基础的查找算法,适用于对未排序或无特定结构的数据集合进行搜索。在C语言中实现时,线性搜索通过遍历数组或链表中的每一个元素,并与目标值进行比较,直至找到匹配项或者遍历完所有元素。其时间复杂度为O(n),其中n代表数

    2024年02月19日
    浏览(35)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包