算法分析与设计实验一递归与分治策略

《算法分析与设计实验一递归与分治策略》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验一递归与分治策略实验目的1.了解并掌握递归的概念，递归算法的基本思想；2.掌握分治法的基木思想方法；3.了解适用于用分治法求解的问题类型，并能用递归或非递归的方式设计相应的分治法算法；4.掌握分治法复杂性分析方法，比较同一个问题的递归算法与循坏迭代算法的效率。预习与实验要求1.预习实验指导书及教材的有关内容，掌握分治法的基本思想；2.严格按照实验内容进行实验，培养良好的算法设计和编程的习惯；3.认真听讲，服从安排，独立思考并完成实验。实验原理简单说来，当一个函数用它自己来定义时就称为递归。一般来说，递归需要有边界条件、递归前进段和

2、递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。因此，在考虑使用递归算法编写程序时，应满足两点：1)该问题能够被递归形式描述；2)存在递归结束的边界条件。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。一般说来，一个递归算法可以转换称为一个与之等效的非递归算法，但转换后的非递归算法代码将成倍地增加。分治是一种被广泛M用的有效方法，它的基木思想是把最初的问题分解成若干了问题,然后在逐个解决各个子问题的基础上得到原始问题的解。所谓分治就是“分1佃治Z”的意思。由于分解出的每个子问

3、题总是要比最初的问题容易些，因而分治策略往往能够降低原始问题的难度，或者捉高解决原始问题的效率。根据如何由分解出的子问题求出原始问题的解，分治策略又可分为两种情形：第一，原始问题的解只存在于分解出的某一个子问题中，则只需要在原始问题的一个划分中求解即可；第二，原始问题的解需要山各个子问题的解再经过综合处理得到。无论是哪一种情况,分治策略可以较快地缩小问题的求解范围，从而加快问题求解的速度。分治策略运用于计算机算法是，往往会出现分解出来的子问题与原始问题类型相同的现彖，而与原问题相比，各个了问题的规模变小了，这刚好符合递归的特征。因此分

4、治策略往往是和递归联系在一起的。实验内容以下几个问题选做一项：1.用分治策略写出并实现二分检索算法。（1）选择合适的数据结构来表示问题屮的数列；（2）根据分治法的基本原理，写出求解二分检索的伪码算法；（3）编制C++或JAVA等高级语言程序实现伪码算法；（4）上机运行程序，验证算法的止确性，并分析算法的时空复杂性。2.用递归和非递归方式各写一布尔函数，由该函数获取一个以0或1为元素的数组,并要求确定每个连续为1的序列的大小是否为偶数。（1）形式化地描述该问题，确定采用的数据结构；（2）用递归的思想写出求解该问题的伪码算法；（3）用非递

5、归的思想写出求解该问题的伪码算法；（4）用C++或JAVA等高级程序语言实现上述伪码算法；（1）比较递归和非递归实现的结果，验证算法的正确性，并作时空复杂性分析。3.川分治策略实现斯特拉森矩阵乘法。（1）选择合适的数据结构來表示问题；（2）根据分治法的基本原理，写出斯特拉森矩阵乘法的伪码算法；（3）编制C++或JAVA等高级语言程序实现伪码算法：（4）上机运行程序，验证算法的正确性，并分析算法的时空复杂性。4.用分治策略实现棋盘覆盖问题。（1）选择合适的数据结构來表示问题；（2）根据分治法的基木原理，写出棋盘覆盖问题的伪码算法；（3）

6、编制C++或JAVA等高级语言程序实现伪码算法；（4）上机运行程序，验证算法的止确性，并分析算法的时空复杂性。5.实现一个“由底向上”的归并分类算法，耍求取消栈空间的需要。（1）选择合适的数据结构來表示问题；（2）根据分治法的基本原理，写出归并分类问题的伪码算法；（3）编制C++或JAVA等高级语言程序实现伪码算法：（4）上机运行程序，验证算法的正确性，并分析算法的时空复杂性。实验报告1.按照实验报告手册的要求认真填写相关栏目；2.写出用分治法实现二分检索、斯特拉森矩阵乘法或棋盘覆盖的伪码算法，写出算法所用到的主要数据结构；3.得出结

7、果，并写出算法的时间复朵性和空间复朵性。4.详细填写完成实验的收获和得失，实验过程中遇到的问题、解决的办法、实验心得以及对该实验的建议和意见。