【算法设计与分析】实验2:递归与分治—Hanoi塔、棋盘覆盖、最大子段和

目录

一、实验目的

二、实验环境

三、实验内容   

四、核心代码

五、记录与处理

六、思考与总结

七、完整报告和成果文件提取链接


一、实验目的

        掌握递归求解问题的思想及对应的程序编码结构。针对不同的问题,能够利用递归进行问题求解,并利用Java/C/C++/Python等高级程序设计语言将算法转换为对应的程序运行(语言自选)。

        掌握分治算法设计策略,以及基于递归结构的程序框架。针对具体问题能够利用分治法进行问题分析、建模、算法设计及优化,并基于递归结构开展编码实践。

二、实验环境

        1、机房电脑  Window11

        2、Eclipse/Dev-C++等

三、实验内容   

实验要求:

        ①必做题:基于递归思想设计并实现Hanoi塔问题求解;

        ②必做题:基于分治法设计并实现棋盘覆盖问题求解;

        ③附加题:利用分治法实现给定整数数组的最大子段和求解问题。

        ④对上述算法进行时间复杂性分析,并输出程序运行时间及运行结果。

实验原理:

1、必做题:描述递归策略以及Hanoi塔问题的递归求解思路;可借助自然语言或算法流程图描述算法步骤。

      在原始的三阶Hanoi塔中,以三个盘子(1,2,3)为例,借助塔座B将塔座A上的盘子移动到托盘C,首先第一步要将盘子1从塔座A移动到塔座C,然后将2从塔座A移动到B,再将1从C移动到B,将3从A移动到C,将1从B移动到A,再将2从B移动到C,最后将1从A移动到C,这样就成功将所有盘子按顺序放在了塔座C处。

      而递归思想的核心是:将要求解的较大规模的问题分割成k个更小规模的子问题。对于具有n个圆盘的Hanoi塔问题而言,它的内部圆盘的核心理论是完全一致的,所以我们就可以采用分而治之的思想,将Hanoi塔问题拆分成n个小问题:

递归分解:将问题分解为更小的子问题。在该问题中,可以将n个盘子的移动分解为三个步骤

递归基准条件:确定递归何时停止。在该问题中,当只有一个盘子时,直接将其从起始柱移动到目标柱,此时递归停止。

Hanoi塔问题的核心思想是将大问题分解为小问题,通过递归调用解决小问题,然后将结果组合起来解决大问题。

分析Hanoi塔的时间复杂度:

根据递归表达式,可求得时间复杂度为O( )

2、必做题:描述分治法求解策略;理解棋盘覆盖问题,并利用分治法进行建模及算法设计。可借助自然语言或算法流程图描述算法步骤。

      在一个2k*2k个方格组成的棋盘中,若恰有一个方格与其他方格不同,则称该方格为特殊方格

 

在棋盘覆盖问题中,我们分解小问题观察到,对于每个2*2的棋盘,一旦有一个特殊位置被标定,骨牌的填充方式就确定了。

如果有3个不带特殊窗格的2*2的棋盘,如果一次性各自添加特殊窗格,那么其相应的L型骨牌的位置也确定了,即可成功填充进去。

基本思想是将一个难以直接解决的大问题分割成一些规模较小的相同问题,以便各个击破,即分而治之。

而采用分治法求解棋盘覆盖问题的方法步骤为:

1. 将2k*2k棋盘分割为4个子棋盘

2. 特殊方格一定在这四个小棋盘中,那么就一定有其余三个子棋盘没有特殊方格;

3. 为了将这三个无特殊方格的子棋盘转换为特殊棋盘,我们可以用一个L型骨盘覆盖这三个较小棋盘的会合处,让每个子棋盘都有一个特殊方格。

然后通过这种一直切割分治的思想,不断填充,依次按照上面的思路进行分治;直到子棋盘的K=1;

棋盘覆盖求解问题的基本思想是将一个难以直接解决的大问题分割成一些规模较小的相同问题,以便各个击破,即分而治之。

覆盖一个2k×2k棋盘所需的L型骨牌个数为( -1)/3

分析棋盘覆盖问题的时间复杂度:

对于覆盖一个 的棋盘所需的时间,从算法的分治策略可知,T(k)满足以下方程:

由此递归方程可知T(k)=O( )

3、附加题:理解最大子段和问题,并利用分治法进行问题分析、建模及设计求解。

     最大字段和问题要解决的是给定由n个整数组成的序列(a1, a2, …, an),求它的连续的最大子段和。我们最先想到的简单粗暴的方法是暴力求解法,利用循环把每一段起点的值的和进行相加,然后进行对比得出最大的和。不过这种方法需要三层循环,时间复杂度为O( ),过于复杂。

      但对于最大子段和问题的求解我们还可以采用分治法,将该序列分成相等的两端,递归求出左边的最大子段和以及右边的最大子段和,以及第三种情况,最大子段和是中间部分的最大子段和。

所以用分治法求解最大子段和问题就分为了求解三部分的相同子问题:

1.最大子段和是左边的最大子段和

2.最大子段和是左边的最大子段和

3.最大子段和是中间部分的最大子段和

采用分治法求解最大子段和问题时,被切割为了两个规模为n/2的小问题,合并小问题所消耗的时间为O(n),由此可得,其算法递归式为:

由此递归式可知,T(n)=O(nlogn)

四、核心代码

1.Hanoi递归算法设计:

int hanoi(int n, char a, char b, char c) {	// a: 起始柱,b: 辅助柱,c: 目标柱
    if (n == 1) {		// 递归基准条件:只有一个盘子时,直接移动
        printf("将第%d个盘子从%c移动到%c\n", n, a, c);
        return 1;
    } else {
        int count = hanoi(n-1, a, c, b);	// 递归调用:移动n-1个盘子到辅助柱
        printf("将第%d个盘子从%c移动到%c\n", n, a, c);   // 移动第n个盘子到目标柱
        count++;
        count += hanoi(n-1, b, a, c);	// 递归调用:移动n-1个盘子到目标柱,从辅助柱移动 
        return count;
    }
}

2.棋盘覆盖

int tile = 1;//L型骨牌的编号(递增)
void chessBoard(int tr, int tc, int dr, int dc, int size)
{
    if(size == 1) 	
		return;	//棋盘方格大小为1,说明递归到最里层
    int t = tile++;    		//每次递增1
    int s = size / 2;    	//计算棋盘中间行列的索引,因为棋盘是正方形,行和列的中间索引相同
	
	if(dr < tr + s && dc < tc + s) 		
		//检查特殊方块是否在左上角子棋盘中
		chessBoard(tr, tc, dr, dc, s);		
			//在,递归寻找子棋盘
    else{	
		//不在,将该子棋盘右下角的方块视为特殊方块
		board[tr+s-1][tc+s-1] = t;		//左上角子棋盘的右下角方块
        chessBoard(tr, tc, tr+s-1, tc+s-1, s);}
	
	if(dr < tr + s && dc >= tc + s) 
		//检查特殊方块是否在右上角子棋盘中
        chessBoard(tr, tc+s, dr, dc, s);
    else{
		//不在,将该子棋盘左下角的方块视为特殊方块	
		board[tr+s-1][tc+s] = t;	//右上角棋盘的左下角方块
        chessBoard(tr, tc+s, tr+s-1, tc+s, s);}
		
	if(dr >= tr + s && dc < tc + s) 
		//检查特殊方块是否在左下角子棋盘中
		chessBoard(tr+s, tc, dr, dc, s);
    else{            
		//不在,将该子棋盘右上角的方块视为特殊方块
		board[tr+s][tc+s-1] = t;
        chessBoard(tr+s, tc, tr+s, tc+s-1, s);
		}
	
	if(dr >= tr + s && dc >= tc + s) 
		//检查特殊方块是否在右下角子棋盘中
		chessBoard(tr+s, tc+s, dr, dc, s);
    else{         
		//不在,将该子棋盘左上角的方块视为特殊方块
     	board[tr+s][tc+s] = t;//右下角棋盘的左上角
        chessBoard(tr+s, tc+s, tr+s, tc+s, s);
		}
}

3.最大字段和

int MaxSubSum(int a[],int left,int right)
{
    int sum=0;
    
	// 如果left和right相等,说明当前子数组只有一个元素
    if(left==right)
    {
        sum=a[left]>0 ? a[left]:0;// 如果该元素大于0,则最大子段和为该元素,否则为0
        
    }else{
    	
    	// 将数组分为左右两部分,并递归计算最大子段和
        int center=(left+right)/2;	//计算中间位置
        int leftsum=MaxSubSum(a,left,center);// 左边最大子段
        int rightsum=MaxSubSum(a,center+1,right);// 右边最大子段
        
		//求中间最大子段
		int s1=0;
        int lefts=0;	// 临时变量,用于计算从左到中间的过程中当前子段和
        for(int i=center;i>=left;i--){ // 注意:这里是从中间向左遍历,目的是为了让划分的左右两边序列能连接起来
        	lefts+=a[i];
        	if(lefts>s1) s1=lefts;	// 更新从左到中间的最大子段和
    	}
        
    
    	int s2=0;
		int rights=0;	// 临时变量,用于计算从右到中间的过程中当前子段和
    	for(int i=center+1;i<=right;i++){	// 从中间向右遍历
        	rights+=a[i];
        	if(rights>s2) s2=rights;
    	}
    	
    	// 计算当前子数组的最大子段和
    	sum=s1+s2;	// 中间最大子段和,可能跨越中心
    	
    	 // 与左边和右边进行比较 
    	if(sum<leftsum)	sum=leftsum;
		if(sum<rightsum) sum=rightsum; 
	}
	return sum;
 
}


五、记录与处理

1.Hanoi递归算法:

2.棋盘覆盖算法:

0代表特殊方格的位置,每个编号代表相应的L型骨牌。

3分治法求最大子段和的算法:


六、思考与总结

在设计递归算法时,必须明确递归基准条件和递归表达式。递归基准条件是递归的终止条件,决定了递归何时停止,否则代码不会有输出结果。在Hanoi塔问题的设计中,我注意到了递归调用的顺序和参数的传递方式,确保递归能够正确进行。


七、完整报告和成果文件提取链接

完整可运行代码以及相关实验报告以下链接可获取:
链接: https://pan.baidu.com/s/1iss6-C2nxZQGkEpo-WDn0A?pwd=g5cg 提取码: g5cg 

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

mysql_init和mysql_real_connect的形象化认识

解析总结 1. mysql_init 的作用 mysql_init 用于初始化一个 MYSQL 结构体&#xff0c;为后续数据库连接和操作做准备。该结构体存储连接配置及状态信息&#xff0c;是 MySQL C API 的核心句柄。 示例&#xff1a; MYSQL *conn mysql_init(NULL); // 初始化连接句柄2. mysql_…

C语言------数组从入门到精通

1.一维数组 目标:通过思维导图了解学习一维数组的核心知识点: 1.1定义 使用 类型名 数组名[数组长度]; 定义数组。 // 示例&#xff1a; int arr[5]; 1.2一维数组初始化 数组的初始化可以分为静态初始化和动态初始化两种方式。 它们的主要区别在于初始化的时机和内存分配的方…

留学毕业论文如何利用不同问题设计问卷

在留学毕业论文的写作中&#xff0c;我们经常会遇到各种问题&#xff0c;例如选择合适的问题&#xff0c;选择合适的研究方法&#xff0c;以及设计合理的研究过程。然而在完成留学毕业论文的过程中&#xff0c;我们往往会在研究设计这里卡住。即使我们选准了研究问题和研究方法…

范冰冰担任第75届柏林电影节主竞赛单元评委 共鉴电影佳作

近日&#xff0c;备受瞩目的柏林电影节迎来了新一届盛事&#xff0c;而华人演员范冰冰将以主竞赛单元评委身份亮相&#xff0c;引发了广泛关注。此前她已担任过戛纳国际电影节、东京国际电影节、圣塞巴斯蒂安国际电影节等众多电影节主竞赛单元评委。作为国际影坛的知名人物&…

对顾客行为的数据分析:融入2+1链动模式、AI智能名片与S2B2C商城小程序的新视角

摘要&#xff1a;随着互联网技术的飞速发展&#xff0c;企业与顾客之间的交互方式变得日益多样化&#xff0c;移动设备、社交媒体、门店、电子商务网站等交互点应运而生。这些交互点不仅为顾客提供了便捷的服务体验&#xff0c;同时也为企业积累了大量的顾客行为数据。本文旨在…

如何用 Groq API 免费使用 DeepSeek-R1 70B,并通过 Deno 实现国内访问

这几天都被Deepseek刷屏了&#xff0c;而且Deepseek由于异常访问量&#xff0c;这几天都不能愉快的和它玩耍了&#xff0c; 我发现Groq新增了一个Deepseek的70b参数的模型&#xff0c; DeepSeek-R1 70B 作为一款强大的开源模型&#xff0c;提供了卓越的推理能力&#xff0c;而 …

docker配置mysql并使用mysql connector cpp编程

mysql 配置mysql使用docker 这里使用docker安装了&#xff0c;比较简洁&#xff0c;不想使用了直接就可以把容器删掉&#xff0c;首先获取下镜像&#xff0c;如下命令 docker pull container-registry.oracle.com/mysql/community-server这里直接默认使用最新版本的mysql了 …

STM32 TIM输入捕获 测量频率

输入捕获简介&#xff1a; IC&#xff08;Input Capture&#xff09;输入捕获 输入捕获模式下&#xff0c;当通道输入引脚出现指定电平跳变时&#xff0c;当前CNT的值将被锁存到CCR中&#xff0c;可用于测量PWM波形的频率、占空比、脉冲间隔、电平持续时间等参数 每个高级定时器…

【已解决】windows7虚拟机安装VMtools频繁报错

为了在虚拟机VMware中安装win7&#xff0c;题主先在网上下载了windows7 professional版本的镜像&#xff0c;在vmware中安装vmtools时报错&#xff0c;信息如下 &#xff08;安装程序无法继续&#xff0c;本程序需要您将此虚拟机上安装的操作系统更新到SP1&#xff09; 然后就…

7.抽象工厂(Abstract Factory)

抽象工厂与工厂方法极其类似&#xff0c;都是绕开new的&#xff0c;但是有些许不同。 动机 在软件系统中&#xff0c;经常面临着“一系列相互依赖的对象”的创建工作&#xff1b;同时&#xff0c;由于需求的变化&#xff0c;往往存在更多系列对象的创建工作。 假设案例 假设…

电路研究9.2.3——合宙Air780EP中FTP——FTPGET 命令使用方法研究

怎么说呢&#xff0c;之前也是看的&#xff0c;但是也很迷茫&#xff0c;感觉上虽然是对的&#xff0c;但是无法联系到应用里面&#xff0c;今天研究一下FTP 命令使用方法吧。 15.29 使用方法举例 这里发现下面那些看的不懂呢&#xff0c;于是就返回FTP的应用了。 9.5.4 FTP 应…

高精度加法乘法

高精度加法&乘法都是把数字转化成数组进行运算&#xff0c;存储 高精度加法 建议多在纸上画画&#xff0c;梳理思路 代码实现 输入字符串 //初始化数组存储 int a[250]{0}; int b[250]{0}; int c[251]{0}; //定义字符串&#xff0c;输入字符串 string s1,s2; getline(c…

【C++】STL介绍 + string类使用介绍 + 模拟实现string类

目录 前言 一、STL简介 二、string类 1.为什么学习string类 2.标准库中的string类 3.auto和范围for 4.迭代器 5.string类的常用接口说明 三、模拟实现 string类 前言 本文带大家入坑STL&#xff0c;学习第一个容器string。 一、STL简介 在学习C数据结构和算法前&#xff0c;我…

数据结构的队列

一.队列 1.队列&#xff08;Queue&#xff09;的概念就是先进先出。 2.队列的用法&#xff0c;红色框和绿色框为两组&#xff0c;offer为插入元素&#xff0c;poll为删除元素&#xff0c;peek为查看元素红色的也是一样的。 3.LinkedList实现了Deque的接口&#xff0c;Deque又…

【开源免费】基于SpringBoot+Vue.JS体育馆管理系统(JAVA毕业设计)

本文项目编号 T 165 &#xff0c;文末自助获取源码 \color{red}{T165&#xff0c;文末自助获取源码} T165&#xff0c;文末自助获取源码 目录 一、系统介绍二、数据库设计三、配套教程3.1 启动教程3.2 讲解视频3.3 二次开发教程 四、功能截图五、文案资料5.1 选题背景5.2 国内…

LabVIEW温度修正部件测试系统

LabVIEW温度修正部件测试系统 这个基于LabVIEW的温度修正部件测试系统旨在解决飞行器温度测量及修正电路的测试需求。该系统的意义在于提供一个可靠的测试平台&#xff0c;用于评估温度修正部件在实际飞行器环境中的性能表现&#xff0c;从而确保飞行器的安全性和可靠性。 系统…

vim的特殊模式-可视化模式

可视化模式&#xff1a;按 v进入可视化模式 选中 y复制 d剪切/删除 可视化块模式: ctrlv 选中 y复制 d剪切/删除 示例&#xff1a; &#xff08;vim可视化模式的进阶使用&#xff1a;vim可视化模式的进阶操作-CSDN博客&#xff09;

mysql重学(一)mysql语句执行流程

思考 一条查询语句如何执行&#xff1f;mysql语句中若列不存在&#xff0c;则在哪个阶段报错一条更新语句如何执行&#xff1f;redolog和binlog的区别&#xff1f;为什么要引入WAL什么是Changbuf&#xff1f;如何工作写缓冲一定好吗&#xff1f;什么情况会引发刷脏页删除语句会…

【Docker】Docker入门了解

文章目录 Docker 的核心概念Docker 常用命令示例&#xff1a;构建一个简单的 C 应用容器1. 创建 C 应用2. 创建 Dockerfile3. 构建镜像4. 运行容器 Docker 优势学习 Docker 的下一步 **一、Docker 是什么&#xff1f;****为什么 C 开发者需要 Docker&#xff1f;** **二、核心概…

使用langchain ollama gradio搭建一个本地基于deepseek r1的RAG问答系统

目录 简介 环境配置 具体实现 安装依赖 定义模型和prompt 加载检索文档 切割 向量存储 创建检索器 实例化 前端搭建 实现效果 小tips 简介 首先介绍一下使用的几个工具&#xff0c;模型和rag的步骤&#xff0c;注&#xff1a;这里只是简单描述一下&#xff0c;不展…