文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 工学 > 分治算法实验报告
侵权投诉

分治算法实验报告

算法分析与设计,分治算法,实验报告

实验课程:算法分析与设计

实验名称:实验2 分治算法 (综合性/设计性)

实验目标:

(1)熟悉二分搜索算法和快速排序算法;

(2)初步掌握分治算法;

实验任务:

1、设a[0:n-1]是一个已排好序的数组。请改写二分搜索算法,使得当搜索元素x不在数组中时,返回小于x的最大元素的位置i和大于x的最小元素位置j。当搜索元素在数组中时,I和j相同,均为x在数组中的位置。设有n个不同的整数排好序后存放于t[0:n-1]中,若存在一个下标i,0≤i<n,使得t[i]=i,设计一个有效的算法找到这个下标。要求算法在最坏的情况下的计算时间为O(logn)。

2、在快速排序中,记录的比较和交换是从两端向中间进行的,关键字较大的记录一次就能交换到后面单元,关键字较小的记录一次就能交换到前面单元,记录每次移动的距离较大,因而总的比较和移动次数较少。

实验设备及环境:

PC;C/C++的编程环境Visual C++。

实验主要步骤:

(1) 明确实验目标和具体任务;

(2) 理解实验所涉及的分治算法;

(3) 编写程序并实现分治算法;

(4) 设计实验数据并运行程序、记录运行的结果;

实验数据及运行结果、实验结果分析及结论:

(学生填写)

#include<iostream>

using namespace std;

int BinarySearch(

int a[],int n,int x,int &i,int &j) {

int left=0;

int right=n-1;

while(left<=right) {

int mid=(left+right)/2;

if(x==a[mid]) {

return mid;

}

if(x>a[mid])

left=mid+1;

else right=mid-1;

第1页

你可能喜欢

  • 算法分析
  • 算法报告
  • 分治算法
  • 最小生成树算法
  • 进程调度算法实验报告
  • 银行家算法实验报告
  • 页面置换算法实验报告
  • 排序算法实验报告

热门文档

相关文档

  • 分治算法实验报告

    一、实验目的 1.加深对分治算法的基本思想、 基本步骤和一般形式的理解, 掌握分治算法设计的基本 方法。 2.用分治法设计 L 型组件填图问题的算法,分析其复杂性,...

  • 分治算法 实验报告

    分治算法分治算法隐藏>> 武 夷 学 院 实验报告课程名称: 实验题目: 学生班级: 学生姓名: 学生学号: 指导教师: 完成日期: 200940110 李小飞 2011/10/12 算法...

  • 算法实验报告一 分治法实验

    算法实验报告一 分治法实验 一、实验目的及要求 利用分治方法设计大整数乘法的递归算法, 掌握分治法的基本思想和算法设 计的基本步骤。 要求:设计十进制的大整数...

  • 算法实验报告-分治法性能分析

    因此分治策略将问题划分成 k 个子问题分 别求解合并能有效提高计算效率。 1 算法性能比较 1.1 问题分析比较插入排序,合并排序和快速排序性能。 算法性能比较通常是...

  • 分治算法实验

    分治算法实验_工学_高等教育_教育专区。算分析与设计中的实验中南大学 《算法设计与分析》实验报告 姓 名: 专业班级: 学号: 指导教师:完成日期: 2010.1 一....

  • 算法分析与设计实验报告--分治法

    《算法分析与设计》实验报告 完成日期: 20011.11.10 一、实验目的 (1) 了解分治策略算法思想 (2) 掌握快速排序、归并排序算法 (3) 了解其他分治问题典型算法 ...

  • 递归与分治实验报告

    递归与分治实验报告班级:计科 1102 姓名:赵春晓 学号:2011310200631 实验目的:进一步掌握递归与分治算法的设计思想,通过实际问题来应用递归与 分治设计算法。 实际问题...

  • 算法分析实验报告--分治策略

    算法分析实验报告--分治策略算法分析实验报告--分治策略隐藏>> 《算法设计与分析》实验报告分治策略 姓 名: XXX XXX XXX XXX XXX 专业班级: 学号: 指导教师:...

  • 算法实验报告

    指导教师: 实验成绩: 一、实验名称分治算法实验 - 棋盘覆盖问题 二、实验目的及要求 1、熟悉递归算法编写; 2、理解分治算法的特点; 3、掌握分治算法的基本结构。...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email