欢迎来到天天文库
浏览记录
ID:33409040
大小:333.50 KB
页数:11页
时间:2019-02-25
《数据结构域算法设计-实验一 分治与递归》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、实验一分治与递归基本题一:基本递归算法一、实验目的与要求1、熟悉C/C++语言的集成开发环境;2、通过本实验加深对递归过程的理解二、实验内容:掌握递归算法的概念和基本思想,分析并掌握“整数划分”问题的递归算法。三、实验题任意输入一个整数,输出结果能够用递归方法实现整数的划分。四、实验步骤1.理解算法思想和问题要求;2.编程实现题目要求;3.上机输入和调试自己所编的程序;4.验证分析实验结果;5.整理出实验报告。五.实验源代码:(1)//基本递归算法整数划分#include#includeusingnamespacestd;//intn;intinte
2、ger_split(intn,intm){if(m==1
3、
4、n==1){return1;}if(n=1;m--)//{count=integer_split(n,n);//}printf("%d",count);return0;}(2
5、)运行结果:Input:请输入一个待划分的整数Output:输出有多少种划分样例:Input:6Output:11;(3)算法思路:11/11首先要找出递归的公式来,首先分析几种简单的情况,n==1
6、
7、m==1可以直接得出结果为1;而当nm时,可以用q(n,m-1)+q(n-m,m),其中q(n-m,m表示的时当m固定后,求剩下可能的情况。参考下图:基本题二:二分搜索一、实验目的与要求1、熟悉二分搜索算法;2、初步掌握分治算法;二、实验题1、设a[0:n-1
8、]是一个已排好序的数组。请改写二分搜索算法,使得当搜索元素x不在数组中时,返回小于x的最大元素的位置I和大于x的最大元素位置j。当搜索元素在数组中时,I和j相同,均为x在数组中的位置。2、设有n个不同的整数排好序后存放于t[0:n-1]中,若存在一个下标I,0≤i<n,使得t[i]=i,设计一个有效的算法找到这个下标。要求算法在最坏的情况下的计算时间为O(logn)。三.(1)实验源代码:#include#include#includeusingnamespacestd;intn,x,i,j;voidBinarysearch(i
9、ntleft,intright,inta[]){i=left;j=right;if(i<=j){intmid=(i+j)/2;if(a[mid]==x)11/11{i=mid;j=mid;return;}if(a[mid]>x){j=mid-1;Binarysearch(i,j,a);}elseif(a[mid]10、){scanf("%d",&a[k]);}printf("请输入待查的一个数据值:");scanf("%d",&x);if(x>a[n-1]11、12、x13、分搜索,计算mid=left+right;若a[mid]的值小与待查元素值,则更新left=mid+1;反之,更新rightmid-1;若这个元素找不到,那么就便利到i>j的时刻点,跳出while循环,i与j分别表示大于待查元素和小于待查元素的下标.2、设有n个不同的整数排好序后存放于t[0:n-1]中,若存在一个下标I,0≤i<n,使得t[i]=i,设计一个有效的算法找到这个下标。要求算法在最坏的情况下的计算时间为O(logn)。(1)实验源
10、){scanf("%d",&a[k]);}printf("请输入待查的一个数据值:");scanf("%d",&x);if(x>a[n-1]
11、
12、x13、分搜索,计算mid=left+right;若a[mid]的值小与待查元素值,则更新left=mid+1;反之,更新rightmid-1;若这个元素找不到,那么就便利到i>j的时刻点,跳出while循环,i与j分别表示大于待查元素和小于待查元素的下标.2、设有n个不同的整数排好序后存放于t[0:n-1]中,若存在一个下标I,0≤i<n,使得t[i]=i,设计一个有效的算法找到这个下标。要求算法在最坏的情况下的计算时间为O(logn)。(1)实验源
13、分搜索,计算mid=left+right;若a[mid]的值小与待查元素值,则更新left=mid+1;反之,更新rightmid-1;若这个元素找不到,那么就便利到i>j的时刻点,跳出while循环,i与j分别表示大于待查元素和小于待查元素的下标.2、设有n个不同的整数排好序后存放于t[0:n-1]中,若存在一个下标I,0≤i<n,使得t[i]=i,设计一个有效的算法找到这个下标。要求算法在最坏的情况下的计算时间为O(logn)。(1)实验源
此文档下载收益归作者所有