湖北汽车工业学院
算法设计与分析
----实验指导书
电气工程系软件教研室 王文燕 编
二○○六年
目 录
实验一：分治与递归………………………………………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
一共进行n-1天。按此要求可将比赛日程表设计－成有n行和n-l列的一个表。在表中第i行和第j列处填入第i个选手在第j天所遇到的选手。用分治法编写为该循环赛设计一张比赛日程表的算法并运行实现、对复杂度进行分析。
实验二：贪心算法
【实验目的】应用贪心算法求解管道铺设施工的最佳方案。
【实验要求】需要在某个城市的n个居民区之间铺设煤气管道，则在这n个居民区之间只要铺设n-1条管道即可。假设任意两个居民区之间都可以架设管道，但由于地理环境的不同，所需经费不同。选择最优的施工方案能使总投资尽可能少，这个问题即为求网的“最小生成树”问题。参照以下居民区示意图，使得求解算法为：在可能架设的m条管道中选取n-1条，既能连通n-1个居民区，有使总投资达到“最小”。网可采用邻接矩阵为存储结构，以定点对（i,j）的形式输出最小生成树的边。
要求完成：⑴算法描述⑵写出程序代码⑶完成调试⑷进行过程与结果分析。
【实验性质】验证型实验。
D 23.1 675.9 C 41.1 56B A 38.2 441218.2 I 8.7 H 52.5 G 10.5 E 98.7 居民区示意图 85F 79【实验内容】应用贪心算法策略，具体可采用Kruskal算法或Prim算法来求解居民区示意图的最小生成树，使得对每一条边的选择都是当前状态下最优的。但无论采用何种算法实现都要选好恰当的辅助数据结构，来存放边或顶点的集合。根据所设计的算法完成程序实现。
3
【注意事项】选上述居民区示意图中的数据作为测试数据。用C语言或C++实现算法。选择合适的数据结构。
【调试分析和心得体会】注意整个算法的时间复杂度，并对其进行分析。
【选做题一】就下列问题描述应用贪心策略完成其算法描述并实现该算法，之后对其复杂度进行分析：有n个活动的集合A={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。已知：每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si 设待安排的11个活动的开始时间和结束时间按结束时间的升序排列如下： i 1 2 3 5 3 0 6 4 5 7 5 3 8 6 5 9 7 6 10 8 8 11 9 8 12 10 2 13 11 12 14 s[i] 1 f[i] 4 将此表数据作为实现该算法的测试数据。 【选做题二】构造以n=6, 相应的频率表为={45,13,12,16,9,5}的字符集CS={A,B,C,D,E,F} 为测试数据的Huffman树。应用贪心算法思想完成其算法描述，并编码实现以及对其时间复杂度进行分析。 实验三：动态规划法 【实验目的】应用动态规划算法思想求解矩阵连乘的顺序问题。 【实验要求】应用动态规划算法的最优子结构性质和子问题重叠性质求解此问题。分析动态规划算法的基本思想，应用动态规划策略写出算法及相应的程序，求解此题。要读懂读透A[i,j]，A[1,n]=A[1,k] ×A[k+1,n]，m[i][j]，s[i][j]各式所表达的含义并正确加以应用。m[i][j]的递归定义： 0 （ i=j ） m[i][j]= min{m[i][k]＋ m[k+1][j]+ni-1nknj （ i 4