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

实验报告 分治与递归基本题一：基本递归算法一、实验目的与要求1、熟悉C/C+语言的集成开发环境；2、通过本实验加深对递归过程的理解二、实验内容：掌握递归算法的概念和基本思想，分析并掌握“整数划分”问题的递归算法。三、实验题任意输入一个整数，输出结果能够用递归方法实现整数的划分。四、算法思想对于数据n,递归计算最大加数等于x的划分个数+最大加数不大于x-1的划分个数。最大加数x从n开始，逐步变小为n-1,1。考虑增加一个自变量：对于数据n,最大加数n1不大于的划分个数记作。则有：五、代码实现#include stdafx.h#include#include#includeusing namespace std;int q(int n,int m);int main()int n;cout请输入要划分的整数：n;int p=q(n,n);cout正整数n有p种不同的划分endl;system(pause);return 0;int q(int n,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);六、运行结果六、实验小结 通过本次试验：1、 熟悉了C/C+语言的集成开发环境；2、 通过本实验加深了对递归过程的理解基本题二：二分搜索一、实验目的与要求1、熟悉二分搜索算法；2、初步掌握分治算法；二、实验题1、设a0:n-1是一个已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素的位置I和大于x的最小元素位置j。当搜索元素在数组中时，I和j相同，均为x在数组中的位置。2、设有n个不同的整数排好序后存放于t0:n-1中，若存在一个下标i，0in，使得ti=i，设计一个有效的算法找到这个下标。要求算法在最坏的情况下的计算时间为O（logn）。三、算法思想将个元素分成个数大致相同的两半，取与作比较。 算法终止， 在数组的左半部继续搜索 ， 在数组的右半部继续搜索。四、代码实现1、 #include stdafx.h#include #include #includeusing namespace std;bool BinarySearch(int a,int n,int x,int &i,int &j);int main() int a=1,2,4,6,8,10,32,56,67,78,89; int n,i,j,x; n=sizeof(a)/4; cout数组a为：; for(int m=0;mn;m+) coutam ; while(1) coutendlx; if(BinarySearch(a,n,x,i,j) cout能找到,该数下标为iendl; else cout找不到，小于该数的最大数的下标为i，大于该数的最小数的下标为jendl; system(pause); return 0;bool BinarySearch(int a,int n,int x,int &i,int &j) int left=0; int right=n-1; while(leftamid) left=mid+1; else right=mid-1; if(aleft=x) i=j=left; return true; if(xaleft) i=left-1; j=left; else i=left; j=left+1; return false;2、 #include stdafx.h#include #include using namespace std;bool BinarySearch(int a,int n,int &i);int main()int a=-1,0,1,3,8,10,32,56,67,78,89; int n,i; n=sizeof(a)/4;cout数组a为：; for(int m=0;mn;m+) coutam ; if(BinarySearch(a,n,i) coutendl能找到值等于下标的数组元素，该元素为:iendl; else cout找不到;system(pause); return 0;bool BinarySearch(int a,int n,int &i) int left=0; int right=n-1; while(leftright) int mid=(left+right)/2; if(mid=amid) i=mid; return true; if(midamid) right=mid-1; else left=mid+1; if(aleft=left) i=left; return true; return false;五、运行结果1、2、六、实验小结 通过本次试验：1、熟悉了二分搜索算法；2、初步掌握了分治算法；提高题一： 用分治法实现元素选择一、实验要求与目的1、了解分治法的基本思想，掌握递归程序编写方法；2、使用分治法编程，求解线形序列中第k小元素。二、实验内容 1、给定线形序列集中n个元素和一个整数k，1kn，输出这n个元素中第k小元素的值及其位置。2、简述该算法的原理、步骤。对该算法与直接排序查找进行比较。3、编写并调试程序。4、测试要求：元素个数不少于100；分三种情况：k=1、k=n和k=中位数。三、算法思想随机产生支点J，对输入数组进行划分为a和b两段，然后计算a部分的元素个数j: 如果kj，则a段的所有元素都比第k小元素还要小，第k小元素落在b段，为b段中的第k-j小元素（-j的含义是去掉a段的元素总个数）直接选择排序：得到最小的数，需要次比较；得到第二小的数，需要 次比较；得到第小的数，需要次比较因此，总比较次数为，其时间复杂性为。四、代码实现#include stdafx.h#include #include #include using namespace std;int partition(int a,int low,int high) int first = low; int last = high; int m=rand()%high; int key = am; am=afirst; afirst=key; while(first last) while(first = key) -last; afirst = alast; while(first last & afirst = key) +first; alast = afirst; alast = key; return first;int select(int a,int p,int r,int k) if(p=r) return ap; int i=partition(a,p,r); int j=i-p+1; if(k=j) return select(a,p,i,j); else return select(a,i+1,r,k-j);int main() while(1) int n; coutn; coutendl; int *a=new intn; for(int i=0;in;i+) ai=rand()%1000; for(int i=1;i=n;i+) cout ai-1 ;if (i%10=0)coutendl; co