贪心法解活动安排问题(计算机算法设计与分析)

实验报告

课程名称：算法设计与分析实验名称：贪心法解活动安排问题任课教师：张锦雄专业：计算机科学与技术班级: 2007 级 1班学号：

姓名：蓝冠恒完成日期： 2011年1月12日

《计算机算法设计与分析》习题及答案

《计算机算法设计与分析》习题及答案 一．选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5．下列算法中通常以自底向上的方式求解最优解的是（B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是（ D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是（A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9．下面不是分支界限法搜索方式的是（D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 10．下列算法中通常以深度优先方式系统搜索问题解的是（D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法

11.备忘录方法是那种算法的变形。（ B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法 12．哈夫曼编码的贪心算法所需的计算时间为（B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 13．分支限界法解最大团问题时，活结点表的组织形式是（B ）。 A、最小堆 B、最大堆 C、栈 D、数组 14．最长公共子序列算法利用的算法是（B）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．实现棋盘覆盖算法利用的算法是（A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是（C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素（ D ） A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略（B ） A．递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 19. （D）是贪心算法与动态规划算法的共同点。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质 20. 矩阵连乘问题的算法可由（ B ）设计实现。 A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法 21. 分支限界法解旅行售货员问题时，活结点表的组织形式是（ A ）。

算法设计与分析实验报告贪心算法

算法设计与分析实验报告 贪心算法 班级：2013156 学号：201315614 姓名：张春阳哈夫曼编码 代码 #include float small1,small2; int flag1,flag2,count; typedefstructHuffmanTree { float weight; intlchild,rchild,parent; }huffman; huffmanhuffmantree[100]; void CreatHuffmanTree(intn,int m) { inti; void select(); printf("请输入%d个节点的权值:",n); for(i=0;i

printf("\n"); for(i=0;i

算法设计与分析课后部分习题答案

算法实现题3-7 数字三角形问题 问题描述： 给定一个由n行数字组成的数字三角形，如图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。编程任务： 对于给定的由n行数字组成的数字三角形，编程计算从三角形的顶至底的路径经过的数字和的最大值。数据输入： 有文件input.txt提供输入数据。文件的第1行是数字三角形的行数n，1<=n<=100。接下来的n行是数字三角形各行的数字。所有数字在0-99之间。结果输出： 程序运行结束时，将计算结果输出到文件output.txt中。文件第1行中的数是计算出的最大值。 输入文件示例输出文件示 例 input.txt output.txt 5 30 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 源程序： #include "stdio.h" voidmain() { intn,triangle[100][100],i,j;//triangle数组用来存储金字塔数值,n表示行数 FILE *in,*out;//定义in，out两个文件指针变量 in=fopen("input.txt","r"); fscanf(in,"%d",&n);//将行数n读入到变量n中

for(i=0;i=0;row--)//从上往下递归计算 for(int col=0;col<=row;col++) if(triangle[row+1][col]>triangle[row+1][col+1]) triangle[row][col]+=triangle[row+1][col]; else triangle[row][col]+=triangle[row+1][col+1]; out=fopen("output.txt","w"); fprintf(out,"%d",triangle[0][0]);//将最终结果输出到output.txt中 } 算法实现题4-9 汽车加油问题 问题描述： 一辆汽车加满油后可行驶nkm。旅途中有若干加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。并证明算法能产出一个最优解。编程任务： 对于给定的n和k个加油站位置，编程计算最少加油次数。数据输入： 由文件input.txt给出输入数据。第1行有2个正整数n和k ，表示汽车加满油后可行驶nkm，且旅途中有k个加油站。接下来的1行中，有k+1个整数，表示第k个加油站与第k-1个加油站之间的距离。第

贪心算法 会场安排问题 算法设计分析

贪心算法会场安排问题算法设计分析Description 假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的算法进行安排。(这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相应于要找的最小会场数。) 编程任务： 对于给定的k个待安排的活动，编程计算使用最少会场的时间表。 Input 输入数据是由多组测试数据组成。每组测试数据输入的第一行有1 个正整数k，表示有k个待安排的活动。接下来的k行中，每行有2个正整数，分别表示k 个待安排的活动开始时间和结束时间。时间以0 点开始的分钟计。 Output 对应每组输入，输出的每行是计算出的最少会场数。 Sample Input 5 1 23 12 28 25 35 27 80 3 6 50

Sample Output 3 程序： #include int fnPartition(int a[], int low, int high) { int i,j; int x = a[low]; i = low; j = high; while(i =a[i]) i++; if(i -1) { n = 1; for(; i <=e; i++) if(a[i]>=b[s]) s++; else n++; } return n; } int main(void) { int n,i; while(1 == scanf("%d",&n)) { int *st = new int [n]; int *et = new int [n]; for (i = 0; i

计算机算法设计与分析

算法设计与分析 实 验 报 告 班级： 姓名： 学号： (备注：共给出5个参考实验案例，根据学号尾数做对应的实验，即如尾号为1，则模仿案例实验123；尾号2，则模仿案例实验234；尾号3，即345；尾号4，同1.)

目录 实验一分治与递归 (1) 1、基本递归算法 (1) 2、棋盘覆盖问题 (2) 3、二分搜索 (3) 4、实验小结 (5) 实验二动态规划算法 (5) 1、最长公共子序列问题 (5) 2、最大子段和问题 (7) 3、实验小结 (8) 实验三贪心算法 (8) 1、多机调度问题 (8) 2、用贪心算法求解最小生成树 (10) 3、实验小结 (12) 实验四回溯算法和分支限界法 (12) 1、符号三角形问题 (12) 2、0—1背包问题 (14) 3、实验小结 (18) 实验五多种排序算法效率比较 1、算法：起泡排序、选择排序、插入排序、shell排序，归并排序、快速排序等 (19) 2、实验小结 (18)

P art1：课程设计过程 设计选题--→题目分析---→系统设计--→系统实现--→结果分析---→撰写报告 P art2：课程设计撰写的主要规范 1.题目分析：主要阐述学生对题目的分析结果，包括题目描述、 分析得出的有关模型、相关定义及假设； 2.总体设计：系统的基本组成部分，各部分所完成的功能及相互 关系； 3.数据结构设计：主要功能模块所需的数据结构，集中在逻辑设 计上； 4.算法设计：在数据结构基础上，完成算法设计； 5.物理实现：主要有数据结构的物理存储，算法的物理实现，系 统相关的实现。具体在重要结果的截图，测试案例的结果数据，核心算法的实现结果等； 6.结果分析：对第五步的分析，包括定性分析和定量分析，正确 性分析，功能结构分析，复杂性分析等； 7.结论：学生需对自己的课程设计进行总结，给出评价，并写出 设计体会； 8.附录：带有注释的源代码，系统使用说明等； 9.参考文献：列出在撰写过程中所需要用到的参考文献。

算法设计与分析课程设计报告样本

课程设计报告 课程设计名称: 算法设计与分析 系 : 三系 学生姓名: 吴阳 班级: 12软件(2)班 学号: 0311232 成绩: 指导教师: 秦川 开课时间: 年一学期 一、问题描述 1．普通背包问题

给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。选择装入的背包的物品, 使得装入背包中的物品的总价值最大, 在选择物品i装入背包时, 能够选择物品i的一部分, 而不一定要全部装入背包, 1≤i≤n。 2．0/1背包问题 给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。选择装入的背包的物品, 使得装入背包中的物品的总价值最大, 在选择物品i装入背包时, 对于每种物品i只有两种选择, 即装入背包或者不装入背包, 不能将物品装入背包多次, 也不能只装入部分的物品i。 3．棋盘覆盖问题 在一个2k x 2k个方格组成的棋盘中恰有一个方格与其它的不同称为特殊方格, 想要求利用四种L型骨牌( 每个骨牌可覆盖三个方格) 不相互重叠覆盖的将除了特殊方格外的其它方格覆盖。 二、问题分析

1．普通背包问题 对于背包问题, 若它的一个最优解包含物品j, 则从该最优解中拿出所含的物品j的那部分重量Ｗ, 剩余的将是n-1个原重物品1, 2, ······, j-1, j+1, ·····, n以及重为Ｗi－Ｗ的物品j 中可装入容量为C－Ｗ的背包且具有最大价值的物品。 2．0/1背包问题 如果当前背包中的物品的总容量是cw, 前面的k-1件物品都已经决定好是否要放入包中, 那么第k件物品是否放入包中取决于不等式 cw + wk <= M (其中, wk为第k件物品的容量, M为背包的容量)( 此即约束条件) 然后我们再寻找限界函数, 这个问题比较麻烦, 我们能够回忆一下背包问题的贪心算法, 即物品按照物品的价值/物品的体积来从大到小排列, 然后最优解为( 1, 1, 1......., 1, t, 0, 0, ......) , 其中0<=t<=1; 因此, 我们在确定第k个物品到底要不要放入的时候(在前k-1个物品已经确定的情况下), 我们能够考虑我们能够达到的最大的价值, 即我们能够经过计算只放入一部分的k物品来计算最大的价值。我们要确保当前选择的路径的最大的价值要大于我们已经选择的路径的价值。这就是该问题的限界条件。经过该条件, 能够减去很多的枝条, 大大节省运行时间。 3．棋盘覆盖问题 每次都对分割后的四个小方块进行判断, 判断特殊方格是否

计算机算法设计与分析课程设计.

成绩评定表 学生姓名吴旭东班级学号1309010236 专业信息与计算 科学课程设计题目 分治法解决棋盘覆 盖问题；回溯法解 决数字拆分问题 评 语 组长签字： 成绩 日期20 年月日

课程设计任务书 学院理学院专业信息与计算科学 学生姓名吴旭东班级学号1309010236 课程设计题目分治法解决棋盘覆盖问题；回溯法解决数字拆分问题实践教学要求与任务: 要求： 1．巩固和加深对基本算法的理解和运用，提高综合运用课程知识进行算法设计与分析的能力。 2．培养学生自学参考书籍，查阅手册、和文献资料的能力。 3．通过实际课程设计，掌握利用分治法或动态规划算法，回溯法或分支限界法等方法的算法的基本思想，并能运用这些方法设计算法并编写程序解决实际问题。 4．了解与课程有关的知识，能正确解释和分析实验结果。 任务： 按照算法设计方法和原理，设计算法，编写程序并分析结果，完成如下内容： 1.运用分治算法求解排序问题。 2. 运用回溯算法求解N后问题。 工作计划与进度安排: 第12周：查阅资料。掌握算法设计思想，进行算法设计。 第13周：算法实现，调试程序并进行结果分析。 撰写课程设计报告，验收与答辩。 指导教师： 201 年月日专业负责人： 201 年月日 学院教学副院长： 201 年月日

算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。算法 （Algorithm）是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中，算法要用计算机算法语言描述，算法代表用计算机解一类问题的精确、有效的方法。 分治法字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。在一个2^k*2^k的棋盘上， 恰有一个放歌与其他方格不同，且称该棋盘为特殊棋盘。 回溯法的基本做法是深度优先搜索，是一种组织得井井有条的、能避免不必要重复搜索的穷举式搜索算法。数字拆分问题是指将一个整数划分为多个整数之和的问题。利用回溯法可以很好地解决数字拆分问题。将数字拆分然后回溯，从未解决问题。 关键词：分治法，回溯法，棋盘覆盖，数字拆分

算法设计与分析第2版 王红梅 胡明 习题答案

精品文档习题胡明-版)-王红梅-算法设计与分析(第2答案 1 习题）—1783Leonhard Euler，17071.图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（提 出并解决了该问题。七桥问题是这样描述的：北区一个人是否能在一次步行中穿越哥尼斯堡（现东区在叫加里宁格勒，在波罗的海南岸）城中全部岛区的七座桥后回到起点，且每座桥只经过一次，南区是这条河以及河上的两个岛和七座桥的图1.7 1.7 七桥问题图草图。请将该问题的数据模型抽象出来，并判断此问题是否有解。 七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点一次步行1，经过七座桥，且每次只经历过一次2，回到起点3，该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。）用的不是除法而是减最初的欧几里德算法2．在欧几里德提出的欧几里德算法中（即法。请用伪代码描述这个版本的欧几里德算法 1.r=m-n r=0 循环直到2.m=n 2.1 n=r 2.2 r=m-n 2.3 m 输出3 ．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代3++描述。C码和 采用分治法// //对数组先进行快速排序在依次比较相邻的差//精品文档． 精品文档 #include using namespace std; int partions(int b[],int low,int high) { int prvotkey=b[low]; b[0]=b[low]; while (low=prvotkey)

算法设计(eclipse编写贪心算法设计活动安排)

陕西师大计科院2009级《算法设计与分析》课程论文集 算法设计（贪心算法解决活动安排） 设计者：朱亚君 贪心算法的计算过程如下图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。 图1贪心算法的计算过程图 若被检查的活动i的开始时间Si小于最近选择的活动j的结束时间fi，则不选择活动i，否则选择活动i加入集合A中。 贪心算法并不总能求得问题的整体最优解。但对于活动安排问题，贪心算法却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。这个结论可以用数学归纳法证明。

运用贪心算法解决活动安排问题 附录： 贪心算法的实现具体程序如下： // 贪心算法实现代码 n为活动个数 s为活动开始起始时间队列 f 为活动结束队列 A为已选入集合 import java.util.Scanner; public class a { /** * @param args */ static void GreedySelector(int s[],int f[],boolean A[]) { //第一个活动为结束时间最早进入选入队列 int n=s.length; A[1]=true; int j=2; for(int i=2;i=f[j]) { A[i]=true; j=i; } else A[i]=false; } } static void paixu(int s[],int f[])//进行以结束时间的大小排序 { int n=s.length; int m; for(int i=0;if[j+1]) { m=f[j]; f[j]=f[j+1]; f[j+1]=m;//终止时间如果前一个大于后一个就交换位置

计算机算法设计与分析期末考试复习题

1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 5. 回溯法解TSP问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、实现最长公共子序列利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。 A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解14．广度优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．背包问题的贪心算法所需的计算时间为（ B ）。

算法设计与分析课程设计报告

压缩软件课程设计书 一、问题描述： 建立一个文本文件，统计该文件中各字符频率，对各字符进行Huffman编码，将该文件至翻译成Huffman编码文件，再将Huffman编码文件翻译成原文件。 二、算法分析及思路： 对于该问题，我们做如下分析： （1）首先得构造出哈弗曼树，我们用函数HuffmanTree(int w[],int s[],int n)设计；（2）在构建哈弗曼树的基础上，进一步实现哈弗曼编码问题，我们用函数Huffmancode(char wen[])设计； （3）实现哈弗曼编码后再进一步实现哈弗曼译码问题，我们用函数Huffmandecode()设计； （4）其中编码问题中，得进一步统计出各个字符在文件中的频率，并进行一些必要的标记，我们用函数runhuffman(char wen[])设计； （5）在译码过程中，还有必要的一步是比较原文件与译码后的文件是否相同，我们用函数compare(char wen[])设计； （6）其中的文件输入我们用到类”fstream.h”中的输入输出流，并在运行的文件夹中建立一个文件名为逍遥游的文本文件，且在逍遥游文件中输入需要编码的数据。 三、主要解决的设计问题： 1.写一个对txt文件压缩和解压的程序，使用动态编码。 2.使用Huffman编码压缩和解压时，Huffman树的存储可以直接存储树结构，也可以存储所有字符的频度或权值，然后读取时建立Huffman树； 3.使用Huffman编码压缩和解压时，注意定义压缩码的结束标记，可以使用一个特殊的字符作为结束标记，也可以在压缩码之前存储其比特长度；如果使用一个特殊字符作为结束标记，则其频度为1，需要在建立Huffman树时把它看作一个独立的字符进行建树。 4.使用Huffman编码压缩和解压时，在一个缓冲区里面收集压缩码比特流，每当收集的比特数满8时，可以把这8比特通过位操作合并成一个字节写入文件（当然也可以收集满一定数目的字节后再写入文件）。写入文件的最小信息单位为字节。 四、程序设计的流程图：

算法设计与分析考试题及答案

1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。 2.算法的复杂性有_____________和___________之分，衡量一个算法 好坏的标准是______________________。 3.某一问题可用动态规划算法求解的显著特征是 ____________________________________。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y的一个最长公共子序列_____________________________。 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。 6.动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为_____________。 8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。 9.动态规划算法的两个基本要素是___________和___________。 10.二分搜索算法是利用_______________实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 2.流水作业调度问题的johnson算法的思想。

算法设计与分析课程报告

算法设计与分析课程报告 第一章 算法问题求解基础 1、算法的概念：算法是指解决问题的一种方法或过程，是由若干条指令组成的有穷序列。 2、算法的特性 ① 有穷性：一个算法必须保证执行有限步之后结束; ② 确切性：算法的每一步骤必须有确切的定义; ③ 输入： 一个算法有 0 个或多个输入， 法 本身定除了初始条件; ④ 输出： 一个算法有一个或多个输出， 是毫无意义的; ⑤可行性：算法原则上能够精确地运行, 而且人们用笔和纸做有限次运算后即可完成 3、算法与程序的关系： 区别：程序可以不一定满足可终止性。但算法必须在有限时间内结束; 程序可以没有输出 ,而算法则必须有输出; 算法是面向问题求解的过程描述，程序则是算法的实现。 联系：程序是算法用某种程序设计语言的具体实现; 程序可以不满足算法的有限性性质。 4、算法描述方式：自然语言，流程图，伪代码，高级语言。 第二章 算法分析基础 1、算法复杂性分析： 算法复杂性的高低体现运行该算法所需计算机资源（时间，空间）的多少。 算法复杂性度量： 期望反映算法本身性能，与环境无关。 理论上不能用算法在机器上真正的运行开销作为标准（硬件性能、代码质量影响） 般是针对问题选择基本运算和基本存储单位，用算法针对基本运算与基本存储单 以刻画运算对象的初始情况， 所谓 0 个输入是指算 以反映对输入数据加工后的结果。 没有输出的算法

位的开销作为标准。算法复杂性C依赖于问题规模N、算法输入I和算法本身A。即C=F（N, I,A）。 第五章分治法 1、递归算法：直接或间接地调用自身的算法。 用函数自身给出定义的函数称为递归函数。 注：边界条件与递归方程是递归函数的二个要素。 实例：①阶乘函数; ② Fibonacci 数列；③ Ackerman 函数; ④排列问题; ⑤整数划分问题; ⑥ Hanoi 塔问题 优缺点：①优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性, 因此它为设计算法、调试程序带来很大方便。 ②缺点：递归算法的运行效率低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 2、分治法的设计思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。（将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解） 分治法所能解决的问题一般具有以下几个特征： ①该问题的规模缩小到一定的程度就可以容易地解决; ②该问题可以分为若干个规模更小的相同问题，即该问题具有最有子结构性质; ③利用该问题分解出的子问题的解可以合并为该问题的解; ④该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 第六章贪心法 1、贪心算法的思想：

算法设计与分析试卷及答案

湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型：开卷 试卷类型：C 卷 考试时量：120 分钟 1. 用O 、Ω和θ表示函数f 与g 之间的关系______________________________。 ()()log log f n n n g n n == 2. 算法的时间复杂性为1, 1()8(3/7), 2 n f n f n n n =?=? +≥?，则算法的时间复杂性的阶 为__________________________。 3. 快速排序算法的性能取决于______________________________。 4. 算法是_______________________________________________________。 5. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是_________________________。 6. 在算法的三种情况下的复杂性中，可操作性最好且最有实际价值的是_____情况下的时间复杂性。 7. 大Ω符号用来描述增长率的下限，这个下限的阶越___________，结果就越有价值。。 8. ____________________________是问题能用动态规划算法求解的前提。 9. 贪心选择性质是指________________________________________________________ ____________________________________________________________。 题 号 一 二 三 四 五 总分 统分人 得 分 阅卷人

算法设计与分析实验报告

本科实验报告 课程名称：算法设计与分析 实验项目：递归与分治算法 实验地点：计算机系实验楼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）f=Ο(g)当且仅当g=Ω(f) 证明：充分性。若f=Ο(g)，则必然存在常数c1>0和n0，使得?n≥n0，有f≤c1*g(n)。由于c1≠0，故g(n) ≥ 1/ c1 *f(n)，故g=Ω(f)。 必要性。同理，若g=Ω(f)，则必然存在c2>0和n0，使得?n≥n0，有g(n) ≥ c2 *f(n).由于c2≠0，故f(n) ≤ 1/ c2*f(n)，故f=Ο(g)。 2）若f=Θ(g)则g=Θ(f) 证明：若f=Θ(g)，则必然存在常数c1>0，c2>0和n0，使得?n≥n0，有c1*g(n) ≤f(n) ≤ c2*g(n)。由于c1≠0，c2≠0，f(n) ≥c1*g(n)可得g(n) ≤ 1/c1*f(n)，同时，f(n) ≤c2*g(n)，有g(n) ≥ 1/c2*f(n)，即1/c2*f(n) ≤g(n) ≤ 1/c1*f(n)，故g=Θ(f)。 3）Ο(f+g)= Ο(max(f,g))，对于Ω和Θ同样成立。 证明：设F(n)= Ο(f+g)，则存在c1>0，和n1，使得?n≥n1，有 F(n) ≤ c1 (f(n)+g(n)) = c1 f(n) + c1g(n) ≤ c1*max{f,g}+ c1*max{f,g} =2 c1*max{f,g} 所以，F(n)=Ο(max(f,g))，即Ο(f+g)= Ο(max(f,g)) 对于Ω和Θ同理证明可以成立。 4）log(n!)= Θ(nlogn)

证明： ?由于log(n!)=∑=n i i 1 log ≤∑=n i n 1 log =nlogn ，所以可得log(n!)= Ο(nlogn)。 ?由于对所有的偶数n 有， log(n!)= ∑=n i i 1 log ≥∑=n n i i 2 /log ≥∑=n n i n 2 /2/log ≥(n/2)log(n/2)=(nlogn)/2-n/2。 当n ≥4，(nlogn)/2-n/2≥(nlogn)/4，故可得?n ≥4，log(n!) ≥(nlogn)/4，即log(n!)= Ω(nlogn)。 综合以上两点可得log(n!)= Θ(nlogn) 2. 设计一个算法，求给定n 个元素的第二大元素，并给出算法在最坏情况下使用的比较次数。（复杂度至多为2n-3） 算法： V oid findsecond(ElemType A[]) { for (i=2; i<=n;i++) if (A[1]

0021算法笔记——【贪心算法】贪心算法与活动安排问题

0021算法笔记——【贪心算法】贪心算法与活动安排问题 1、贪心算法 (1)原理：在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。 (2)特性：贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。能够用贪心算法求解的问题一般具有两个重要特性：贪心选择性质和最优子结构性质。 1)贪心选择性质 所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局 部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素。贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。证明的大致过程为：

首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始。做了贪心选择后，原问题简化为规模更小的类似子问题。然后用数学归纳法证明通过每一步做贪心选择，最终可得到问题的整体最优解。其中，证明贪心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质。 2)最优子结构性质 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。 (3)贪心算法与动态规划算法的差异: 动态规划和贪心算法都是一种递推算法，均有最优子结构性质，通过局部最优解来推导全局最优解。两者之间的区别在于：贪心算法中作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一部之前的最优解则不作保留，贪心算法每一步的最优解一定包含上一步的最优解。动态规划算法中全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解。 (4)基本思路： 1)建立数学模型来描述问题。 2)把求解的问题分成若干个子问题。 3)对每一子问题求解，得到子问题的局部最优解。 4)把子问题的解局部最优解合成原来解问题的一个解。 2、活动安排问题

算法设计与分析报告 正文

实验总体要求 为避免重复与抄袭，算法分析与设计的实验只规定算法策略，具体的算法题目由学生依据现实当中的问题自行拟定，选题的难易会影响实验得分。 实验可以分组进行，组内与组间可选不同策略的不同题目（问题）、相同策略里面的不同题目、相同题目的不同解法等，尽量避免重复。完全相同的实验报告得0分，不同的重复率扣不同的分数。分组的意义在于研究与实践不同策略的不同题目的差异、不同策略里不同题目异同、相同题目不解法之间的异同与算法效率等。 所有实验都需要包含八个组成部分： （1）实验题目 要求：一句简要的话概括或抽象出所做的实验内容 （2）个人所承担的工作 要求：独立完成报告所有内容者仅填写独立完成即可，此种情况若发现报告有雷同者得0分。协作完成的，重点写自己完成的部分，其他部分可略写，为了锻炼同学们的设计与分析能力，原则上不允许算法模型、算法描述与分析、算法实现上相同。 （3）选题背景与意义 要求：描述选题的背景、针对该问题求解的算法有多少种，发展历史及研究价值等。 （4）问题描述 要求：可以实际问题的描述，也可以某类问题的抽像描述。如果是某类问题的抽象描述，需要指出它的应用场景。 （5）算法策略选择 要求：简要说出选择该策略的理由 （6）计算模型 要求：最接近程序实现中问题求解的数学模型。指明定义域和值的范围或解空间。可以有数据结构及推导或计算公式。递归模型至少有递推公式、递归的出口。如果有的话，给出必要的证明。 （7）算法描述与分析 要求：以标准的描述方式，如流程图、伪码、语言文字。对算法进行时间和空间复杂度分析。时间复杂度要求有必要的推导步骤。 （8）算法实现 要求：给出编程语言、开发环境。给出可执行的算法代码，提供必要的注释。 （9）调试分析记录 要求：软件开发调试过程中遇到的问题及解决过程；核心算法的运行时间和所需内存空间的

《算法设计与分析实用教程》习题参考解答

《算法设计与分析实用教程》参考解答 1-1 加减得1的数学游戏 西西很喜欢数字游戏，今天他看到两个数，就想能否通过简单的加减，使最终答案等于1。而他又比较厌烦计算，所以他还想知道最少经过多少次才能得到1。 例如，给出16,9：16-9+16-9+16-9-9-9+16-9-9=1，需要做10次加减法计算。 设计算法，输入两个不同的正整数，输出得到1的最少计算次数。（如果无法得到1，则输出-1）。 （1）若输入两个不同的正整数a,b均为偶数，显然不可能得到1。 设x*a与y*b之差为“1”或“-1”,则对于正整数a,b经n=x+y-1次加减可得到1。 为了求n的最小值，令n从1开始递增，x在1——n中取值，y=n+1-x： 检测d=x*a+y*b，若d=1或-1，则n=x+y-1为所求的最少次数。 （2）算法描述 // 两数若干次加减结果为1的数学游戏 #include void main() {long a,b,d,n,x,y; printf(" 请输入整数a,b: "); scanf("%ld,%ld",&a,&b); if(a%2==0 && b%2==0) { printf(" -1\n");return;} n=0; while(1) { n++; for(x=1;x<=n;x++) { y=n+1-x;d=x*a-y*b; if(d==1 || d==-1) // 满足加减结果为1 { printf(" n=%ld\n",n);return;} } } } 请输入整数a,b: 2012,19 961 请输入整数a,b: 101,2013 606