当前位置：文档库 › 二分搜索实验报告

二分搜索实验报告

竭诚为您提供优质文档/双击可除

二分搜索实验报告

篇一：算法设计与分析二分查找实验报告

课程设计说明书

设计题目：二分查找程序的实现

专业：班级：

设计人：

山东科技大学年月日

课程设计任务书

学院：信息科学与工程学院专业：班级：姓名：

一、课程设计题目：二分查找程序的实现二、课程设计主要参考资料

（1）计算机算法设计与分析（第三版）王晓东著（2）三、课程设计应解决的主要问题

（1）二分查找程序的实现（2）（3）四、课程设计相关附件（如：图纸、软件等）：

（1）（2）

五、任务发出日期：20XX-11-21课程设计完成日期：

20XX-11-24

指导教师签字：系主任签字：

指导教师对课程设计的评语

成绩：

指导教师签字：

年月日

二分查找程序的实现

一、设计目的

算法设计与分析是计算机科学与技术专业的软件方向的必修课。同时，算法设计与分析既有较强的理论性，也有较强的实践性。算法设计与分析的实验过程需要完成课程学习过程各种算法的设计和实现，以达到提高教学效果，增强学生实践动手能力的目标。

用分治法，设计解决二分查找程序的实现问题的一个简捷的算法。通过解决二分查找程序的实现问题，初步学习分治策略。

二、设计要求

给定已按升序排好序的n个元素a[0:n-1]，现要在这n 个元素中找出一特定元素x。实现二分搜索的递归程序并进行跟踪分析其执行过程。

用顺序搜索方法时，逐个比较a[0:n-1]中的元素，直至找出元素x，或搜索遍整个数组后确定x不在其中。这个方

法没有很好的利用n个元素已排好序这个条件，因此在最坏情况下，顺序搜索方法需要o(n)次比较。要求二分法的时间复杂度小于o(n)。

三、设计说明（一）、需求分析

二分搜索方法充分利用了元素间的次序关系，采用分治策略，可在最坏情况下用o(logn)时间完成搜索任务。

该算法的流程图如下：

（二）、概要设计

二分查(:二分搜索实验报告)找的基本思路是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果

x=a[n/2],则找到x，算法终止；如果xa[n/2]，则只要在数组a的右半部分继续搜索x。

由于二分查找的数组不一定是一个整数数组，所以我采用了c++中的模板函数，将排序函数sort和二分查找函数binarysort写为了模板函数，这样不尽可以查找整数数组，也可以查找小数数组。

由于查找的数组的长度不固定，所以我用了c语言中的malloc和realloc函数，首先定义一个数组指针，用malloc 函数该它分配空间，然后向数组中存数，当数组空间满时，在用realloc函数为数组再次分配空间。由于在随机输入一组数时不知在什么位置停止，所以

篇二：二分搜索实验报告

二分搜索

一．实验目的：

1.理解算法设计的基本步骤及各步的主要内容、基本要求；

2.加深对分治设计方法基本思想的理解，并利用其解决现实生活中的问题；

3.通过本次实验初步掌握将算法转化为计算机上机程

序的方法。

二．实验内容：

1.编写实现算法：给定n个元素，在这n个元素中找到值为key的元素。

2.将输入的数据存储到指定的文本文件中，而输出数据存放到另一个文本文件中，包括结果和具体的运行时间。

3.对实验结果进行分析。

三．实验操作：

1.二分搜索的思想：

首先，假设表中的元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复上述过程，知道找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找

不成功。由于二分搜索是基于有序序列的一种搜索算法，故将输入的一组数据首先进行排序，考虑到输入数据可能有多个，采用快速排或者是合并排序，其中与冒泡做了对比。冒泡排序算法：

voidsort(intList[],intlength){

intchange;

for(inti=0;i for(intj=i+1;j

if(List[i]>List[j]){

change=List[i];

List[i]=List[j];

List[j]=change;

}

快速排序算法：

voidQsort(intList[],intlow,inthigh){

if(low>=high)return;

intfirst=low;

intlast=high;

intkey=List[first];

while(first while(first while(first } List[first]=key;

Qsort(List,low,first-1);

Qsort(List,last+1,high);}

二分查找算法：

intbinarysearch(intList[],intlow,inthigh,intkey){ intmid=(low+high)/2;

if(high while(low

if(List[mid]==key)returnmid+1;

else{

if(List[mid]>key)returnbinarysearch(List,low,mid-1, key);elsereturnbinarysearch(List,mid+1,high,key);

}

2.实验数据的输入：

本实验采用将数据输入与输出存储到文件中的方式，需要采用c++文件流操作，对于数据的输入，由于cin对数据的读取会忽略空格和换行操作，使用cin流输入来控制数据的输入。

对于输出操作，首先要从文件中读取数据，为了区别各数据，用逗号隔离，经过处理后将数据存入到另一文件之中。

搜索策略实验报告

学生实验报告实验课名称：人工智能实验项目名称：八数码实验专业名称：计算机科学与技术班级： 2012240201 学号： 201224020102 学生姓名：张璐教师姓名：陈亮亮 2014年12 月13 日

实验日期：2014 年12 月9 日实验室名称：明远2202

最后，为提高程序的运行效率，减少程序扩展节点时搜索量，将当前0所处位置(i_0：0在s[3][3]中所处行号，j_0：0在s[3][3]中所处列号)也存储在DATA中。五．源程序： struct array { int id; int depth; int Wx; //错位个数 int moveNum;//计算移动距离 int a[MAX_X][MAX_Y]; int x; //0的横坐标（在数组里的） int y; //0的纵坐标 }; class EightDigital { public: EightDigital(int a[MAX_X][MAX_Y],int b[MAX_X][MAX_Y]); ~EightDigital(); bool safe(int x,int y); //判断与0相邻的位置能否交换，防止数组越界bool compare(); //判断是否到达目标 void search(int x,int y); //搜索目标 void addOpenTable(int x0,int y0,int x1,int y1);//x0,y0是交换前0的坐标，x1,y1是交换后0的坐标,加入open表 void addCloseTable(); //create close table void deleteOpenTable(); void insertSort(); void exchange(int x0,int y0,int x1,int y1); //交换数组值，移动0 int Wx(); //计算错位个数 void print(); //打印数组 bool haveSolution(); int moveNum();

《人工智能基础》实验报告-实验名称：启发式搜索算法

实验名称:启发式搜索算法 1、实验环境 Visual C++ 6.0 2、实验目的和要求（复述问题）使用启发式算法求解8数码问题（1）编制程序实现求解8数码问题A*算法，采用估价函数 f(n)=d(n)+p（n）其中：d(n)是搜索树中结点n的深度；w(n)为节点n的数据库中错放的旗子个数； p(n)为结点n的数据库中每个棋子与其目标位置之间的距离总和。（2）分析上述（1）中两种估价函数求解8数码问题的效率差别，给出一个是p(n)的上界h(n)的定义，并测试该估价函数是否使算法失去可采纳性。实验目的：熟练掌握启发式搜索A*算法及其可采纳性。 3、解题思路、代码 3.1解题思路八数码问题的求解算法（1）盲目搜索宽度优先搜索算法、深度优先搜索算法（2）启发式搜索启发式搜索算法的基本思想是：定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。先定义下面几个函数的含义： f*(n)=g*(n)+h*(n) (1) 式中g*(n)表示从初始节点s到当前节点n的最短路径的耗散值；h*(n)表示从当前节点n到目标节点g的最短路径的耗散值，f*(n)表示从初始节点s经过n到目标节点g的最短路径的耗散值。评价函数的形式可定义如(2)式所示： f(n)=g(n)+h(n) (2) 其中n是被评价的当前节点。f(n)、g(n)和h(n)分别表示是对f*(n)、g*(n)和h*(n)3个函数值的估计值。利用评价函数f(n)=g(n)+h(n)来排列OPEN表节点顺序的图搜索算法称为算法A。在A算法中，如果对所有的x，h(x)<=h*(x) (3)成立，则称好h(x)为h*(x)的下界，它表示某种偏于保守的估计。采用h*(x)的下界h(x)为启发函数的A算法，称为A*算法针对八数码问题启发函数设计如下： F(n)=d(n)+p(n) (4)

查找与及其应用实验报告

{ printf("%d ",R[i].key); i++; //从表头往后找} if (i>=n) return -1; else { printf("%d",R[i].key); return i; } } int main() { SeqList R; int n=10,i; KeyType k=5; int a[]={3,6,2,10,1,8,5,7,4,9}; for (i=0;i

printf("%d ",R[i].key); printf("\n"); printf("查找%d所比较的关键字:\n\t",k); if ((i=SeqSearch(R,n,k))!=-1) printf("\n元素%d的位置是%d\n",k,i); else printf("\n元素%d不在表中\n",k); printf("\n"); } 代码片段2： #include #define MAXL 100//定义表中最多记录个数 typedef int KeyType; typedef char InfoType[10]; typedef struct { KeyType key;//KeyType为关键字的数据类型InfoType data;//其他数据 } NodeType; typedef NodeType SeqList[MAXL];//顺序表类型 int BinSearch(SeqList R,int n,KeyType k)//二分查找算法{

搜索引擎-第二次实验报告

实验二：实验一、实验目的：根据网络爬虫的基本原理，实现一个简易网络爬虫，需要达到以下指标： 1、种子URL为https://www.wendangku.net/doc/0c12179377.html,； 2、至少抓取10000个页面； 3、至少完成3轮抓取，每轮给出更新的URL及其数量； 4、实现ＵＲＬ判重，列出每轮爬去时重复的URL数量； 5、数据存放到数据库中，能抽取出网页中的标题、页面生成日期（http协议中的时间），至少包含标题、时间、url、抓取时间、网页正文这几个字段。二、实验方案： 1.爬虫分析与设计我们组应用的是java来写爬虫，我们应用SSM框架将数据库和应用程序连接起来，可以在程序中更简单的进行数据库插入、查询等操作。在对url处理的时候我们用的是Java的URL类，通过这个类可以获得请求头的一些信息，例如编码方式。如何获取url，我们一开始遇到了一些问题，直接解析网页中的ref 标签的时候得到的不全是网页链接，所以转换思路，我们先得到页面中的标签，然后再得到标签里边href中的url，然后再对url进行处理。在处理url的时候，因为网页中的url并不是全部以http开头的，所以在url获取部分，对url的格式进行判断，如果通常格式就进行修改，例如，有的链接是”#”，我们就把开始搜索的url加到它的前边，形成一个正确的url。

图1：应用URL类获取网页内容图2：利用url请求头获取编码信息图3：获取a标签

图4-1：获取url 图4-2：获取url

图5：url判重 2.数据库分析与设计我们设计了两个表，一个是未爬取url表，两一个是已经爬取url表。未爬取的表中村的是搜索判重之后，还没有爬取的url，已爬取的存储爬取到的信息。图6：判重后需要爬取的url表图7：爬取后url信息存储表