算法分析与设计实验报告第一次附加实验
}
for(int i=1;i { Type min=inf; int j=1; for(int k=2;k<=n;k++)//找出V-S中是lowcost最小的顶点j { if((lowcost[k] { min=lowcost[k];//更新min的值 j=k; } } cout< s[j]=true;//将j添加到集合s中 for(int k=2;k<=n;k++) { if((c[j][k] { lowcost[k]=c[j][k]; closest[k]=j; } } } } 输入较小的有向带权图结果： 测试结果 附录： 完整代码（贪心法） //贪心算法最小生成树prim算法 #include #include #include #include #include using namespace std; #define inf 9999; //定义无限大的值const int N=6; template void Prim(int n,Type c[][N+1]); int main() { int c[N+1][N+1]; cout<<"连通带权图的矩阵为："< for(int i=1;i<=N;i++) //输入邻接矩阵{ for(int j=1;j<=N;j++) { cin>>c[i][j]; } } cout<<"Prim算法最小生成树选边次序如下："< clock_t start,end,over; //计算程序运行时间的算法 start=clock(); end=clock(); over=end-start; start=clock(); Prim(N,c); //调用Prim算法函数 end=clock(); printf("The time is %6.3f",(double)(end-start-over)/CLK_TCK); //显示运行时间 cout< system("pause"); return 0; } template //参数为结点个数n，和无向带权图中各结点之间的距离c[][N+1] void Prim(int n,Type c[][N+1]) { Type lowcost[N+1]; //记录c[j][closest]的最小权值 int closest[N+1]; //V-S中点j在s中的最临接顶点 bool s[N+1]; //标记各结点是否已经放入S集合| s[1]=true; //初始化s[i],lowcost[i],closest[i] for(int i=2;i<=n;i++) { lowcost[i]=c[1][i]; closest[i]=1; s[i]=false; } for(int i=1;i { Type min=inf; int j=1; for(int k=2;k<=n;k++)//找出V-S中是lowcost最小的顶点j { if((lowcost[k] { min=lowcost[k]; //更新min的值 j=k; } } cout< s[j]=true; //将j添加到s中 for(int k=2;k<=n;k++) { if((c[j][k] { lowcost[k]=c[j][k]; closest[k]=j; } } } } 算法设计与分析实验报告 贪心算法 班级：2013156 学号：201315614 姓名：张春阳哈夫曼编码 代码 #include printf("\n"); for(i=0;i 软件02 1311611006 张松彬利用贪心算法构造哈夫曼树及输出对应的哈夫曼编码 问题简述： 两路合并最佳模式的贪心算法主要思想如下： （1）设w={w0,w1,......wn-1}是一组权值，以每个权值作为根结点值，构造n棵只有根的二叉树 （2）选择两根结点权值最小的树，作为左右子树构造一棵新二叉树，新树根的权值是两棵子树根权值之和 （3）重复（2），直到合并成一颗二叉树为 一、实验目的 （1）了解贪心算法和哈夫曼树的定义（2）掌握贪心法的设计思想并能熟练运用（3）设计贪心算法求解哈夫曼树（4）设计测试数据，写出程序文档 二、实验内容 （1）设计二叉树结点数据结构，编程实现对用户输入的一组权值构造哈夫曼树（2）设计函数，先序遍历输出哈夫曼树各结点3)设计函数，按树形输出哈夫曼树 代码： #include 《数据结构与算法设计》 实验报告 ——实验一 学院： 班级： 学号： 姓名： 一、实验目的 1.通过实验实践、巩固线性表的相关操作； 2.熟悉VC环境，加强编程、调试的练习； 3.用C语言编写函数，实现循环链表的建立、插入、删除、取数据等基本操作； 4.理论知识与实际问题相结合，利用上述基本操作实现约瑟夫环。 二、实验内容 1、采用单向环表实现约瑟夫环。 请按以下要求编程实现： ①从键盘输入整数m，通过create函数生成一个具有m个结点的单向环表。环表中的 结点编号依次为1，2，……，m。 ②从键盘输入整数s（1<=s<=m）和n，从环表的第s个结点开始计数为1，当计数到 第n个结点时，输出该第n结点对应的编号，将该结点从环表中消除，从输出结点 的下一个结点开始重新计数到n，这样，不断进行计数，不断进行输出，直到输出 了这个环表的全部结点为止。 三、程序设计 1、概要设计 为实现上述程序功能，应用单向环表寄存编号，为此需要建立一个抽象数据类型：单向环表。 （1）、单向环表的抽象数据类型定义为： ADT Joseph{ 数据对象：D={ai|ai∈ElemSet,i=1,2,3……,n,n≥0} 数据关系：R1={ 实验四 哈夫曼编码的贪心算法设计（4学时） [实验目的] １. 根据算法设计需要,掌握哈夫曼编码的二叉树结构表示方法; ２. 编程实现哈夫曼编译码器; ３. 掌握贪心算法的一般设计方法。 实验目的和要求 （1）了解前缀编码的概念，理解数据压缩的基本方法； （2）掌握最优子结构性质的证明方法； （3）掌握贪心法的设计思想并能熟练运用 （4）证明哈夫曼树满足最优子结构性质； （5）设计贪心算法求解哈夫曼编码方案； （6）设计测试数据，写出程序文档。 实验内容 设需要编码的字符集为{d 1, d 2, …, dn }，它们出现的频率为 {w 1, w 2, …, wn }，应用哈夫曼树构造最短的不等长编码方案。 核心源代码 #include //选择两个parent为0，且weight最小的结点s1和s2 void Select(HuffmanTree *ht,int n,int *s1,int *s2) { int i,min; for(i=1; i<=n; i++) { if((*ht)[i].parent==0) { min=i; break; } } for(i=1; i<=n; i++) { if((*ht)[i].parent==0) { if((*ht)[i].weight<(*ht)[min].weight) min=i; } } *s1=min; for(i=1; i<=n; i++) 贪心算法经典例题 发布日期：2009-1-8 浏览次数：1180 本资料需要注册并登录后才能下载！ ·用户名密码验证码找回密码·您还未注册？请注册 您的账户余额为元，余额已不足，请充值。 您的账户余额为元。此购买将从您的账户中扣除费用0.0元。 内容介绍>> 贪心算法经典例题 在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪心算法。 从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。 我们看看下面的例子 例1 均分纸牌（NOIP2002tg） [问题描述] 有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如 N=4，4 堆纸牌数分别为： ①9 ②8 ③17 ④ 6 移动3次可达到目的： 从③取 4 张牌放到④（9 8 13 10） -> 从③取 3 张牌放到②（9 11 10 10）-> 从②取 1 张牌放到①（10 10 10 10）。 [输入]：键盘输入文件名。 文件格式：N（N 堆纸牌，1 <= N <= 100） A1 A2 … An （N 堆纸牌，每堆纸牌初始数，l<= Ai <=10000） [输出]：输出至屏幕。格式为：所有堆均达到相等时的最少移动次数。 [输入输出样例] a.in： 4 9 8 17 6 屏慕显示：3 算法分析：设a[i]为第i堆纸牌的张数（0<=i<=n），v为均分后每堆纸牌的张数，s为最小移到次数。 我们用贪心法，按照从左到右的顺序移动纸牌。如第i堆(0 本科实验报告 课程名称：算法设计与分析 实验项目：递归与分治算法 实验地点：计算机系实验楼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．代码设计： 算法设计与分析实验报告 学院：信息学院 专业：物联网1101 姓名：黄振亮 学号：20113379 2013年11月 目录 作业1 0-1背包问题的动态规划算法 (7) 1.1算法应用背景 (3) 1.2算法原理 (3) 1.3算法描述 (4) 1.4程序实现及程序截图 (4) 1.4.1程序源码 (4) 1.4.2程序截图 (5) 1.5学习或程序调试心得 (6) 作业2 0-1背包问题的回溯算法 (7) 2.1算法应用背景 (3) 2.2算法原理 (3) 2.3算法描述 (4) 2.4程序实现及程序截图 (4) 2.4.1程序源码 (4) 2.4.2程序截图 (5) 2.5学习或程序调试心得 (6) 作业3循环赛日程表的分治算法 (7) 3.1算法应用背景 (3) 3.2算法原理 (3) 3.3算法描述 (4) 3.4程序实现及程序截图 (4) 3.4.1程序源码 (4) 3.4.2程序截图 (5) 3.5学习或程序调试心得 (6) 作业4活动安排的贪心算法 (7) 4.1算法应用背景 (3) 4.2算法原理 (3) 4.3算法描述 (4) 4.4程序实现及程序截图 (4) 4.4.1程序源码 (4) 4.4.2程序截图 (5) 4.5学习或程序调试心得 (6) 作业1 0-1背包问题的动态规划算法 1.1算法应用背景 从计算复杂性来看,背包问题是一个NP难解问题。半个世纪以来,该问题一直是算法与复杂性研究的热点之一。另外,背包问题在信息加密、预算控制、项目选择、材料切割、货物装载、网络信息安全等应用中具有重要的价值。如果能够解决这个问题那么则具有很高的经济价值和决策价值，在上述领域可以获得最大的价值。本文从动态规划角度给出一种解决背包问题的算法。 1.2算法原理 1.2.1、问题描述： 给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 形式化描述：给定c >0, wi >0, vi >0 , 1≤i≤n.要求找一n元向量(x1,x2,…,xn,), xi ∈{0,1}, ?∑ wi xi≤c,且∑ vi xi达最大.即一个特殊的整数规划问题。 1.2.2、最优性原理： 设(y1,y2,…,yn)是 (3.4.1)的一个最优解.则(y2,…,yn)是下面相应子问题的一个最优解: 证明:使用反证法。若不然,设(z2,z3,…,zn)是上述子问题的一个最优解,而(y2,y3,…,yn)不是它的最优解。显然有 ∑vizi > ∑viyi (i=2,…,n) 且 w1y1+ ∑wizi<= c 因此 v1y1+ ∑vizi (i=2,…,n) > ∑ viyi, (i=1,…,n) 说明(y1,z2, z3,…,zn)是(3.4.1)0-1背包问题的一个更优解,导出(y1,y2,…,yn)不是背包问题的最优解,矛盾。 1.2.3、递推关系： 0023算法笔记——【贪心算法】哈夫曼编码问题 1、问题描述 哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%～90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。一个包含100,000个字符的文件，各字符出现频率不同，如下表所示。 有多种方式表示文件中的信息，若用0,1码表示字符的方法，即每个字符用唯一的一个0,1串表示。若采用定长编码表示，则需要3位表示一个字符，整个文件编码需要300,000位；若采用变长编码表示，给频率高的字符较短的编码；频率低的字符较长的编码，达到整体编码减少的目的，则整个文件编码需要（45×1+13×3+12×3+16×3+9×4+5×4）×1000=224,000位，由此可见，变长码比定长码方案好，总码长减小约25%。 前缀码：对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀。这种编码称为前缀码。编码的前缀性质可以使译码方法非常简单；例如001011101可以唯一的分解为0,0,101,1101，因而其译码为aabe。 译码过程需要方便的取出编码的前缀，因此需要表示前缀码的合适的数据结构。为此，可以用二叉树作为前缀码的数据结构：树叶表示给定字符；从树根到树叶的路径当作该字符的前缀码；代码中每一位的0或1分别作为指示某节点到左儿子或右儿子的“路标”。 从上图可以看出，表示最优前缀码的二叉树总是一棵完全二叉树，即树中任意节点都有2个儿子。图a表示定长编码方案不是最优的，其编码的二叉树不是一棵完全二叉树。在一般情况下，若C是编码字符集，表示其最优前缀码的二叉树中恰有|C|个叶子。每个叶子对应于字符集中的一个字符，该二叉树有|C|-1个内部节点。 给定编码字符集C及频率分布f,即C中任一字符c以频率f(c)在数据文件中出现。C的一个前缀码编码方案对应于一棵二叉树T。字符c在树T中的深度记为d T(c)。d T(c)也是字符c的前缀码长。则平均码长定义为： 银行家算法设计实验报告 银行家算法设计实验报告 一．题目分析 1.银行家算法： 我们可以把操作系统看做是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求资源相当于客户向银行家贷款。操作系统按银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程尚需求的资源量，若是系统现存的资源可以满足它尚需求的资源量，则按当前的申请量来分配资源，否则就推迟分配。 当进程在执行中继续申请资源时，先测试该进程申请的资源量是否超过了它尚需的资源量。若超过则拒绝分配，若没有超过则再测试系统尚存的资源是否满足该进程尚需的资源量，若满足即可按当前的申请量来分配，若不满足亦推迟分配。 2.基本要求： （1）可以输入某系统的资源以及T0时刻进程对资源的占用及需求情况的表项，以及T0时刻系统的可利用资源数。 （2）对T0时刻的进行安全性检测，即检测在T0时刻该状态是否安全。 （3）进程申请资源，用银行家算法对其进行检测，分为以下三种情况： A. 所申请的资源大于其所需资源，提示分配不合理不予分配并返回 B. 所申请的资源未大于其所需资源， 但大于系统此时的可利用资源，提 示分配不合理不予分配并返回。 C. 所申请的资源未大于其所需资源， 亦未大于系统此时的可利用资源，预 分配并进行安全性检查： a. 预分配后系统是安全的，将该进 程所申请的资源予以实际分配并 打印后返回。 b. 与分配后系统进入不安全状态，提示系统不安全并返回。 （4）对输入进行检查，即若输入不符合条件，应当报错并返回重新输入。 3.目的： 根据设计题目的要求，充分地分析和理解题 目，叙述系统的要求，明确程序要求实现的功能以及限制条件。 明白自己需要用代码实现的功能，清楚编写每部分代码的目的，做到有的放矢，有条理不遗漏的用代码实现银行家算法。 淮海工学院计算机工程学院实验报告书 课程名：《算法分析与设计》 题目：实验3 贪心算法 哈夫曼编码 班级：软件102班 学号：11003215 姓名：鹿迅 实验3 贪心算法 实验目的和要求 （1）了解前缀编码的概念，理解数据压缩的基本方法； （2）掌握最优子结构性质的证明方法； （3）掌握贪心法的设计思想并能熟练运用 （4）证明哈夫曼树满足最优子结构性质； （5）设计贪心算法求解哈夫曼编码方案； （6）设计测试数据，写出程序文档。 实验内容 设需要编码的字符集为{d 1, d 2, …, dn }，它们出现的频率为 {w 1, w 2, …, wn }，应用哈夫曼树构造最短的不等长编码方案。 实验环境 Turbo C 或VC++ 实验学时 2学时，必做实验 数据结构与算法 struct huffman { double weight; //用来存放各个结点的权值 int lchild,rchild,parent; //指向双亲、孩子结点的指针 }; 核心源代码 #include int min=11000; int min1; for(int k=0;k 华南农业大学期末考试试卷（A卷）2008学年第一学期考试科目：算法分析与设计 考试类型：（闭卷）考试时间：120 分钟 学号姓名年级专业 一、选择题（20分，每题2分） 1.下述表达不正确的是。 A．n2/2 + 2n的渐进表达式上界函数是O(2n) B．n2/2 + 2n的渐进表达式下界函数是Ω(2n) C．logn3的渐进表达式上界函数是O(logn) D．logn3的渐进表达式下界函数是Ω(n3) 2.当输入规模为n时，算法增长率最大的是。 A．5n B．20log 2n C．2n2 D．3nlog 3 n 3.T（n）表示当输入规模为n时的算法效率，以下算法效率最优的是。A．T（n）= T（n – 1）+1，T（1）=1 B．T（n）= 2n2 C．T（n）= T（n/2）+1，T（1）=1 D．T（n）= 3nlog 2 n 4.在棋盘覆盖问题中，对于2k×2k的特殊棋盘（有一个特殊方块），所需的L型骨 牌的个数是。 A．（4k– 1）/3 B．2k /3 C．4k D．2k 5.在寻找n个元素中第k小元素问题中，若使用快速排序算法思想，运用分治算 法对n个元素进行划分，应如何选择划分基准？下面答案解释最合理。 A．随机选择一个元素作为划分基准 B．取子序列的第一个元素作为划分基准 C．用中位数的中位数方法寻找划分基准 D．以上皆可行。但不同方法，算法复杂度上界可能不同 6.有9个村庄，其坐标位置如下表所示： 现在要盖一所邮局为这9个村庄服务，请问邮局应该盖在才能使到邮局到这9个村庄的总距离和最短。 A．（4.5，0）B．（4.5，4.5）C．（5，5）D．（5，0） 7.n个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，水桶必须打满水， 水流恒定。如下说法不正确？ A．让水桶大的人先打水，可以使得每个人排队时间之和最小 B．让水桶小的人先打水，可以使得每个人排队时间之和最小 C．让水桶小的人先打水，在某个确定的时间t内，可以让尽可能多的人打上水D．若要在尽可能短的时间内，n个人都打完水，按照什么顺序其实都一样 8.分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题， 分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题。 实验报告 （2009/2010学年第一学期） 课程名称算法分析与设计A 实验名称动态规划法 实验时间2009 年11 月20 日指导单位计算机学院软件工程系 指导教师张怡婷 学生姓名丁力琪班级学号B07030907 学院(系) 计算机学院专业软件工程 实验报告 实验名称动态规划法指导教师张怡婷实验类型验证实验学时2×2实验时间2009-11-20一、实验目的和任务 目的：加深对动态规划法的算法原理及实现过程的理解，学习用动态规划法解决实际应用中的最长公共子序列问题。 任务：用动态规划法实现求两序列的最长公共子序列，其比较结果可用于基因比较、文章比较等多个领域。 要求：掌握动态规划法的思想，及动态规划法在实际中的应用；分析最长公共子序列的问题特征，选择算法策略并设计具体算法，编程实现两输入序列的比较，并输出它们的最长公共子序列。 二、实验环境(实验设备) 硬件：计算机 软件：Visual C++ 三、实验原理及内容（包括操作过程、结果分析等） 1、最长公共子序列（LCS）问题是：给定两个字符序列X={x1,x2,……,x m}和Y={y1,y2,……,y n}，要求找出X和Y的一个最长公共子序列。 例如：X={a,b,c,b,d,a,b},Y={b,d,c,a,b,a}。它们的最长公共子序列LSC={b,c,d,a}。 通过“穷举法”列出所有X的所有子序列，检查其是否为Y的子序列并记录最长公共子序列并记录最长公共子序列的长度这种方法，求解时间为指数级别的，因此不可取。 2、分析LCS问题特征可知，如果Z={z1,z2,……，z k}为它们的最长公共子序列，则它们一定具有以下性质： （1）若x m=y n，则z k=x m=y n，且Z k-1是X m-1和Y n-1的最长公共子序列； （2）若x m≠y n且x m≠z k，则Z是X m-1和Y的最长公共子序列； （3）若x m≠y n且z k≠y n，则Z是X和Y的最长公共子序列。 这样就将求X和Y的最长公共子序列问题，分解为求解较小规模的问题： 若x m=y m，则进一步分解为求解两个（前缀）子字符序列X m-1和Y n-1的最长公共子序列问题； 如果x m≠y n，则原问题转化为求解两个子问题，即找出X m-1和Y的最长公共子序列与找出X 和Y n-1的最长公共子序列，取两者中较长者作为X和Y的最长公共子序列。 由此可见，两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列，具有最优子结构性质。 3、令c[i][j]保存字符序列X i={x1,x2,……,x i}和Y j={y1,y2,……,y j}的最长公共子序列的长度，由上述分析可得如下递推式： 0 i=0或j=0 c[i][j]= c[i-1][j-1]+1 i,j>0且x i=y j max{c[i][j-1],c[i-1][j]} i,j>0且x i≠y j 由此可见，最长公共子序列的求解具有重叠子问题性质，如果采用递归算法实现，会得到一个指数时间算法，因此需要采用动态规划法自底向上求解，并保存子问题的解，这样可以避免重复计算子问题，在多项式时间内完成计算。 4、为了能由最优解值进一步得到最优解（即最长公共子序列），还需要一个二维数组s[][]，数组中的元素s[i][j]记录c[i][j]的值是由三个子问题c[i-1][j-1]+1,c[i][j-1]和c[i-1][j]中的哪一个计算得到，从而可以得到最优解的当前解分量（即最长公共子序列中的当前字符），最终构造出最长公共子序列自身。 第四章作业 部分参考答案 1． 设有n 个顾客同时等待一项服务。顾客i 需要的服务时间为n i t i ≤≤1,。应该如何安排n 个顾客的服务次序才能使总的等待时间达到最小？总的等待时间是各顾客等待服务的时间的总和。试给出你的做法的理由（证明）。 策略： 对 1i t i n ≤≤进行排序，,21n i i i t t t ≤≤≤ 然后按照递增顺序依次服务12,,...,n i i i 即可。 解析：设得到服务的顾客的顺序为12,,...,n j j j ，则总等待时间为 ,2)2()1(1221--+++-+-=n n j j j j t t t n t n T 则在总等待时间T 中1j t 的权重最大，jn t 的权重最小。故让所需时间少的顾客先得到服务可以减少总等待时间。 证明：设,21n i i i t t t ≤≤≤ ，下证明当按照不减顺序依次服务时，为最优策略。 记按照n i i i 21次序服务时，等待时间为T ，下证明任意互换两者的次序，T 都不减。即假设互换j i ,)(j i <两位顾客的次序，互换后等待总时间为T ~ ，则有.~ T T ≥ 由于 ,2)2()1(1221--+++-+-=n n i i i i t t t n t n T ,2)()()2()1(1221--+++-++-++-+-=n n j i i i i i i i t t t j n t i n t n t n T ,2)()()2()1(~ 1221--+++-++-++-+-=n n i j i i i i i i t t t j n t i n t n t n T 则有 .0))((~ ≥--=-i j i i t t i j T T 同理可证其它次序，都可以由n i i i 21经过有限次两两调换顺序后得到，而每次交换，总时间不减，从而n i i i 21为最优策略。 计算机算法与分析 设计报告 班级：信管一班信管二班 姓名（学号）：赵立贺(060340219) 赵艳（060340114）刘辉（060340125）王勇（060340116）万玉琪（060340213）刘旺（060340205）指导教师：赵晓峰姚天祥 设计地点：信息系统实验室 信息管理系 2008年12月13日 一、实验名称： 用贪心算法、回溯算法、动态规划等解决汽车加油次数最少问题。 二、实验目的： 课程设计是《计算机算法与设计》课程不可缺少的重要实践性环节。通过实践教学，要达到以下目的： （1）使学生掌握线性表、栈、队列、串、树、二叉树、图、集合等各种典型抽象数据类型的数学模型及其所支持基本运算的实现方法； （2）使学生掌握以抽象数据类型为模块的面向对象程序设计方法； （3）使学生提高对实际问题的分析、设计和实现能力； （4）为学生后续课程的学习及课程设计打下坚实的实践基础。 三、使用的策略： 贪心算法、回溯算法等。 四、实验内容： （一）问题描述 一辆汽车加满油后可以行驶N千米。旅途中有若干个加油站。指出若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。 给出N，并以数组的形式给出加油站的个数及相邻距离，指出若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。要求：算法执行的速度越快越好。 （二）问题分析（前提行驶前车里加满油） 对于这个问题我们有以下几种情况：设加油次数为k，每个加油站间距离为a[i]；i=0，1，2，3……n 1.始点到终点的距离小于Ｎ，则加油次数k=0； 2.始点到终点的距离大于N， A 加油站间的距离相等，即ａ[i]=a[j]=L=N，则加油次数最少k=n； B 加油站间的距离相等，即ａ[i]=a[j]=L>N，则不可能到达终点； C 加油站间的距离相等，即ａ[i]=a[j]=L 算法与分析实验报告软件工程专业 安徽工业大学 指导老师：许精明 实验内容 1：杨辉三角 2：背包问题 3：汉诺塔问题 一：实验目的 1：掌握动态规划算法的基本思想，学会用其解决实际问题。 2：通过几个基本的实验，提高算法分析与设计能力，提高动手操作能力和培养良好的编程习惯。 二：实验内容 1：杨辉三角 2：背包问题 3：汉诺塔问题 实验一：杨辉三角 问题分析： ①每行数字左右对称，由1开始逐渐变大，然后变小，回到1。 ②第n行数之和为2^n。 ③下一行每个数字等于上一行的左右两个数字之和。 算法设计及相关源代码： public void yanghui(int n) { int[] a = new int[n]; if(n==1){ System.out.println(1); }else if(n==2) { System.out.print(1 + " " +1); }else{ a[1]=1; System.out.println(a[1]); a[2]=1; System.out.println(a[1]+" "+a[2]); for(int i=3;i<=n;i++){ a[1]=a[i]=1; for(int j=i-1;j>1;j--){ a[j]=a[j]+a[j-1]; } for(int j=1;j<=i;j++){ System.out.print(a[j]+" "); } System.out.println(); } } } 实验结果：n=10 实验二：0-1背包问题 问题分析：：令V(i,j)表示在前i(1<=i<=n)个物品中能够装入容量为就 j(1<=j<=C)的背包中的物品的最大价值，则可以得到如下的动态规划函数: (1) V(i,0)=V(0,j)=0 (2) V(i,j)=V(i-1,j) j 实验名称：贪心算法实例编程 求解最优服务次序问题 1、实验目的： 1)理解贪心算法的概念 2)掌握贪心算法的基本要素 3)掌握设计贪心算法的一般步骤 4)针对具体问题，能应用贪心算法设计有效算法 5)用C++实现算法，并且分析算法的效率 2、实验设备及材料： 硬件设备：PC机 机器配置：双核cpu频率2.2GHz,内存2G 操作系统：Windows 7 开发工具：VC++6.0 3、实验内容： ①问题描述 设有n个顾客同时等待一项服务。顾客i需要的服务时间为t i，1≤i≤n。 应如何安排n个顾客的服务次序才能使平均等待时间达到最小？平均等待时间是n恶搞顾客等待服务时间的总和除以n。 ②编程任务 对于给定的n个顾客需要的服务时间，计算最优服务次序。 ③样例 例如，现在有5个顾客，他们需要的服务时间分别为：56，12，5，99，33。 那么，按照所需服务时间从小到大排序为：5,12,33,56,99。排序后的顾客等待服务完成的时间为：5，17，50，106，205；和为：383；平均等待时间为：76.6。 4、实验方法步骤及注意事项： ①实验步骤 a、分析问题，确定最优的贪心选择； b、针对贪心选择过程进行算法设计； c、举例验证算法的正确性； d、上机调试算法。 ②解题思路 1)求解最优服务次序问题的贪心策略为：先为所需服务时间最短的顾客服务。 2)使用贪心算法求解最优服务次序问题的算法，用C++语言描述。 ①.最优值：(贪心算法) text(int n,int x[],int s[])//s[]为保存每个顾客等待时间的数组 { int i; int sum=0; for(i=0;i 《算法设计》课程报告 课序号： 01 学号： 2012141461134 姓名：刘佳玉 任课教师：陈瑜 评阅成绩： 评阅意见： 提交报告时间：2014年 6 月 16 日 贪心算法 1、问题描述 （这是我在soj上找的一道题，以前没做出来，现在用贪心的思想做出来了） 约翰要去钓鱼。他有h小时可用（1≤h≤16），在这个地区有n个湖泊（2≤n≤25），所有的湖泊沿着一条单行道可到达。约翰从湖泊1开始，他可以在任何湖泊结束。他只能从一个湖，到下一个，但他没有必要停在任何湖除非他想停。对于每个i = 1，……，n-1，ti 表示从湖i到湖i+1的5分钟的时间间隔（0 < ti < = 192）。例如，t3 = 4意味着它从湖3湖4需要20分钟的时间。 为了帮助他们规划自己的钓鱼旅行，约翰已经收集了一些关于湖泊信息。对于每个湖泊的i，能钓到的鱼在最初的5分钟的数量，用fi表示（fi > = 0），是已知的。每钓5分钟的鱼，能钓到的鱼在接下来的5分钟的间隔降低一个恒定的数di（di＞＝0）。如果能钓到的鱼在一个时间区的数量小于或等于di，将不会有更多的鱼留在湖里在下一个时间间隔。为了简化规划，约翰认为没有人会在影响他期待钓到的鱼的数量的湖里钓鱼。 写一个程序来帮助约翰计划他的最大化期望钓到的鱼的数量的钓鱼之旅。在每个湖花费的时间数必须是5的倍数。 这个问题包含多个测试案例！ 一个多输入的第一行是一个整数N，然后一个空白行后的N个输入块。每个输入块由问题描述中的格式表示的。每个输入块之间有一个空行。 输出格式包含N个输出块。输出块之间要有一个空白行。 输入 在输入中，会给你一个案例输入的数量。每一种情况下，以n开始，其次是h，接下来有一行n个整数指定fi（1 < =i< = n），然后有一行n个整数di（1≤i＜＝n），最后，有一行n - 1的整数ti（1≤i＜＝n-1）。输入在n=0的情况下终止。 输出 算法设计与分析课程实验项目目录 学生：学号： *实验项目类型：演示性、验证性、综合性、设计性实验。 *此表由学生按顺序填写。 本科实验报告专用纸 课程名称算法设计与分析成绩评定 实验项目名称蛮力法指导教师 实验项目编号实验项目类型设计实验地点机房 学生学号 学院信息科学技术学院数学系信息与计算科学专业级 实验时间2012年3月1 日～6月30日温度24℃ 1.实验目的和要求： 熟悉蛮力法的设计思想。 2.实验原理和主要容： 实验原理：蛮力法常直接基于问题的描述和所涉及的概念解决问题。 实验容：以下题目任选其一 1).为蛮力字符串匹配写一段可视化程序。 2).写一个程序，实现凸包问题的蛮力算法。 3).最著名的算式谜题是由大名鼎鼎的英国谜人 H.E.Dudeney(1857-1930)给出的： S END +MORE MONEY . 这里有两个前提假设： 第一，字母和十进制数字之间一一对应，也就是每个字母只代表一个数字，而且不同的字母代表不同的数字；第二，数字0不出现在任何数的最左边。求解一个字母算术意味着找到每个字母代表的是哪个数字。请注意，解可能并不是唯一的，不同人的解可能并不相同。3.实验结果及分析： （将程序和实验结果粘贴，程序能够注释清楚更好。） 该算法程序代码如下： #include "stdafx.h" #include "time.h" int main(int argc, char* argv[]) { int x[100],y[100]; int a,b,c,i,j,k,l,m,n=0,p,t1[100],num; int xsat[100],ysat[100]; printf("请输入点的个数：\n"); scanf("%d",&num); getchar(); clock_t start,end; start=clock(); printf("请输入各点坐标:\n"); for(l=0;l 贪心算法概论 贪心算法一般来说是解决“最优问题”，具有编程简单、运行效率高、空间 复杂度低等特点。是信息学竞赛中的一个有为武器，受到广大同学们的青睐。本 讲就贪心算法的特点作些概念上的总结。 一、贪心算法与简单枚举和动态规划的运行方式比较 贪心算法一般是求“最优解”这类问题的。最优解问题可描述为：有n个输入，它的解是由这n 个输入的某个子集组成，并且这个子集必须满足事先给定的条 件。这个条件称为约束条件。而把满足约束条件的子集称为该问题的可行解。这 些可行解可能有多个。为了衡量可行解的优劣，事先给了一个关于可行解的函数，称为目标函数。目标函数最大（或最小）的可行解，称为最优解。 a)求“最优解”最原始的方法为搜索枚举方案法（一般为回溯法）。 除了极简单的问题，一般用深度优先搜索或宽度优先搜索。通常优化方法为利用约束条件进行可行性判断剪枝；或利用目标函数下界（或上界），根据当前最 优解进行分枝定界。 b)其次现今竞赛中用的比较普遍的动态规划（需要满足阶段无后效性原则）。 动态规划主要是利用最最优子问题的确定性，从后向前（即从小规模向大规模）得到当前最优策略，从而避免了重复的搜索。 举例说明：求多段图的最短路径。 在图（1）中，我们省略了各线段的长度。 如果用回溯法，搜索树大致如下： 显然，上面的搜索有大量重复性工作。比如节点8、9、10到11的最短路分别被调用了9次，从节点5、6、7到节点11也分别搜索了3次。 如果先算出节点8、9、10到11的最短路，由于它与前面的点无关，因此最优值确定下来，再用它们求定节点5、6、7 到节点11 的最短路径。同理，再用节 点5、6、7 的最优值，来求节点2、3、4 优值。最后从节点2、3、4 推出1 到 11的最优值。显然复杂度大为降低。 当然，如果本题把简单搜索改为搜索＋记忆化的方法，则就是得能动态规划的原理，本质上就是动态规划，只是实现的方法不同与传统的表格操作法。搜索＋记忆化算法有其特有的特点，以后再讨论。 c)贪心算法则不同，它不是建立在枚举方案的基础上的。它从前向后，根据当前情况，“贪心地”决定出下一步，从而一步一步直接走下去，最终得到解。 假如上面的例子中，我们定下这样的贪心策略：节点号k%3= =1。则有图3：算法设计与分析实验报告贪心算法
贪心算法构造哈夫曼树
北京理工大学《数据结构与算法设计》实验报告实验一
实验三.哈夫曼编码的贪心算法设计
贪心算法经典例题
算法设计与分析实验报告
算法设计与实验报告讲解
0023算法笔记——【贪心算法】哈夫曼编码问题
银行家算法设计实验报告
哈夫曼编码_贪心算法
2009.1算法设计与分析课程期末试卷-A卷(自测 )
南京邮电大学算法设计实验报告——动态规划法
4+四+贪心算法+习题参考答案
贪心算法解汽车加油问题实验报告
算法与设计实验报告
贪心算法求解最优服务次序问题
算法设计实验报告(川大陈瑜)
《算法设计与分析》实验报告
贪心算法概论
相关主题
文本预览