算法设计课件实验题目

10/1/20232006《AlgorithmDesignandAnalysis》SCUEC1

蛮力法在查找问题中的应用——串匹配问题

1.实验题目给定一个文本，在该文本中查找并定位任意给定字符串2．实验目的1）熟悉上机环境VC＋＋6.02）深刻理解并掌握分蛮力法的设计思想；3）掌握并应用算法的验前分析和验后分析方法；

4）理解这样一个观点：用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对算法的第一个版本进行一定程度的改良，改进其时间性能。10/1/20232006《AlgorithmDesignandAnalysis》SCUEC2

3.实验要求1）设计并实现现用BF方法求解串匹配问题的算法；2）对上述算法进行时间复杂度分析，并根据所分析的结果设计相应的输入实例用计数法进行验证。蛮力法在查找问题中的应用——串匹配问题

10/1/20232006《AlgorithmDesignandAnalysis》SCUEC3

1.实验题目设p1=(x1,y1),p2=(x1,y2),……,pn=(xn,yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对。2．实验目的1）深刻理解并掌握分治法的设计思想；2）掌握递归算法的设计思想以及递归程序的调试技术；3）理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反复努力和重新修正的结果。

2分治法在数值问题中的应用——最近点对问题

10/1/20232006《AlgorithmDesignandAnalysis》SCUEC4

3.实验要求1）设计并实现用BF方法求解最近点对问题的算法；2）设计并实现用DAC方法求解最近点对问题的算法；3）以上两种算法的输入既可以手动输入，也可以自动生成；4）算法不仅要输出最近点对的距离，还要输出最近点对的两个点；5）对上述两个算法进行时间复杂性分析，并设计实验程序验证分析结果。

2分治法在数值问题中的应用——最近点对问题

10/1/20232006《AlgorithmDesignandAnalysis》SCUEC5

1.实验题目

在8枚外观相同的硬币中，有一枚是假币，并且已知假币与真币的重量不同，但不知道假币与真币相比较轻还是较重。可以通过一架天平来任意比较两组硬币，设计一个高效的算法来检测这枚假币。2.实验目的1）深刻理解并掌握减治法的设计思想并理解它与分治法的区别；2）提高应用减治法设计算法的技能。3）理解这样一个观点：建立正角的模型对于问题的求解是非常重要的。3减治法在组合问题中的应用——8枚硬币问题

10/1/20232006《AlgorithmDesignandAnalysis》SCUEC6

3.实验要求1）设计减治算法实现8枚硬币问题；2）设计实验程序，考察用减治技术设计的算法是否高效；3）扩展算法，使之能处理n枚硬币中有一枚假币的问题。4.实现提示假设用一个数组B[n]表示硬币，元素B[i]中存放第i枚硬币的重量，其中n-1个元素的值都是相同的，只有一个元素与其他元素值不同，则当n=8时即代表8枚硬币问题。由于8枚硬币问题限制只允许使用天平比较轻重，所以，算法中只能出现元素相加和比较的语句。3减治法在组合问题中的应用——8枚硬币问题

10/1/20232006《AlgorithmDesignandAnalysis》SCUEC7

1.实验题目用基于变治法的堆排序算法对任意一组给定的数据进行排序2．实验目的1）深刻理解并掌握变治法的设计思想；2）掌握堆的概念以及如何用变治法把任意给定的一组数据改变成堆；3）提高应用变治法设计算法的技能。

4变治法在排序问题中的应用——堆排序

10/1/20232006《AlgorithmDesignandAnalysis》SCUEC8

3.实验要求1）设计与实现堆排序算法；2）待排序的数据可以手工输入(通常规模比较小，10个数据左右），用以检测程序的正确性；也可以计算机随机生成（通常规模比较大，1500－3000个数据左右），用以检验(用计数法)堆排序算法的时间效率。4变治法在排序问题中的应用——堆排序

10/1/20232006《AlgorithmDesignandAnalysis》SCUEC9

1.实验题目给定一个加权连通图(无向的或有向的)，要求找出从每个定点到其他所有定点之间的最短路径以及最短路径的长度。2．实验目的（1）深刻掌握动态规划法的设计思想并能熟练运用，理解它与分治法的区别；（2）掌握最优性原理和最优子结构性质；（3）理解这样一个观点：用动态规划方法求解问题的关键在于确定动态规划函数的递推式。5动态规划法在图问题中的应用——全源最短路径问题

10/1/20232006《AlgorithmDesignandAnalysis》SCUEC10

3.实验要求（1）实现Floyd算法；（2）算法的输入可以手动输入，也可以自动生成；（3）算法不仅要输出从每个顶点到其他所有顶点之间的最短路径，还有输出最短路径的长度；（4）设计一个权重为负的图或有向图的例子，对于它，Floyd算法不能输出正确的结果。

5动态规划法在图问题中的应用——全源最短路径问题

10/1/20232006《AlgorithmDesignandAnalysis》SCUEC