二分搜索算法实验报告

《算法设计与分析》实验指导书本书是为配合《算法分析与设计实验教学大纲》而编写的上机指导，其目的是使学生消化理论知识，加深对讲授内容的理解，尤其是一些算法的实现及其应用，培养学生独立编程和调试程序的能力，使学生对算法的分析与设计有更深刻的认识。

上机实验一般应包括以下几个步骤：（1）、准备好上机所需的程序。

手编程序应书写整齐，并经人工检查无误后才能上机。

（2）、上机输入和调试自己所编的程序。

一人一组，独立上机调试，上机时出现的问题，最好独立解决。

（3）、上机结束后，整理出实验报告。

实验报告应包括：题目、程序清单、运行结果、对运行情况所作的分析。

本书共分阶段4个实验，每个实验有基本题和提高题。

基本题必须完成，提高题根据自己实际情况进行取舍。

题目不限定如下题目，可根据自己兴趣爱好做一些与实验内容相关的其他题目，如动态规划法中的图象压缩，回溯法中的人机对弈等。

其具体要求和步骤如下：实验一分治与递归（4学时）一、实验目的与要求1、熟悉C/C++语言的集成开发环境；2、通过本实验加深对递归过程的理解二、实验内容：掌握递归算法的概念和基本思想，分析并掌握“整数划分”问题的递归算法。

三、实验题任意输入一个整数，输出结果能够用递归方法实现整数的划分。

四、实验步骤1．理解算法思想和问题要求；2．编程实现题目要求；3．上机输入和调试自己所编的程序；4．验证分析实验结果；5．整理出实验报告。

一、实验目的与要求1、掌握棋盘覆盖问题的算法；2、初步掌握分治算法二、实验题：盘覆盖问题：在一个2k×2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。

在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。

三、实验提示void chessBoard(int tr, int tc, int dr, int dc, int size) {if (size == 1) return;int t = tile++, // L型骨牌号s = size/2; // 分割棋盘// 覆盖左上角子棋盘if (dr < tr + s && dc < tc + s)// 特殊方格在此棋盘中chessBoard(tr, tc, dr, dc, s);else {// 此棋盘中无特殊方格// 用t 号L型骨牌覆盖右下角board[tr + s - 1][tc + s - 1] = t;// 覆盖其余方格chessBoard(tr, tc, tr+s-1, tc+s-1, s);}// 覆盖右上角子棋盘if (dr < tr + s && dc >= tc + s)// 特殊方格在此棋盘中chessBoard(tr, tc+s, dr, dc, s);else {// 此棋盘中无特殊方格// 用t 号L型骨牌覆盖左下角board[tr + s - 1][tc + s] = t;// 覆盖其余方格chessBoard(tr, tc+s, tr+s-1, tc+s, s);}// 覆盖左下角子棋盘if (dr >= tr + s && dc < tc + s)// 特殊方格在此棋盘中chessBoard(tr+s, tc, dr, dc, s);else {// 用t 号L型骨牌覆盖右上角board[tr + s][tc + s - 1] = t;// 覆盖其余方格chessBoard(tr+s, tc, tr+s, tc+s-1, s);}// 覆盖右下角子棋盘if (dr >= tr + s && dc >= tc + s)// 特殊方格在此棋盘中chessBoard(tr+s, tc+s, dr, dc, s);else {// 用t 号L型骨牌覆盖左上角board[tr + s][tc + s] = t;// 覆盖其余方格chessBoard(tr+s, tc+s, tr+s, tc+s, s);}}一、实验目的与要求1、熟悉二分搜索算法；2、初步掌握分治算法；二、实验题1、设a[0:n-1]是一个已排好序的数组。

二分搜索算法实验报告篇一：实验报告2--二分搜索技术注意：红色的部分需要用自己的代码或内容进行替换。

湖南涉外经济学院实验报告实验课程：算法设计与分析实验项目：二分搜索技术学院专业实验地点分组组号实验时间 XX年 3 月 10 日星期一第 12节指导老师【实验目的和要求】1. 理解分治法的原理和设计思想；2．要求实现二分搜索算法；3．要求交互输入一组关键字序列，输入需要查找的关键字；4. 要求显示结果。

【系统环境】操作系统：Windows XP 操作系统开发工具：VC++6.0英文企业版开发语言：C，C++【实验原理】1、问题描述给定已排好序的n个元素a[0…n-1]，现要在这n个元素中找出一特定元素x。

2、实验原理二分搜索方法充分利用了元素间的次序关系（但也局限于此），采用分治策略，将n个元素分成个数大致相同的两半，取a[n/2]与x进行比较。

如果x=a[n/2]，则找到x，算法终止。

如果xa[n/2]，则只要在数组a的右半部继续搜索x。

【实验任务与步骤】1、实验步骤(可以根据自己的程序修改)(1) 实现顺序搜索。

(2) 实现二分搜索算法的递归算法。

(3) 实现二分搜索算法的非递归算法。

(4) 编写主函数，调用所写的三个算法进行测试，并进行输出。

2、源程序代码// 此处为解决问题的完整源程序，要求带注释，代码必须符合书写规范。

(1) 顺序搜索(2) 递归的二分搜索(3) 非递归的二分搜索(原文来自：小草范文网:二分搜索算法实验报告)……【实验结论(包括实验数据处理、问题与解决办法、心得体会、意见与建议等)】// 此处为程序运行的结果，要求有程序运行输入输出实例，要求至少有两组实验结果。

// 必须写心得体会、意见与建议等，或者遇到的问题、难题等。

……篇二：查找排序实验报告实验十：查找、排序计算机学院 12级2班 12110XX 李龙实验目的：1．掌握折半查找算法的思想。

2．实现折半查找的算法。

3．掌握常见的排序算法（插入排序、交换排序、选择排序等）的思想、特点及其适用条件。

实验四搜索实验报告一、实验目的本次实验的主要目的是深入了解和掌握不同的搜索算法和技术，通过实际操作和分析，提高对搜索问题的解决能力，以及对搜索效率和效果的评估能力。

二、实验环境本次实验使用的编程语言为 Python，使用的开发工具为 PyCharm。

实验中所需的数据集和相关库函数均从网络上获取和下载。

三、实验原理1、线性搜索线性搜索是一种最简单的搜索算法，它从数据的开头开始，依次比较每个元素，直到找到目标元素或者遍历完整个数据集合。

2、二分搜索二分搜索则是基于有序数组的一种搜索算法。

它每次将数组从中间分割，比较目标值与中间元素的大小，然后在可能包含目标值的那一半数组中继续进行搜索。

3、广度优先搜索广度优先搜索是一种图搜索算法。

它从起始节点开始，逐层地访问相邻节点，先访问距离起始节点近的节点，再访问距离远的节点。

4、深度优先搜索深度优先搜索也是一种图搜索算法，但它沿着一条路径尽可能深地访问节点，直到无法继续，然后回溯并尝试其他路径。

四、实验内容及步骤1、线性搜索实验编写线性搜索函数，接受一个列表和目标值作为参数。

生成一个包含随机数的列表。

调用线性搜索函数，查找特定的目标值，并记录搜索所用的时间。

2、二分搜索实验先对列表进行排序。

编写二分搜索函数。

同样生成随机数列表，查找目标值并记录时间。

3、广度优先搜索实验构建一个简单的图结构。

编写广度优先搜索函数。

设定起始节点和目标节点，进行搜索并记录时间。

与广度优先搜索类似，构建图结构。

编写深度优先搜索函数。

进行搜索并记录时间。

五、实验结果与分析1、线性搜索结果在不同规模的列表中，线性搜索的时间消耗随着列表长度的增加而线性增加。

对于较小规模的列表，线性搜索的效率尚可，但对于大规模列表，其搜索时间明显较长。

2、二分搜索结果二分搜索在有序列表中的搜索效率极高，其时间消耗增长速度远低于线性搜索。

即使对于大规模的有序列表，二分搜索也能在较短的时间内找到目标值。

3、广度优先搜索结果广度优先搜索能够有效地遍历图结构，并找到最短路径（如果存在）。

第1篇一、实验背景与目的随着计算机技术的飞速发展，算法在计算机科学中扮演着至关重要的角色。

为了加深对算法设计与分析的理解，提高实际应用能力，本实验课程设计旨在通过实际操作，让学生掌握算法设计与分析的基本方法，学会运用所学知识解决实际问题。

二、实验内容与步骤本次实验共分为三个部分，分别为排序算法、贪心算法和动态规划算法的设计与实现。

1. 排序算法（1）实验目的：熟悉常见的排序算法，理解其原理，比较其优缺点，并实现至少三种排序算法。

（2）实验内容：- 实现冒泡排序、快速排序和归并排序三种算法。

- 对每种算法进行时间复杂度和空间复杂度的分析。

- 编写测试程序，对算法进行性能测试，比较不同算法的优劣。

（3）实验步骤：- 分析冒泡排序、快速排序和归并排序的原理。

- 编写三种排序算法的代码。

- 分析代码的时间复杂度和空间复杂度。

- 编写测试程序，生成随机测试数据，测试三种算法的性能。

- 比较三种算法的运行时间和内存占用。

2. 贪心算法（1）实验目的：理解贪心算法的基本思想，掌握贪心算法的解题步骤，并实现一个贪心算法问题。

（2）实验内容：- 实现一个贪心算法问题，如活动选择问题。

- 分析贪心算法的正确性，并证明其最优性。

（3）实验步骤：- 分析活动选择问题的贪心策略。

- 编写贪心算法的代码。

- 分析贪心算法的正确性，并证明其最优性。

- 编写测试程序，验证贪心算法的正确性。

3. 动态规划算法（1）实验目的：理解动态规划算法的基本思想，掌握动态规划算法的解题步骤，并实现一个动态规划算法问题。

（2）实验内容：- 实现一个动态规划算法问题，如背包问题。

- 分析动态规划算法的正确性，并证明其最优性。

（3）实验步骤：- 分析背包问题的动态规划策略。

- 编写动态规划算法的代码。

- 分析动态规划算法的正确性，并证明其最优性。

- 编写测试程序，验证动态规划算法的正确性。

三、实验结果与分析1. 排序算法实验结果：- 冒泡排序：时间复杂度O(n^2)，空间复杂度O(1)。

算法实验报告范文《算法设计与分析》实验报告班级姓名学号年月日目录实验一二分查找程序实现…………………………………………………………………03页实验二棋盘覆盖问题（分治法）.…………………………………………………………08页实验三0-1背包问题的动态规划算法设计……………………………………………….11页实验四背包问题的贪心算法………………………………………………………………14页实验五最小重量机器设计问题（回溯法）………………………………………………17页实验六最小重量机器设计问题（分支限界法）…………………………………………20页指导教师对实验报告的评语成绩：指导教师签字：年月日2实验一：二分查找程序实现一、实验时间：2022年10月8日，星期二，第一、二节地点：J13#328二、实验目的及要求目的：1、用c/c++语言实现二分搜索算法。

2、通过随机产生有序表的方法，测出在平均意义下算法比较次数随问题规模的变化曲线，并作图。

三、实验环境平台：Win732位操作系统开发工具：Codeblock10.05四、实验内容对已经排好序的n个元素a[0：n-1]，现在要在这n个元素中找出一特定元素某。

五、算法描述及实验步骤算法描述：折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(logn)完成搜索任务。

它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的某作比较，如果某=a[n/2]则找到某，算法终止。

如果某a[n/2]，则我们只要在数组a的右半部继续搜索某。

二分搜索法的应用极其广泛，而且它的思想易于理解。

确定算法复杂度基本步骤：1、首先设定问题规模n；2、随即产生递增数列；3、在n个有序数中随机取一个作为待查找量，搜索之；4、记录查找过程中的比较次数，再次生成新的有序表并查找，记录查找次数，每个数组重复10次；5、改变问题规模n重复上述步骤2~4，n取100、200……1000；6、依实验数据作图，并与理论图作比较；7、二分搜索算法平均查找次数：问题规模为n时，平均查找次数为：A(n)=Int(logn)+1/2//Int()函数为向下取整3即二分搜索算法对于含有n个数据的有序表L平均作了约Int(logn)+1/2次的查找操作。

算法与分析实验报告一、引言算法是现代计算机科学中的核心概念，通过合理设计的算法可以解决复杂的问题，并提高计算机程序的执行效率。

本次实验旨在通过实际操作和数据统计，对比分析不同算法的执行效率，探究不同算法对于解决特定问题的适用性和优劣之处。

二、实验内容本次实验涉及两个经典的算法问题：排序和搜索。

具体实验内容如下：1. 排序算法- 冒泡排序- 插入排序- 快速排序2. 搜索算法- 顺序搜索- 二分搜索为了对比不同算法的执行效率，我们需要设计合适的测试用例并记录程序执行时间进行比较。

实验中，我们将使用随机生成的整数数组作为排序和搜索的测试数据，并统计执行时间。

三、实验步骤1. 算法实现与优化- 实现冒泡排序、插入排序和快速排序算法，并对算法进行优化，提高执行效率。

- 实现顺序搜索和二分搜索算法。

2. 数据生成- 设计随机整数数组生成函数，生成不同大小的测试数据。

3. 实验设计- 设计实验方案，包括测试数据的规模、重复次数等。

4. 实验执行与数据收集- 使用不同算法对随机整数数组进行排序和搜索操作，记录执行时间。

- 多次重复同样的操作，取平均值以减小误差。

5. 数据分析与结果展示- 将实验收集到的数据进行分析，并展示在数据表格或图表中。

四、实验结果根据实验数据的收集与分析，我们得到以下结果：1. 排序算法的比较- 冒泡排序：平均执行时间较长，不适用于大规模数据排序。

- 插入排序：执行效率一般，在中等规模数据排序中表现良好。

- 快速排序：执行效率最高，适用于大规模数据排序。

2. 搜索算法的比较- 顺序搜索：执行时间与数据规模成线性关系，适用于小规模数据搜索。

- 二分搜索：执行时间与数据规模呈对数关系，适用于大规模有序数据搜索。

实验结果表明，不同算法适用于不同规模和类型的问题。

正确选择和使用算法可以显著提高程序的执行效率和性能。

五、实验总结通过本次实验，我们深入了解了不同算法的原理和特点，并通过实际操作和数据分析对算法进行了比较和评估。

算法与及数据结构实验报告算法与数据结构实验报告一、实验目的本次算法与数据结构实验的主要目的是通过实际操作和编程实现，深入理解和掌握常见算法和数据结构的基本原理、特性和应用，提高我们解决实际问题的能力和编程技巧。

二、实验环境本次实验使用的编程语言为 Python，开发环境为 PyCharm。

同时，为了进行算法性能的分析和比较，使用了 Python 的 time 模块来计算程序的运行时间。

三、实验内容1、线性表的实现与操作顺序表的实现：使用数组来实现顺序表，并实现了插入、删除、查找等基本操作。

链表的实现：通过创建节点类来实现链表，包括单向链表和双向链表，并完成了相应的操作。

2、栈和队列的应用栈的实现与应用：用数组或链表实现栈结构，解决了表达式求值、括号匹配等问题。

队列的实现与应用：实现了顺序队列和循环队列，用于模拟排队系统等场景。

3、树结构的探索二叉树的创建与遍历：实现了二叉树的先序、中序和后序遍历算法，并对其时间复杂度进行了分析。

二叉搜索树的操作：构建二叉搜索树，实现了插入、删除、查找等操作。

4、图的表示与遍历邻接矩阵和邻接表表示图：分别用邻接矩阵和邻接表来存储图的结构，并对两种表示方法的优缺点进行了比较。

图的深度优先遍历和广度优先遍历：实现了两种遍历算法，并应用于解决路径查找等问题。

5、排序算法的比较插入排序、冒泡排序、选择排序：实现了这三种简单排序算法，并对不同规模的数据进行排序，比较它们的性能。

快速排序、归并排序：深入理解并实现了这两种高效的排序算法，通过实验分析其在不同情况下的表现。

6、查找算法的实践顺序查找、二分查找：实现了这两种基本的查找算法，并比较它们在有序和无序数据中的查找效率。

四、实验步骤及结果分析1、线性表的实现与操作顺序表：在实现顺序表的插入操作时，如果插入位置在表的末尾或中间，需要移动后续元素以腾出空间。

删除操作同理，需要移动被删除元素后面的元素。

在查找操作中，通过遍历数组即可完成。

一、实验目的1. 理解逻辑代码算法的基本原理和实现方法。

2. 掌握逻辑代码算法在实际问题中的应用。

3. 提高编程能力和算法设计能力。

二、实验环境1. 操作系统：Windows 102. 编程语言：Python3.73. 开发工具：PyCharm三、实验内容本次实验主要涉及以下逻辑代码算法：1. 排序算法2. 搜索算法3. 图算法四、实验步骤1. 排序算法（1）选择排序选择排序是一种简单直观的排序算法。

它的工作原理是：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

以此类推，直到所有元素均排序完毕。

代码实现如下：```pythondef selection_sort(arr):n = len(arr)for i in range(n):min_index = ifor j in range(i+1, n):if arr[j] < arr[min_index]:min_index = jarr[i], arr[min_index] = arr[min_index], arr[i]return arr# 测试arr = [64, 25, 12, 22, 11]print("原始数组：", arr)sorted_arr = selection_sort(arr)print("排序后的数组：", sorted_arr)```（2）冒泡排序冒泡排序是一种简单的排序算法。

它的工作原理是：比较相邻的元素。

如果第一个比第二个大（升序排序），就交换它们两个；对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。

这步做完后，最后的元素会是最大的数。

针对所有的元素重复以上的步骤，除了最后已经排序好的元素。

代码实现如下：```pythondef bubble_sort(arr):n = len(arr)for i in range(n):for j in range(0, n-i-1):arr[j], arr[j+1] = arr[j+1], arr[j]return arr# 测试arr = [64, 34, 25, 12, 22, 11]print("原始数组：", arr)sorted_arr = bubble_sort(arr)print("排序后的数组：", sorted_arr)```2. 搜索算法（1）二分查找二分查找是一种在有序数组中查找特定元素的搜索算法。

第1篇一、实验目的通过本次实验，掌握常见算法的设计原理、实现方法以及性能分析。

通过实际编程，加深对算法的理解，提高编程能力，并学会运用算法解决实际问题。

二、实验内容本次实验选择了以下常见算法进行设计和实现：1. 排序算法：冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序。

2. 查找算法：顺序查找、二分查找。

3. 图算法：深度优先搜索（DFS）、广度优先搜索（BFS）、最小生成树（Prim算法、Kruskal算法）。

4. 动态规划算法：0-1背包问题。

三、实验原理1. 排序算法：排序算法的主要目的是将一组数据按照一定的顺序排列。

常见的排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序等。

2. 查找算法：查找算法用于在数据集中查找特定的元素。

常见的查找算法包括顺序查找和二分查找。

3. 图算法：图算法用于处理图结构的数据。

常见的图算法包括深度优先搜索（DFS）、广度优先搜索（BFS）、最小生成树（Prim算法、Kruskal算法）等。

4. 动态规划算法：动态规划算法是一种将复杂问题分解为子问题，通过求解子问题来求解原问题的算法。

常见的动态规划算法包括0-1背包问题。

四、实验过程1. 排序算法（1）冒泡排序：通过比较相邻元素，如果顺序错误则交换，重复此过程，直到没有需要交换的元素。

（2）选择排序：每次从剩余元素中选取最小（或最大）的元素，放到已排序序列的末尾。

（3）插入排序：将未排序的数据插入到已排序序列中适当的位置。

（4）快速排序：选择一个枢纽元素，将序列分为两部分，使左侧不大于枢纽，右侧不小于枢纽，然后递归地对两部分进行快速排序。

（5）归并排序：将序列分为两半，分别对两半进行归并排序，然后将排序好的两半合并。

（6）堆排序：将序列构建成最大堆，然后重复取出堆顶元素，并调整剩余元素，使剩余元素仍满足最大堆的性质。

2. 查找算法（1）顺序查找：从序列的第一个元素开始，依次比较，直到找到目标元素或遍历完整个序列。

分治策略算法实验报告引言分治策略是一种经典的算法设计策略，也是算法设计中最重要的思想之一。

其基本思想是将大问题划分成小的、相互独立的子问题，再将子问题合并求解，最终得到原问题的解。

本实验将通过实际例子，验证分治策略算法的有效性。

实验内容本实验选择两个经典的算法问题进行实现和验证，分别是二分查找和快速排序。

这两个问题在算法领域都有重要的应用价值，也是实践分治算法的好例子。

问题1：二分查找二分查找是一种在有序数组中查找特定元素的算法，其基本思想是将数组分为两部分，然后判断目标值在哪一部分，并且逐步缩小问题的规模。

具体实现如下：pythondef binary_search(arr, target):low = 0high = len(arr) - 1while low <= high:mid = (low + high) 2if arr[mid] == target:return midelif arr[mid] < target:low = mid + 1else:high = mid - 1return -1问题2：快速排序快速排序是一种高效的排序算法，其基本思想是通过一趟划分将待排序序列分割成两个独立的子序列，然后递归地对子序列进行排序，最终得到有序序列。

具体实现如下：pythondef quicksort(arr):if len(arr) <= 1:return arrpivot = arr[len(arr) 2]left = [x for x in arr if x < pivot]middle = [x for x in arr if x == pivot]right = [x for x in arr if x > pivot]return quicksort(left) + middle + quicksort(right)实验结果为了验证分治策略算法的有效性，我们分别对上述两个问题进行了测试。