学生学号 0121510880508 实验课成绩 学 生 实 验 报 告 书 实验课程名称 开课学院 指导教师姓名 学生姓名 学生专业班级 算法设计与分析B实验 计算机科学与技术学院 丁小兵 软件学术1502 2015 -- 2016 学年 第 2 学期 1 实验项目名称 实验者 同组者 分治法的应用 报告成绩 组别 丁小兵 专业班级 软件学术1502 完成日期 2017年5月10日 第一部分：实验分析与设计（可加页） 一、 实验目的和要求 1.目的 （1） 基本掌握分治算法的原理。 掌握递归算法及递归程序的设计。 能用程序设计语言求解相关问题。 用分治法求解问题； 分析算法的时间性能，设计实验程序验证分析结论。 （2） （3） 2.要求 （1） （2） 二、 分析与设计 1.了解用分治法求解的问题：当要求解一个输入规模为n，且n的取值相当大的问题时，如果问题可以分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1 设X[ 0 : n - 1]和Y[ 0 : n – 1 ]为两个数组，每个数组中含有n个已排好序的数。找出X和Y的2n个数的中位数。 ? 编程任务 利用分治策略试设计一个O (log n)时间的算法求出这2n个数的中位数。 ? 数据输入 由文件input.txt提供输入数据。文件的第1行中有1个正整数n（n<=200），表示每个数组有n个数。接下来的两行分别是X，Y数组的元素。 ? 结果输出 程序运行结束时，将计算出的中位数输出到文件output.txt中。 输入文件示例 输出文件示例 input.txt output.txt 3 14 5 15 18 3 14 21 三、主要仪器设备及耗材 1． 安装了Windows 10 操作系统的PC机1台 2．PC 机系统上安装了Microsoft Visual Studio 2013 开发环境 3
算法设计及分析报告
