算法分析与设计

基本上就是复杂度分析、几种排序、动态规划、图的最短路径。作业做好考试应该不难。

实验一：递归与分治

根号n段合并排序算法：将数组a[0,n-1]划分为floor(根号n)个子数组，每个子数组有O(根号n)个元素。然后递归地对分割后的子数组进行排序，最后将所得到的floor(根号n)个排好序的子数组合并排序。

用分治法设计一个算法，在数组A中寻找最大元素和最小元素。

理解动态规划的基本思想，理解动态规划算法的两个基本要素最优子结构性质和子问题的重叠性质。熟练掌握典型的动态规划问题。掌握动态规划思想分析问题的一般方法，对较简单的问题能正确分析，设计出动态规划算法，并能快速编程实现。

对于长度相同的2个字符串A和B，其距离定义为相应位置字符距离之和。2个非空格字符的距离是它们的ASCII码之差的绝对值。空格与空格的距离为0，空格与其他字符的距离为一定值k。

在一般情况下，字符串A和B的长度不一定相同。字符串A的扩展是在A中插入若干空格字符所产生的字符串。在字符串A和B的所有长度相同的扩展中，有一对距离最小的扩展，该距离称为字符串A和B的扩展距离。

算法要求如下

例如输入：

cmc
snmn
2

输出：10

注：设字符串A和B的子串A[1..i]和B[1..j]的扩展距离为val(i,j)，则val(i,j)具有最优子结构性质，递归定义为：val(i,j)=min{val(i-1,j)+k, val(i,j-1)+k, val(i-1,j-1)+dist(ai,bj)}

EXP2

在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或右下走。只需要求出这个最大和即可，不必给出具体路径。

三角形的行数大于1小于等于100，数字为0~99

输入格式：

5 //表示三角形的行数 接下来输入三角形
7
3  8
8  1  0
2  7  4  4
4  5  2  6  5

要求输出最大和