递归与分治实验报告

递归与分治算法心得
递归与分治算法都是常用的算法思想，可以很好地解决复杂问题。

递归算法是通过将问题分解为相同或相似的子问题来解决整个问题，然后再逐步合并回原问题的过程。

递归算法通常需要明确边界条件，以确保递归能够正确地停止。

分治算法是将问题分解成若干个相同或相似的子问题，递归地解决这些子问题，然后合并这些子问题的解来解决原始问题。

通常，分治算法可以高效地解决问题，但需要注意分解问题的方式和合并子问题的解的过程。

在实际应用中，递归和分治算法可以相互结合，以解决更加复杂的问题。

例如，可以使用分治算法来将问题分解成多个子问题，然后使用递归算法来解决这些子问题。

此外，还可以在递归算法中使用分治算法来对子问题进行分解和合并。

总而言之，递归与分治算法都是非常有用的算法思想，可以在许多领域中得到应用。

但是，在实际使用时，需要仔细考虑问题的性质和算法的复杂度，以确保算法的正确性和效率。

- 1 -。

递归与分治算法心得
递归与分治算法是算法设计中常见的两种方法，它们在解决问题时都采用了“分而治之”的思想，将问题分解成更小的子问题，然后通过递归调用或者合并子问题的解来得到原问题的解。

通过我的学习和实践，我深刻认识到了递归与分治算法的重要性和优势。

首先，递归算法可以使问题的描述更加简单明了。

通过将问题转化为自身的子问题，我们可以建立起更为简洁优美的数学模型。

其次，递归算法可以使问题的解决过程更加自然。

在递归过程中，我们可以利用已知的子问题解决同类问题，实现代码的复用和模块化。

此外，递归算法还可以解决一些重要的数学问题，如斐波那契数列和二分查找等。

分治算法则更加注重问题的分解和合并。

它将问题划分成若干个规模相同或相近的子问题，然后将子问题的解合并起来得到原问题的解。

这种方法在解决某些复杂问题时具有很大的优势。

例如，在排序算法中，归并排序采用了分治算法的思想，将待排序的序列分成两个长度相等的子序列，然后递归地对子序列排序，最后将子序列合并成有序序列。

这种算法具有较高的稳定性和灵活性，常常被应用于海量数据的排序任务中。

总之，递归与分治算法是算法设计中不可或缺的两种方法。

在解决问题时，我们应该根据具体情况选择合适的算法，并在实践中不断探索、总结和优化。

只有这样，我们才能更好地应对日益复杂多变的计算机科学挑战。

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

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

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

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

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

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

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

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

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

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

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

当n 较大时（n＞2），第一步，把这袋金块平分成两个小袋A和B。

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

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

第三步，通过比较HA 和HB，可以找到所有金块中最重的；通过比较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 ]为最大的重量。

首先处理n≤1的情况。

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

当n 是偶数时，首先将两个重量值放在for 循环外进行比较，较小和较大的重量值分别置为Min和Max，因此也有偶数个重量值w[2:n-1]参与for循环。

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

二、实验内容1、①设a[0:n-1]是已排好序的数组。

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

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

②写出三分搜索法的程序。

三、实验要求（1）用分治法求解上面两个问题；（2）再选择自己熟悉的其它方法求解本问题；（3）上机实现所设计的所有算法；四、实验过程设计（算法设计过程）1、已知a[0:n-1]是一个已排好序的数组，可以采用折半查找（二分查找）算法。

如果搜索元素在数组中，则直接返回下表即可；否则比较搜索元素x与通过二分查找所得最终元素的大小，注意边界条件，从而计算出小于x的最大元素的位置i和大于x的最小元素位置j。

2、将n个元素分成大致相同的三部分，取在数组a的左三分之一部分中继续搜索x。

如果x>a[2(n-1)/3]，则只需在数组a的右三分之一部分中继续搜索x。

上述两种情况不成立时，则在数组中间的三分之一部分中继续搜索x。

五、实验结果分析二分搜索法：三分搜索法：时间复杂性：二分搜索每次把搜索区域砍掉一半，很明显时间复杂度为O(log n)。

（n代表集合中元素的个数）三分搜索法：O（3log3n）空间复杂度：O（1）。

六、实验体会本次试验解决了二分查找和三分查找的问题，加深了对分治法的理解，收获很大，同时我也理解到学习算法是一个渐进的过程，算法可能一开始不是很好理解，但是只要多看几遍，只看是不够的还要动手分析一下，这样才能学好算法。

七、附录：（源代码）二分搜索法：#include<iostream.h>#include<stdio.h>int binarySearch(int a[],int x,int n){int left=0;int right=n-1;int i,j;while(left<=right){int middle=(left+right)/2;if(x==a[middle]){i=j=middle;return 1;}if(x>a[middle])left=middle+1;else right=middle-1;}i=right;j=left;return 0;}int main(){ int a[10]={0,1,2,3,4,5,6,7,8,9};int n=10;int x=9;if(binarySearch(a,x,n))cout<<"找到"<<endl;elsecout<<"找不到"<<endl;return 0;}实验二动态规划——求解最优问题一、实验目的1．加深学生对动态规划算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；2．提高学生利用课堂所学知识解决实际问题的能力；3．提高学生综合应用所学知识解决实际问题的能力。

一、实验背景分治算法是一种常用的算法设计方法，其基本思想是将一个复杂问题分解成若干个相互独立的小问题，然后将小问题递归求解，最终将子问题的解合并为原问题的解。

分治算法具有高效性、可扩展性和易于实现等优点，被广泛应用于各个领域。

本实验旨在通过实现分治算法解决实际问题，掌握分治算法的设计思想，并分析其时间复杂度。

二、实验目的1. 理解分治算法的基本思想；2. 掌握分治算法的递归实现方法；3. 分析分治算法的时间复杂度；4. 应用分治算法解决实际问题。

三、实验内容本实验选择两个分治算法：快速排序和合并排序。

1. 快速排序快速排序是一种高效的排序算法，其基本思想是将待排序序列分为两个子序列，其中一个子序列的所有元素均小于另一个子序列的所有元素，然后递归地对两个子序列进行快速排序。

（1）算法描述：① 选择一个基准值（pivot），通常取序列的第一个元素；② 将序列分为两个子序列，一个子序列包含所有小于基准值的元素，另一个子序列包含所有大于基准值的元素；③ 递归地对两个子序列进行快速排序。

（2）代码实现：```cvoid quickSort(int arr[], int left, int right) {if (left < right) {int pivot = arr[left];int i = left;int j = right;while (i < j) {while (i < j && arr[j] >= pivot) {j--;}arr[i] = arr[j];while (i < j && arr[i] <= pivot) {i++;}arr[j] = arr[i];}arr[i] = pivot;quickSort(arr, left, i - 1);quickSort(arr, i + 1, right);}}```2. 合并排序合并排序是一种稳定的排序算法，其基本思想是将待排序序列分为两个子序列，分别对两个子序列进行排序，然后将排序后的子序列合并为一个有序序列。

一. 实验目的及实验环境实验目的：熟练掌握运用分治法解决问题。

实验环境：windows下的Ubuntu虚拟机二. 实验内容利用分治法求一个数组的最大值、最小值（要求：数组的大小和数组的长度随机产生）三．方案设计分治法解决问题就是要将原问题分解成小问题，再将小问题分解成更小的问题，以此类推，直到最终分解的问题能够一步解决即可。

代码要求最后要输出数组的最大值、最小值。

所以，在用分治法求最值的函数max_min（）中，需要将设置参数int *max，int *min。

即void max_min(int a[],int m,int n,int *max,int *min)。

这样就可以直接得到最大值、最小值。

该函数使用递归来实现，而递归的终止条件是最后分得的数组中只有一个或两个元素，当分得的数组元素个数大于2时，就进行递归调用。

四．测试数据及运行结果正确的3组运行结果：出现的错误：若将代码中的随机数函数返回值的类型改变，则会出现错误结果，甚至编译不通过。

五．总结1．实验过程中遇到的问题及解决办法；实验过程中，用分治法求最大值、最小值时，如果用返回值求最大值和最小值，则需要两个函数。

这样就会导致代码冗余，不会达到代码的复用性功能。

所以要将两个功能用一个函数直接实现就可以使用参数指针的形式。

2．对设计及调试过程的心得体会。

算法设计的课内实验既要实现实验的功能，还要讲究代码中算法的精妙、简单以及它的效率。

不能同其他高级语言的课内实验一样仅仅考虑如何完成该实验的功能，这样就可以真正地体验到算法与设计这门课的意义。

平时做实验时我们可以用不同算法实现，这样不仅可以积累平常上课学到的知识，还可以为以后的算法设计能力奠定基础。

平常更多地进行思考，可以让我们在求职时更受益。

六．附录：源代码（电子版）#include<stdio.h>#include<stdlib.h>#include<time.h>void max_min(int a[],int m,int n,int *max,int *min){int middle,hmax,hmin,gmax,gmin;if(m==n){ *max=a[m];*min=a[m];}else if(m==n-1){if(a[m]>a[n]){*max=a[m];*min=a[n];}else{*max=a[n];*min=a[m];}}else{max_min(a,m,middle,&gmax,&gmin);max_min(a,middle+1,n,&hmax,&hmin);if(gmax>hmax)*max=gmax;else*max=hmax;if(gmin<hmin)*min=gmin;else*min=hmin;}}int main(){int i;int max,min;srand((unsigned)time(NULL));int n=rand()%10+1;printf("数组的个数：%d\n",n);int a[n];for(i=0;i<n;i++){a[i]=rand()%50+1;printf("%d\t",a[i]);}max_min(a,0,n-1,&max,&min);printf("最大数:%d,最小数：%d\n",max,min);retur n 0;}。

《算法设计与分析》实验报告实验一递归与分治策略应用基础学号：**************姓名：*************班级：*************日期：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、掌握递归与分治算法时间空间复杂度分析，以及问题复杂性分析方法二、实验内容任务：从以下题目中任选一题完成，要求应用递归与分治策略设计解决方案。

算法设计与分析：递归与分治法-实验报告(总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) 时间复杂度的概念：指完成算法所需的计算次数或操作次数。

算法分析与设计实验报告第一次实验附录：完整代码（分治法）#include<iostream>#include<time.h>#include<iomanip>using namespace std;//当数组中的元素个数小于3时，处理最大值int compmax(int A[],int start,int end){int max;if(start<end) //有两个元素{if(A[start]<=A[end])max=A[end];elsemax=A[start];}else//有一个元素max=A[start];return max;}//当数组中元素的个数小于2时，处理最小值int compmin(int A[],int start,int end){int min;if(start<end) //有两个元素{if(A[start]<=A[end])min=A[start];elsemin=A[end];}else//有一个元素min=A[start];return min;}//分治法处理整个数组，求最大值与最小值void merge(int a[],int left,int right,int &Max,int &Min) //Max,Min用来保存最大值与最小值//之所以使用&引用，是由于如果只是简单的使用变量，并不会改变Max与Min的值，使用指针也可以{int max1=0,min1=0,max2=0,min2=0;if(right-left>2) //当数组中元素个数大于等于3时，进行分治{int mid=(right+left)/2;merge(a,left,mid,max1,min1); //左半边递归调用自身，求出最大值最小值，分别保存在max1,min1中merge(a,mid+1,right,max2,min2); //右半边递归调用自身，求出最大值最小值，分别保存在max2,min2中if(max1>=max2) //子序列两两合并，求出最大值与最小值，保存在Max与Min中Max=max1;elseMax=max2;if(min1<=min2)Min=min1;elseMin=min2;}else//数组中元素个数小于3时的情况，直接赋值{Max=compmax(a,left,right);Min=compmin(a,left,right);}}void ran(int *input,int n) //随机生成数组元素函数{int i;srand(time(0));for(i=0;i<n;i++)input[i]=rand();input[i]='\0';}int a[1000000]; //定义全局变量用来存放要查找的数组int main(){int n;int i;int max;int min;cout<<"请输入要查找的序列个数："<<endl;for(i=0;i<5;i++){cin>>n;ran(a,n);clock_t start,end,over; //计算程序运行时间的算法start=clock();end=clock();over=end-start;start=clock();merge(a,0,n-1,max,min); //调用分治法算法cout<<max<<" "<<min<<endl;end=clock();printf("The time is %6.3f",(double)(end-start-over)/CLK_TCK); //显示运行时间}system("pause"); //停止运行窗口return 0;}完整代码（非递归方法）#include<iostream>#include<time.h>#include<iomanip>using namespace std;void ran(int *input,int n) //随机生成数组元素函数{int i;srand(time(0));for(i=0;i<n;i++)input[i]=rand();input[i]='\0';}int a[1000000];int main(){int max=a[0],min=a[0];int i,j,n;cout<<"请输入数据规模："<<endl;for(j=0;j<5;j++){cin>>n;ran(a,n);clock_t start,end,over; //计算程序运行时间的算法start=clock();end=clock();over=end-start;start=clock();for(i=1;i<n;i++){if(a[i]>max)max=a[i];if(a[i]<min)min=a[i];}cout<<max<<" "<<min<<endl;end=clock();printf("The time is %6.3f",(double)(end-start-over)/CLK_TCK); //显示运行时间}system("pause");return 0;}。

分治法实验总结
分治法是一种常用的算法设计策略，它将问题分解成若干个子问题，然后递归地解决这些子问题，最后将子问题的解合并成原问题的解。

在本次实验中，我们通过实现归并排序和快速排序两个算法，深入理解了分治法的思想和实现方式。

我们实现了归并排序算法。

归并排序的基本思想是将待排序的序列分成若干个子序列，每个子序列都是有序的，然后再将子序列合并成一个有序的序列。

在实现过程中，我们采用了递归的方式，将序列不断地分成两半，直到每个子序列只有一个元素，然后再将这些子序列两两合并，直到最终得到一个有序的序列。

归并排序的时间复杂度为O(nlogn)，是一种稳定的排序算法。

接着，我们实现了快速排序算法。

快速排序的基本思想是选择一个基准元素，将序列分成两个部分，一部分比基准元素小，一部分比基准元素大，然后递归地对这两个部分进行排序。

在实现过程中，我们选择了序列的第一个元素作为基准元素，然后使用两个指针分别从序列的两端开始扫描，将比基准元素小的元素放在左边，将比基准元素大的元素放在右边，最后将基准元素放在中间，然后递归地对左右两个部分进行排序。

快速排序的时间复杂度为O(nlogn)，但是在最坏情况下，时间复杂度会退化为O(n^2)。

通过实现归并排序和快速排序两个算法，我们深入理解了分治法的
思想和实现方式。

分治法是一种非常重要的算法设计策略，可以用来解决很多复杂的问题，比如最近点对问题、矩阵乘法问题等。

在实际应用中，我们可以根据具体问题的特点选择合适的分治算法，以提高算法的效率和准确性。