西电软件学院算法实验报告模板2份

《西电软件学院算法实验报告模板2份》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第二次试验问题：Matrix-chainproduct分析：本题是矩阵链乘W题，需要求出最优括号化方案。即在矩阵的乘法链上添加括号来改变运算顺序以使矩阵链乘法的代价降低。可以分析该链乘的一个子段总结一些结论。假设m[ij]表示的链成需要进行的乘法次数(假设j-i足够大)，我们可以将氏*...%分为W段进行计算：(Aj*...*Ak)*(Ak+i*...*Aj)可以得出m[i,j]的递推公式町以得出，当i=j的吋候，m[ij]=0o当i

2、[i,j]的值，取出最小值即时m[i,j】的最优化方案。递推公式如下：可以根据上式得到一个递归算法。本题即是求m[l,n]的值。用二维数组m存储的值，用二维数组s来储存应当分割的位置。以本题中第一个矩阵a)<3,5,2,1,10>为例，可以得出如下矩阵：通过m数组可以得出最少的乘法次数，通过s数组可以输出最优方案。遇到的问题：在输出S数组的结果的吋候仍然需要递归调用，需要合适的控制递归的条件。总结：在矩阵链乘问题中可以看岀，动态规划结合递归的思想可以快捷的解决很多问题。木题屮，重点是归纳出m[ij]的递推

3、公式。问题:LongestCommonSubsequence分析：本题即是最长公共子序列问题。假设冇序列A[m]和序列B[n]，显然，对于每一个都对应着一个公共子序列的长度。假设K度为c,就可以得到一个二维数组c[m,n】。对于c[i,j]，当Ai=Bj的吋候，问题就转变力求A[l..i-1]和B[l..j-1]的公共子序列长度的问题，所以c[i，j]的长度就是c[i-l，j-1]+1;同理，当Ai!=Bj的时候，c[i,j]应该在c[i-l,j]与c[i,j-l]中取最大值。另外，当i或者j等于0的时候

4、，显然c的值为0。由上面所述，可以得到递推公式如下：为了解决这个问题，还如要定义另一个数组用于存放c数组中每一个元素的来源。这个来源其实就反映了公共子申。可以通过箭头表示来源，相连的箭头序列中指句左上方的箭头最多的一率对应的就是最K公共子序列。比如对于题□屮给出的第一个例子X:xzyzzyxY:zxyyzxz可以用一个矩阵表示计算的过程：遇到的问题：在算法中，‘=’是属于‘<’还是‘>’会给结果带来不同。在输出子序列的吋候，最松公共子序列可能不止一个，似是最终未能解决还是只能输出—个。总结：最K公共子序列

5、问题可以利用动态规划很好的解决。动态规划的思想就是根据规律获得推导公式，然后解决问题。问题：LongestCommonSubstring分析：最长公共子序列问题就是和最长公共子申问题差不多，就是当当Ai!=Bj的时候，对应的c[i，j]置为0。推导公式如下：最终c数组的最大值max对应的就是最长公共子审，只需耍将从本位置向前述max-1个的子串即是所求子串。总结：本题就是第二题的一种特殊的情况，即C数组中的值不能从左和上两个方向获取，其他基本相同。在代码上，只需耍修改小部分代码就可以实现该问题。四、问题:

6、MaxSum分析：求和最大的子串。这个M题和第三题很像，不过这次不用二维数组而是使用两个标记来标志所求子申的起始位置（maxb）结束位置（maxe）。思路是，对于第i个元素，如果当前元素与目前选中的序列的sum小于0,那么这么序列不会被选择，更新sumb与sume的值；如果sum仍然大于0，则sum可以选屮。比较sum与max的值，如果sum>max,则更新maxb与maxe的值。递推公式如卜、遇到的问题：在全是负数吋出现问题，后来讲max的初始值设置为第一个元素的值后就能正常了。总结：动态规划能解决很多

7、问题，找到递推公式非常重要。问题：Shortestpathinmultistagegraphs.Findtheshortestpathfrom0to15forthefollowinggraph.分析：观察本题阁的特点，发现可以将阁分解为7个部分，以此可以计算到每一个节点的最短的路径。即可求出最终的最短路径。总结：结合木题中的特殊情况，可以采用适当的方法來处理。第三次实验问题：KnapsackProblem.Thereare5itemsthathaveavalueandweightlistbelow,the

8、knapsackcancontainatmost100Lbs.Solvetheproblembothasfractionalknapsackand0/1knapsack.value(SUS)2030654060weight(Lbs)1020304050value/weight21.52.111.2分析：本题是背包w题的两个解法。对于部分背包来说比较简单，就是将单位价值大的物品优先放置到背包中，这样就能在背包中获取最大的价值。但