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

实验报告分治与递归基本题一：基本递归算法一、实验目的与要求1、熟悉C/C++语言的集成开发环境；2、通过本实验加深对递归过程的理解二、实验内容：掌握递归算法的概念和基本思想，分析并掌握“整数划分”问题的递归算法。三、实验题任意输入一个整数，输出结果能够用递归方法实现整数的划分。四、算法思想对于数据n,递归计算最大加数等于x的划分个数+最大加数不大于x-1的划分个数。最大加数x从n开始，逐步变小为n-1,…,1。考虑增加一个自变量：对于数据n,最大加数n1不大于的划分个数记作。则有：五、代码实现#include stdafx.h#includeiostream#includestdlib.h#includewindows.husing namespace std;int q(intn,int m);int main(){int n;cout请输入要划分的整数：endl;cinn;int p=q(n,n);cout正整数n有p种不同的划分endl;system(pause);return 0;}int q(intn,int m){if((n1)||(m1)) return 0;if((n==1)||(m==1)) return 1;if(nm) return q(n,n);if(n==m) return q(n,m-1)+1;return q(n,m-1)+q(n-m,m);}六、运行结果六、实验小结通过本次试验：熟悉了C/C++语言的集成开发环境；通过本实验加深了对递归过程的理解基本题二：二分有哪些信誉好的足球投注网站一、实验目的与要求1、熟悉二分有哪些信誉好的足球投注网站算法；2、初步掌握分治算法；二、实验题1、设a[0:n-1]是一个已排好序的数组。请改写二分有哪些信誉好的足球投注网站算法，使得当有哪些信誉好的足球投注网站元素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#include iostream#include stdlib.h#includewindows.husing namespace std;boolBinarySearch(int a[],intn,intx,int i,int j);int main(){int a[]={1,2,4,6,8,10,32,56,67,78,89};intn,i,j,x; n=sizeof(a)/4;cout数组a为：;for(int m=0;mn;m++) {couta[m] ; }while(1){coutendl输入需要查找的数：;cinx;if(BinarySearch(a,n,x,i,j)) {cout能找到,该数下标为iendl; }else {cout找不到，小于该数的最大数的下标为i，大于该数的最小数的下标为jendl; }system(pause);}return 0;}boolBinarySearch(int a[],intn,intx,int i,int j){int left=0;int right=n-1;while(leftright) {int mid=(left+right)/2;if(x==a[mid]) { i=j=mid;return true; }if(xa[mid]) {left=mid+1; }else {right=mid-1; } }if(a[left]==x) { i=j=left;return true; }if(xa[left]) { i=left-1; j=left; }else { i=left; j=left+1; }return false;}2、#include stdafx.h#include iostream#include stdlib.husing namespace std;boolBinarySearch(int a[],intn,int i);int main(){int a[]={-1,0,1,3,8,10,32,56,67,78,89};intn,i; n=sizeof(a)/4;cou