数据结构与算法(三)——递归

一、递归的概念

递归就是方法自己调用自己,每次调用时传入不同的变量。
递归有助于编程者解决复杂的问题,同时可以让代码变得简洁。

1.1 递归机制

在这里插入图片描述

递归调用规则:
1>当程序执行到一个方法时,就会开辟一个独立的空间(栈)
2>每个空间的数据(局部变量)是独立的

打印问题

在这里插入图片描述

阶乘问题

在这里插入图片描述

1.2 递归需要遵守的重要规则

1、执行一个方法时,就创建一个新的受保护的独立空间(栈空间)
2、方法的局部变量是独立的,不会相互影响
3、如果方法中使用的是引用类型变量(比如数组),就会共享该引用类型的数据
4、递归必须向推出递归的条件逼近,否则就是无限递归
5、当一个方法执行完毕,或者遇到 return, 就会返回。谁调用就将结果返回给谁,同事当方法执行完毕或者返回时,该方法也就执行完毕。

二、 递归应用实例

1、各种数学问题,如 8皇后问题、汉诺塔、阶乘、迷宫等
2、各种算法中也会使用到递归,如快排、归并排序、二分查找、分治算法等
3、将用栈解决的问题 -> 递归代码比较简洁

2.1 迷宫回溯问题

主函数

def main(args: Array[String]): Unit = {//先创建一个二维数组模拟迷宫//地图val map = Array.ofDim[Int](8, 7)new Array[Int](2)//使用1表示墙//上下全部置为1for (i <- map(0).indices) {map(0)(i) = 1map(7)(i) = 1}//左右全部置为1for (i <- map.indices) {map(i)(0) = 1map(i)(6) = 1}//设置挡板map(3)(1) = 1map(3)(2) = 1//输出地图for (i <- map.indices) {for (j <- map(i).indices) {print(s"${map(i)(j)}\t")}println()}//使用递归回溯给小球找路setWay(map, 1, 1)//输出新的地图,小球走过,并标识过的递归println("======小球走过,并标识过的地图======")for (i <- map.indices) {for (j <- map(i).indices) {print(s"${map(i)(j)}\t")}println()}}

方法

使用递归回溯来给小球找路

说明:

  1. map表示地图
  2. i,j表示从那个位置开始(1,1)
  3. 如果小球能到map[6,5]则表示小球通路找到
  4. 约定:当map[i,j]
    为 0 表示该点没有走过
    为 1 表示墙
    为 2 表示通路可以走
    为 3 表示该点已经走过,但是走不通
  5. 在走迷宫时,需要确定一个策略(方法) 下=>右=>上=>左 // 如果该点走不通,再回溯
  /**** @param map 地图* @param i   从哪个位置开始找* @param j   从哪个位置开始找* @return 如果找到通路,就返回true,否则返回false*/def setWay(map: Array[Array[Int]], i: Int, j: Int): Boolean = {if (map(6)(5) == 2) true //通路已经找到else {if (map(i)(j) == 0) { //如果当前这个点还没有走过//按照策略 下=>右=>上=>左 走map(i)(j) = 2 //假定该点可以走通map(i)(j) match {case _ if setWay(map, i + 1, j) => true //向下走case _ if setWay(map, i, j + 1) => true //向右走case _ if setWay(map, i - 1, j) => true //向上走case _ if setWay(map, i, j - 1) => true //向左走case _ => { //说明该点走不通,是死路map(i)(j) = 3false}}} else { //如果map(i)(j) != 0,可能是1,2,3false}}}

在这里插入图片描述

最短路径

说明:
1、小球得到的路径,和设置的找路策略有关。即 找路的上下左右顺序有关。
2、修改找路的策略,改成 上=>右=>下=>左
3、那么得到最短路径,我们可以把所有的策略用数组的方式表示出来,把每一个策略得到的节点进行统计,最少的集合就是最短的路径。

2.2 八皇后问题(回溯问题)

问题介绍:

在 8 × 8 格的国际象棋上摆放8个皇后,使其不能互相攻击,即:任意两个皇后都不能处于同一行、同一列或者统一斜线上,问有多少种摆法。

思路分析:

1、第一个皇后先放第一行第一列
2、第二个皇后放在第二行第一列、然后判断是否ok,如果不ok,继续放在第二列、第三列、依次把所有列都放完,找到一个合适
3、继续第三个皇后,第一列、第二列……直到第8个皇后也能放在一个不冲突的位置
4、得到一个正确解时,在栈回退到上一个栈时,就会开始回溯,即将第一个皇后,放到第一列的所有正确解,全部得到。
5、然后回头继续第一个皇后放第二列,继续循环执行1,2,3步骤
【说明】理论上应该创建一个二维数组来表示棋盘,但是实际上用一个一维数组即可解决问题。

输出皇后摆放位置

  //写一个方法,可以将皇后摆放的位置输出def print(): Unit = {for (i <- array.indices) {printf(s"${array(i)}\t")}println()}

判断皇后是否和之前的冲突

//查看当我们放置第n个皇后,就去检测该皇后是否和前面已经摆放的皇后冲突/**** @param n 表示第n个皇后* @return*/def judge(n: Int): Boolean = {for (i <- 0 until n) {//说明//1. array(n) == array(i) 表示判断 第n个皇后是否和前面的n-1个皇后在同一列//2. Math.abs(n - i) == Math.abs(array(n) - array(i)) 表示判断第n个皇后是否和第i皇后在同意斜线//3. 判断是否在同一行,没有必要,n每次都在递增if (array(n) == array(i) || Math.abs(n - i) == Math.abs(array(n) - array(i)))return false}true}

放置第n个皇后

//编写一个方法,放置第n个皇后//注意:check 是 每一次递归时,进入到check中都有 for (i <- 0 until  max)def check(n: Int): Unit = {if (n == max) { //n=8,8个皇后已经放好count += 1print()return}//依次放入皇后,并判断是否冲突for (i <- 0 until max) {//先把当前皇后n放到该行的第1列array(n) = i//判断是否冲突if (judge(n)) {check(n + 1) //不冲突,开始递归//如果冲突,就继续执行arr(n)=i,即将第n个皇后 放置在本行的后移的一个位置}}}

主函数

  //定义一个max表示共有多少个皇后val max = 8//定义数组array,保存皇后放置位置的结果,比如 arr={0,4,7,5,2,6,1,3}val array: Array[Int] = new Array[Int](max)var count = 0def main(args: Array[String]): Unit = {check(0)println(s"一共有 ${count} 种解法")}

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/135548.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

vr飞机驾驶舱模拟流程3D仿真演示加大航飞安全法码

众所周知&#xff0c;航空航天飞行是一项耗资大、变量参数很多、非常复杂的系统工程&#xff0c;因此可利用虚拟仿真技术经济、安全及可重复性等特点&#xff0c;进行飞行任务或操作的模拟&#xff0c;以代替某些费时、费力、费钱的真实试验或者真实试验无法开展的场合&#xf…

2023 Google 开发者大会:Web平台新动向

目录 前言一、Open in WordPress playground二、WebGPU三、新的核心 Web 指标INP四、Webview1、Custom Tabs2、JavaScriptEngine 五、Passkeys六、View Transitions API七、Google Chrome开发者工具优化1、覆盖HTTP的响应标头2、改变stack trance 八、Baseline总结 前言 在前不…

攻防世界-WEB-easyupload

1.新建.user.ini文件&#xff0c;内容如下 GIF89a auto_prepend_filea.jpg 2.上传该文件&#xff0c;并用burp抓包&#xff0c;将Content-Type: application/octet-stream修改为 Content-Type: image/jpg 3.放包&#xff0c;结果如下 4. 新建a.txt文件&#xff0c;内容为 GIF89…

插槽指的是什么?插槽的基础用法体验

什么是插槽 插槽(Slot)是 vue 为组件的封装者提供的能力。允许开发者在封装组件时&#xff0c;把不确定的、希望由用户指定的部分定义为插槽。 <template><p>这是MyCom1组件的第1个p标签</p><&#xff01;--通过slot标签&#xff0c;为用户预留内容占位符…

蓝牙核心规范(V5.4)10.1-BLE 入门笔记(1)

ble 规范 深入了解蓝牙LE需要熟悉相关的规格。蓝牙LE的架构、程序和协议由一项关键规范完全定义,称为蓝牙核心规范。产品如何使用蓝牙以实现互操作性由两种特殊类型称为配置文件和服务的规范集合所涵盖。图1展示了BLE规范类型及其相互关系。 1.1 蓝牙核心规范 蓝牙核心规范是…

html+js写一个可编辑的元素 支持直接向上粘贴文本或图片

有一说一来讲 CSDN 博客的编辑器还是非常厉害的 能够完美设配图片与文字的粘贴与输入 但其实 如果做个捡漏版的 js也可以完成 但这里 为了方便 我选择了vue2的环境 参考代码如下 <template><div class"editable-div" contenteditable"true" past…

WavJourney:进入音频故事情节生成世界的旅程

推荐&#xff1a;使用 NSDT场景编辑器快速搭建3D应用场景 若要正确查看音频生成的强大功能&#xff0c;请考虑以下方案。我们只需要提供一个简单的指令&#xff0c;描述场景和场景设置&#xff0c;模型就会生成一个扣人心弦的音频脚本&#xff0c;突出与原始指令的最高上下文相…

小米6/6X/米8/米9手机刷入鸿蒙HarmonyOS.4.0系统-刷机包下载-遥遥领先

小米手机除了解锁root权限&#xff0c;刷GSI和第三方ROM也是米粉的一大爱好&#xff0c;这不&#xff0c;在华为发布了HarmonyOS.4.0系统后不久&#xff0c;我们小米用户也成功将自己的手机干山了HarmonyOS.4.0系统。虽然干上去HarmonyOS.4.0系统目前BUG非常多&#xff0c;根本…

数仓主题域和数据域、雪花模型,星型模型和星座模型

数仓模型和领域划分 一、主题域和数据域的差别二、雪花模型&#xff0c;星座模型和星型模型 一、主题域和数据域的差别 明确数据域作为数仓搭建的重要一环&#xff0c;能够让数仓的数据便于管理和应用。 数据域和主题域都是数据仓库中的重要概念&#xff0c;但含义略有不同&am…

【Pinia】Pinia的概念、优势及使用方式

学习公司的项目&#xff0c;发现用到了Pinia&#xff0c;于是上网学习了一下&#xff0c;发现了一篇比较优秀的文章&#xff0c;于是将极少部分放到此记录学习&#xff0c;原文链接在末尾。 是什么 官网解释&#xff1a; Pinia 是 Vue 的存储库&#xff0c;它允许您跨组件/页…

2023年中国场馆产业研究报告

第一章 行业综述 1.1 定义与分类 场馆&#xff0c;作为一个多元化和充满活力的行业&#xff0c;为人们提供了一个为不同目的而聚集的空间。无论是为了活动、表演、展览还是聚会&#xff0c;场馆都在为社区的社会、文化和经济建设做出了不可或缺的贡献。 场馆是一个为举办各类…

VR全景展示的功能有哪些?你了解多少?

VR全景展示作为一种全新的视觉体验技术&#xff0c;能够为人们带来强烈的视觉效果以及沉浸式的观感&#xff0c;在旅游、房地产、车展、博物馆等都有着十分广泛的应用。这种富媒体技术&#xff0c;具有很好的交互性和沉浸感&#xff0c;能够带给大家更好的体验&#xff0c;那么…

uni-app实现web-view图片长按下载

<template><view><web-view :webview-styles"webviewStyles" :src"webUrl"></web-view></view> </template> uniapp的web-view中图片无法长按保存&#xff0c;IOS下是正常的&#xff0c;但是Android下长按无反应 解…

如何统计iOS产品不同渠道的下载量?

一、前言 在开发过程中&#xff0c;Android可能会打出来很多的包&#xff0c;用于标识不同的商店下载量。原来觉得苹果只有一个商店&#xff1a;AppStore&#xff0c;如何做出不同来源的统计呢&#xff1f;本篇文章就是告诉大家如何做不同渠道来源统计。 二、正文 先看一下苹…

【C++模拟实现】map、set容器的模拟实现

【C模拟实现】map、set容器的模拟实现 目录 【C模拟实现】map、set容器的模拟实现map、set模拟实现的代码&#xff08;insert部分&#xff09;部分一&#xff1a;红黑树的迭代器以及红黑树部分二&#xff1a;对set进行封装部分三&#xff1a;对map进行封装 遇到的问题以及解决方…

Stability AI推出Stable Audio;ChatGPT:推荐系统的颠覆者

&#x1f989; AI新闻 &#x1f680; Stability AI推出Stable Audio&#xff0c;用户可以生成个性化音乐片段 摘要&#xff1a;Stability AI公司发布了一款名为Stable Audio的工具&#xff0c;用户可以根据自己的文本内容自动生成音乐或音频。免费版可生成最长20秒音乐片段&a…

JL653—一个基于ARINC653的应用程序仿真调试工具

JL653是安装在PC机Windows操作系统上面的一层接插件&#xff0c;它能够真实地模拟ARINC653标准规定的功能性行为&#xff0c;从而可以供研发人员在PC机Windows环境下高效、快速的进行基于ARINC653的应用程序的开发、调试等。 JL653提供了ARINC 653 Part 1中要求的以下服务&…

手把手教你搭建农产品商城小程序:详细步骤解析

随着移动互联网的普及&#xff0c;越来越多的人开始关注如何在手机上进行购物&#xff0c;尤其是对于农产品这类日常生活所需品。本文将手把手教你搭建一个农产品商城小程序&#xff0c;让你轻松实现在手机上购买农产品的愿望。 一、登录乔拓云网后台 首先&#xff0c;我们需要…

ARM Linux DIY(十一)板子名称、开机 logo、LCD 控制台、console 免登录、命令提示符、文件系统大小

文章目录 前言板子名称uboot Modelkernel 欢迎词、主机名 开机 logoLCD 控制台console 免登录命令提示符文件系统大小 前言 经过前面十篇文章的介绍&#xff0c;硬件部分调试基本完毕&#xff0c;接下来的文章开始介绍软件的个性化开发。 板子名称 uboot Model 既然是自己的…

Lua学习笔记:在Visual Studio中调试Lua源码和打断点

前言 本篇在讲什么 调试Lua源码 本篇需要什么 对Lua语法有简单认知 依赖Visual Studio工具 本篇的特色 具有全流程的图文教学 重实践&#xff0c;轻理论&#xff0c;快速上手 提供全流程的源码内容 ★提高阅读体验★ &#x1f449; ♠ 一级标题 &#x1f448; &…