实验一分治与递归算法.doc_第1页
实验一分治与递归算法.doc_第2页
实验一分治与递归算法.doc_第3页
实验一分治与递归算法.doc_第4页
全文预览已结束

下载本文档

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

文档简介

实验一 分治与递归算法的应用 一、实验目的1掌握分治算法的基本思想（分-治-合）、技巧和效率分析方法。2熟练掌握用递归设计分治算法的基本步骤（基准与递归方程）。3学会利用分治算法解决实际问题。二、实验内容 1.问题描述：题目一：大整数乘法用分治算法编程实现两个n位十进制大整数的乘法运算。题目二：线性时间选择给定n个元素和一个整数k，要求用O(n)时间找出这n个元素中第k小元素。题目三：二分搜索算法设a0:n-1是一个已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素的位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。并对自己的程序进行复杂性分析。题目四：金块问题老板有一袋金块（共n块，n是2的幂（n2）,最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，希望用最少的比较次数找出最重和最轻的金块。并对自己的程序进行复杂性分析。题目五：双色四圆盘梵塔问题与梵塔问题相同，设ABC是3个塔座，初始时塔座A上有四个圆盘，各圆盘从小到大编号为：1、2、3、4，奇数号圆盘为红色，偶数号圆盘为蓝色。现要求将塔座A上的圆盘移到塔座C上，除满足梵塔问题的移动规则外，还必须满足：任何时刻不允许将同色圆盘叠在一起。试设计一个算法，以最少次数完成上述移动，并输出每次移动的圆盘编号、起始塔座、目的塔座。并对自己的程序进行复杂性分析。题目六：桶排序问题明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N100），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作，并对自己的程序进行复杂性分析。【输入样例】1020 40 32 67 40 20 89 300 400 15【输出样例】815 20 32 40 67 89 300 4002.数据输入：个人设定，由键盘输入。3.要求：1）上述题目任选一做。上机前，完成程序代码的编写2）独立完成实验及实验报告三、实验步骤1.理解算法思想和问题要求；2.编程实现题目要求；3.上机输入和调试自己所编的程序；4.验证分析实验结果；5.整理出实验报告。附：实验报告的主要内容一实验目的二问题描述三算法设计包含：数据结构与核心算法的设计描述、函数调用及
人人文库> 全部分类> 生活休闲 > 科普知识

温馨提示

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

最新文档

评论

0/150

提交评论