实验一 递归与分治策略算法设计与实现实验报告

实验报告题目实验一递归与分治策略一、实验目的1．加深学生对分治法算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；2．提高学生利用课堂所学知识解决实际问题的能力；3．提高学生综合应用所学知识解决实际问题的能力。

二、实验内容设计一个递归和分治算法，找出数组的最大元素，找出x在数组A中出现的次数。

三、实验要求（1）用分治法求解…问题；（2）再选择自己熟悉的其它方法求解本问题；（3）上机实现所设计的所有算法；四、实验过程设计（算法设计过程）1.设计一个递归算法，找出数组的最大元素。

2.设计一个分治算法，找出x在数组A中出现的次数。

3.写一个主函数，调用上述算法。

五、实验结果分析（分析时空复杂性，设计测试用例及测试结果）时间复杂性：最好情况下，O(n)最坏情况下：O(nlog(n)空间复杂性分析：O(n)六、实验体会通过写递归与分治策略实验，更加清楚的知道它的运行机理，分治法解题的一般步骤：（1）分解，将要解决的问题划分成若干规模较小的同类问题；（2）求解，当子问题划分得足够小时，用较简单的方法解决；（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。

做实验重在动手动脑，还是要多写写实验，才是硬道理。

七、附录：（源代码）#include"stdio.h"#define ElemType intint count(ElemType a[],int i,int j,ElemType x){int k=0,mid; //k用来计数，记录数组中x出现的次数if(i==j){if(a[i]==x) k++;return k;}else{mid=(i+j)/2;k+=count(a,i,mid,x);k+=count(a,mid+1,j,x);}return k;}ElemType Maxitem(ElemType a[],int n){ElemType max=a[n-1],j;if(n==1){max=a[n-1];return max;}else{j=Maxitem(a,n-1);if(j>max) max=j;return max;}}void main(void){ElemType a[]={1,5,2,7,3,7,4,8,9,5,4,544,2,4,123};ElemType b;ElemType x;int n;b=Maxitem(a,15);printf("数组的最大元素为%d\n",b);printf("输入想要计数的数组元素:\n");scanf("%d",&x);n=count(a,0,14,x);printf("%d在数组中出现的次数为%d次\n",x,n);}实验二动态规划——求解最优问题一、实验目的1．加深学生对动态规划算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；2．提高学生利用课堂所学知识解决实际问题的能力；3．提高学生综合应用所学知识解决实际问题的能力。

应用数学学院信息安全专业班学号姓名实验题目递归与分治法综合实验评分表实验报告一、实验目的与要求1.掌握递归算法的设计思想2.掌握分治法设计算法的一般过程3.理解并掌握算法渐近时间复杂度的分析方法二、实验内容1、折半查找的递归算法（1）源程序代码#include <StdAfx.h>#include <iostream>using namespace std;int bin_search(int key[],int low, int high,int k){int mid;if(low>high)return -1;else{mid = (low+high) / 2;if(key[mid]==k)return mid;if(k>key[mid])return bin_search(key,mid+1,high,k);elsereturn bin_search(key,low,mid-1,k);}}int main(){int n , i , addr;int A[10] = {2,3,5,7,8,10,12,15,19,21};cout << "在下面的10个整数中进行查找" << endl;for(i=0;i<10;i++){cout << A[i] << " " ;}cout << endl << endl << "请输入一个要查找的整数" << endl;cin >> n;addr = bin_search(A,0,9,n);if(-1 != addr)cout << endl << n << "是上述整数中的第" << addr << "个数" << endl;elsecout << endl << n << "不在上述的整数中" << endl << endl;getchar();return 0;}（2）运行界面①查找成功②查找失败2、用分治法求x的n次方，要求时间复杂度为O(lgn)（1）源程序代码#include <StdAfx.h>#include <iostream>using namespace std;int Pow(int x, int n){if (n == 1)return x;else if (n > 1){int s;int m = n / 2;s = Pow (x, m);if (n % 2 == 0)return (s * s);elsereturn (s * s * x);}}int main(){int x, n;cout << "你将进行x的n次方计算" << endl << endl;cout << "请输入x：" << endl;cin >> x;cout << "请输入n：" << endl;cin >> n;cout << endl << "计算结果：" << Pow(x, n) << endl << endl;return 0;}（2）运行界面3、自然合并排序算法（1）源程序代码#include "StdAfx.h"#include <iostream>using namespace std;const int SIZE = 100;int arr[SIZE];int rec[SIZE];void merge(int fir,int end,int mid);int pass(int n);void mergeSort(int n);void mergeSort(int n){int num=pass(n);while(num!=2){for(int i=0;i<num;i+=2)merge(rec[i],rec[i+2]-1,rec[i+1]-1);num=pass(n);}}void merge(int fir,int end,int mid){int tempArr[SIZE];int fir1=fir,fir2=mid+1;for(int i=fir;i<=end;i++){if(fir1>mid)tempArr[i]=arr[fir2++];else if(fir2>end)tempArr[i]=arr[fir1++];else if(arr[fir1]>arr[fir2])tempArr[i]=arr[fir2++];elsetempArr[i]=arr[fir1++];}for(int i=fir;i<=end;i++)arr[i]=tempArr[i];}int pass(int n){int num=0;int biger=arr[0];rec[num++]=0;for(int i=1;i<n;i++){if(arr[i]>=biger)biger=arr[i];else {rec[num++]=i;biger=arr[i];}}rec[num++]=n;return num;}int main(){int n;cout<<"请输入需要排序的整数个数："<<endl;while(cin>>n){for(int i=0;i<n;i++){cout<<"请输入整数："<<endl;cin>>arr[i];}mergeSort(n);cout<<"排序结果为："<<endl;for(int i=0;i<n;i++){cout<<arr[i]<<" ";}cout<<endl<<endl;cout<<"请输入需要排序的整数个数："<<endl;}return 0;}（2）运行界面三、问题与讨论问题：分治法能解决的问题一般具有什么特征？解答：任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。

递归与分治实验报告班级：计科1102 姓名：赵春晓学号：2011310200631实验目的：进一步掌握递归与分治算法的设计思想，通过实际问题来应用递归与分治设计算法。

实际问题：1集合划分问题，2输油管道问题，3邮局选址问题，4整数因子分解问题，5众数问题。

问题1：集合划分算法思想：对于n个元素的集合，可以划分为由m个子集构成的集合，例如{{1,2}{3,4}}就是由2个子集构成的非空子集。

假设f（n，m）表示将n个元素划分成由m个子集构成的集合的个数。

那么1）若m == 1 ，则f（n，m）= 1 ；2）若n == m ，则f（n，m）= 1 ；3）若不是上面两种情况则有下面两种情况构成：3.1）向n-1个元素划分成的m个集合里面添加一个新的元素，则有m*f(n-1,m)种方法；3.2）向n-1个元素划分成的m-1个集合里添加一个由一个元素形成的独立的集合，则有f(n-1,m-1)种方法。

实验代码：#include<iostream>#include<fstream>using namespace std ;int jihehuafen( int n , int m ){if( m == 1 || n == m )return 1 ;elsereturn jihehuafen( n - 1 , m - 1 ) + m*jihehuafen( n - 1 , m ) ;}int main(){ifstream fin("C:/input.txt") ;ofstream fout("C:/output.txt") ;int N , M , num ;fin >> N >> M ;num = jihehuafen( N , M) ;fout << num << endl ;return 0 ;}问题2：输油管道算法思想：由于主管道由东向西铺设。

《算法设计与分析》实验报告实验一递归与分治策略应用基础学号：**************姓名：*************班级：*************日期：2014-2015学年第1学期第九周一、实验目的1、理解递归的概念和分治法的基本思想2、了解适用递归与分治策略的问题类型，并能设计相应的分治策略算法3、掌握递归与分治算法时间空间复杂度分析，以及问题复杂性分析方法二、实验内容任务：以下题目要求应用递归与分治策略设计解决方案，本次实验成绩按百分制计，完成各小题的得分如下，每小题要求算法描述准确且程序运行正确。

1、求n个元素的全排。

（30分）2、解决一个2k*2k的特殊棋牌上的L型骨牌覆盖问题。

（30分）3、设有n=2k个运动员要进行网球循环赛。

设计一个满足要求的比赛日程表。

（40分）提交结果：算法设计分析思路、源代码及其分析说明和测试运行报告。

三、设计分析四、算法描述及程序五、测试与分析六、实验总结与体会#include "iostream"using namespace std;#define N 100void Perm(int* list, int k, int m){if (k == m){for (int i=0; i<m; i++)cout << list[i] << " ";cout << endl;return;}else{for (int i=m; i<k; i++){swap(list[m], list[i]);Perm(list, k, m+1);swap(list[m], list[i]);}}}void swap(int a,int b){int temp;temp=a;a=b;b=temp;}int main(){int i,n;int a[N];cout<<"请输入排列数据总个数：";cin>>n;cout<<"请输入数据：";for(i=0;i<n;i++){cin>>a[i];}cout<<"该数据的全排列："<<endl;Perm(a,n,0);return 0;}《算法设计与分析》实验报告实验二递归与分治策略应用提高学号：**************姓名：*************班级：*************日期：2014-2015学年第1学期一、实验目的1、深入理解递归的概念和分治法的基本思想2、正确使用递归与分治策略设计相应的问题的算法3、掌握递归与分治算法时间空间复杂度分析，以及问题复杂性分析方法二、实验内容任务：从以下题目中任选一题完成，要求应用递归与分治策略设计解决方案。

竭诚为您提供优质文档/双击可除递归与分治实验报告篇一：实验一递归与分治算法编程-实验报告纸南京信息工程大学实验（实习）报告实验（实习）名称递归与分治算法编程实验（实习）日期得分指导教师院专业年级班次姓名学号1．实验目的：1）掌握递归与分治策略的基本思想2）掌握递归算法在阶乘函数、Ackerman函数、整数划分等问题上的应用3）掌握二分查找、合并排序、快速排序等问题的分治算法实现4）熟悉myeclipse或eclipse等Java开发工具的使用。

2．实验内容：1）采用myeclipse或eclipse编程实现基于分治策略的二分查找算法。

2）采用myeclipse或eclipse编程实现基于分治策略的合并排序算法。

3）采用myeclipse或eclipse编程实现基于分治策略的合并排序算法。

3．实验步骤二分查找publicclasssorting{publicstaticintbinarysearch(int[]a,intx,intn){intle ft=0;intright=n-1;while(left intmiddle=(left+right)/2;if(x==a[middle])returnmiddle;if(x>a[middle])left=middle+1;elseright=middle-1;}return-1;}publicstaticvoidmain(stringargs[]){intx,n;inta[]={1,3,4,5,6,13,25};x=6;n=7;ints;s=binarysearch(a,x,n);system.out.println(s);合并排序publicclassmergesort{publicstaticvoidmergesort(int[]a){}publicstaticvoid mergepass(int[]x,int[]y,ints){}publicstaticvoidmerg e(int[]c,int[]d,intl,intm,intr){inti=1,j=m+1,k=1;in ti=0;while(i }}if(c[i]-(c[j])m)for(intq=j;q快速排序publicclassQsort{privatestaticvoidqsort(inta[],intp,intr){}privatest aticintpartition(inta[],intp,intr){inti=p;intj=r+1; intx=a[p];inttemp;while(true){while((a[++i]-x)0);if (i>=j)break;temp=a[i];if(p }}}a[j]=temp;mymath.s wap(a,i,j);//a[p]=a[j];a[j]=x;returnj;publicstaticv oidmain(string[]args){}inta[]={4,2,7,9,1};qsort(a,0,4);for(inti=0;;i++){}s ystem.out.println(a[i]);4．实验分析和总结掌握了递归与分治策略的基本思想掌握了递归算法在阶乘函数、Ackerman函数、整数划分等问题上的应用掌握了二分查找、合并排序、快速排序等问题的分治算法实现熟悉了myeclipse或eclipse等Java开发工具的使用。

《算法设计与分析》实验指导实验一分治与递归一、实验目的：1. 理解递归的概念。

2. 掌握设计有效算法的分治策略。

3. 掌握C++面向对象编程方法。

二、实验指导1. 分治法的总体思想求解一个复杂问题可以将其分解成若干个子问题，子问题还可以进一步分解成更小的问题，直到分解所得的小问题是一些基本问题，并且其求解方法是已知的，可以直接求解为止。

分治法作为一种算法设计策略，要求分解所得的子问题是同类问题，并要求原问题的解可以通过组合子问题的解来获取。

分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效的算法。

2. 分治法的基本步骤divide-and-conquer(P){if ( | P | <= n0) adhoc(P); //解决小规模的问题divide P into smaller subinstances P1,P2,...,Pk；//分解问题for (i=1,i<=k,i++)yi=divide-and-conquer(Pi); //递归的解各子问题return merge(y1,...,yk); //将各子问题的解合并为原问题的解}3. C++类定义例class Complex{public:Complex( ):real(0),imag(0) {} //构造函数Complex(double r,double i):real(r),imag(i) {} //构造函数Complex operator + (Complex c2); //重载“+”运算符operator double( ) //重载类型转换运算符{return real;}friend ostream& operator << (ostream&,Complex&); //重载流插入运算符“<<”private:double real;double imag;};三、实验内容及要求：在程序中创建一个学生对象数组并初始化数据，完成如下编程任务。

实验一我保证没有抄袭别人作业!1.实验题目必做：n 用分治思想设计实现二分搜索、合并排序，并且用不同数据量进行实验对比分析。

选做：阶乘（递归与分治）。

2.实验目的掌握设计算法的分治策略,通过实验学习分治策略设计技巧, 理解递归的概念验证二分搜索的时间复杂度。

掌握算法效率的分析和实验验证方法。

3.算法设计3.1 分治法基本思想将一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题相同。

然后递归的解这些子问题，然后将这些子问题的解合并得到原问题的解。

3.2二分搜索技术分解（devide）：将n个元素分成个数大致相同的两半。

此时，原问题a[n]->子问题a[1,n/2]与a[2/n,n] 解决（conquer）:取a[n/2]与欲查找的x作比较。

如果x=a[n/2]，则找到x，算法终止。

如果x<a[n/2]，则我们只要在数组a的左半部继续搜索x。

如果x>a[n/2]，则我们只要在数组a的右半部继续搜索x。

合并（combine）：此结果无需合并。

3.3合并排序分解（devide）：将n个元素分成个数大致相同的两半。

此时，原问题a[n]->子问题a[1,n/2]与a[2/n,n] 解决（conquer）:递归解n/2规模的子问题合并（combine）：合并已排好序的两部分进行合并。

3.4快速排序分解（devide）：找到基准元素，将数组分为三部分，两段。

此时，原问题a[p,r]->子问题a[p,q-1]、a[q]、a[q+1,r]。

解决（conquer）:通过递归调用快速排序，对数组a[p,q-1]与a[q+1,r]进行排序。

合并（combine）：此结果无需合并，因为子数组都是原址排序得，所以不需要合并操作。

3.5阶乘分解（devide）：将n!分成n*(n-1)!,每次使其规模减少一。

解决（conquer）:如果n=0，则输出结果1。

如果n=1，则输出结果1。

算法设计与分析：递归与分治法-实验报告(总8页)实验目的：掌握递归与分治法的基本思想和应用，学会设计和实现递归算法和分治算法，能够分析和评价算法的时间复杂度和空间复杂度。

实验内容：1.递归算法的设计与实现3.算法的时间复杂度和空间复杂度分析实验步骤：1）递归定义：一个函数或过程，在其定义或实现中，直接或间接地调用自身的方法，被成为递归。

递归算法是一种控制结构，它包含了解决问题的基础情境，也包含了递归处理的情境。

2）递归特点：递归算法具有以下特点：①依赖于递归问题的部分解被划分为若干较小的部分。

②问题的规模可以通过递推式递减，最终递归终止。

③当问题的规模足够小时，可以直接求解。

3）递归实现步骤：①确定函数的定义②确定递归终止条件③确定递归调用的过程4）经典实例：斐波那契数列递推式：f(n) = f(n-1) + f(n-2)int fib(int n) {if (n <= 0)return 0;else}5）优化递归算法：避免重复计算例如，上述斐波那契数列的递归算法会重复计算一些中间结果，影响效率。

可以使用动态规划技术，将算法改为非递归形式。

int f1 = 0, f2 = 1;for (int i = 2; i <= n; i++) {f1 = f2;使用循环避免递归，重复计算可以大大减少，提高效率。

1）分治算法的定义：将原问题分解成若干个规模较小且类似的子问题，递归求解子问题，然后合并各子问题得到原问题的解。

2）分治算法流程：②将问题分解成若干个规模较小的子问题。

③递归地解决各子问题。

④将各子问题的解合并成原问题的解。

3）分治算法实例：归并排序归并排序是一种基于分治思想的经典排序算法。

排序流程：②分别对各子数组递归进行归并排序。

③将已经排序好的各子数组合并成最终的排序结果。

实现源代码：void mergeSort(int* arr, int left, int right) {if (left >= right)while (i <= mid && j <= right)temp[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];temp[k++] = arr[i++];1) 时间复杂度的概念：指完成算法所需的计算次数或操作次数。

实验报告院部：计算机信息与科学专业班级：计科1703学号：学生姓名：学期： 2019-2020-2}printf("\n\n");bubble(a, n);printf("冒泡递增排列为：\n");for (i = 0; i < n; i++) {printf("%d ", a[i]);}printf("\n");printf("\n");printf("99乘法表如下:\n");chengfa(1, 1);system("pause");return 0;}图1-1 运行结果printf("您输入的字符串超过最大长度,请重新输入!");scanf("%s", X);}printf("请输入字符串Y:");scanf("%s", Y);while (strlen(Y) > 200){printf("您输入的字符串超过最大长度,请重新输入!");scanf("%s", Y);}s = LCS(X, Y);printf("X和Y的LCS数: %d \n", s);printf("----------------分割线----------------\n"); printf("投资最大利润问题：\n");profit();}图2-1 运行结果图3-1 运行结果五实验小节通过本次实验，充分理解了动态规划的基本思想和程序的执行过程，并且能熟练编写相应的程序；同时，在编程的过程中，进一步加深理解动态规划算法的两个基本要素最优子结构性质和子问题的重叠性质，对上一次实验所学到的知识进行了进一步的巩固加强，学会了规避一些逻辑上的错误；熟练地掌握了典型的动态规划问题，能够运用动态规划思想分析问题的一般方法，对较简单的问题能够正确分析，设计出动态规划算法，并且能快速编程实现。

实验一递归与分治法
一、实验目的：
利用递归与分治法解决简单问题，加深对分治算法的理解与掌握。

二、实验内容：
利用递归与分治法解决Strassen矩阵乘法问题。

三、实验原理与方法：
递归与分治法。

四、实验条件：
具有C语言编程平台、JAVA语言编程平台的计算机系统；Internet环境。

五、实验步骤：
1、设计解决“Strassen矩阵乘法”的分治算法；
2、编程实现“Strassen矩阵乘法”分治算法。

六、实验注意事项：
算法设计要求能解决一定规模的问题，Strassen矩阵乘法中矩阵阶N可达16；递归分治维数为2*2；算法实现要有一定的测试量和等价覆盖，有一定的健壮性。

七、实验报告要求：
1、实验报告格式应使用院系实验报告参考格式。

2、“一、实验预习部分”，主要填写实验目的、实验内容、实验原理、实验条件、算法设计等，其中算法设计是主要部分。

3、“二、实验过程记录”，主要记录实验的步骤与方法，主体部分是算法的实现，程序运行结果等，要有算法实现核心代码。

4、“三、实验结果与讨论”，主要总结做了什么，结果怎样，遇到哪些重要问题，如何解决的，有哪些技术提高，还有哪些问题有待进一步研究。

5、实验报告用语应尽量采用书面技术语言，以求简明准确。

6、实验报告应独立完成，在规定时间内提交。

1。

淮海工学院计算机工程学院实验报告书课程名：《算法分析与设计》题目：实验1 递归与分治算法班级：软件102班学号：111003215姓名：鹿迅实验1 递归与分治算法实验目的和要求（1）进一步掌握递归算法的设计思想以及递归程序的调试技术；（2）理解这样一个观点：分治与递归经常同时应用在算法设计之中。

（3）分别用蛮力法和分治法求解最近对问题；（4）分析算法的时间性能，设计实验程序验证分析结论。

实验内容设p1=(x1, y1), p2=(x2, y2), …, pn=(xn, yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对。

实验环境Turbo C 或VC++实验学时2学时，必做实验数据结构与算法#include<iostream>#include<Cmath>#include<algorithm>#define N 100using namespace std;struct point{int x,y;};bool cmpx(point a,point b){return a.x<b.x;}bool cmpy(point a,point b){return a.y>b.y;}{int k;k=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);return k;}double min(double d1,double d2){if(d1<=d2)return d1;elsereturn d2;}bool different(point p[],int n,int start,int end){for(int i=start;i<end;i++){if(p[i].x==p[end].x&&p[i].y==p[end].y)return true;}return false;}int ClosestPoints1(point p[],int n,point & one,point & two)//求出两最近点的相关信息{int d=9999;for(int i=0;i<n;i++)for(int j=i+1;j<n;j++){int temp=Sqrt(p[i],p[j]);if(temp<d){one=p[i];two=p[j];d=temp;}return d;}int ClosestPoints2(point S[],int n){if(n<2) return 10000;if(n==2){int d=Sqrt(S[0],S[1]);return d;}sort(S,S+n,cmpx);//按照X大小排序int m=S[n/2].x;int t=n/2;int i=0;point S1[5000],S2[5000];for(i=0;i<t;i++){S1[i]=S[i];}for(i=t;i<n;i++){S2[i-t]=S[i];}int d1=ClosestPoints2(S1,t);int d2=ClosestPoints2(S2,n-t);int d=min(d1,d2);point p1[N],p2[N];int j=0;int p1l=0,p2l=0;//对x坐标差值在2d之间的点进行归类，找到这些点for(i=0;i<t;i++){if(abs(S1[i].x-m)<d){p1[p1l]=S1[i];p1l++;}for(i=0;i<n-t;i++){if(abs(S2[i].x-m)<d){p2[p2l]=S2[i];p2l++;}}//对两个区间内的点沿Y坐标轴进行排序sort(p1,p1+p1l,cmpy);sort(p2,p2+p2l,cmpy);int md=9999;for(i=0;i<p1l;i++){for(j=0;fabs(p2[j].y-p1[i].y)<d;j++){int pd=Sqrt(p1[i],p2[j]);md=min(pd,md);}}return min(d,md);}void main(){point p[N],a,b;int n=20;int d;cout<<"please input the number of the points:";cin>>n;cout<<"the points:"<<endl;for(int i=0;i<n;i++){p[i].x=rand()%131;p[i].y=rand()%131;while(different(p,n,0,i)){p[i].y=rand()%50;}cout<<" ("<<p[i].x<<","<<p[i].y<<") "<<" ";}d=ClosestPoints1(p,n,a,b);cout<<endl;cout<<"蛮力法求最近点对："<<endl;cout<<"the distance of two points:"<<sqrt(d)<<endl;cout<<"the point ("<<a.x<<","<<a.y<<") the another point ("<<b.x<<","<<b.y<<")"<<endl;d=ClosestPoints2(p,n);cout<<"分治法求最近点对："<<endl;cout<<"the distance of two points:"<<sqrt(d)<<endl;cout<<" the point ("<<a.x<<","<<a.y<<") the another point ("<<b.x<<","<<b.y<<")"<<endl;cout<<"实验测试点数为："<<n<<endl;}核心源代码蛮力法核心源代码：int ClosestPoints1(point p[],int n,point & one,point & two)//蛮力法求出两最近点的相关信息{int d=9999;for(int i=0;i<n;i++)for(int j=i+1;j<n;j++){int temp=Sqrt(p[i],p[j]);if(temp<d){one=p[i];two=p[j];d=temp;}}return d;}int ClosestPoints2(point S[],int n){if(n<2) return 10000;if(n==2){int d=Sqrt(S[0],S[1]);return d;}sort(S,S+n,cmpx);//按照X大小排序int m=S[n/2].x;int t=n/2;int i=0;point S1[5000],S2[5000];for(i=0;i<t;i++){S1[i]=S[i];}for(i=t;i<n;i++){S2[i-t]=S[i];}int d1=ClosestPoints2(S1,t);int d2=ClosestPoints2(S2,n-t);int d=min(d1,d2);point p1[N],p2[N];int j=0;int p1l=0,p2l=0;//对x坐标差值在2d之间的点进行归类，找到这些点for(i=0;i<t;i++){if(abs(S1[i].x-m)<d){p1[p1l]=S1[i];p1l++;}}for(i=0;i<n-t;i++)if(abs(S2[i].x-m)<d){p2[p2l]=S2[i];p2l++;}}//对两个区间内的点沿Y坐标轴进行排序sort(p1,p1+p1l,cmpy);sort(p2,p2+p2l,cmpy);int md=9999;for(i=0;i<p1l;i++){for(j=0;fabs(p2[j].y-p1[i].y)<d;j++){int pd=Sqrt(p1[i],p2[j]);md=min(pd,md);}}return min(d,md);}实验结果实验体会通过这次实验，我深刻了解到分治法的实用性，有效性。

实验一分治与递归算法的应用一、实验目的1．掌握分治算法的基本思想（分-治-合）、技巧和效率分析方法。

2．熟练掌握用递归设计分治算法的基本步骤（基准与递归方程）。

3．学会利用分治算法解决实际问题。

二、实验内容1.问题描述：题目一：大整数乘法用分治算法编程实现两个n位十进制大整数的乘法运算。

题目二：线性时间选择给定n个元素和一个整数k，要求用O(n)时间找出这n个元素中第k小元素。

题目三：二分搜索算法设a[0:n-1]是一个已排好序的数组。

请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素的位置i和大于x的最小元素位置j。

当搜索元素在数组中时，i和j相同，均为x在数组中的位置。

并对自己的程序进行复杂性分析。

题目四：金块问题老板有一袋金块（共n块，n是2的幂（n≥2））,最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。

假设有一台比较重量的仪器，希望用最少的比较次数找出最重和最轻的金块。

并对自己的程序进行复杂性分析。

题目五：双色四圆盘梵塔问题与梵塔问题相同，设ABC是3个塔座，初始时塔座A上有四个圆盘，各圆盘从小到大编号为：1、2、3、4，奇数号圆盘为红色，偶数号圆盘为蓝色。

现要求将塔座A上的圆盘移到塔座C上，除满足梵塔问题的移动规则外，还必须满足：任何时刻不允许将同色圆盘叠在一起。

试设计一个算法，以最少次数完成上述移动，并输出每次移动的圆盘编号、起始塔座、目的塔座。

并对自己的程序进行复杂性分析。

题目六：桶排序问题明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N≤100），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。

然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。

请你协助明明完成“去重”与“排序”的工作，并对自己的程序进行复杂性分析。

【输入样例】1020 40 32 67 40 20 89 300 400 15【输出样例】815 20 32 40 67 89 300 4002.数据输入：个人设定，由键盘输入。

编写程序，实现线性时间内选择 n 个元素的中位数的算法。

并对于不同的 n，测试平均时间效率。

本问题属于线性选择问题的一个特例，可以使用分治法进行求解。

其基本思想是摹仿快速排序方法，对输入的数组进行划分，求出中位数所在的子数组，然后用递归的方法进行求解，最终可以求得问题的解。

将n 个输入元素根据随机选择的基准划分成2 个子数组，a[p:r]被划分成a[p:i]和a[i+1:r]两组，使得a[p:i]中每一个元素都不大于a[i+1:r] 中元素。

接着算法计算子数组a[p:i]中元素个数j，如果k<=j，则a[p:r] 中第k 个小元素落在子数组a[p:i]中元素均小于要找的第k小元素，因此要找的a[p:r]中第k 小元素是a[i+1:r]中的第k-j 小元素。

按照上述的方法递归的执行，直到当前数组中只剩下一个元素，就可以得到问题的解。

#include "iostream.h"#include "stdlib.h"#include "time.h"#include <sys/types.h>#include <sys/timeb.h>#include "windows.h"#include<stdio.h>int randomizedSel(int *,int ,int ,int );void main(){srand((unsigned int)time(NULL));_timeb time0,time1;int n;cout << "请输入数组的长度： ";cin >> n;cout << "请输入数组的每一个数： " << endl;int *a=new int[n];for(int i=0;i<n;i++)cin >> a[i];DWORD stime=GetTickCount();_ftime(&time0);int result=randomizedSel(a,0,n-1,(n+1)/2);DWORD Etime=GetTickCount();_ftime(&time1);cout << "结果为： " << result << endl;cout << litm*litm*1000<<endl;cout<<Etime-stime<<endl;}void swap(int *a,int i,int j){int temp=a[i];a[i]=a[j];a[j]=temp;}int partition(int *a,int p,int r){int i=p,j=r+1;int x=a[p];while(1){while(a[++i]<x && i<r);while(a[--j]>x);if(i>=j) break;swap(a,i,j);}a[p]=a[j];a[j]=x;return j;}int randomizedpar(int *a,int p,int r){int i=rand()%(r-p+1)+p;swap(a,i,p);return partition(a,p,r);}int randomizedSel(int *a,int p,int r,int k){if(p == r)return a[p];int i=randomizedpar(a,p,r);int j=i-p+1;if(k<=j) return randomizedSel(a,p,i,k);else return randomizedSel(a,i+1,r,k-j);}运行结果如下图所示：经过测试，当输入的数组长度不大时，执行时间几乎为零，当输入数组很大时，执行时间随之增大，与数组长度成正相关。

实验一 递归与分治策略一、实验目的（1）理解递归与分治策略算法设计思想和方法；（2）培养学生的动手能力。

二、实验工具（1）JDK1.8（2）Eclipse IDE for Java EE Developers三、实验题：1、设n 个不同的整数排好序后存于T[0:n-1]中。

若存在下标i ，n i <≤0，使得T[i]=i ，设计一个有效算法找到这个下标。

要求算法在最坏情况下的计算时间为)(log n O 。

2、设子数组]1-:0[k a 和]1:[-n k a 已排好序10-≤≤n k 。

试设计一个合并这两个子数组为排好序的数组]1:0[-n a 的算法，要求算法在最坏情况下的计算时间为)(n O ，且只用到)1(O 的辅助空间。

三、实验提示：1、由于n 个整数是不同的，因此对任意0≤i ＜n-1 有T[i]≤T[i+1]-1。

(1) 对于0＜i ＜n ，当T[i]>i 时，对任意的i ≤j ≤n-2 有T[j]≥T[i]+j-i>i+j-i=j 。

(2) 对于0＜i ＜n,当T[i]＜i 时，对任意的0≤j ≤i 有T[j]≤T[i] -i+j ＜i-i +j =j 。

由①和②可知，用二分搜索算法可以在)(log n O 时间内找到所要求的下标，伪代码如下：SEARCH(A,n)low <-- 0high <-- n-1while low < high doif A[middle] = middlethen return middleif A[middle] < middlethen low <-- middle + 1elsehigh <-- middle - 1middle <-- (low+high)/2if A[middle] = middlethen return middleelsereturn -12、算法：循环换位合并算法（1）向右循环换位合并向右循环换位合并算法首先用二分搜索算法在数组段]1:[-n k a 中搜索]0[a 的插入位置，即找到位数p 使得]1[]0[][+≤<p a a p a 。

实验一分治与递归算法的应用一、实验目的1．掌握分治算法的基本思想（分-治- 合）、技巧和效率分析方法。

2．熟练掌握用递归设计分治算法的基本步骤（基准与递归方程）。

3．学会利用分治算法解决实际问题。

二. 实验容金块问题老板有一袋金块（共n块，n是2的幕（n》2））,最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。

假设有一台比较重量的仪器，希望用最少的比较次数找出最重和最轻的金块。

并对自己的程序进行复杂性分析。

三. 问题分析:一般思路：假设袋中有n个金块。

可以用函数M a x （程序1 - 3 1）通过n-1 次比较找到最重的金块。

找到最重的金块后，可以从余下的n-1 个金块中用类似法通过n-2 次比较找出最轻的金块。

这样，比较的总次数为2n-3。

分治法：当n很小时，比如说，nW2,识别出最重和最轻的金块，一次比较就足够了。

当n较大时(n>2),第一步，把这袋金块平分成两个小袋A和B。

第二步，分别找出在A和B中最重和最轻的金块。

设A 中最重和最轻的金块分别为HA 与LA ，以此类推，B中最重和最轻的金块分别为HB和LB。

第三步，通过比较HA 和H B ，可以找到所有金块中最重的；通过比较LA 和LB，可以找到所有金块中最轻的。

在第二步中，若n> 2,则递归地应用分而治之方法程序设计据上述步骤, 可以得出程序1 4 - 1的非递归代码。

该程序用于寻找到数组w [ 0 : n - 1 ]中的最小数和最大数, 若n < 1 ,则程序返回f a l s e, 否则返回t r u e。

当n》1时，程序1 4 - 1给M i n和M a x置初值以使w [ M i n ]是最小的重量, w [ M a x ]为最大的重量。

首先处理nW 1的情况。

若n>1且为奇数，第一个重量w [ 0 ]将成为最小值和最大值的候选值,因此将有偶,数个重量值w [ 1 : n - 1 ]参与f o r 循环。

本科实验报告课程名称：算法设计与分析实验项目：递归与分治算法实验地点：计算机系实验楼110专业班级：物联网1601 学号：2016002105 学生姓名：俞梦真指导教师：郝晓丽2018年05月04 日实验一递归与分治算法1.1 实验目的与要求1．进一步熟悉C/C++语言的集成开发环境；2．通过本实验加深对递归与分治策略的理解和运用。

1.2 实验课时2学时1.3 实验原理分治（Divide-and-Conquer）的思想：一个规模为n的复杂问题的求解，可以划分成若干个规模小于n的子问题，再将子问题的解合并成原问题的解。

需要注意的是，分治法使用递归的思想。

划分后的每一个子问题与原问题的性质相同，可用相同的求解方法。

最后，当子问题规模足够小时，可以直接求解，然后逆求原问题的解。

1.4 实验题目1．上机题目：格雷码构造问题Gray码是一个长度为2n的序列。

序列无相同元素，每个元素都是长度为n的串，相邻元素恰好只有一位不同。

试设计一个算法对任意n构造相应的Gray码（分治、减治、变治皆可）。

对于给定的正整数n，格雷码为满足如下条件的一个编码序列。

（1）序列由2n个编码组成，每个编码都是长度为n的二进制位串。

（2）序列中无相同的编码。

（3）序列中位置相邻的两个编码恰有一位不同。

2．设计思想：根据格雷码的性质，找到他的规律，可发现，1位是0 1。

两位是00 01 11 10。

三位是000 001 011010 110 111 101 100。

n位是前n-1位的2倍个。

N-1个位前面加0，N-2为倒转再前面再加1。

3．代码设计：}}}int main(){int n;while(cin>>n){get_grad(n);for(int i=0;i<My_grad.size();i++)cout<<My_grad[i]<<endl;My_grad.clear();}return 0;}运行结果：1.5 思考题（1）递归的关键问题在哪里？答：1.递归式，就是如何将原问题划分成子问题。