华东师范大学计算机科学技术系学生上机实践报告
华东师范大学计算机科学技术系上机实践报告
课程名称： 算法设计与分析 指导教师： 柳银萍 上机实践名称：动态规划 上机实践编号：NO.4 一、目的
二、内容与设计思想
1. 2．对于以下n 个矩阵：
M1: p0?p1, M2: p1?p2, M3: p2?p3, M4: p3?p4, M5:p4?p5 ,…. (a) 找出这n个矩阵相乘需要的最小数量乘法的次数。
(b) 请给出一个括号化表达式，使在这种次序下达到乘法的次数最少。 要求：
输入：输入一个正整数n,表示要处理的矩阵个数。在接下来的1行中，输入n+1个数，依次为这n个矩阵的维数。
输出：计算出的最少的乘法次数及相应的加括号方式。
1.1其思路是：
1.2具体算法是：
2. 设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括:
(1)删除一个字符; (2)插入一个字符；
(3)将一个字符改为另一个字符。
将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离,记为d(A,B)。试设计一个有效算法,对任给的2个字符串A和B,计算出它们的编辑距离d(A,B)。 要求：
输入：第1行是字符串A,第2行是字符串B。 输出：字符串A和B的编辑距离d(A,B) 2.1其思路是：
年级： 姓名： 学号： 组号：
上机实践成绩：
上机实践日期： 上机实践时间：
第 1 页 共 3 页
华东师范大学计算机科学技术系学生上机实践报告
2.2具体算法是：
3*．定义于字母表∑{a,b,c)上的乘法表如表1所示。
表1∑乘法表 a b c a b b a b c b a c a c c
依此乘法表,对任一定义于∑上的字符串,适当加括号表达式后得到一个表达式。例如,对于字符串x=bbbba,它的一个加括号表达式为i(b(bb))(ba)。依乘法表,该表达式的值为a。试设计一个动态规划算法,对任一定义于∑上的字符串x=x1x2…xn，计算有多少种不同的加括号方式,使由x导出的加括号表达式的值为a。 要求：
输入：输入一个以a,b,c组成的任意一个字符串。 输出：计算出的加括号方式数。
3.1其思路是：
3.2具体算法是：
三、使用环境
四、调试过程
五、总结
六、附录
1.动态规划1 的程序：
（此处放程序）
运行结果：
第 2 页 共 3 页
华东师范大学计算机科学技术系学生上机实践报告
2. 动态规划2 的程序：
（此处放程序）
运行结果:
3*．动态规划3 的程序：
（此处放程序）
运行结果:
要求至少给出1组测试数据运行结果。
第 3 页 共 3 页
华东师范大学计算机科学技术系上机实践报告
