实验一分治与递归算法的应用
一、实验目的
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），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作，并对自己的程序进行复杂性分析。
【输入样例】
10
20 40 32 67 40 20 89 300 400 15
【输出样例】
8
15 20 32 40 67 89 300 400
2.数据输入：个人设定，由键盘输入。
3.要求：
1）上述题目任选两题做。上机前，完成程序代码的编写
2）独立完成实验及实验报告
三、实验步骤
1.理解算法思想和问题要求；
2.编程实现题目要求；
3.上机输入和调试自己所编的程序；
4.验证分析实验结果；
5.整理出实验报告。
附：实验报告的主要内容
一．实验目的
二．问题描述
三．算法设计
包含：数据结构与核心算法的设计描述、函数调用及主函数设计、主要算法流程图等
四.程序调试及运行结果分析
五.实验总结
附录：程序清单（程序过长，可附主要部分）
题目二：线性时间选择
学号1607070212 《算法设计与分析》 实验报告一 学生姓名张曾然 专业、班级16软件二班 指导教师唐国峰 成绩 计算机与信息工程学院软件工程系 2018 年9 月19 日
实验一：递归策略运用练习 一、实验目的 本次实验是针对递归算法的算法设计及应用练习，旨在加深学生对该算法原理的理解，提高学生运用该算法解决问题的能力。 二、实验步骤与要求 1．实验前复习课程所学知识以及阅读和理解指定的课外阅读材料； 2．学生独自完成实验指定内容； 3．实验结束后，用统一的实验报告模板编写实验报告。 4．提交说明： （1）电子版提交说明： a 需要提交Winrar压缩包，文件名为“《算法设计与分析》实验一_学号_姓名”， 如“《算法设计与分析》实验一_09290101_张三”。 b 压缩包内为一个“《算法设计与分析》实验一_学号_姓名”命名的顶层文件夹， 其下为两个文件夹，一个文件夹命名为“源程序”，另一个文件夹命名为“实验 报告电子版”。其下分别放置对应实验成果物。 （2）打印版提交说明： a 不可随意更改模板样式。 b 字体：中文为宋体，大小为10号字，英文为Time New Roman，大小为10号 字。 c 行间距：单倍行距。 （3）提交截止时间：2018年10月10日16:00。 三、实验项目 1．运用递归策略设计算法实现下述题目的求解过程。 题目列表如下： 【必做题】 （1）运动会开了N天，一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求N和M。 （2）国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；……；给第i 个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？
一、教学目标 1、知识与技能 (1)．认识递归现象。 (2)．使用递归算法解决问题往往能使算法的描述乘法而易于表达 (3)．理解递归三要素：每次递归调用都要缩小规模；前次递归调用为后次作准备：递归调用必须有条件进行。 (4)．认识递归算法往往不是高效的算法。 (5)．了解递归现象的规律。 (6)．能够设计递归程序解决适用于递归解决的问题。 (7)．能够根据算法写出递归程序。 (8)．了解生活中的递归现象，领悟递归现象的既有重复，又有变化的 特点，并 且从中学习解决问题的一种方法。 2、方法与过程 本节让同学们玩汉诺塔的游戏，导入递归问题，从用普通程序解决斐波那契的兔子问题入手，引导学生用自定义了一个以递归方式解决的函数过程解决问题，同时让同学们做三个递归练习，巩固提高。然后让学生做练习(2)和练习(3)这两道题目的形式相差很远，但方法和答案却是完全相同的练习，体会其中的奥妙，加深对递归算法的了解。最后用子过程解决汉诺塔的经典问题。 3、情感态度和价值观 结合高中生想象具有较强的随意性、更富于现实性的身心发展特点，综合反映出递归算法的特点，以及递归算法解答某些实践问题通常得很简洁，从而激发学生对程序设计的追求和向往。 二、重点难点 1、教学重点 （1）了解递归现象和递归算法的特点。
（2）能够根据问题设计出恰当的递归程序。 2、教学难点 (1)递归过程思路的建立。 (2)判断问题是否适于递归解法。 (3)正确写出递归程序。 三、教学环境 1、教材处理 教材选自《广东省普通高中信息技术选修一：算法与程序设计》第四章第五节，原教材的编排是以本节以斐波那契的兔子问题引人，导出递归算法，从而自定义了一个以递归方式解决的函数过程。然后利用子过程解决汉诺塔的经典问题。 教材经处理后，让同学们玩汉诺塔的游戏，导入递归问题，从用普通程序解决斐波那契的兔子问题入手，引导学生用自定义了一个以递归方式解决的函数过程解决问题，同时让同学们做三个递归练习，巩固提高。然后让学生做练习(2)和练习(3)这两道题目的形式相差很远，但方法和答案却都是完全相同的练习，体会其中的奥妙，加深对递归算法的了解。最后用子过程解决汉诺塔的经典问题。 教学方法采用讲解、探究、任务驱动和学生自主学习相结合 2、预备知识 学生已掌握了用计算机解决问题的过程，掌握了程序设计基础，掌握了解析法、穷举法、查找法、排序法设计程序的技巧。 3、硬件要求 建议本节课在多媒体电脑教室中完成，最好有广播教学系统或投影仪，为拓展学习，学生机应允许上互联网。 4、所需软件 学生机要安装VB6.0或以上版本。 5、所需课时 2课时（90分钟）
实验报告分治与递归 中国矿业大学计算机科学与技术学院孟靖宇 一、实验目的与要求 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 分治算法 一、分治算法 分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。 分治法解题的一般步骤： （1）分解，将要解决的问题划分成若干规模较小的同类问题； （2）求解，当子问题划分得足够小时，用较简单的方法解决； （3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。 当我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解法在时间上相当长，或者根本无法直接求出。对于这类问题，我们往往先把它分解成几个子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个问题的解法。如果这些子问题还较大，难以解决，可以再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。这就是分治策略的基本思想。下面通过实例加以说明。 【例1】[找出伪币] 给你一个装有1 6个硬币的袋子。1 6个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。比较硬币1与硬币2的重量。假如硬币1比硬币2轻，则硬币1是伪造的；假如硬币2比硬币1轻，则硬币2是伪造的。这样就完成了任务。假如两硬币重量相等，则比较硬币3和硬币4。同样，假如有一个硬币轻一些，则寻找伪币的任务完成。假如两硬币重量相等，则继续比较硬币5和硬币6。按照这种方式，可以最多通过8次比较来判断伪币的存在并找出这一伪币。 另外一种方法就是利用分而治之方法。假如把1 6硬币的例子看成一个大的问题。第一步，把这一问题分成两个小问题。随机选择8个硬币作为第一组称为A组，剩下的8个硬币作为第二组称为B组。这样，就把1 6个硬币的问题分成两个8硬币的问题来解决。第二步，判断A和B组中是否有伪币。可以利用仪器来比较A组硬币和B组硬币的重量。假如两组硬币重量相等，则可以判断伪币不存在。假如两组硬币重量不相等，则存在伪币，并且可以判断它位于较轻的那一组硬币中。最后，在第三步中，用第二步的结果得出原先1 6个硬币问题的答案。若仅仅判断硬币是否存在，则第三步非常简单。无论A组还是B组中有伪币，都可以推断这1 6个硬币中存在伪币。因此，仅仅通过一次重量的比较，就可以判断伪币是否存在。 实验一分治与递归算法的应用 一、实验目的 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负责找出较小重量值和较大重量值中的最小值和最大值， 递归算法与递归程序 岳西中学：崔世义一、教学目标 1知识与技能 (1) ?认识递归现象。 (2) ?使用递归算法解决冋题往往能使算法的描述乘法而易于表达 (3) ?理解递归三要素：每次递归调用都要缩小规模；前次递归调用为后次作准备：递归调用必须有条件进行。 (4) ?认识递归算法往往不是咼效的算法。 (5) ? 了解递归现象的规律。 (6) ?能够设计递归程序解决适用于递归解决的问题。 (7) ?能够根据算法写出递归程序。 (8) ? 了解生活中的递归现象，领悟递归现象的既有重复，又有变化的特点，并且从中学习解决问题的一种方法。 2、方法与过程 本节让同学们玩汉诺塔的游戏，导入递归问题，从用普通程序解决斐波那契的兔子问题入手，引导学生用自定义了一个以递归方式解决的函数过程解决问题，同时让同学们做三个递归练习，巩固提高。然后让学生做练习(2) 和练习(3)这两道题目的形式相差很远，但方法和答案却是完全相同的练习，体会其中的奥妙，加深对递归算法的了解。最后用子过程解决汉诺塔的经典问题。 3、情感态度和价值观 结合高中生想象具有较强的随意性、更富于现实性的身心发展特点，综合反映出递归算法的特点，以及递归算法解答某些实践问题通常得很简洁，从而激发学生对程序设计的追求和向往。 二、重点难点 1、教学重点 (1) 了解递归现象和递归算法的特点。 (2) 能够根据问题设计出恰当的递归程序。 2、教学难点 (1) 递归过程思路的建立。 (2) 判断冋题是否适于递归解法。 (3) 正确写出递归程序。 三、教学环境 1、教材处理 教材选自《浙江省普通高中信息技术选修：算法与程序设计》第五章，原教材的编排是以本节以斐波那契的兔子问题引人，导出递归算法，从而自 定义了一个以递归方式解决的函数过程。然后利用子过程解决汉诺塔的经典问题。 教材经处理后，让同学们玩汉诺塔的游戏，导入递归问题，从用普通程序解决斐波那契的兔子问题入手，引导学生用自定义了一个以递归方式解决的函数过程解决问题，同时让同学们做三个递归练习，巩固提高。然后让学生做练习⑵ 和练习 《算法设计与分析》实验报告 分治策略 姓名：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 递归与循环的优缺点（转载） 2011-08-24 17:49:40| 分类：算法数据结构| 标签：|字号大中小订阅 递归的话函数调用是有开销的，而且递归的次数受堆栈大小的限制。 以二叉树搜索为例： bool search(btree* p, int v) { if (null == p) return false; if (v == p->v) return true else { if (v < p->v) return search(p->left, v); else return search(p->right, v); } } 如果这个二叉树很庞大，反复递归函数调用开销就很大，万一堆栈溢出怎么办？现在我们用循环改写： bool search(btree* p, int v) { while (p) { if (v == p->v) return true; else { if (v < p->v) p = p->left; else p = p->right; } } return false; } --------------------------------------------------------------------------------------------------------- 递归好处：代码更简洁清晰，可读性更好 递归可读性好这一点，对于初学者可能会反对。实际上递归的代码更清晰，但是从学习的角度要理解递归真正发生的什么，是如何调用的，调用层次和路线，调用堆栈中保存了什么，可能是不容易。但是不可否认递归的代码更简洁。一般来说，一个人可能很容易的写出前中后序的二叉树遍历的递归算法，要写出相应的非递归算法就比较考验水平了，恐怕至少一半的人搞不定。所以说递归代码更简洁明了。 递归坏处：由于递归需要系统堆栈，所以空间消耗要比非递归代码要大很多。而且，如果递归深度太大，可能系统撑不住。 楼上的有人说： 小的简单的用循环, 太复杂了就递归吧,,免得循环看不懂 话虽然简单，其实非常有道理：对于小东西，能用循环干嘛要折腾？如果比较复杂，在系统撑的住的情况下，写递归有利于代码的维护（可读性好） 另：一般尾递归（即最后一句话进行递归）和单向递归（函数中只有一个递归调用地方）都可以用循环来避免递归，更复杂的情况则要引入栈来进行压栈出栈来改造成非递归，这个栈不一定要严格引入栈数据结构，只需要有这样的思路，用数组什么的就可以。 至于教科书上喜欢n!的示例，我想只是便于递归思路的引进和建立。真正做代码不可能的。 -------------------------------------------------------------------------------------------------------------------- 循环方法比递归方法快, 因为循环避免了一系列函数调用和返回中所涉及到的参数传递和返回值的额外开销。 递归和循环之间的选择。一般情况下, 当循环方法比较容易找到时, 你应该避免使用递归。这在问题可以按照一个递推关系式来描述时, 是时常遇到的, 比如阶乘问题就是这种情况。反过来, 当很难建立一个循环方法时, 递归就是很好的方法。实际上, 在某些情形下, 递归方法总是显而易见的, 而循环方法却相当难找到。当某些问题的底层数据结构本身就是递归时, 则递归也就是最好的方法了。 递归算法向非递归算法转换 递归算法实际上是一种分而治之的方法，它把复杂问题分解为简单问题来求解。对于某些复杂问题(例如hanio塔问题)，递归算法是一种自然且合乎逻辑的解决问题的方式，但是递归算法的执行效率通常比较差。因此，在求解某些问题时，常采用递归算法来分析问题，用非递归算法来求解问题；另外，有些程序设计语言不支持递归，这就需要把递归算法转换为非递归算法。 将递归算法转换为非递归算法有两种方法，一种是直接求值，不需要回溯；另一种是不能直接求值，需要回溯。前者使用一些变量保存中间结果，称为直接转换法；后者使用栈保存中间结果，称为间接转换法，下面分别讨论这两种方法。 1. 直接转换法 直接转换法通常用来消除尾递归和单向递归，将递归结构用循环结构来替代。 尾递归是指在递归算法中，递归调用语句只有一个，而且是处在算法的最后。例如求阶乘的递归算法： long fact(int n) { if (n==0) return 1; else return n*fact(n-1); } 当递归调用返回时，是返回到上一层递归调用的下一条语句，而这个返回位置正好是算法的结束处，所以，不必利用栈来保存返回信息。对于尾递归形式的递归算法，可以利用循环结构来替代。例如求阶乘的递归算法可以写成如下循环结构的非递归算法： long fact(int n) { int s=0; for (int i=1; i<=n;i++) s=s*i; //用s保存中间结果 return s; } 单向递归是指递归算法中虽然有多处递归调用语句，但各递归调用语句的参数之间没有关系，并且这些递归调用语句都处在递归算法的最后。显然，尾递归是单向递归的特例。例如求斐波那契数列的递归算法如下： int f(int n) { 递归与分治实验报告 班级：计科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 目录 实验一循环与递归算法的应用.................................. - 2 - 一、实验目的............................................... - 2 - 二、实验内容............................................... - 2 - 三、实验步骤............................................... - 3 - 四.程序调试及运行结果分析.................................. - 5 - 五.实验总结................................................ - 5 - 附录：程序清单（程序过长，可附主要部分）.................. - 6 - 实验一循环与递归算法的应用 一、实验目的 1．掌握循环、递归算法的基本思想、技巧和效率分析方法。 2．熟练掌握循环和递归的设计要点，清楚循环和递归的异同。 3．学会利用循环、递归算法解决实际问题。 二、实验内容 1.问题描述： 题目一：打印图形 编写程序：根据参数n打印具有下面规律的图形， 如，当n=4时，图形如下： 1 5 2 8 6 3 10 9 7 4 题目二：回文判断 判断s字符串是否为“回文”的递归程序。 题目三：计算前n项和 根据参数n，计算1+2+……+n。 要求：用循环和递归分别实现 2.数据输入：个人设定，由键盘输入。 3.要求： 1）上述题目中学号为单数的做题目一和三，双数做二和三。上机前，完成程序代码的编写 2）独立完成实验及实验报告 三、实验步骤 1.理解算法思想和问题要求； 2.编程实现题目要求； 3.上机输入和调试自己所编的程序； 4.验证分析实验结果； 5.整理出实验报告。 实验一递归与分治策略 实验目的 1.了解并掌握递归的概念，递归算法的基本思想； 2.掌握分治法的基本思想方法； 3.了解适用于用分治法求解的问题类型，并能用递归或非递归的方式设计相应的分治法算法； 4.掌握分治法复杂性分析方法，比较同一个问题的递归算法与循环迭代算法的效率。预习与实验要求 1.预习实验指导书及教材的有关内容，掌握分治法的基本思想； 2.严格按照实验内容进行实验，培养良好的算法设计和编程的习惯； 3.认真听讲，服从安排，独立思考并完成实验。 实验原理 简单说来，当一个函数用它自己来定义时就称为递归。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。因此，在考虑使用递归算法编写程序时，应满足两点：1）该问题能够被递归形式描述；2）存在递归结束的边界条件。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。一般说来，一个递归算法可以转换称为一个与之等效的非递归算法，但转换后的非递归算法代码将成倍地增加。 分治是一种被广泛应用的有效方法，它的基本思想是把最初的问题分解成若干子问题，然后在逐个解决各个子问题的基础上得到原始问题的解。所谓分治就是“分而治之”的意思。由于分解出的每个子问题总是要比最初的问题容易些，因而分治策略往往能够降低原始问题的难度，或者提高解决原始问题的效率。 根据如何由分解出的子问题求出原始问题的解，分治策略又可分为两种情形：第一，原始问题的解只存在于分解出的某一个子问题中，则只需要在原始问题的一个划分中求解即可；第二，原始问题的解需要由各个子问题的解再经过综合处理得到。无论是哪一种情况，分治策略可以较快地缩小问题的求解范围，从而加快问题求解的速度。 分治策略运用于计算机算法是，往往会出现分解出来的子问题与原始问题类型相同的现象，而与原问题相比，各个子问题的规模变小了，这刚好符合递归的特征。因此分治策略往往是和递归联系在一起的。 算法递归典型例题 实验一：递归策略运用练习 三、实验项目 1．运用递归策略设计算法实现下述题目的求解过程。 题目列表如下： （1）运动会开了N天，一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求N和M。 （2）国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；……；给第i 个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？ 源程序： （3）出售金鱼问题：第一次卖出全部金鱼的一半加二分之一条金鱼；第二次卖出乘余金鱼的三分之一加三分之一条金鱼；第三次卖出剩余金鱼的四分之一加四分之一条金鱼；第四次卖出剩余金鱼的五分之一加五分之一条金鱼；现在还剩下11条金鱼，在出售金鱼时不能把金鱼切开或者有任何破损的。问这鱼缸里原有多少条金鱼？ （4）某路公共汽车，总共有八站，从一号站发轩时车上已有n位乘客，到了第二站先下一半乘客，再上来了六位乘客；到了第三站也先下一半乘客，再上来了五位乘客，以后每到一站都先下车上已有的一半乘客，再上来了乘客比前一站少一个……，到了终点站车上还有乘客六人，问发车时车上的乘客有多少？ （5）猴子吃桃。有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只（即第二天吃剩下的一半加一只，以此类推），第九天正好吃完，问猴子们摘来了多少桃子？ （6）小华读书。第一天读了全书的一半加二页，第二天读了剩下的一半加二页，以后天天如此……，第六天读完了最后的三页，问全书有多少页？ （7）日本著名数学游戏专家中村义作教授提出这样一个问题：父亲将2520个桔子分给六个儿子。分完后父亲说：“老大将分给你的桔子的1/8给老二；老二拿到后连同原先的桔子分1/7给老三；老三拿到后连同原先的桔子分1/6给老四；老四拿到后连同原先的桔子分1/5给老五；老五拿到后连同原先的桔子分1/4给老六；老六拿到后连同原先的桔子分1/3给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子？ 四、实验过程 （一）题目一：…… 1.题目分析 由已知可得，运动会最后一天剩余的金牌数gold等于运动会举行的天数由此可倒推每一 天的金牌剩余数，且每天的金牌数应为6的倍数。 2.算法构造 设运动会举行了N天， If(i==N)Gold[i]=N; Else gold[i]=gold[i+1]*7/6+i; 递归算法的实现 【基本信息】 【课标要求】 （三）算法与问题解决例举 1. 内容标准 递归法与问题解决 （1）了解使用递归法设计算法的基本过程。 （2）能够根据具体问题的要求，使用递归法设计算法、编写递归函数、编写程序、求解问题。 【教材分析】 “算法的程序实现”是《算法与程序设计》选修模块第三单元的内容，本节课是“递归算法的程序实现”，前面学习了用解析法解决问题、穷举法解决问题、在数组中查找数据、对数进行排序以及本节的前一小节知识点“什么是自定义函数”的学习，在学习自定义函数的基础上，学习递归算法的程序实现是自定义函数的具体应用，培养学生“自顶向下”、“逐步求精”的意识起着重要的作用。 『递归算法在算法的学习过程中是一个难点，在PASCAL和C语言等程序语言的学习过程中，往往是将其放在“函数与过程”这一章节中来讲解的。递归算法的实现也是用函数或是过程的自我调用来实现的。从这一点上来讲，作者对教材的分析与把握是准确的，思路是清晰的，目标是明确的。』 【学情分析】 教学对象是高中二年级学生，前面学习了程序设计的各种结构，在学习程序设计各种结构的应用过程中培养了用计算机编程解决现实中问题的能力，特别是在学习循环语句的过程中，应用了大量的“递推”算法。前一节课学习了如何自定义函数，在此基础上学习深入学习和体会自定义函数的应用。以递推算法的逆向思维进行求解问题，在学习过程中体会递归算法的思想过程。多维度的思考问题和解决问题是提高学生的学习兴趣关键。 『递归算法的本质是递推，而递推的实现正是通过循环语句来完成的。作者准确把握了学生前面的学习情况，对递归算法的本质与特征也分析的很透彻，可以说作者对教学任务的分析是很成功的，接来就要看，在成功分析的基础上作者是如何通过设计教学来解决教学难点的了。』 【教学目标】 应用数学学院信息安全专业班学号姓名 实验题目递归与分治法 综合实验评分表 实验报告 一、实验目的与要求 1.掌握递归算法的设计思想 2.掌握分治法设计算法的一般过程 3.理解并掌握算法渐近时间复杂度的分析方法 二、实验内容 1、折半查找的递归算法 （1）源程序代码 #include if(-1 != addr) cout << endl << n << "是上述整数中的第" << addr << "个数" << endl; else cout << endl << n << "不在上述的整数中" << endl << endl; getchar(); return 0; } （2）运行界面 ①查找成功 ②查找失败 西北农林科技大学信息工程学院《算法分析与设计》综合训练实习报告 题目：分治法循环赛日程表 学号 姓名 专业班级 指导教师 实践日期2011年5月16日-5月20日 目录 一、综合训练目的与要求 (1) 二、综合训练任务描述 (1) 三、算法设计 (1) 四、详细设计及说明 (3) 五、调试与测试 (4) 六、实习日志 (6) 七、实习总结 (6) 八、附录：核心代码清单 (6) 一、综合训练目的与要求 本综合训练是软件工程专业重要的实践性环节之一，是在学生学习完《算法分析》课程后进行的综合练习。本课综合训练的目的和任务： （1）巩固和加深学生对算法分析课程基本知识的理解和掌握； （2）培养利用算法知识解决实际问题的能力； （3）掌握利用程序设计语言进行算法程序的开发、调试、测试的能力； （4）掌握书写算法设计说明文档的能力； （5）提高综合运用算法、程序设计语言、数据结构知识的能力。 二、综合训练任务描述 假设有n=2k 个运动员要进行网球循环赛。设计一个满足一下要求的比赛日程表：（1）每个选手必须与其他n-1个选手各赛一次 （2）每个选手一天只能赛一次 （3）循环赛一共进行n-1天 利用Java语言开发一个界面，输入运动员的个数，输出比赛日程表。对于输入运动员数目不满足n=2k时，弹出信息提示用户。 三、算法设计 (1) 文字描述 假设n位选手顺序编号为1，2，3……n，比赛的日程表是一个n行n-1列的表格。第i行j列表示第i号选手在第j天的比赛对手，根据分治法，要求n个选手的比赛日程，只要知道其中一半的比赛日程，所以使用递归最终可以分到计算两位选手的比赛日程，然后逐级合并，得出结果。 (2) 框图 递 归 冯文科 一、递归的基本概念。 一个函数、概念或数学结构，如果在其定义或说明内部直接或间接地出现对其本身的引 用，或者是为了描述问题的某一状态，必须要用至它的上一状态，而描述上一状态，又必须用到它的上一状态……这种用自己来定义自己的方法，称之为递归或递归定义。在程序设计中，函数直接或间接调用自己，就被称为递归调用。 二、递归的最简单应用：通过各项关系及初值求数列的某一项。 在数学中，有这样一种数列，很难求出它的通项公式，但数列中各项间关系却很简单，于是人们想出另一种办法来描述这种数列：通过初值及n a 与前面临近几项之间的关系。 要使用这样的描述方式，至少要提供两个信息：一是最前面几项的数值，一是数列间各项的关系。 比如阶乘数列 1、2、6、24、120、720…… 如果用上面的方式来描述它，应该是： ???>==-1 ,1,11n na n a n n 如果需要写一个函数来求n a 的值，那么可以很容易地写成这样： 这就是递归函数的最简单形式，从中可以明显看出递归函数都有的一个特点：先处理一 些特殊情况——这也是递归函数的第一个出口，再处理递归关系——这形成递归函数的第二个出口。 递归函数的执行过程总是先通过递归关系不断地缩小问题的规模，直到简单到可以作为 特殊情况处理而得出直接的结果，再通过递归关系逐层返回到原来的数据规模，最终得出问题的解。 以上面求阶乘数列的函数)(n f 为例。如在求)3(f 时，由于3不是特殊值，因此需要计 算)2(*3f ，但)2(f 是对它自己的调用，于是再计算)2(f ，2也不是特殊值，需要计算 )1(*2f ，需要知道)1(f 的值，再计算)1(f ，1是特殊值，于是直接得出1)1(=f ，返回上 一步，得2)1(*2)2(==f f ，再返回上一步，得62*3)2(*3)3(===f f ，从而得最终解。 用图解来说明，就是 下面再看一个稍复杂点的例子。 【例1】数列}{n a 的前几项为 《算法设计与分析》 课程设计报告 题目：循环赛日程表 院（系）：信息科学与工程学院 专业班级：软工 学生姓名： 学号： 指导教师： 2018 年 1 月 8 日至 2018 年 1 月 19 日 算法设计与分析课程设计任务书 目录 1 常用算法 (1) 1.1分治算法 (1) 基本概念: (1) 1.2递推算法 (2) 2 问题分析及算法设计 (5) 2.1分治策略递归算法的设计 (5) 2.2 分治策略非递归算法的设计 (7) 2.3 递推策略算法的设计 (8) 3 算法实现 (9) 3.1分治策略递归算法的实现 (9) 3.2 分治策略非递归算法的实现 (10) 3.3 递推策略算法的实现 (12) 4 测试和分析 (15) 4.1分治策略递归算法测试 (15) 4.2分治策略递归算法时间复杂度的分析 (16) 4.3 分治策略非递归算法测试 (16) 4.4分治策略非递归算法时间复杂度的分析 (17) 时间复杂度为：O(5^(n-1)) (17) 4.5 递推策略算法测试 (17) 4.6 递推策略算法时间复杂度的分析 (18) 时间复杂度为：O(5^(n-1)) (18) 4.7 三种算法的比较 (18) 5 总结 (19) 参考文献 (20) 1 常用算法 1.1分治算法 基本概念: 在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)…… 任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。 基本思想及策略: 分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。 分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。 如果原问题可分割成k个子问题，1 淮海工学院计算机工程学院实验报告书 课程名：《算法分析与设计》 题目：实验1 递归与分治算法 班级： 学号： 姓名： 实验1 递归与分治算法 实验目的和要求 （1）进一步掌握递归算法的设计思想以及递归程序的调试技术； （2）理解这样一个观点：分治与递归经常同时应用在算法设计之中。 （3）分别用蛮力法和分治法求解最近对问题； （4）分析算法的时间性能，设计实验程序验证分析结论。 实验内容 设p1=(x1, y1), p2=(x2, y2), …, pn=(xn, yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对。 实验环境 Turbo C 或VC++ 实验学时 2学时，必做实验 数据结构与算法 核心源代码 蛮力法： #include { scanf("%d",&y[i]); } ClosestPoints(x,y,4); return 0; } int ClosestPoints(int x[ ], int y[ ], int n) { int index1, index2; //记载最近点对的下标 int d, minDist = 1000; //假设最大距离不超过1000 for (int i = 0; i < n - 1; i++) for (int j = i + 1; j < n; j++) //只考虑i＜j的点对 { d =sqrt ((x[i]-x[j])* (x[i]-x[j]) + (y[i]-y[j])* (y[i]-y[j])); if (d < minDist) { minDist = d; index1 = i; index2 = j; } } cout<<"最近的点对是："<递归与分治
算法实验报告
《递归算法与递归程序》教学设计
算法分析实验报告--分治策略
递归与循环的优缺点
递归算法和非递归算法的区别和转换
递归与分治实验报告
循环与递归算法实验
算法分析与设计实验一递归与分治策略
算法设计及分析递归算法典型例题
高中信息技术 算法与程序设计-递归算法的实现教案 教科版
算法设计与分析：递归与分治法-实验报告
(完整word版)分治法循环赛日程表实验报告
递归算法详解
使用分治策略递归和非递归和递推算法解决循环赛日程表课程设计报告
实验1++递归与分治算法
相关主题
文本预览