算法基础 上机实验 3 学 期: 2015 (秋).

Slides:



Advertisements
Similar presentations
2.5 函数的微分 一、问题的提出 二、微分的定义 三、可微的条件 四、微分的几何意义 五、微分的求法 六、小结.
Advertisements

练一练: 在数轴上画出表示下列各数的点, 并指出这些点相互间的关系: -6 , 6 , -3 , 3 , -1.5, 1.5.
用“自言自语法”提高学生 英语口头表达能力 李奉栖.
在文章中插入图片 What to do? 任务一(1):请你在“愤怒的小鸟”这个文档中插入“红色小鸟”的图片。 要求:1、自学课本45-47页“做一做”的内容,找到在文档中插入图片的方法后,就动手试一试吧。 哪一小组最先完成,会加平时成绩10分噢,加油吧!
10.2 立方根.
实验四 利用中规模芯片设计时序电路(二).
第三章 数据类型和数据操作 对海量数据进行有效的处理、存储和管理 3.1 数据类型 数据源 数据量 数据结构
C语言实验 第一课 标题:学号+姓名.
C++中的声音处理 在传统Turbo C环境中,如果想用C语言控制电脑发声,可以用Sound函数。在VC6.6环境中如果想控制电脑发声则采用Beep函数。原型为: Beep(频率,持续时间) , 单位毫秒 暂停程序执行使用Sleep函数 Sleep(持续时间), 单位毫秒 引用这两个函数时,必须包含头文件
在PHP和MYSQL中实现完美的中文显示
Hadoop I/O By ShiChaojie.
SOA – Experiment 3: Web Services Composition Challenge
SVN服务器的搭建(Windows) 柳峰
走进编程 程序的顺序结构(二).
元素替换法 ——行列式按行(列)展开(推论)
大数据管理技术 --NoSQL数据库 HBase 陈 辉 大数据分析技术.
第一单元 初识C程序与C程序开发平台搭建 ---观其大略
第17章 网站发布.
单元测试工具XUnit 任课老师:黄武 下午2时20分 25.
数据挖掘工具性能比较.
动态规划(Dynamic Programming)
用event class 从input的root文件中,由DmpDataBuffer::ReadObject读取数据的问题
算法基础 上机实验 2 学 期: 2015 (秋).
Java语言程序设计 清华大学出版社 第8章 输入输出流(1).
SOA – Experiment 2: Query Classification Web Service
第4章 非线性规划 4.5 约束最优化方法 2019/4/6 山东大学 软件学院.
编程作业3:网页正文抽取 (10分).
C++语言程序设计 C++语言程序设计 第七章 类与对象 第十一组 C++语言程序设计.
数列.
专题作业.
C语言程序设计 主讲教师:陆幼利.
简单介绍 用C++实现简单的模板数据结构 ArrayList(数组, 类似std::vector)
顺序表的删除.
计算机及办公软件应用 ©2013 苏州工业园区职业技术学院
线 性 代 数 厦门大学线性代数教学组 2019年4月24日6时8分 / 45.
实验一 体验Nachos下的并发程序设计 陈毅东 2006年春.
姚金宇 MIT SCHEME 使用说明 姚金宇
实验七 安全FTP服务器实验 2019/4/28.
用计算器开方.
Lightweight Data-flow Analysis for Execution-driven Constraint Solving
实体描述呈现方法的研究 实验评估 2019/5/1.
Web安全基础教程
成绩是怎么算出来的? 16级第一学期半期考试成绩 班级 姓名 语文 数学 英语 政治 历史 地理 物理 化学 生物 总分 1 张三1 115
第4章 Excel电子表格制作软件 4.4 函数(一).
算法基础 上机实验 1 学 期: 2016 (秋).
实验三 16位算术逻辑运算实验 不带进位控制的算术运算 置AR=1: 设置开关CN 1 不带进位 0 带进位运算;
iSIGHT 基本培训 使用 Excel的栅栏问题
3.16 枚举算法及其程序实现 ——数组的作用.
算法基础 上机实验 1 学 期: 2015 (秋).
算法基础 上机实验 4 学 期: 2016 (秋).
序言 報告內容: 你對父母的感覺 你與父母的關係 你是否與父母同居 你與父母見面的時間 每天與父母的談話時間 與父母談話的內容 結論 感想.
第七、八次实验要求.
基于最大margin的决策树归纳 李 宁.
算法基础 上机实验 4 学 期: 2017 (秋).
2019/5/21 实验一 离散傅立叶变换的性质及应用 实验报告上传到“作业提交”。 11:21:44.
第9章 多媒体技术 掌握 Windows 画图工具的基本操作; 掌握 Windows 音频工具进行音频播放;
实验目的:掌握数据的顺序存储结构及它们在计算机中的操作。 实验内容:
生 物 信 息 学 Bioinformatics 巩晶 癌症研究中心 山东大学 医学院
第六章 Excel的应用 五、EXCEL的数据库功能 1、Excel的数据库及其结构 2、Excel下的数据排序 (1)Excel的字段名行
算法基础 上机实验 3 学 期: 2017 (秋).
基于列存储的RDF数据管理 朱敏
第三章 从概率分布函数的抽样 (Sampling from Probability Distribution Functions)
本节内容 进程 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群 : 联系电话:
第四章 UNIX文件系统.
插入排序的正确性证明 以及各种改进方法.
使用Fragment 本讲大纲: 1、创建Fragment 2、在Activity中添加Fragment
任课教师:戴开宇 TA:时均帅、谭肖、王安华 程序设计B班 :20-16:50(90分钟)
实验六、COM类型病毒分析实验 实验开发教师: 刘乃琦 谌黔燕.
第二次课后作业答案 函数式编程和逻辑式编程
最小生成树 最优二叉树.
Presentation transcript:

算法基础 上机实验 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点整。