内容发布更新时间 : 2025/1/7 8:01:28星期一 下面是文章的全部内容请认真阅读。

湖北汽车工业学院

算法设计与分析

----实验指导书

电气工程系软件教研室 王文燕 编

二○○六年

目 录

实验一：分治与递归???????????????2 实验二：贪心算法????????????????3 实验三：动态规划法???????????????4 实验四（1）：回溯法???????????????6 实验四（2）：分枝限界法?????????????7 参考书目????????????????????8

1

实验一：分治与递归

【实验目的】学会应用分治算法思想完成汽车牌照的快速查找。

【实验要求】利用基数排序的思想对一批具有结构特征的汽车牌照进行排序，并且利用二分查找的思想对排好序的汽车牌照记录实现查询。对于车牌号为关键字的记录集合，可以人工录入数据，也可以按自动方式随机生成。按分治与递归的算法思想策略完成的程序，输入要求的一批数据记录后，屏幕输出排好序的车牌号码及相关信息。查询时，程序查找到匹配的数据，输出该关键字的其他数据项。要求完成：⑴算法描述⑵写出程序代码⑶完成调试⑷进行过程与结果分析。 【实验性质】验证型实验。

【实验内容】应用分治策略，进行二分查找。将一个较大的问题划分为若干较小的问题进行求解，降低求解难度，从而获得原问题的解。进行算法设计，并写出相应程序，进行调试测试。

测试数据的每个记录包括五项，分别为牌照号码、汽车商标、颜色、注册日期和车主的姓名，其中牌照号码一项的输入形式如下：

k0 0 k1 1 k2 B k3 7 k4 3 k5 2 k6 8 其中k0----k1输入值为01―31（代表地区），k2输入值为A----Z（代表车的使用类型），后4位为0000―9999（代表车号），例如：01B7328。这种牌照号码具有多关键字的特征，可以将其分为三段来考虑，即：数字、字母和数字。其余四项输入内容因为不涉及本程序的核心思想，故只要求一般字符串类型即可。查询时要求输入合法的汽车牌照号码。测试数据要求用30个左右的数据项进行测试，头两位暂限定01－04，第3位也暂限定为A----E，以便可使牌照号码相对集中。

【注意事项】用C语言或C++实现算法。选择合适的数据结构。 【调试分析和心得体会】对整个算法实现的时间复杂度进行讨论分析。 【选做题一】完成矩阵乘积的Strassen算法描述、实现及其复杂度分析。

【选做题二】设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：⑴每个选手必须与其他n-1个选手各赛一次；⑵每个选手一天只能赛一次；⑶循环赛

2