一、实验目的:
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); //将各子问题的解合并为原问题的解
}
三、实验内容及要求:
在程序中创建一个学生对象数组并初始化数据,完成如下编程任务。
⑴找出成绩排名第4的学生,输出其姓名。
要求:
①编写功能较为完善的学生类,重载必要的运算符;
②使用快速排序的方法。
⑵使用分治法找出成绩最高和成绩最低的学生,输出他们的姓名。
四、实验报告要求
①实验报告只写实验⑵。
②写出算法思想、主要程序代码、算法复杂性分析。
1
习题1 1. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉(Leonhard Euler ,1707—1783)提出并解决了该问题。七桥问题是这样描述的:一个人是否能在一次步行中穿越哥尼斯堡(现 在叫加里宁格勒,在波罗的海南岸)城中全部的七座桥后回到起点,且每座桥只经过一次, 图是这条河以及河上的两个岛和七座桥的草 图。请将该问题的数据模型抽象出来,并判断此问题是否有解。 七桥问题属于一笔画问题。 输入:一个起点 输出:相同的点 1, 一次步行 2, 经过七座桥,且每次只经历过一次 3, 回到起点 该问题无解:能一笔画的图形只有两类:一类是所有的点都是偶点。另一类是只有二个奇点的图形。 2.在欧几里德提出的欧几里德算法中(即最初的欧几里德算法)用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法 =m-n 2.循环直到r=0 m=n n=r r=m-n 3 输出m 3.设计算法求数组中相差最小的两个元素(称为最接近数)的差。要求分别给出伪代码和C++描述。 编写程序,求n 至少为多大时,n 个“1”组成的整数能被2013整除。 #include
for(int n=1;n<=10000 ;++n) { value=value*10+1; if(value%2013==0) { cout<<"n至少为:"<
实验报告分治与递归 中国矿业大学计算机科学与技术学院孟靖宇 一、实验目的与要求 1、熟悉C/C++语言的集成开发环境; 2、通过本实验加深对递归过程的理解 二、实验内容: 掌握递归算法的概念和基本思想,分析并掌握“整数划分”问题的递归算法。 三、实验题 任意输入一个整数,输出结果能够用递归方法实现整数的划分。 四、算法思想 对于数据n,递归计算最大加数等于x 的划分个数+最大加数不大于x-1的划分个数。最大加数x 从n 开始,逐步变小为n-1, (1) 考虑增加一个自变量:对于数据n,最大加数n1不大于m 的划分个数记作),(m n q 。则有: ???????>>=<==-+--+=1 1,1),()1,()1,(1),(1),(m n m n m n m n m m n q m n q n n q n n q m n q 五、代码实现 #include "stdafx.h" #include return 0; } int q(intn,int m){ if((n<1)||(m<1)) return 0; if((n==1)||(m==1)) return 1; if(n 本科实验报告 课程名称:算法设计与分析 实验项目:递归与分治算法 实验地点:计算机系实验楼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 011 010 110 111 101 100。n位是前n-1位的2倍个。N-1个位前面加0,N-2为倒转再前面再加1。 3.代码设计: 递归算法与递归程序 岳西中学:崔世义一、教学目标 1知识与技能 (1) ?认识递归现象。 (2) ?使用递归算法解决冋题往往能使算法的描述乘法而易于表达 (3) ?理解递归三要素:每次递归调用都要缩小规模;前次递归调用为后次作准备:递归调用必须有条件进行。 (4) ?认识递归算法往往不是咼效的算法。 (5) ? 了解递归现象的规律。 (6) ?能够设计递归程序解决适用于递归解决的问题。 (7) ?能够根据算法写出递归程序。 (8) ? 了解生活中的递归现象,领悟递归现象的既有重复,又有变化的特点,并且从中学习解决问题的一种方法。 2、方法与过程 本节让同学们玩汉诺塔的游戏,导入递归问题,从用普通程序解决斐波那契的兔子问题入手,引导学生用自定义了一个以递归方式解决的函数过程解决问题,同时让同学们做三个递归练习,巩固提高。然后让学生做练习(2) 和练习(3)这两道题目的形式相差很远,但方法和答案却是完全相同的练习,体会其中的奥妙,加深对递归算法的了解。最后用子过程解决汉诺塔的经典问题。 3、情感态度和价值观 结合高中生想象具有较强的随意性、更富于现实性的身心发展特点,综合反映出递归算法的特点,以及递归算法解答某些实践问题通常得很简洁,从而激发学生对程序设计的追求和向往。 二、重点难点 1、教学重点 (1) 了解递归现象和递归算法的特点。 (2) 能够根据问题设计出恰当的递归程序。 2、教学难点 (1) 递归过程思路的建立。 (2) 判断冋题是否适于递归解法。 (3) 正确写出递归程序。 三、教学环境 1、教材处理 教材选自《浙江省普通高中信息技术选修:算法与程序设计》第五章,原教材的编排是以本节以斐波那契的兔子问题引人,导出递归算法,从而自 定义了一个以递归方式解决的函数过程。然后利用子过程解决汉诺塔的经典问题。 教材经处理后,让同学们玩汉诺塔的游戏,导入递归问题,从用普通程序解决斐波那契的兔子问题入手,引导学生用自定义了一个以递归方式解决的函数过程解决问题,同时让同学们做三个递归练习,巩固提高。然后让学生做练习⑵ 和练习 应用数学学院信息安全专业班学号姓名 实验题目递归与分治法 综合实验评分表 实验报告 一、实验目的与要求 1.掌握递归算法的设计思想 2.掌握分治法设计算法的一般过程 3.理解并掌握算法渐近时间复杂度的分析方法 二、实验内容 1、折半查找的递归算法 (1)源程序代码 #include if(-1 != addr) cout << endl << n << "是上述整数中的第" << addr << "个数" << endl; else cout << endl << n << "不在上述的整数中" << endl << endl; getchar(); return 0; } (2)运行界面 ①查找成功 ②查找失败 算法分析与设计习题集整理 第一章算法引论 一、填空题: 1、算法运行所需要的计算机资源的量,称为算法复杂性,主要包括时间复杂度和空间复杂度。 2、多项式10()m m A n a n a n a =+++L 的上界为O(n m )。 3、算法的基本特征:输入、输出、确定性、有限性 、可行性 。 4、如何从两个方面评价一个算法的优劣:时间复杂度、空间复杂度。 5、计算下面算法的时间复杂度记为: O(n 3) 。 for(i=1;i<=n;i++) for(j=1;j<=n;j++) {c[i][j]=0; for(k=1;k<=n;k++) c[i][j]= c[i][j]+a[i][k]*b[k][j]; } 6、描述算法常用的方法:自然语言、伪代码、程序设计语言、流程图、盒图、PAD 图。 7、算法设计的基本要求:正确性 和 可读性。 8、计算下面算法的时间复杂度记为: O(n 2) 。 for (i =1;i 《算法设计与分析》实验报告 分治策略 姓名:XXX 专业班级:XXX 学号:XXX 指导教师:XXX 完成日期:XXX 一、试验名称:分治策略 (1)写出源程序,并编译运行 (2)详细记录程序调试及运行结果 二、实验目的 (1)了解分治策略算法思想 (2)掌握快速排序、归并排序算法 (3)了解其他分治问题典型算法 三、实验内容 (1)编写一个简单的程序,实现归并排序。 (2)编写一段程序,实现快速排序。 (3)编写程序实现循环赛日程表。设有n=2k个运动员要进行网球循环赛。现 要设计一个满足以下要求的比赛日程表:(1)每个选手必须与其它n-1个选手各赛一次(2)每个选手一天只能赛一场(3)循环赛进行n-1天 四、算法思想分析 (1)编写一个简单的程序,实现归并排序。 将待排序元素分成大小大致相同的2个子集合,分别对2个子集合进行 排序,最终将排好序的子集合合并成为所要求的排好序的集合。 (2)编写一段程序,实现快速排序。 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有 数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数 据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据 变成有序序列。 (3)编写程序实现循环日赛表。 按分治策略,将所有的选手分为两组,n个选手的比赛日程表就可以通 过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割, 直到只剩下2个选手时,比赛日程表的制定就变得很简单。这时只要让 这2个选手进行比赛就可以了。 五、算法源代码及用户程序 (1)编写一个简单的程序,实现归并排序。 #include 递归算法的实现 【基本信息】 【课标要求】 (三)算法与问题解决例举 1. 内容标准 递归法与问题解决 (1)了解使用递归法设计算法的基本过程。 (2)能够根据具体问题的要求,使用递归法设计算法、编写递归函数、编写程序、求解问题。 【教材分析】 “算法的程序实现”是《算法与程序设计》选修模块第三单元的内容,本节课是“递归算法的程序实现”,前面学习了用解析法解决问题、穷举法解决问题、在数组中查找数据、对数进行排序以及本节的前一小节知识点“什么是自定义函数”的学习,在学习自定义函数的基础上,学习递归算法的程序实现是自定义函数的具体应用,培养学生“自顶向下”、“逐步求精”的意识起着重要的作用。 『递归算法在算法的学习过程中是一个难点,在PASCAL和C语言等程序语言的学习过程中,往往是将其放在“函数与过程”这一章节中来讲解的。递归算法的实现也是用函数或是过程的自我调用来实现的。从这一点上来讲,作者对教材的分析与把握是准确的,思路是清晰的,目标是明确的。』 【学情分析】 教学对象是高中二年级学生,前面学习了程序设计的各种结构,在学习程序设计各种结构的应用过程中培养了用计算机编程解决现实中问题的能力,特别是在学习循环语句的过程中,应用了大量的“递推”算法。前一节课学习了如何自定义函数,在此基础上学习深入学习和体会自定义函数的应用。以递推算法的逆向思维进行求解问题,在学习过程中体会递归算法的思想过程。多维度的思考问题和解决问题是提高学生的学习兴趣关键。 『递归算法的本质是递推,而递推的实现正是通过循环语句来完成的。作者准确把握了学生前面的学习情况,对递归算法的本质与特征也分析的很透彻,可以说作者对教学任务的分析是很成功的,接来就要看,在成功分析的基础上作者是如何通过设计教学来解决教学难点的了。』 【教学目标】 递归与分治实验报告 班级:计科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 算法分析(第二章):递归与分治法 一、递归的概念 知识再现:等比数列求和公式: 1、定义:直接或间接地调用自身的算法称为递归算法。 用函数自身给出定义的函数称为递归函数。 2、与分治法的关系: 由分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便。在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归经常同时应用在算法设计之中,并由此产生许多高效算法。 3、递推方程: (1)定义:设序列01,....n a a a简记为{ n a},把n a与某些个() i a i n <联系起来的等式叫做关于该序列的递推方程。 (2)求解:给定关于序列{n a}的递推方程和若干初值,计算n a。 4、应用:阶乘函数、Fibonacci数列、Hanoi塔问题、插入排序 5、优缺点: 优点:结构清晰,可读性强,而且容易用数学归纳法来证明算法的正确性,因此它为设计算法、调试程序带来很大方便。 缺点:递归算法的运行效率较低,无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 二、递归算法改进: 1、迭代法: (1)不断用递推方程的右部替代左部 (2)每一次替换,随着n的降低在和式中多出一项 (3)直到出现初值以后停止迭代 (4)将初值代入并对和式求和 (5)可用数学归纳法验证解的正确性 2、举例: -----------Hanoi塔算法----------- ---------------插入排序算法----------- ()2(1)1 (1)1 T n T n T =?+ = ()(1)1 W n W n n W =?+? (1)=0 实验一分治与递归算法的应用 一、实验目的 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循环。 在for 循环中,外层if 通过比较确定( w [ i ] , w [ i + 1 ] )中的较大和较小者。此工作与前面提到的分而治之算法步骤中的2) 相对应,而内层的i f负责找出较小重量值和较大重量值中的最小值和最大值, 分治策略 姓名:XXX 专业班级:XXX 学号:XXX 指导教师:XXX 完成日期:XXX 一、试验名称:分治策略 (1)写出源程序,并编译运行 (2)详细记录程序调试及运行结果 二、实验目的 (1)了解分治策略算法思想 (2)掌握快速排序、归并排序算法 (3)了解其他分治问题典型算法 三、实验内容 (1)编写一个简单的程序,实现归并排序。 (2)编写一段程序,实现快速排序。 (3)编写程序实现循环赛日程表。设有n=2k个运动员要进行网球循环赛。现 要设计一个满足以下要求的比赛日程表:(1)每个选手必须与其它n-1个选手各赛一次(2)每个选手一天只能赛一场(3)循环赛进行n-1天 四、算法思想分析 (1)编写一个简单的程序,实现归并排序。 将待排序元素分成大小大致相同的2个子集合,分别对2个子集合进行 排序,最终将排好序的子集合合并成为所要求的排好序的集合。 (2)编写一段程序,实现快速排序。 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有 数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数 据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据 变成有序序列。 (3)编写程序实现循环日赛表。 按分治策略,将所有的选手分为两组,n个选手的比赛日程表就可以通 过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割, 直到只剩下2个选手时,比赛日程表的制定就变得很简单。这时只要让 这2个选手进行比赛就可以了。 五、算法源代码及用户程序 (1)编写一个简单的程序,实现归并排序。 #include 实验一分治与递归算法的应用一、实验目的 1.掌握分治算法的基本思想(分-治-合)、技巧和效率分析方法。 2.熟练掌握用递归设计分治算法的基本步骤(基准与递归方程)。 3.学会利用分治算法解决实际问题。 二、算法问题要求 老板有一袋金块(共n块,n是2的幂(n≥2)),最优秀的雇员得到其中最重的一块,最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器,希望用最少的比较次数找出最重和最轻的金块。并对自己的程序进行复杂性分析。 三、算法设计 在n个元素的集合中寻找最大和最小值元素。(1)将集合一分为二,变为两个集合,目的是在较小的两个集合中分别找最大、最小元素。(2)递归分解较小集合,直到每个集合中的元素个数≤2,然后找出小集合的最大、最小元素。(3)合并(回溯):自低向上把子问题的解合并,大元素中取最大者,小元素中取最小者,最后得到元问题的解。 四、验证分析实验结果 图1.1 运行界面 图1.2 运行结果五、程序 #include 算法设计与分析实验报告
《递归算法与递归程序》教学设计
算法设计与分析:递归与分治法-实验报告
算法分析与设计习题集整理
算法分析实验报告--分治策略
高中信息技术 算法与程序设计-递归算法的实现教案 教科版
递归与分治实验报告
算法之2章递归与分治
算法实验报告
算法分析实验报告--分治策略
实验一分治与递归算法报告