算法设计与分析：递归与分治法-实验报告

实验一分治与递归算法的应用一、实验目的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循环。

算法设计与分析实验报告一实验名称统计数字问题评分实验日期2014 年11 月15 日指导教师姓名专业班级学号一.实验要求1、掌握算法的计算复杂性概念。

2、掌握算法渐近复杂性的数学表述。

3、掌握用C++语言描述算法的方法。

4．实现具体的编程与上机实验，验证算法的时间复杂性函数。

二.实验内容统计数字问题1、问题描述一本书的页码从自然数1 开始顺序编码直到自然数n。

书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。

例如，第6 页用数字6 表示，而不是06 或006 等。

数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1，2， (9)2、编程任务给定表示书的总页码的10 进制整数n (1≤n≤109) 。

编程计算书的全部页码中分别用到多少次数字0，1，2， (9)三.程序算法将页码数除以10，得到一个整数商和余数，商就代表页码数减余数外有多少个1—9作为个位数，余数代表有1—余数本身这么多个数作为剩余的个位数，此外，商还代表1—商本身这些数出现了10次，余数还代表剩余的没有计算的商的大小的数的个数。

把这些结果统计起来即可。

四.程序代码#include<iostream.h>int s[10]; //记录0~9出现的次数int a[10]; //a[i]记录n位数的规律void sum(int n,int l,int m){ if(m==1){int zero=1;for(int i=0;i<=l;i++) //去除前缀0{ s[0]-=zero;zero*=10;} }if(n<10){for(int i=0;i<=n;i++){ s[i]+=1; }return;}//位数为1位时,出现次数加1//位数大于1时的出现次数for(int t=1;t<=l;t++)//计算规律f(n)=n*10^(n-1){m=1;int i;for(i=1;i<t;i++)m=m*10;a[t]=t*m;}int zero=1;for(int i=0;i<l;i++){ zero*= 10;} //求出输入数为10的n次方int yushu=n%zero; //求出最高位以后的数int zuigao=n/zero; //求出最高位zuigaofor(i=0;i<zuigao;i++){ s[i]+=zero;} //求出0~zuigao-1位的数的出现次数for(i=0;i<10;i++){ s[i]+=zuigao*a[l];} //求出与余数位数相同的0~zuigao-1位中0~9出现的次数//如果余数是0,则程序可结束,不为0则补上所缺的0数,和最高位对应所缺的数if(yushu==0) //补上所缺的0数,并且最高位加1{ s[zuigao]++;s[0]+=l; }else{ i=0;while((zero/=10)>yushu){ i++; }s[0]+=i*(yushu+1);//补回因作模操作丢失的0s[zuigao]+=(yushu+1);//补回最高位丢失的数目sum(yushu,l-i-1,m+1);//处理余位数}}void main(){ int i,m,n,N,l;cout<<"输入数字要查询的数字:";cin>>N;cout<<'\n';n = N;for(i=0;n>=10;i++){ n/=10; } //求出N的位数n-1l=i;sum(N,l,1);for(i=0; i<10;i++){ cout<< "数字"<<i<<"出现了:"<<s[i]<<"次"<<'\n'; }}五.程序调试中的问题调试过程，页码出现报错。

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

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

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

二、实验目的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. 合并排序合并排序是一种稳定的排序算法，其基本思想是将待排序序列分为两个子序列，分别对两个子序列进行排序，然后将排序后的子序列合并为一个有序序列。

竭诚为您提供优质文档/双击可除递归与分治实验报告篇一：实验一递归与分治算法编程-实验报告纸南京信息工程大学实验（实习）报告实验（实习）名称递归与分治算法编程实验（实习）日期得分指导教师院专业年级班次姓名学号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. 时间复杂度时间复杂度衡量了算法执行所需的时间。

通常用大O表示法表示时间复杂度，表示算法的最坏情况下的运行时间。

常见的时间复杂度有O(1)、O(log n)、O(n)、O(n log n)和O(n^2)等。

其中，O(1)表示常数时间复杂度，O(log n)表示对数时间复杂度，O(n)表示线性时间复杂度，O(n log n)表示线性对数时间复杂度，O(n^2)表示平方时间复杂度。

2. 空间复杂度空间复杂度衡量了算法执行所需的存储空间。

通常用大O表示法表示空间复杂度，表示算法所需的额外存储空间。

常见的空间复杂度有O(1)、O(n)和O(n^2)等。

其中，O(1)表示常数空间复杂度，O(n)表示线性空间复杂度，O(n^2)表示平方空间复杂度。

三、算法设计算法设计是构思和实现算法的过程。

好的算法设计能够提高算法的效率和可靠性。

常用的算法设计方法包括贪心算法、动态规划、分治法和回溯法等。

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) 时间复杂度的概念：指完成算法所需的计算次数或操作次数。

算法设计与分析实验报告实验一全排列、快速排序【实验目的】1. 掌握全排列的递归算法。

2. 了解快速排序的分治算法思想。

【实验原理】一、全排列全排列的生成算法就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。

任何n个字符集的排列都可以与1～n的n个数字的排列一一对应，因此在此就以n 个数字的排列为例说明排列的生成法。

n个字符的全体排列之间存在一个确定的线性顺序关系。

所有的排列中除最后一个排列外，都有一个后继；除第一个排列外，都有一个前驱。

每个排列的后继都可以从它的前驱经过最少的变化而得到，全排列的生成算法就是从第一个排列开始逐个生成所有的排列的方法。

二、快速排序快速排序（Quicksort）是对冒泡排序的一种改进。

它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

【实验内容】１.全排列递归算法的实现。

２.快速排序分治算法的实现。

【实验结果】１. 全排列：２. 快速排序：实验二最长公共子序列、活动安排问题【实验目的】１. 了解动态规划算法设计思想，运用动态规划算法实现最长公共子序列问题。

２. 了解贪心算法思想，运用贪心算法设计思想实现活动安排问题。

【实验原理】一、动态规划法解最长公共子序列设序列X=和Y=的一个最长公共子序列Z=，则：i. 若xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列；ii. 若xm≠yn且zk≠xm ，则Z是Xm-1和Y的最长公共子序列；iii. 若xm≠yn且z k≠yn ，则Z是X和Yn-1的最长公共子序列。

其中Xm-1=，Yn-1=，Zk-1=。

最长公共子序列问题具有最优子结构性质。

由最长公共子序列问题的最优子结构性质可知，要找出X=和Y=的最长公共子序列，可按以下方式递归地进行：当xm=yn时，找出Xm-1和Yn-1的最长公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的一个最长公共子序列。

实验一找最大和最小元素与归并分类算法实现（用分治法）一、实验目的1．掌握能用分治法求解的问题应满足的条件；2．加深对分治法算法设计方法的理解与应用；3．锻炼学生对程序跟踪调试能力；4．通过本次实验的练习培养学生应用所学知识解决实际问题的能力。

二、实验内容1、找最大和最小元素输入n 个数，找出最大和最小数的问题。

2、归并分类将一个含有n个元素的集合，按非降的次序分类（排序）。

三、实验要求（1）用分治法求解问题（2）上机实现所设计的算法；四、实验过程设计（算法设计过程）1、找最大和最小元素采用分治法，将数组不断划分，进行递归。

递归结束的条件为划分到最后若为一个元素则max和min都是这个元素，若为两个取大值赋给max，小值给min。

否则就继续进行划分，找到两个子问题的最大和最小值后，比较这两个最大值和最小值找到解。

2、归并分类使用分治的策略来将一个待排序的数组分成两个子数组，然后递归地对子数组进行排序，最后将排序好的子数组合并成一个有序的数组。

在合并过程中，比较两个子数组的首个元素，将较小的元素放入辅助数组，并指针向后移动，直到将所有元素都合并到辅助数组中。

五、源代码1、找最大和最小元素#include<iostream>using namespace std;void MAXMIN(int num[], int left, int right, int& fmax, int& fmin); int main() {int n;int left=0, right;int fmax, fmin;int num[100];cout<<"请输入数字个数：";cin >> n;right = n-1;cout << "输入数字:";for (int i = 0; i < n; i++) {cin >> num[i];}MAXMIN(num, left, right, fmax, fmin);cout << "最大值为：";cout << fmax << endl;cout << "最小值为：";cout << fmin << endl;return 0;}void MAXMIN(int num[], int left, int right, int& fmax, int& fmin) { int mid;int lmax, lmin;int rmax, rmin;if (left == right) {fmax = num[left];fmin = num[left];}else if (right - left == 1) {if (num[right] > num[left]) {fmax = num[right];fmin = num[left];}else {fmax = num[left];fmin = num[right];}}else {mid = left + (right - left) / 2;MAXMIN(num, left, mid, lmax, lmin);MAXMIN(num, mid+1, right, rmax, rmin);fmax = max(lmax, rmax);fmin = min(lmin, rmin);}}2、归并分类#include<iostream>using namespace std;int num[100];int n;void merge(int left, int mid, int right) { int a[100];int i, j,k,m;i = left;j = mid+1;k = left;while (i <= mid && j <= right) {if (num[i] < num[j]) {a[k] = num[i++];}else {a[k] = num[j++];}k++;}if (i <= mid) {for (m = i; m <= mid; m++) {a[k++] = num[i++];}}else {for (m = j; m <= right; m++) {a[k++] = num[j++];}}for (i = left; i <= right; i++) { num[i] = a[i];}}void mergesort(int left, int right) { int mid;if (left < right) {mid = left + (right - left) / 2;mergesort(left, mid);mergesort(mid + 1, right);merge(left, mid, right);}}int main() {int left=0,right;int i;cout << "请输入数字个数：";cin >> n;right = n - 1;cout << "输入数字:";for (i = 0; i < n; i++) {cin >> num[i];}mergesort(left,right);for (i = 0; i < n; i++) {cout<< num[i];}return 0;}六、运行结果和算法复杂度分析1、找最大和最小元素图1-1 找最大和最小元素结果算法复杂度为O(logn）2、归并分类图1-2 归并分类结果算法复杂度为O(nlogn）实验二背包问题和最小生成树算法实现（用贪心法）一、实验目的1．掌握能用贪心法求解的问题应满足的条件；2．加深对贪心法算法设计方法的理解与应用；3．锻炼学生对程序跟踪调试能力；4．通过本次实验的练习培养学生应用所学知识解决实际问题的能力。

算法实验报告一分治法实验一、实验目的及要求利用分治方法设计大整数乘法的递归算法，掌握分治法的基本思想和算法设计的基本步骤。

要求：设计十进制的大整数乘法，必须利用分治的思想编写算法，利用c语言（或者c++语言）实现算法，给出程序的正确运行结果。

（必须完成）设计二进制的大整数乘法，要求利用分治的思想编写递归算法，并可以实现多位数的乘法（利用数组实现），给出程序的正确运行结果。

（任选）二、算法描述1、输入两个相同位数的大整数u，v 输出uv的值判断大整数的位数i；w=u/10^(i/2);y=v/10^(i/2);x=u-w*10^(i/2);z= v-y*10^(i/2);然后将w,x,y,z代入公式求得最后结果uv=wy10^i+((w+x)(y+z)-wy-xz)10^(i/2)+xz三、调试过程及运行结果在实验中我遇到的问题：原来以为这两个大整数的位数不同，结果题目要求是相同位数的大整数在写10的多少次方时，写的是10^(i/2),10^(i)，结果不对，我就将它改成了for循环语句四、实验总结在本次实验中，我知道了分治算法，以及分治算法的基本思想。

我还掌握了编写大整数乘法的算法与步骤，以及如何修改在编写程序时遇到的问题。

五、附录（源程序代码清单）1、#include&lt;iostream.h&gt; int weishu(int x){int i;while(x!=0){ x=x/10;i++;}return i;}void main(){int u,v;cout&lt;&lt;输入两个位数相同的大整数:&lt;&lt;endl; cin&gt;&gt;u;cin&gt;&gt;v;int i,j,m,n;int p,x,y,z,w;int a=1;int b=1;i=weishu(u);for(int k=1;k&lt;=i;k++){a=a*10;}for(int q=1;q&lt;=i/2;q++) {b=b*10;}w=u/b;y=v/b;x=u-w*b;z=v-y*b;p=w*y*a+((w+x)*(y+z)-w*y-x*z)*b+x*z; cout&lt;&lt;u&lt;&lt;*&lt;&lt;v&lt;&lt;=&lt;&lt;p; }教师评语：成绩：√优良中及格不及格算法实验报告二动态规划法实验一、实验目的及要求利用动态规划方法设计背包问题算法，掌握动态规划法的基本思想和算法设计的基本步骤。

分治法实验报告分治法实验报告一、引言分治法是一种重要的算法设计策略，它将一个大问题分解成若干个小问题，并通过递归的方式解决这些小问题，最终将它们的解合并起来得到原问题的解。

本实验旨在通过实际案例，探索分治法的应用和效果。

二、背景在计算机科学领域，分治法常常被用于解决一些复杂的问题，如排序、搜索、图算法等。

它的核心思想是将问题划分为更小的子问题，然后分别解决这些子问题，最后将它们的解合并起来得到原问题的解。

通过这种方式，我们可以降低问题的复杂度，提高算法的效率。

三、实验目的本实验旨在通过实际案例，验证分治法在问题解决中的有效性，并探索其在不同问题上的应用效果。

通过对比不同算法的运行时间和结果准确性，评估分治法在不同场景下的适用性。

四、实验过程本次实验选取了两个典型的问题，分别是最大子数组和快速排序。

首先，我们使用分治法来解决最大子数组问题。

该问题要求在一个给定的数组中，找到一个连续子数组，使得该子数组的和最大。

我们将数组分为两半，分别求解左半部分和右半部分的最大子数组，然后再考虑跨越中点的最大子数组。

通过递归的方式，最终得到整个数组的最大子数组。

接着，我们使用分治法来实现快速排序算法。

快速排序是一种高效的排序算法，它的核心思想是通过选择一个基准元素，将数组分为两个部分，使得左边的元素都小于等于基准元素，右边的元素都大于等于基准元素。

然后，对左右两个部分分别递归地进行快速排序，最终得到有序的数组。

五、实验结果通过对最大子数组和快速排序问题的实验，我们得到了以下结果。

首先，分治法在解决最大子数组问题上表现出色。

通过将问题划分为更小的子问题，我们可以在较短的时间内找到最大子数组，大大提高了算法的效率。

其次，在快速排序问题上，分治法同样展现了强大的能力。

通过不断地划分数组并进行排序，我们可以快速得到有序的结果。

六、实验分析分治法作为一种重要的算法设计策略，具有许多优点。

首先，它可以将复杂的问题分解为简单的子问题，降低了问题的复杂度，提高了算法的效率。