精华内容
下载资源
问答
  • 二分搜索算法--《算法分析与设计》实 验 报 告(一)
    千次阅读
    2020-05-07 23:41:40

    一、实验目的

    1.理解分治算法的概念和基本要素;
    2.理解递归的概念;
    3.掌握设计有效算法的分治策略;
    4.通过二分搜索技术学习分治策略设计技巧;
    



    二、实验内容

    实验内容:
    1.使用二分搜索算法查找任意N个有序数列中的指定元素。
    2.通过上机实验进行算法实现。
    3.保存和打印出程序的运行结果,并结合程序进行分析,上交实验报告。
    至少使用两种方法进行编程。
    



    三、源程序

    import java.util.Scanner;
    
    public class BinarySearchTest {
    
        /**
         * 穷举法
         * @param nums :查找数组
         * @param target :目标整数
         * @return
         */
        public static int ExhaustiveSearch(int[] nums, int target) {
            for (int i = 0; i < nums.length; ++i) {
                if (nums[i] == target) {
                    return i;
                }
            }
            return -1;
        }
    
    
        /**
         * 二分搜索(迭代)
         * @param nums :查找数组
         * @param target : 目标整数
         * @return
         */
        public static int binarySearchIteration(int[] nums, int target) {
            int left = 0, right = nums.length-1;
            while (left <= right) {
                int mid = (left + right) / 2; // 中间索引
                if (nums[mid] == target) { // 找到输出索引
                    return mid;
                } else if (nums[mid] < target) { // 左边界更变
                    left = mid + 1;
                } else if (nums[mid] > target) { // 右边界更变
                    right = mid - 1;
                }
            }
            return -1;
        }
    
        /**
         * 二分搜索(递归)
         * @param nums :查找数组
         * @param target :目标整数
         * @param left :左边界
         * @param right :右边界
         * @return
         */
        public static int binarySearchRecursion(int[] nums, int target, int left, int right) {
            while (left <= right) {
                int mid = (left + right) / 2;
                if (nums[mid] == target) {
                    return mid;
                } else if (nums[mid] < target) {
                    left = mid + 1;
                    binarySearchRecursion(nums, target, left, right);
                } else if (nums[mid] > target) {
                    right = mid - 1;
                    binarySearchRecursion(nums, target, left, right);
                }
            }
            return -1;
        }
    
    
        public static void main(String[] args) {
            int n, target, index;
            Scanner in = new Scanner(System.in);
            // 输入数组元素个数
            System.out.print("请输入整数数组的元素个数:");
            n = in.nextInt();
            int[] nums = new int[n];
            //输入数组元素
            for (int i = 0; i < n; ++i) {
                System.out.print(i + "号元素的值为:");
                nums[i] = in.nextInt();
            }
            do {
                System.out.print("请输入要搜索的整数:");
                target = in.nextInt();
    
                index = ExhaustiveSearch(nums, target);
                if (index == -1) {
                    System.out.println("抱歉,未查找到该数字");
                } else {
                    System.out.println("本次使用穷举法\n" + target + "的索引为:" + index);
                }
    
                index = binarySearchIteration(nums, target);
                if (index == -1) {
                    System.out.println("抱歉,未查找到该数字");
                } else {
                    System.out.println("本次使用二分搜索(迭代)\n" + target + "的索引为:" + index);
                }
    
                index = binarySearchRecursion(nums, target, 0, nums.length-1);
                if (index == -1) {
                    System.out.println("抱歉,未查找到该数字");
                } else {
                    System.out.println("本次使用二分搜索(递归)\n" + target + "的索引为:" + index);
                }
    
            } while (true);
        }
    }
    



    四、实验结果

    在这里插入图片描述

    更多相关内容
  • 二分搜索算法实验报告.doc
  • 算法分析与设计-实验二 二分查找实验报告
  • ——二分搜索程序算法的实现 实验目的及要求 1.理解分治算法的概念和基本要素; 2.理解递归的概念; 3.掌握设计有效算法的分治策略; 4.通过二分搜索技术学习分治策略设计技巧; 实验环境 操作系统:Windows 10 操作...

    算法分析与设计实验报告

    ——二分搜索程序算法的实现

    实验目的及要求

    1.理解分治算法的概念和基本要素;
    2.理解递归的概念;
    3.掌握设计有效算法的分治策略;
    4.通过二分搜索技术学习分治策略设计技巧;

    实验环境

    操作系统:Windows 10 操作系统
    开发工具:Eclipse(4.15.0)
    开发语言:Java

    实验内容

    1.使用二分搜索算法查找有序数列中的指定元素;
    2.通过上机实验进行算法实现;
    3.保存和打印出程序的运行结果,并结合程序进行分析,上交实验报告。

    算法描述及实验步骤

    算法流程图
    实验步骤:

    1. 编写二分搜索算法;
    2. 将输入的数组元素排序,转化成有序列;
    3. 编写输入输出;
    4. 测试结果。

    调试过程及实验结果

    问题1:编写递归方法时返回的边界错误,导致陷入死循环。如
    return RecursionBinarySearch(arr,key,left,middle);//搜索左半区
    return RecursionBinarySearch(arr,key,middle,right);//搜索右半区

    正确修改:return RecursionBinarySearch(arr,key,left,middle-1);
    return RecursionBinarySearch(arr,key,middle+1,right);

    问题2:编写迭代方法时while()的条件写成while(left<right)遗漏等号,导致搜索值key=arr[arr.length]时,输出“未搜索到key”。
    正确修改:while(left<=right)
    输出结果为:
    实验结果

    总结

    元素存储在数组中,因此搜索输出的结果为有序数组元素的下标。
    若有序列中存在重复元素,搜索结果输出第一个元素的下标。
    对二分搜索算法的边界问题要考虑清楚, 循环体外的初始条件与循环体内的步骤一定要遵守一致的区间规则(左右开闭),否则会发生陷入死循环、无法找到搜索元素的错误。
    二分搜索算法是将数列按有序化排列,查找过程中采用跳跃式方式查找,先以有序数列的中点位置为比较对象,如果查找的元素值小于中点元素(key<middle),则将待查序列缩小为左半区间,否则为右半区间,直到找到相同元素,或者查找范围为空。
    二分搜索算法的优点是比较次数少,查找速度快,平均性能好;缺点是要求待查表为有序表,且插入删除困难。

    源代码

    import java.util.Scanner;
    public class BinarySearch{	
    	public static int RecursionBinarySearch(int[] arr , int key , int left , int right)
    	{	//递归
    		if((key<arr[left]||(key>arr[right])||(right>right)))
    				return -1;
    		int middle =(left &right) + ((left ^ right) >> 1); //防溢出(left &right) + ((left ^ right) >> 1);
    		if(key<arr[middle])
    		{
    			return RecursionBinarySearch(arr,key,left,middle-1);//搜索左半区
    		}
    		else if(key>arr[middle]) 
    		{
    			return RecursionBinarySearch(arr,key,middle+1,right);//搜索右半区
    		}
    		else
    		{
    			return middle;
    		}
    	}
    	
    	public static int CommonBinarySearch(int[] arr,int key) 
    	{	//迭代
    		int left = 0;
    		int right = arr.length-1;
    		int middle = 0;
    		if((key<arr[left])||(key>arr[right]))
    			return -1;
    		while(left<=right)  
    			{
    				middle =(left &right) + ((left ^ right) >> 1);
    				if(key==arr[middle])
    					return middle;
    				else if(key<arr[middle])
    					right = middle-1;//左半区搜索
    				else if(key>arr[middle])
    					left = middle+1;//右半区搜索
    			}
    		return -1;//未搜索到目标key返回-1
    	}
    	
    	public static int[] Selectionsort(int[] arr) 
    	{//选择排序
    		for(int i=0;i<arr.length-1;i++)
    		{
    			int min = i;
    			for(int j=i+1;j<arr.length;j++)
    			{
    				if(arr[j]<arr[min])
    					min = j;
    			}
    			if(i!=min) 
    			{
    				int temp=arr[i];
    				arr[i]=arr[min];
    				arr[min]=temp;
    			}
    		}
    		return arr;
    	}
    	
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		System.out.println("输入元素个数:");
    		int n = sc.nextInt();
    		int position;
    		
    		int[] arr = new int[n];//输入数组元素
    		for(int i=0;i<n;i++)
    		{
    			System.out.print(i+"号元素为:");
    			arr[i] = sc.nextInt();
    		}
    		
    		Selectionsort(arr);//选择排序数组元素
    		System.out.println("选择排序(升序)后有序列为:");
    		for(int i=0;i<arr.length;i++)
    		{
    			System.out.print(arr[i]+" ");
    		}
    		System.out.println("");
    		
    		do {
    			System.out.println("输入查找元素key:");
    			int key =sc.nextInt();
    			//递归搜索
    			 position = RecursionBinarySearch(arr,key,0,arr.length-1);
    			if(position==-1)
    			{
    				System.out.println("查找"+key+",有序列中不存在");
    			}
    			else
    			{
    				System.out.println("查找"+key+"(递归)\n"+"在有序列中的位置为:"+position);
    			}
    			//迭代搜索
    			  position = CommonBinarySearch(arr,key);
    			if(position==-1)
    			{
    				System.out.println("查找"+key+",有序列中不存在");
    			}
    			else
    			{
    				System.out.println("查找"+key+"(迭代)\n"+"在有序列中的位置为:"+position);
    			}
    			
    		}while(true);
    		
    	}
    	
    	
    }
    
    
    展开全文
  • 算法分析 二分搜索算法 实验报告 包含实验目的 试验分析和程序代码
  • 哈工程本科算法实验-二分搜索【数据+代码+说明+流程图+测试用例】
  • 算法设计与分析实验报告,附已通过源码,供学习参考,共勉♪ 目录摘要如下: 1.问题描述 2.实验目的 3.实验原理 4.实验设计 (包括输入格式、算法、输出格式) 5.实验结果与分析 (除了截图外,实验结果还用...
  • 数据结构实验报告 实验第四章 实验 : 简单查找算法 一需求和规格说明 查找算法这里主要使用了顺序查找折半查找二叉排序树查找和哈希表查找四种方法由于自己能力有 限本想实现其他算法但没有实现其中顺序查找相对...
  • 合并排序算法二分搜索技术算法的实现实验报告.doc
  • 算法分析与设计实验报告——二分搜索算法的实现 目录:算法分析与设计实验报告——二分搜索算法的实现一、 实验目的二、实验要求三、 实验原理四、 实验过程(步骤)五、 运行结果六、实验分析与讨论七、实验特色与...

    算法分析与设计实验报告——二分搜索算法的实现

    一、 实验目的

    掌握分治法的基本思想,建立算法复杂度的理论分析与实验分析的联系,深刻体会算法复杂度作为算法的好坏评价指标的本质含义。

    二、实验要求

    用c++语言实现二分搜索算法,分析时间复杂性。实现二分搜索的递归与非递归程序,并进行跟踪分析其执行过程,体会两者的执行效率。

    三、 实验原理

    折半查找法也称为二分查找法,它充分利用了元素间的次序关系,采用分治策略,可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是,将n个元素分成个数大致相同的两半,取a[n/2]与欲查找的x作比较,如果x=a[n/2]则找到x,算法终止。如果x<a[n/2],则我们只要在数组a的左半部继续搜索x(这里假设数组元素呈升序排列)。如果x>a[n/2],则我们只要在数组a的右半部继续搜索x。二分搜索法的应用极其广泛,而且它的思想易于理解。

    四、 实验过程(步骤)

    见附件一
    实验步骤、特点
    重要源代码(流操作的部分要醒目的提示并注释)

    五、 运行结果

    见附件二

    六、实验分析与讨论

    编写程序时由于传参错误,导致结果不能输出,一直输出没有找到,然后更改了参数之后,程序输出就正确了。还有数组的大小计算不能用strlen函数,要用sizeof(a)/sizeof(a[0])。
    遇到的问题,及解决方案

    七、实验特色与心得

    这是我第一次实质上应用分治法编写程序。二分搜索算法能够实现O(logn)的时间复杂度,比一般的顺序搜索快了不少。这次实验也加深了我对分治法的理解。

    附件一 实验过程(步骤)

    二分搜索的递归程序:

    #include <bits/stdc++.h>
    using namespace std;
    template<class Type>
    int BinarySearch2(Type a[],const Type &x,int left,int right) //递归算法
    {
        int middle=(left+right)/2;
        if(x==a[middle])//查找成功,返回下标
        {
            return middle;
        }
        if(left>=right)
        {
            return -1;
        }
        else if(x>a[middle])//如果x>a[n/2],则我们只要在数组a的右半部继续搜索x
        {
            return BinarySearch2(a,x,middle+1,right);
        }
        else if(x<a[middle])//如果x<a[n/2],则我们只要在数组a的左半部继续搜索x
        {
            return BinarySearch2(a,x,left,middle-1);
        }
        return -1;
    }
    int main()
    {
        int x,len,b1,b2;
        int a[]= {1,2,3,4,5,6,7,8,9,10};//初始化a数组
        len=sizeof (a) / sizeof (a[0]);//计算a数组的长度
        cout<<"请输入您需要查找的数:";
        cin>>x;
        b2=BinarySearch2(a,x,0,len);
        if(b2==-1)
            cout<<"递归方法未找到"<<endl;
        else
            cout<<"递归方法:"<<x<<" 的位置是第 "<<b2<<" 位"<<endl;
    return 0;
    }
    

    二分搜索的非递归程序:

    #include <bits/stdc++.h>
    using namespace std;
    template<class Type>
    int BinarySearch1(Type a[],const Type &x,int n) //非递归算法
    {
        int left = 0;
        int right = n-1;
        while(left <= right)
        {
            int middle = (left+right)/2;
            if(x == a[middle])//查找成功,返回下标
                return middle;
            if(x > a[middle])//如果x>a[n/2],则我们只要在数组a的右半部继续搜索x
                left = middle + 1;
            else//如果x<a[n/2],则我们只要在数组a的左半部继续搜索x
                right = middle - 1;
        }
        return -1;
    }
    int main()
    {
        int x,len,b1,b2;
        int a[]= {1,2,3,4,5,6,7,8,9,10};//初始化a数组
        len=sizeof (a) / sizeof (a[0]);//计算a数组的长度
        cout<<"请输入您需要查找的数:";
        cin>>x;
        b1=BinarySearch1(a,x,len);
        if(b1==-1)
            cout<<"迭代方法未找到"<<endl;
        else
            cout<<"迭代方法:"<<x<<" 的位置是第 "<<b1<<" 位"<<endl;
        return 0;
    }
    

    附件二 运行结果

    a[]= {1,2,3,4,5,6,7,8,9,10};
    二分搜索的递归程序运行结果:

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    a[]= {1,2,3,4,5,6,7,8,9,10};
    二分搜索的非递归程序运行结果:

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 算法设计与分析既有较强的理论性,也有较强的实践性。算法设计与分析的时间过程需要完成课程学习过程各种算法算法的设计和实现,以达到提高教学效果,增强学生实践动手能力的目标
  • 数据挖掘实验报告 PAGE 4 实验 分类挖掘算法ID3 一实验目的 1理解分类 2掌握分类挖掘算法ID3 3为改进ID3打下基础 实验内容 1选定一个数据集可以参考教学中使用的数据集 2选择合适的实现环境和工具实现算法 ID3 3...
  • 实验名称: 二分搜索算法 实验地点: 实验目的: 理解分治算法的概念和基本要素; 理解递归的概念; 掌握设计有效算法的分治策略; 通过二分搜索技术学习分治策略设计技巧; ...

    实验名称: 二分搜索算法

    实验地点:

    实验目的:

    1. 理解分治算法的概念和基本要素;
    2. 理解递归的概念;
    3. 掌握设计有效算法的分治策略;
    4. 通过二分搜索技术学习分治策略设计技巧;

    实验原理:

    二分搜索算法也称为折半查找法,它充分利用了元素间的次序关系,采用分治策略,可在最坏的情况下用O(log n)完成搜索任务。

    实验内容:

    1. 使用二分搜索算法查找任意N个有序数列中的指定元素。
    2. 通过上机实验进行算法实现。
    3. 保存和打印出程序的运行结果,并结合程序进行分析,上交实验报告。
    4. 至少使用两种方法进行编程。

     

    源代码:

    #include<stdio.h>
    #include<stdlib.h>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    //这个算法仅适用于有序序列
    int a[1000];
    int BinarySearch1(int a[], int left, int right, int x)
    {
    	int mid;
    	mid = (left + right) / 2;
    	if(left < right) {
    		if (x == a[mid])
    			return mid;
    		else if (x < a[mid])
    			return BinarySearch1(a, left, mid - 1, x);//递归调用前一半数组
    		else
    			return BinarySearch1(a, mid + 1, right, x);//。。。后一半。。。
    	}
    	return 0;
    }
    int BinarySearch2(int a[], int left, int right, int x)
    {
    	int mid;
    	while (left <= right) {
    		mid = (left + right) / 2;
    		if (x == a[mid])
    			return mid;
    		else if (x < a[mid])
    			right = mid - 1;//递归调用前一半数组
    		else
    			left = mid + 1;//。。。后一半。。。
    	}
    	return 0;
    }
    int main()
    {
    	int x, n, flag = 0;
    	cin >> x >> n;
    	for (int i = 1; i <= n; i++)
    		cin >> a[i];
    	flag = BinarySearch2(a, 1, n, x);
    	if (flag)
    		printf("%d", flag);
    	else
    		printf("no answer");
    	return 0;
    }
    

     

    实验结果:

    BinarySearch1:

    BinarySearch2:

    心得与体会:

    1. 理解分治算法的概念和基本要素;
    2. 理解递归的概念;
    3. 掌握设计有效算法的分治策略;
    4. 通过二分搜索技术学习分治策略设计技巧;
    5. 分析二分算法的时间和空间复杂度;
    6. 通过不同方式的二分算法增进对分治算法的理解。

     

    参考文章

    https://blog.csdn.net/zsnowwolfy/article/details/81039836

    https://blog.csdn.net/weixin_45929067/article/details/104781020

    展开全文
  • 测试过程实验中出现的问题错误解决...签名 年 月 日 评语与成绩 教师签名 年 月 日 洛阳师范学院信息技术学院 软件实验报告 专业软件工程 课程计算机算法分析与设计 学号121164040 姓名董亚兵 班级12级软件工程 实验
  • 哈工程——算法实验代码&报告
  • 必做:n 用分治思想设计实现二分搜索、合并排序,并且用不同数据量进行实验对比分析。 选做:阶乘(递归与分治)。
  • 感知器算法 感知器算法是通过训练模式的迭代和学习算法 产生线性可的模式判别函数 感知器 算法就是通过对训练模式样本集的学习得出判别函数的系数解在本次实验中我们主 要是采用硬限幅函数进行分类 感知器的训练...
  • 华中科技大学计算机学院大二下算法上机实验报告——二分检索树
  • 分治算法实验报告

    2012-12-15 20:31:27
    分值算法实验报告,简单易懂,适合初学者而且不愿意去花大心思的人
  • 文章目录一、顺序查找算法二、折半查找算法二分查找) 一、顺序查找算法 1、算法核心 在顺序表ST中顺序查找其关键字等于key的元素,若找到,则函数值为该元素所在元素表中的位置。 2、实现过程(详解在每一步的...
  • 动 态 内 存 配 算 法 实 验 报 告 院系:计算机与通信工程学院 班级:计科08-1班 姓名:胡太祥 学号:200807010112 一实验题目动态内存分配算法 二实验目的 深入了解动态分区存储管理方式内存分配与回收的实现 三...
  • 算法与程序设计实验报告二 4 学时 实验目的 1 掌握迭代算法的三方面工作 2 了解递推算法掌握递推算法的思想 3 掌握递归算法的程序编写 4 了解分治算法的思想 5 熟练使用二分查找方法实现代码的编写 实验内容 1 n!...
  • 合工大数据结构C++二分查找实验报告Visio流程图
  • 实验内容 编写一个简单的程序,实现单源最短路径问题。 编写一段程序,实现找零。 【问题描述】当前有面值分别为2角5,1角,5,1的硬币,请给出找n钱的最佳方案(要求找出的硬币数目最少)。 编写程序...
  • 山东科技大学计算方法实验 非线性方程求根实验报告完整版,C语言编程+流程图+运行结果 进一步熟练掌握求解非线性方程的二分法与Newton迭代法。 掌握二分法与Newton迭代法的算法,能运用程序设计语言和此方法编制...
  • PAGE PAGE 12 姓名 姓名 学号 班级 指导老师 李敏 算法设计与分析基础 实验报告 实验一递归与分治 [实验目的] 1.理解递归算法的思想和递归程序的执行过程并能熟练编写递归程序 2.掌握分治算法的思想对给定的问题能...
  • 算法与程序设计实验报告二(4学时) 实验目的 1 掌握迭代算法的三方面工作 2 了解递推算法掌握递推算法的思想 3 掌握递归算法的程序编写 4 了解分治算法的思想 5 熟练使用二分查找方法实现代码的编写 实验内容 1n!...
  • 数据结构课程设计 各种排序算法比较 课程设计 课程数据结构 题目排序算法比较 专业班级 姓名 学号 设计时间 指导教师 设计题目 排序算法比较 运行环境软硬件环境 操作系统 windows 运行环境vc6.0 三 算法设计的...
  • 梯度算法实验报告

    千次阅读 2020-09-23 22:40:53
    机器学习算法的数学解析与python实现—1.4机器学习的基本概念 1.常用函数 1.1假设函数(Hypothesis Function) 用H(x)表示,类似于泰坦尼克号上的锅炉,数据就是源源不断填入锅炉的燃料,锅炉带动机器运行使整个轮船...
  • 实验三 决策树算法实验实验报告

    千次阅读 2021-04-24 21:03:25
    实验三决策树算法实验一、实验目的:熟悉和掌握决策树的分类原理、实质和过程;掌握典型的学习算法和实现技术。、实验原理: 决策树学习和分类.三、实验条件:四、实验内容:1 根据现实生活中的原型自己创建一个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 30,001
精华内容 12,000
关键字:

二分搜索算法实验报告