当前位置：首页 > article >正文

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

article 2025/2/1 2:12:16

一、实验目的

二、实验环境

三、实验内容

四、核心代码

五、记录与处理

六、思考与总结

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

一、实验目的

掌握递归求解问题的思想及对应的程序编码结构。针对不同的问题，能够利用递归进行问题求解，并利用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;
 
}