分治,递归,二分查找,快速排序

《分治,递归,二分查找,快速排序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验报告分治与递归基本题一：基本递归算法一、实验目的与要求1、熟悉C/C++语言的集成开发环境；2、通过本实验加深对递归过程的理解二、实验内容：掌握递归算法的概念和基本思想，分析并掌握“整数划分”问题的递归算法。三、实验题任意输入一个整数，输出结果能够用递归方法实现整数的划分。四、算法思想对于数据n,递归计算最大加数等于x的划分个数+最大加数不大于x-1的划分个数。最大加数x从n开始，逐步变小为n-1,…,1。考虑增加一个自变量：对于数据n,最大加数n1不大于的划分个数记作。则有：五、代码实现#

2、include"stdafx.h"#include#include#includeusingnamespacestd;intq(intn,intm);intmain(){intn;cout<<"请输入要划分的整数："<>n;intp=q(n,n);cout<<"正整数"<

3、<1)

4、

5、(m<1))return0;if((n==1)

6、

7、(m==1))return1;if(n

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"stdafx.h"#incl

9、ude#include#includeusingnamespacestd;boolBinarySearch(inta[],intn,intx,int&i,int&j);intmain(){inta[]={1,2,4,6,8,10,32,56,67,78,89};intn,i,j,x;n=sizeof(a)/4;cout<<"数组a为：";for(intm=0;m

10、<>x;if(BinarySearch(a,n,x,i,j)){cout<<"能找到,该数下标为"<

11、right){intmid=(left+right)/2;if(x==a[mid]){i=j=mid;returntrue;}if(x>a[mid]){left=mid+1;}else{right=mid-1;}}if(a[left]==x){i=j=left;returntrue;}if(x#in

12、cludeusingnamespacestd;boolBinarySearch(inta[],intn,int&i);intmain(){inta[]={-1,0,1,3,8,10,32,56,67,78,89};intn,i;n=sizeof(a)/4;cout<<"数组a为：";for(intm=0;m