下载文档原格式
应用数学学院信息安全专业班学号姓名实验题目递归与分治法综合实验评分表实验报告一、实验目的与要求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）运行界面三、问题与讨论问题：分治法能解决的问题一般具有什么特征？解答：任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。
算法分析(第二章)：递归与分治法一、递归的概念知识再现：等比数列求和公式：1、定义：直接或间接地调用自身的算法称为递归算法。
用函数自身给出定义的函数称为递归函数。
2、与分治法的关系：由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。
在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。
这自然导致递归过程的产生。
分治与递归经常同时应用在算法设计之中，并由此产生许多高效算法。
3、递推方程：(1)定义：设序列01,....na a a简记为{na}，把n a与某些个()ia i n<联系起来的等式叫做关于该序列的递推方程。
(2)求解：给定关于序列{n a}的递推方程和若干初值，计算n a。
4、应用：阶乘函数、Fibonacci数列、Hanoi塔问题、插入排序5、优缺点：优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。
缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。
二、递归算法改进：1、迭代法：(1)不断用递推方程的右部替代左部(2)每一次替换，随着n的降低在和式中多出一项(3)直到出现初值以后停止迭代(4)将初值代入并对和式求和(5)可用数学归纳法验证解的正确性2、举例：-----------Hanoi塔算法----------- ---------------插入排序算法----------- ()2(1)1(1)1T n T nT=−+=()(1)1W n W n nW=−+−（1）=021n-23()2(1)12[2(2)1]12(2)21...2++2 (121)n n n T n T n T n T n T −−=−+=−++=−++==++=−（1）2 ()(1)1((n-2)+11)1(2)(2)(1)...(1)12...(2)(1)(1)/2W n W n n W n n W n n n W n n n n =−+−=−−+−=−+−+−==++++−+−=−3、换元迭代：(1)将对n 的递推式换成对其他变元k 的递推式 (2)对k 进行迭代(3)将解（关于k 的函数）转换成关于n 的函数4、举例：---------------二分归并排序---------------()2(/2)1W n W n n W =+−（1）=0（1）换元：假设2kn =，递推方程如下()2(/2)1W n W n n W =+−（1）=0 → 1(2)2(2)21k k k W W W−=+−（0）=0（2）迭代求解：12122222321332133212()2(2)212(2(2)21)212(2)22212(2)2*2212(2(2)21)2212(2)222212(2)3*2221...2(0)*2(22...21)22k k k k k k k k k k k k k k k k k k k k k k k k W n W W W W W W W W k k −−−−−−−+−+−−−=+−=+−+−=+−+−=+−−=+−+−−=+−+−−=+−−−==+−++++=−1log 1n n n +=−+（3）解的正确性—归纳验证： 证明递推方程的解是()(1)/2W n n n =−()(1)1W n W n n W =−+−（1）=0,(n 1)=n +n=n(n-1)/2+n =n[(n-1)/2+1]=n(n+1)/2n W W +方法：数学归纳法证 n=1,W(1)=1*(1-1)/2=0假设对于解满足方程，则（）---------------快速排序--------------------->>>平均工作量：假设首元素排好序在每个位置是等概率的112()()()(1)0n i T n T i O n n T −==+=∑ >>>对于高阶方程应该先化简，然后迭代(1)差消化简：利用两个方程相减，将右边的项尽可能消去，以达到降阶的目的。
《算法设计与分析》实验指导实验一分治与递归一、实验目的：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.了解并掌握递归的概念，递归算法的基本思想；2.掌握分治法的基本思想方法；3.了解适用于用分治法求解的问题类型，并能用递归或非递归的方式设计相应的分治法算法；4.掌握分治法复杂性分析方法，比较同一个问题的递归算法与循环迭代算法的效率。
预习与实验要求1.预习实验指导书及教材的有关内容，掌握分治法的基本思想；2.严格按照实验内容进行实验，培养良好的算法设计和编程的习惯；3.认真听讲，服从安排，独立思考并完成实验。
实验原理简单说来，当一个函数用它自己来定义时就称为递归。
一般来说，递归需要有边界条件、递归前进段和递归返回段。
当边界条件不满足时，递归前进；当边界条件满足时，递归返回。
因此，在考虑使用递归算法编写程序时，应满足两点：1）该问题能够被递归形式描述；2）存在递归结束的边界条件。
递归的能力在于用有限的语句来定义对象的无限集合。
用递归思想写出的程序往往十分简洁易懂。
一般说来，一个递归算法可以转换称为一个与之等效的非递归算法，但转换后的非递归算法代码将成倍地增加。
分治是一种被广泛应用的有效方法，它的基本思想是把最初的问题分解成若干子问题，然后在逐个解决各个子问题的基础上得到原始问题的解。
所谓分治就是“分而治之”的意思。
由于分解出的每个子问题总是要比最初的问题容易些，因而分治策略往往能够降低原始问题的难度，或者提高解决原始问题的效率。
根据如何由分解出的子问题求出原始问题的解，分治策略又可分为两种情形：第一，原始问题的解只存在于分解出的某一个子问题中，则只需要在原始问题的一个划分中求解即可；第二，原始问题的解需要由各个子问题的解再经过综合处理得到。
无论是哪一种情况，分治策略可以较快地缩小问题的求解范围，从而加快问题求解的速度。
分治策略运用于计算机算法是，往往会出现分解出来的子问题与原始问题类型相同的现象，而与原问题相比，各个子问题的规模变小了，这刚好符合递归的特征。
因此分治策略往往是和递归联系在一起的。
算法设计与分析：递归与分治法-实验报告(总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) 时间复杂度的概念：指完成算法所需的计算次数或操作次数。
