算法基础 上机实验 3 学 期: 2015 (秋)
Project 3: 动态规划法 实验1：实现求最优二分检索树问题的算法。对n的取值分别为： 5、10、15、20，、25、30 ，随机生成 2n+1 个概率值（ p1、p2、…、pn ）和（ q0、q1、…、qn ）， 用动态规划法求出最优二分检索树并输出（用加括号的方式表示树），统计算法运行所需时间 ，画出时间曲线。 实验2：实现求最长公共子序列的算法。序列 X 的长为 m，序列 Y的长为 n，序列 X 和 Y 的元素从 26个大写字母 中随机生成，m 和 n 的取值： 第1组 (15， 10)， (15， 20)， (15， 30)， (15，40)， (15，50)， (15，60) 第2组 (15， 25)， (30， 25)， (45，25)， (60，25)， (75，25)， (90，25) 给出算法运行所需的时间，画出时间曲线。
实验要求 a) 为两个实验建立建立ex1，ex2文件分别夹，每个文件夹分别包含3个文件夹： b)input： 1、输入输出格式: 实验一: Source文件夹：源程序 Output文件夹：输出数据 b)input： 实验一: 实现输入文件中每行一个随机数据(要求是表示概率的随机浮点数) 保留到input文件夹下的input1.txt供读取，可预先生成0-1之间的70个随机浮点数，按照实验要求分别读取 5*2+1、10*2+1、15*2+1、20*2+1，、25*2+1、30*2+1个概率值，为了保证这些概率值之和为1，需要进行归一化处理（保证读入的概率之和等于一）。 实验二: 按照题目要求分为两组读文件，第一组生成的6对随机字符串存在input文件夹下的inputA.txt中供程序读取，第二组生成的6对随机字符串存放在inputB.txt中，每行一个随机字符串。
实验要求 c)output： 实验一： 为每种数据规模建立一个子文件夹，按规模从小到大分别为size1，size2，size3，size4，size5，size6，其输出结果输出到对应子文件夹中： output.txt ：以树的括号表示法来表示构造的最优二叉搜索树，将运行结果输出的树及对应的期望搜索代价值保存到output.txt中 time.txt：将求解这个规模的二叉树的测试时间保存到time.txt 实验二： 为实验二测试的两组数据分别建立子文件夹size1，size2，两个实验的分别的六个输出结果输出保存到对应子文件夹中： output.txt ：要求按序号输出每个公共序列的字符串和长度保存到output.txt中 time.txt：将求解这组实验每个解所消耗时间保存到对应的time.txt
实验要求 2、算法实现: a)本次实验需要实现最优二分检索树问题基本算法主要包括如下： 1.构造最优二叉搜索数的动态规划算法 2.输出构造的二叉检索树的递归算法 b)本次实验需要实现最长公共子序列问题基本算法主要包括如下： 1. 求解最长子序列问题的动态规划算法 2. 输出求解的最长子序列的递归算法
实验要求 3、实验细节 a)对于实验一每个规模生成的2n+1个概率值，前n个为教材对应的p概率值，后n+1个为q概率值 b)所构建的最优搜索二叉树要求能完整详细输出生成树的信息方便检查，最好能够实现生成的最优二叉搜索树形象的图形化表示 c)对于实验二实现的结果，要求求出LCS的长度以及一个可行的LCS解 d)必须按照动态规划的思想设计算法，能够对书上给出的伪代码进行一定程度的改进和创新并能运行出正确结果的可以给予加分 e)每求解出一个最优搜索二叉树测试一次时间 (输出树的时间不计)，同样每求解出一对字符串最长公共子序列的解测试一次时间(输出的时间不计）
实验要求 4、性能测试 a)用适当的方法，或工具记录排序算法在执行时所消耗的时，图表格式参考实验一给出的图表式样； b)根据不同输入规模时记录的数据，画出算法在不同输入规模下的运行时间曲线图，比较不同规模下时间曲线变化规律的异同，给出分析.
实验要求 5、注意事项 a) 实验报告中要有必要的实验过程截图和图表 b) project目录结构严格按照输入输出格式的要求； d) 实验杜绝抄袭他人代码或者实验结果，如发现代码高度相似或者实验报告雷同者算0分； e) 实验报告格式参照project1； f) 实验报告请严格按照“学号-姓名-project3.rar”的方式上传到ftp服务器； g)截止时间： 上机检查截止时间：12月2号 晚上上机课。 实验报告截至时间：12月4号 中午12点整。