int partition(int a[],int low,int high) {
int first = low; int last = high; int m=rand()%high; int key = a[m]; a[m]=a[first]; a[first]=key; while(first < last) {
if(mid==a[mid]) { i=mid;
return true; } if(mid<a[mid]) {
right=mid-1; else {
left=mid+1; } } if(a[left]==left) { i=left; return true; } return false; }五、运行结果 1、
cout <<a[i-1]<< " "; if (i%10==0)
cout<<endl; } cout<<endl; int k; cout<<"查找第 k 小的数，请输入 k："; cin>>k; select(a, 0, n-1,k); cout<<"第"<<k<<"小的数字为"<<a[k-1]<<endl; delete[] a; system("pause");
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;m<n;m++) cout<<a[m]<<" "; if(BinarySearch(a,n,i))
实验报告 分治与递归
中国矿业大学 计算机科学与技术学院 孟靖宇
基本题一：基本递归算法
一、实验目的与要求 1、熟悉 C/C++语言的集成开发环境； 2、通过本实验加深对递归过程的理解
二、实验内容：
掌握递归算法的概念和基本思想，分析并掌握“整数划分”问题的递归算法。 三、实验题
任意输入一个整数，输出结果能够用递归方法实现整数的划分。 四、算法思想
直接选择排序：得到最小的数，需要 (n 1) 次比较；得到第二小的数，需要 (n 2) 次
3n2 3 比较；得到第 k 小的数，需要 (n k) 次比较因此，总比较次数为 8 ，其时间
复杂性为 O(n2 ) 。
四、代码实现 #include "stdafx.h" #include <iostream> #include <cstdlib> #include <stdlib.h> using namespace std;
int main() {
while(1) { int n; cout<<"生成包含 n 个元素的数组，请输入 n："; cin>>n; cout<<endl; int *a=new int[n]; for(int i=0;i<n;i++) {
a[i]=rand()%1000; } for(int i=1;i<=n;i++) {
int left=0; int right=n-1; while(left<right) {
int mid=(left+right)/2; if(x==a[mid]) {
i=j=mid; return true; } if(x>a[mid]) { left=mid+1; } else {
right=mid-1; } } if(a[left]==x) { i=j=left; return true; } if(x<a[left]) { i=left-1; j=left; } else { i=left; j=left+1; } return false; } 2、 #include "stdafx.h" #include <iostream> #include <stdlib.h> using namespace std;
int n; cout<<"请输入要划分的整数："<<endl; cin>>n; int p=q(n,n); cout<<"正整数"<<n<<"有"<<p<<"种不同的划分"<<endl; system("pause");
return 0; } int q(int n,int m){
if((n<1)||(m<1)) return 0; if((n==1)||(m==1)) return 1; if(n<m) return q(n,n); if(n==m) return q(n,m-1)+1; return q(n,m-1)+q(n-m,m); } 六、运行结果
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;m<n;m++) {
cout<<a[m]<<" "; } while(1) { cout<<endl<<"输入需要查找的数："; cin>>x; if(BinarySearch(a,n,x,i,j)) {
对于数据 n,递归计算最大加数等于 x 的划分个数+最大加数不大于 x-1 的划分个数。最 大加数 x 从 n 开始，逐步变小为 n-1,…,1。
考虑增加一个自变量：对于数据 n,最大加数 n1 不大于 m 的划分个数记作 q(n, m) 。则
有：
1
n 1, m 1
q (n,
m)
q(n, n) 1 q(n, n 1)
2、
六、实验小结 通过本次试验： 1、熟悉了二分搜索算法； 2、初步掌握了分治算法；
提高题一： 用分治法实现元素选择
一、实验要求与目的 1、了解分治法的基本思想，掌握递归程序编写方法；
2、使用分治法编程，求解线形序列中第 k 小元素。 二、实验内容
1、给定线形序列集中 n 个元素和一个整数 k，1≤k≤n，输出这 n 个元素中第 k 小元素 的值及其位置。 2、简述该算法的原理、步骤。对该算法与直接排序查找进行比较。 3、编写并调试程序。 4、测试要求：元素个数不少于 100；分三种情况：k=1、k=n 和 k=中位数。 三、算法思想 随机产生支点 J，对输入数组进行划分为 a 和 b 两段，然后计算 a 部分的元素个数 j: 如果 k<=j，则第 k 小元素落在 a 段，为 a 段的第 k 小元素； 如果 k>j，则 a 段的所有元素都比第 k 小元素还要小，第 k 小元素落在 b 段，为 b 段中 的第 k-j 小元素（-j 的含义是去掉 a 段的元素总个数）
六、实验小结 通过本次试验： 1、 熟悉了 C/C++语言的集成开发环境；
2、通过本实验加深了对递归过程的理解
基本题二：二分搜索
一、实验目的与要求 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，使得
1、 #include "stdafx.h" #include <iostream> #include <stdlib.h> #include<windows.h>
using namespace std; bool BinarySearch(int a[],int n,int x,int &i,int &j);
cout<<"能找到,该数下标为"<<i<<endl; } else {
cout<<"找不到，小于该数的最大数的下标为"<<i<<"，大于该数的最小数的下 标为"<<j<<endl;
} system("pause"); } return 0; }
bool BinarySearch(int a[],int n,int x,int &i,int &j) {
cout<<endl<<"能找到值等于下标的数组元素，该元素为:"<<i<<endl; else
cout<<"找不到"; system("pause"); return 0; }
bool BinarySearch(int a[],int n,int &i) {
int left=0; int right=n-1; while(left<right) { int mid=(left+right)/2;