实验1 分治法的应用.doc_第1页
实验1 分治法的应用.doc_第2页
实验1 分治法的应用.doc_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

实验1 分治法的应用1.实验目的（1） 理解分治法的思想。（2） 掌握用分治法解决问题2.实验类型设计型3.预习要求熟悉Visual C+ 6.0上机编程调试的基本方法。掌握教材上分治法的思想。4.实验基本要求（1） 仔细阅读实验的题目，选择其中的两个题目完成，设计的程序要满足正确性，代码中有关键的注释，书写格式清晰，简洁易懂，效率较高，适合各种合理输入，并能对不合理输入做出正确的提示。（2） 实验题目：a) 最大值次大值 问题描述输出n个数中的最大值和次大值（注意：不能用排序） 编程任务 利用分治法策略设计一个算法对任意输入的n个数可以输出最大值和次大值 数据输入第一行输入数的个数n，第二行输入n个数 结果输出 输出最大值和次大值。输入示例输出示例33 22 1 3 实现提示 最大数是两组中的最大值中较大的值，次大值是从两组中较小的最大值和另一组的次大值选取。b) 查找第K小元素 问题描述在n个数当中找第K小元素问题。 编程任务 利用分治策略试设计一个算法对任意的n个数构查找第K小元素，不能用排序。 数据输入第一行输入n的值，第二行输入n个数，第三行输入K的值。 结果输出 程序运行结束时，输出第K小元素的值。输入示例输出示例58 1 3 6 936 实现提示 使用快速排序中所采用的分划方法。c) 中位数问题 问题描述设X 0 : n - 1和Y 0 : n 1 为两个数组，每个数组中含有n个已排好序的数。找出X和Y的2n个数的中位数。 编程任务 利用分治策略试设计一个算法求出这2n个数的中位数。 数据输入第1行中有1个正整数n（n=200），表示每个数组有n个数。接下来的两行分别是X，Y数组的元素。 结果输出 程序运行结束时，将计算出的中位数输出。输入示例输出示例35 15 183 14 2114 实现提示 比较两个序列的中位数大小，如果两个数相等，则该数为整个2n个数据的中位数，否则通过比较，分别减少两个序列的查找范围，确定查找的起止位置，继续查找。按照指定的格式书写实验报告，实验报告清晰，但不赘述，字体最大为四号。在实验结束一周内上交实验报告。5.实验基本步骤（1） 选定实验题目，仔细阅读实验要求，设计好输入输出，按照分治法的思想构思算法，选取合适的存储结构实现应用的操作。（2） 设计的结果应在Visual C+ 实验环境
人人文库> 全部分类> 生活休闲 > 科普知识

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论