算法设计与分析大作业答案

西北工业大学网络教育学院

2020年10月大作业答题纸

学习中心： 课程名称： 成绩： 注意事项：

1. 考生须用黑色或蓝色签字笔、钢笔、圆珠笔作答（画图题可用铅笔做图），其他笔作答均无效。

2. 考生须按题目顺序作答，注明与试题相对应的题号，按题目要求作答。

学

号

姓 名 考试 日期 年 月 日 题

号

一 二 三 四 五 六 七 八 九 十 得

分

《ACM算法与数据结构设计》大作业

《ACM算法与数据结构设计》课程大作业报告 题目：五位以内的对称素数 学生姓名 班级学号 学生学院计算机软件学院 学生专业计算机科学与技术 联系电话 电子邮 指导教师 指导单位计算机学院软件工程系 日期2011.5.24

注意事项 （1）课程大作业从《ACM算法与数据结构设计》课程实验二（2011年4月19日）或实验三（2011年5月10日）中任选一个课题完成。（2）课程大作业内容包括课题名称、课题内容和要求、课题分析、概要设计、详细设计、测试数据及其结果分析、调试过程中的问题、参考资料列表、课程小结等。 （3）课程报告可以打印，也可以手写，但前面两页内容、大作业撰写纲要、课程小结不可遗漏和更换。 （4）课程小结给出ACM程序设计过程的收获、遇到的问题，遇到问题解决问题过程的思考、程序调试能力的思考等，需要手写签字。（5）课程大作业提交时间为2011年5月24日（第14周星期二）晚19:00~20:00，地点：计算中心A机房。

一、课题名称： 五位以内的对称素数 二、课题内容和要求： 题目：判断一个数是否为对称且不大于五位数的素数。 要求：判断输入的一组数据（正整数）是否是五位以内的对称素数，逐个判断并输出“yes”或“no” 三、课题分析： 定义两个函数分别判断数据是否为素数（bool isprime(int n)），是否是对称数（bool issym(int n)）；在main()函数中利用if()语句来判断该数据是否是五位以内的数。只有同时满足三个条件，才能判断一个数据是五位以内的对称素数，输出“yes”；否则输出“no”。 输入输出方案： 输入: 输入数据含有不多于50个的正整数(0

《程序设计与算法综合实践》期末大作业题目及评分标准

2017级《程序设计与算法综合实践》 期末大作业题目及评分标准 有如下情况之一者，为不及格。 （1）未能完成所选题目评分标准的最低要求。 （2）抄袭他人成果。 （3）大作业检查时不带电脑，或电脑没有C语言开发环境。 （4）出勤次数、课堂表现等不符合学校相关教学文件规定等其他情况。 备选题目目录 1.图书购买系统...............................................................................................................- 2 - 2.物流信息管理系统 ....................................................................................................- 3 - 3.PM2.5实时信息管理系统 ............................................................ - 5 - 4.电影评论系统 ............................................................................... - 6 - 5.游戏角色属性分析........................................................................ - 8 - 6.KTV点歌系统 ................................................................................ - 9 - 7.英语词斩系统 ............................................................................. - 11 - 8.校运动会成绩管理系统.............................................................. - 14 - 9.通讯录管理系统 ......................................................................... - 15 - 10.机票购买系统 ............................................................................. - 16 - 11.车辆销售管理系统...................................................................... - 17 - 12.饮品自动贩卖机系统.................................................................. - 18 -

软件系统分析与设计大作业

《软件系统分析与设计》 期末大作业 选题名称：游戏平台管理系统设计人：徐文豪刘青海 赖超宇甘智宏 班级：软工143班 南昌大学软件学院 2016.6.1

目录 一、整体描述 (2) 二、需求分析 (3) 三、系统功能概况 (4) 四、类的属性与方法 (5) 五、系统界面界限 (11) 六、设计模型 (13) 七、设计原则 (17) 八、设计模式······················

一、整体描述 随着移动通讯的发展，手机应用也越来越多，其中，游戏应用占据了很大的比重，游戏平台管理系统是整合了大量游戏应用，以及玩家线上交流的平台。 主要受众群：拥有移动端或电脑端的人群。 应用前景：移动互联的发展为游戏平台的发展提供了很大的生存空间，应用前景十分广阔 盈利方式：向平台中游戏的开发商收取一定的费用，游戏玩家向游戏中注入资金时，收取一定比例的游戏收入。 面临的困难：游戏平台前期的推广，提高游戏平台本身对开发商和游戏玩家的吸引力，游戏平台能否适应大部分游戏玩家的要求。 玩家首先要注册账号，然后就可以在上面下载游戏应用，上传自己的游戏资源。同时，根据玩家的活跃程度获取相应积分，用积分可以兑换游戏礼包，也会根据玩家等级在游戏装备上给与相应的优惠和等级奖励。玩家在每一款游戏的评论区都可以交流游戏经验，提出意见和建议，以便游戏及时更新，弥补相应不足。玩家也可以建立游戏工会，不同游戏的玩家都可以加入，分享自己的游戏心得或者转赠游戏装备或积分。

二、需求分析 时间when：游戏厂商：随时；注册用户：随时；管理人员：正常工作时间。 地点Where：游戏厂商，管理人员：工作地点；注册用户：随地 人员who：游戏厂商，管理人员，注册用户， What：游戏厂商：推广游戏，管理人员：扩大服务，盈利；注册人员：玩游戏。 Why：游戏厂商：推广力度不大，效果不好，管理人员：方便管理，注册用户：良好的游戏环境。 性能Performance：系统提供服务的效率，响应时间快，由于是手机端的APP吞吐量不需要太大。 成本Cost：实现系统需要付出的代价，耗费****元 时间Time：2016年6月3日 可靠性Reliability: 需要系统长时间正确运行的能力 安全性Security: 由于该平台会涉及资金的流动，所以需要对信息安全的保护能力。 合规性Compliance: 需要符合各种行业的标准，法律法规，规范。技术性Technology:要求基于安卓平台开发。 兼容性Compatibility:需要与一些支付平台进行兼容能力。还有对游戏的兼容性。

算法分析大作业动态规划方法解乘法表问题和汽车加油行驶问题#精选.

算法分析大作业 动态规划方法解 乘法表问题和汽车加油行驶问题目录 1.动态规划解乘法表问题 1.1问题描述------ 1.2算法设计思想------ 1.3设计方法------ 1.4源代码------ 1.5最终结果------ 2.动态规划解汽车加油行驶问题 2.1问题描述------ 2.2算法设计思想------ 2.3设计方法------ 2.4源代码------ 2.5最终结果------ 3.总结

1.动态规划解决乘法表问题 1.1问题描述 定义于字母表∑{a,b,c)上的乘法表如表所示： 依此乘法表,对任一定义于∑上的字符串,适当加括号表达式后得到一个表达式。 例如,对于字符串x=bbbba,它的一个加括号表达式为(b(bb))(ba)。依乘法表,该表达式的值为a。 试设计一个动态规划算法,对任一定义于∑上的字符串x=x1x2…xn，计算有多少种不同的加括号方式,使由x导出的加括号表达式的值为a。 1.2算法设计思想 设常量a,b,c 分别为 1, 2 ,3 。n 为字符串的长度。 设字符串的第 i 到第 j 位乘积为 a 的加括号法有result[i][j][a] 种， 字符串的第 i 到第 j 位乘积为 b 的加括号法有result[i][j][b] 种, 字符串的第 i 到第 j 位乘积为 c 的加括号法有 result[i][j][c] 种。 则原问题的解是：result[i][n][a] 。 设 k 为 i 到 j 中的某一个字符，则对于 k 从 i 到 j ：result[i][j][a] += result[i][k][a] * result[k + 1][j][c] + result[i][k][b] * result[k + 1][j][c] + result[i][k][c] * result[k + 1][j][a]; result[i][j][b] += result[i][k][a] * result[k + 1][j][a] + result[i][k][a] * result[k + 1][j][b] + result[i][k][b] * result[k + 1][j][b]; result[i][j][c] += result[i][k][b] * result[k + 1][j][a] + result[i][k][c] * result[k + 1][j][b] + result[i][k][c] * result[k + 1][j][c];

对并行算法的介绍和展望——学期大作业

《计算机系统结构》大作业 对并行算法的介绍和展望 专业计算机科学与技术 班级 111 学号 111425020133 姓名完颜杨威 日期 2014年4月17日 河南科技大学国际教育学院

对并行算法的介绍和展望 我们知道，算法是求解问题的方法和步骤。而并行算法就是用多台处理机联合求解问题的方法和步骤，其执行过程是将给定的问题首先分解成若干个尽量相互独立的子问题，然后使用多台计算机同时求解它，从而最终求得原问题的解。并行算法的研究涉及到理论、设计、实现、应用等多个方面，要保持并行算法研究的持续性和完整性，需要建立一套完整的“理论－设计－实现－应用”的学科体系，也就是所谓的并行算法研究的生态环境。其中，并行算法理论是并行算法研究的理论基础，包含并行计算模型和并行计算复杂性等；并行算法的设计与分析是并行算法研究的核心内容；并行算法的实现是并行算法研究的应用基础，包含并行算法实现的硬件平台和软件支撑技术等；并行应用是并行算法研究的发展动力，除了包含传统的科学工程计算应用外，还有新兴的与社会相关的社会服务型计算应用等。 并行算法主要分为数值计算问题的并行算法和非数值计算问题的并行算法。而并行算法的研究主要分为并行计算理论、并行算法的设计与分析、和并行算法的实现三个层次。现在，并行算法之所以受到极大的重视，是为了提高计算速度、提高计算精度，以及满足实时计算需要等。然而，相对于串行计算，并行计算又可以划分成时间并行和空间并行。时间并行即流水线技术，空间并行使用多个处理器执行并发计算，当前研究的主要是空间的并行问题。并行算法是一门还没有发展成熟的学科，虽然人们已经总结出了相当多的经验，但是远远不及串行算法那样丰富。并行算法设计中最常用的的方法是PCAM方法，即划分，通信，组合，映射。首先划分，就是将一个问题平均划分成若干份，并让各个处理器去同时执行；通信阶段，就是要分析执行过程中所要交换的数据和任务的协调情况，而组合则是要求将较小的问题组合到一起以提高性能和减少任务开销，映射则是要将任务分配到每一个处理器上。任何一个并行算法必须在一个科学的计算模型中进行设计。我们知道，任何算法必须有计算模型。任何并行计算模型必须要有为数不多、有明确定义的、可以定量计算的或者可以实际测量的参数，这些参数可以构成相应函数。并行计算模型是算法设计者与体系结构研究者之间的一个桥梁，是并行算法设计和分析的基础。它屏蔽了并行机之间的差异，从并行机中抽取若干个能反映计算特性的可计算或可测量的参数，并按照模型所定义的计算行为构造成本函数，以此进行算法的复杂度分析。 经过多年的发展，我国在并行算法的研究上也取得了显著进展，并行计算的应用已遍布天气预报、石油勘探、航空航天、核能利用、生物工程等领域，理论研究与应用普及均取得了很大发展。随着高性价比可扩展集群并行系统的逐步成熟和应用，大规模电力系统潮流并行计算和分布式仿真成为可能。目前，并行算法在地震数据处理中应用已较为成熟，近年来向更实用的基于PC机群的并行技术发展.然而，在非地震方法中，并行算法应用较少见文献报道，研究尚处于初级研究阶段。在大地电磁的二维和三维正、反演问题上，并行计算技术逐渐得到越来越多关注和重视.随着资源和能源需求的增长，地球物理勘探向深度和广度快速发展，大幅增长的数据量使得高性能并行计算机和高效的并行算法在勘探地球物理学中的发展和应用将占据愈来愈重要的地位。计算机技术在生物医学领域已经广泛应用，实践证明，并行算法在生物医学工程的各个领域中具有广泛的应用价值，能有效提高作业效率。随着电子科学技术的发展，电磁问题变得越来越复杂，为了在有限的计算机资源条件下求解大规模复杂电磁问题，许电磁学家已

0-1背包问题的算法设计策略对比与讲解

算法设计与分析大作业 班级：电子154 姓名：吴志勇 学号： 1049731503279 任课老师：李瑞芳 日期： 2015.12.25

算法设计与分析课程论文 0-1背包问题的算法设计策略对比与分析 0 引言 对于计算机科学来说，算法的概念是至关重要的。在一个大型软件系统的开发中，设计出有效的算法将起到决定性的作用。通俗的讲，算法是解决问题的一种方法。也因此，《算法分析与设计》成为计算科学的核心问题之一，也是计算机科学与技术专业本科及研究生的一门重要的专业基础课。算法分析与设计是计算机软件开发人员必修课，软件的效率和稳定性取决于软件中所采用的算法；对于一般程序员和计算机专业学生，学习算法设计与分析课程，可以开阔编程思路，编写出优质程序。通过老师的解析，培养我们怎样分析算法的“好”于“坏”，怎样设计算法，并以广泛用于计算机科学中的算法为例，对种类不同难度的算法设计进行系统的介绍与比较。本课程将培养学生严格的设计与分析算法的思维方式，改变随意拼凑算法的习惯。本课程要求具备离散数学、程序设计语言、数据结构等先行课课程的知识。 1 算法复杂性分析的方法介绍 算法复杂性的高低体现在运行该算法所需要的计算机资源的多少上，所需的资源越多，该算法的复杂性越高；反之，所需资源越少，该算法的复杂性越低。对计算机资源，最重要的是时间与空间（即存储器）资源。因此，算法的复杂性有时间复杂性T(n)与空间复杂性S(n)之分。 算法复杂性是算法运行所需要的计算机资源的量，这个量应集中反映算法的效率，并从运行该算法的实际计算机中抽象出来，换句话说，这个量应该只依赖要解决的问题规模‘算法的输入和算法本身的函数。用C表示复杂性，N,I和A表示问题的规模、算法的输入和算法本身规模，则有如下表达式： C=F(N,I,A) T=F(N，I,A) S=F(N，I,A) 其中F(N,I,A)是一个三元函数。通常A隐含在复杂性函数名当中，因此表达式中一般不写A。 即：C=F(N,I) T=F(N,I) S=F(N,I) 算法复杂性中时间与空间复杂性算法相似，所以以下算法复杂性主要以时间复杂性为例： 算法的时间复杂性一般分为三种情况：最坏情况、最好情况和平均情况。下面描述算法复杂性时都是用的简化的复杂性算法分析，引入了渐近意义的记号O,Ω，θ，和o。 O表示渐近上界Ω表示渐近下界： θ表示同阶即：f(n)= O(g(n))且 f(n)= Ω（g(n)） 2 常见的算法分析设计策略介绍 2.1 递归与分治策略 分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。 直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。 由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。 分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。 递归算法举例： 共11页第1页

算法设计与分析课程大作业

题目作业调度问题及算法分析 学院名称：计算机与信息工程学院 专业名称：计算机科学与技术

目录 《算法设计与分析》课程大作业.................................................................... 错误!未定义书签。一．动态规划算法解决流水作业调度. (4) 1、问题描述 (4) 2、算法分析 (4) 3. 算法的描述 (5) 4、部分算法实现 (6) 5. 运行结果 (8) 6、时空效率分析 (8) 二．贪心算法解多机调度问题 (8) 1、问题描述 (8) 2、算法分析 (9) 3.部分算法实现 (9) 4.计算复杂性分析 (11) 5. 运行结果 (12) 三．回溯法解决批作业调度问题 (12) 1.问题描述 (12) 2.算法思想 (13) 3. 部分算法实现 (14) 4.运行结果 (15) 5.时间复杂性分析 (15) 四．作业调度算法比较 (16) 五．课程学习总结 (16)

摘要： 在现代企业中，作业调度已成为提高资源利用率、从而提高企业运行效益的关键环节之一。把各个作业分配到车间现有的设备上，并确定它们的先后次序，这是一项复杂的工作本文就作业调度排序问题进行了研究，通过对几个经典作业调度算法的分析讨论，总结了各个算法对作业调度的求解过程，并给出了每个算法的复杂度及性能分析。 关键词：作业调度；动态规划；贪心算法；回溯法；

一．动态规划算法解决流水作业调度 1、问题描述 给定n 个作业，每个作业有两道工序，分别在两台机器上处理。一台机器一次只能处理一道工序，并且一道工序一旦开始就必须进行下去直到完成。一个作业只有在机器1上的处理完成以后才能由机器2处理。假设已知作业i 在机器j 上需要的处理时间为t[i,j]。流水作业调度问题就是要求确定一个作业的处理顺序使得尽快完成这n 个作业。 2、算法分析 直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。在一般情况下，机器M2上会有机器空闲和作业积压2种情况。 在一般情况下，机器M1开始加工S 中作业时，机器M2还在加工其他作业，要等时间t 后才可利用。将这种情况下完成S 中作业所需的最短时间记为T(S,t)。流水作业调度问题的最优值为T(N,0)。 由流水作业调度问题的最优子结构性质可知， )}},{({min )0,(1i i n i b i N T a N T -+=≤≤（1）

2015数学建模选修大作业

中华女子学院 成绩2014 — 2015学年第二学期期末考试 （论文类） 论文题目数学建模算法之蒙特卡罗算法 课程代码1077080001 课程名称数学建模 学号130801019

姓名陈可心 院系计算机系 专业计算机科学与技术 考试时间2015年5月27日 一、数学建模十大算法 1、蒙特卡罗算法 该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的正确性，是比赛时必用的方法。接下来本文将着重介绍这一算法。 2、数据拟合、参数估计、插值等数据处理算法 比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用Matlab作为工具。 3、线性规划、整数规划、多元规划、二次规划等规划类问题 建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo软件实现。这个也是我们数学建模选修课时主要介绍的问题，所以对这方面比较熟悉，也了解了Lindo、Lingo软件的基本用法。 4、图论算法 这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，上学期数据结构课程以及离散数学课程中都有介绍。它提供了对很多问题都很有效的一种简单而系统的建模方式。

5、动态规划、回溯搜索、分治算法、分支定界等计算机算法 这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中 6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法 这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用。 7、网格算法和穷举法 网格算法和穷举法都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具。 8、一些连续离散化方法 很多问题都是实际来的，数据可以是连续的，而计算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。 9、数值分析算法 如果在比赛中采用高级语言进行编程的话，那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。10、图象处理算法 赛题中有一类问题与图形有关，即使与图形无关，论文中也应该要不乏图片的，这些图形如何展示以及如何处理就是需要解决的问题，通常使用Matlab进行处理。 二、蒙特卡罗方法 2.1算法简介 蒙特·卡罗方法（Monte Carlo method），也称统计模拟方法，1946年，美国拉斯阿莫斯国家实验室的三位科学家John von Neumann,Stan Ulam 和 Nick

算法分析大作业 寻找变位词

深圳大学研究生课程论文 题目大作业：变位词实验成绩 专业计算机与软件学院软件工程 课程名称、代码 年级2015 姓名文成 学号2150230509 时间2015 年12 月任课教师杨烜

一、大作业要求与内容 大作业内容： 在下列问题中挑选一个问题，选用适当的算法进行实现，在课堂上，针对该问题完成一个10分钟的论文演讲与演示，并提交演讲PPT。（30分） 在一个类似英语词典的大文件中找出变位词的所有集合，例如，tea和eat是变位词，同属一个集合，找出所有这种集合。 大作业要求：（70分） （1）要求演示算法解决问题的完整过程，如果我对解这个问题一无所知，看了你的解决过程，就要能理解算法是如何解决问题的； （2）要求交互界面活泼生动，演示速度可控； （3）尽可能提供丰富的功能让我理解你是如何解决这个问题的； （4）提交源程序、大作业报告（介绍详细的算法设计说明和使用说明）； （5）以论文、报告等形式考核专用答题纸写大作业，大作业报告中要分析算法效率，并给出实测效率和理论效率图表； （6）大作业用5号字体，总页数不得少于8页，否则视为无效。 二、大作业步骤 Introduction: 给定一本英语单词词典，找出所有的变位词集。所谓的变位词是指，组成各个单词的字母完全相同，只是字母排列的顺序不同。例如，tea和eat是变位词，同属一个集合，找出所有这种集合。 Motivating idea: 1.如何判断两个单词是否为变位词。 思路一： 如果两个单词是变位词，那么它们具有相同的长度，且每个英语字母的个数是一样的。我们只需要挨个对各个单词进行比较即可。这个思路容易想，但时间效率太低，还可以继续改进一下，且看下面的思路二。 思路二： 将两个字符串按照字母表顺序排序，看排序后的字符串是否相等，如果相等则是兄弟字符串（变位词）。这种方法的时间效率根据你使用的排序算法不同而不同。这里我采取思路二，我使用的是快速排序。但是依旧有个问题，单词与单词一个一个比较的话效率还是太低了，我们可以再做改进。 2.如何从字典中找出所有变位词的集合。 思路一： 对于这个问题，最快想到的最直接的方法就是针对每一个单词跟字典中的其他单词进行比较。然而，假设一次比较至少花费1微秒的时间，则拥有二十万单词的字典将花费：200000

算法分析 期末大作业内容

算法设计与分析期末成绩考核标准 要求：算法设计与分析考试方式为小论文形式。下面给出了小论文的参考模型和参考题目，供大家选择。 1.小作业题目（仅供参考） （题目的难易：●简单10道题★中等11道题▲复杂10道题） ●最佳浏览路线问题 问题描述：某旅游区的街道呈网格状，其中东西向的街道都是旅游街，南向的街道都是林荫道。由于游客众多，旅游街被规定为单行道。游客在旅游街上只能从西向东走，在林荫道上既可以由南向北走，也可以从北向南走。 阿隆想到这个旅游区游玩，他的好友阿福给了他一些建议，用分值表示所有旅游街相邻两个路口之间的道路浏览的必要程度，分值从-100到100的整数，所有林荫道不打分，所有分值不可能全是负值。阿隆可以从任一路口开始浏览，在任一路口结束浏览，请写出一个算法，帮助阿隆寻找一条最佳的浏览路线，使得这条路线的所有分值总和最大。（算法设计与分析第二版P190—11题） ●问题描述：某工业生产部门根据国家计划的安排，拟将某种高效率的5台机器，分配给所属的，A，B，C个工厂，各工厂在获得这种机器后，可以为国家盈利如图表所示，问：这5台机器如何分配给各工厂，才能使得国家盈利最大？（P190-14题） ●问题描述：编写算法对输入的一个整数，判断他能否被4，7，9整除，并输出一下信息之一， 能同时被4，7，9整除; 能被其中两个数（要指出那两个）整除 能被其中一个数（要指出哪一个）整除 不能被4，7，9任一个整除。（P118-16） ●问题描述：某一印刷厂有6项加工任务，对印刷车间和装订车间所需的时间表如下图：完成每项任务都要先去印刷车间印刷，再到装订车间装订。问咋样安排这6项加工任务的加工工序，使得加工工时最少？（P191-17） ●问题描述：编写用动态规划法求组合数m C的算法(P191-19). n ●问题描述：仿照分治算法中两个大数相乘的算法策略，完成求解两个n*n阶矩阵A和矩阵B的乘积的算法。假设n=2k,要求算法的复杂性要小于O（n3）.(P190-12) ●问题描述：在一个n*m的方格中，m为奇数，放置有n*m个数，方格中间的下方有一人，此人可按照5个方向前进但不能跃出方格，如图所示，人每走过一个方格必须取此方格中的数。要求找到一条路径从低到顶的路径，使其数相加之和为最大，输出最大和的值。（P190-14）●问题描述：N 块银币中有一块不合格，已知不合格的银币比正常的银币重，先用一天平，请利用它找不合格的银币，并且用天平的次数最少。（P-19116） ●问题描述：旅行售货员问题：某售货员要到若干城市去推销商品，已知个城市之间的路线。她要选择一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（或总旅行费）最小（P246-6） ●问题描述：54张扑克牌，两个人轮流拿牌，每人每次最少取一张，最多取四张，谁那最后一张谁输。编写模拟计算机先拿牌取且必胜的算法。（P189-3） ★题目一选课方案设计（P290） ★题目二表达式相等判断（P291）

2016春季14级本科“算法设计与分析”大作业题目要求

2014级计算机科学与技术专业“算法设计与分析”大作业题 2015学年~2016学年第2学期 2016年4月18日 总体要求 本次综合大作业（上机实现题目）是为了配合“算法设计与分析”课程的讲授而设置的，目的在于培养学生理论联系实际的问题求解能力。综合大作业题目共两道，两题均要求采用动态规划算法求解。每题50分。以小组为单位检查，自由组合（可跨越班级），每组人数一般不少于3人、但不超过5人。每组提交1份课程报告，检查时每组至少须有1人做成果展示演讲（答辩），在课堂上就题目的设计思想、实现方法的正确性等进行说明，全组成员一起参与答辩，回答教授及同学的提问与质疑。 对于“动态规划”问题，报告中必须对最优值函数和标记函数的含义进行详细说明，列出子问题计算中所使用的有关最优值函数和标记函数的递推关系（一般采用递归式加以描述）和初值（边界条件）。给出所设计算法的时间复杂度分析。 每组自备2、3个相关问题的实例，报告中以实例中的数据描述算法的执行步骤。 一、广义背包问题 广义背包问题的描述如下：给定载重量为M的背包和n种物品，每种物品有一定的重量和价值，现在需要设计算法，在不超过背包载重量的前提下，巧妙选择物品，使得装入背包的物品的总价值最大化。规则是，每种物品均可装入背包多次或不装入（但不能仅装入物品的一部分）。请用数学语言对上述背包问题加以抽象，在此基础上给出动态规划求解该问题的递归公式。要求对所给公式中的符号意义加以详细说明，并简述算法的求解步骤。用一种你熟悉的程序设计语言加以实现。 二、在下面A 、B两道题中选取一道感兴趣的题目完成 A、加工顺序问题 “加工顺序问题”又被称为“批处理作业调度问题”。 设有n个工件需要在机器M1和M2上加工，每个工件的加工顺序都是先在M1上加工，然后在M2上加工。t1j，t2j分别表示工件j在M1，M2上所需的加工时间（j=1，2，···，n）。问应如何在两机器上安排生产，使得第一个工件从在M1上加工开始到最后一个工件在M2上加工完所需的总加工时间最短？关于此（类）问题的回溯法求解被作为经典案例在很多教材或参考文献中出现，现要求设计求解此问题的动态规划算法。 请用数学语言对“加工顺序问题”加以抽象，在此基础上给出动态规划求解该问题的递归公式。要求对所给公式中的符号意义加以详细说明，并简述算法求解步骤。用一种你熟悉的程序设计语言加以实现。 提示（分析最优解的性质，刻画最优解的结构—最优子结构性质）

最优化方法大作业

单位代码03 学号 《最优化方法》课程实践

完成时间：2015年5月30日星期六 选择题目：题目一使用优化软件，编写重要算法的程序 1.第一大题： （1）学习最优流量工程问题，nonsmooth_MCFP.pdf （2）问题重述： Figure 1一个简单的网络拓扑和流量需求 如Figure 1所示，网络有7 个节点，13 条弧，每条弧的容量是5 个单位. 此外有四个需求量均为4个单位的源－目的对（M=4)，具体的源节点、目的节点信息如图所示. 这里为了简单，省去了未用到的弧，此外弧上的数字表示弧的编号。 （3）极小化MAU 设定变量x，为531?的向量，其中(53) x即为变量z。使用linprog 函数求解极小化问题得到x。之前确定三个约束条件。 1、Ax b≤，其中A为1353 ?的矩阵，b为131?的向量。

2、eq eq x b A =，其中eq A 为2853?的矩阵，eq b 为281?的向量。 3、x lb ≥，其中lb 为153?的向量 编程计算后得到结果如下： （4） 极小化FT 成本函数 设定变量x ，为651?的向量，其中(53:65)x 即为变量l z 。使用linprog 函数求解极小化问题得到x 。之前确定三个约束条件。 1、Ax b ≤，其中A 为7865?的矩阵，b 为781?的向量。 2、eq eq x b A =，其中eq A 为2865?的矩阵，eq b 为281?的向量。 3、x lb ≥，其中lb 为165?的向量 编程计算后得到结果如下：

2. 第二大题： 2.1. 习题5.6 2.1.1. 问题分析 问题2112212()(101810)/241513q x x x x x x x =-++-+ 通过matlab 画出其等高线为： 2.1.2. 最速下降法 最速下降法中，取值： k k p g =- ==()()k k k k k T k k T k g p g g p Gp g Gg α- x1 x 2 等高线 -2 2 4 6 8 10 12

实验数据与处理大作业题目及答案

1、用Excel作出下表数据带数据点的折线散点图： （1）分别作出加药量和余浊、总氮T-N、总磷T-P、COD的变化关系图（共四张图，要求它们的格式大小一致，并以两张图并列的形式排版到Word中，注意调整图形的大小）； （2）在一张图中作出加药量和浊度去除率、总氮T-N去除率、总磷T-P去除率、COD去除率的变化关系折线散点图。

2、对离心泵性能进行测试的实验中，得到流量Q v 、压头H 和效率η的数据如表所示，绘制离心泵特性曲线。将扬程曲线和效率曲线均拟合成多项式。（要求作双Y 轴图） 流量Qv 、压头H 和效率η的关系数据 序号 1 2 3 4 5 6 Q v (m 3/h ) H/m η

序 号 7 8 9 10 11 12 Q v( m3/h) H/m η 3、用荧光法测定阿司匹林中的水杨酸（SA），测得的工作曲线和样品溶液的数据如下表: C(SA)/μ样 品1 样品2 F(荧光强度) （1）列出一元线性回归方程，求出相关系数，并给出回归方程的精度； （2）求出未知液（样品）的水杨酸（SA）浓度。 (1) C(SA)/μ

F(荧光强 度) (2) 4、对某矿中的13个相邻矿点的某种伴生金属含量进行测定，得到如下一组数据： 矿样点 距离 x 含量 c 矿样 点 距离 x 矿样 点 12811 23914 341015 451116 571218 681319 710 试找出某伴生金属c与含量距离x之间的关系(要求有分析过程、计算表格以及回归图形)。 提示：⑴作实验点的散点图，分析c~x之间可能的函数关系，如对数函数y=a+blgx、双曲函数(1/y)=a+(b/x)或幂函数y=dx b等；⑵对各函数关系分别建立数学模型逐步讨论，即分别将非线性关系转化成线性模型进行回归分析，分析相关系数：如果R≦，则建立的回归方程无意义，否则选取标准差SD最小（或R最大）的一种模型作为某伴生金属c与含量距离x之间经验公式。

多种方法求多段图的最短路径问题 算法设计与分析课程设计

学号： 《算法设计与分析B》 大作业 题目多种方法解决多段图的最短 路径问题 学院计算机科学与技术学院专业软件工程 班级 姓名 指导教师 2014 年12 月26 日

多种方法解决多段图的最短路径问题 摘要 多段图的最短路径问题是求从源点到终点的最小代价路径。本文主要描述的是分别用动态规划法、贪心法和分支限界法来解决多段图最短路径问题时的情况。文章首先阐述了各个方法的原理，主要的思路是通过输入一组数据，比较三者的输出结果的准确性以及运行时间，以之为基础来分析、讨论三者的性能区别。文章最后讲述了若这几种方法运行到有向图中的情况，几种方法的对比和它们比较适应的使用情况的讨论，并给出了自己的建议。 关键字：多段图最短路径问题；动态规划法；分支限界法；贪心法

目录 摘要................................................................. II 1 引言 (1) 2 问题描述 (1) 3 贪心法求解 (2) 3.1 贪心法介绍 (2) 3.2 问题分析 (3) 4 动态规划法求解 (3) 4.1 动态规划法介绍 (3) 4.2 问题分析 (4) 5 分支限界法求解 (5) 5.1 分支限界法介绍 (5) 5.2 问题分析 (5) 6 程序清单 (6) 6.1 源代码 (6) 6.2 结果截图 (9) 7 结果分析 (9) 8 课程体会 (10) 9 参考文献 (10)

1引言 当前社会，关于最短路径的问题屡屡出现。例如在开车自驾游的一个过程中，排除其它影响因素，从一个地点到另一点，这个时候必然是希望有一条距离最短的路程来尽量减少消耗的时间以及花费的（它们在模型中被称为代价），市场上对该问题的解决有很大的需求，因此，这里我将讨论多段图的最短路径的问题。 大二开设的《数据结构》课程中就包括最短路径这方面问题的讨论。当时老师介绍了分别面向单源（Dijkstra算法）与非单源（Floyd算法）两种问题的算法——这是我们最早的对最短路径方面的理解，也是我们接触的比较早的关于图的问题。 在这学期的《算法设计与分析》课程中，我们学习了很多基本的算法设计技术，蛮力法、分治法、减治法、动态规划法、贪心法、回溯法、分支限界法等，它们把以前学习的诸多方法都命名并归纳分类起来，其中有多种算法都可以用来解决最短路径问题，并且该问题作为一个图的问题，对该问题的继续探讨优化的需求很大、本文将就不同算法在解决该最短路径问题时的不同方法进行对比并给出该问题在不同基础上不同的最终解决方案。由于时间的限制，本文将重点分析动态规划法下的情况，并会对图的情况加以简化、限制，最后会对其它的图做一些拓展。 2问题描述 设图G=(V, E)是一个带权有向连通图，如果把顶点集合V划分成k个互不相交的子集Vi（2≤k≤n, 1≤i≤k），使得E中的任何一条边(u, v)，必有u∈Vi，v∈Vi+m（1≤i＜k, 1＜i+m≤k），则称图G为多段图，称s∈V1为源点，t∈Vk为终点。多段图的最短路径问题是求从源点到终点的最小代价路径。多段图的最短路径问题是求从源点到终点的最小代价路径。 由于多段图将顶点划分为k个互不相交的子集，所以，可以将多段图划分为k段，每一段包含顶点的一个子集。不失一般性，将多段图的顶点按照段的顺序进行编号，同一段内顶点的相互顺序无关紧要。假设图中的顶点个数为n，则源点s的编号为0，终点t的编号为n-1，并且，对图中的任何一条边(u, v)，顶点u的编号小于顶点v的编号。 这里我们讨论的多段图是可以分段的，各段之间的关系最好是单向的，即对该有向图来说，图中是没有环的存在的。

算法设计与分析第7章作业.pdf

「算法设计与分析」第7章作业2015.10 学号: 15S103172 姓名: 谢浩哲 1.在下图中考虑哈密顿环问题. 将问题的解空间表示成树, 并分别利用深度优先搜索和广度优先搜索判 定该图中是否存在哈密顿环. 问题解空间的树状结构: 算法概述: 从起始点出发, 搜索从这个点出发所有可到达的点(深度优先或广度优先策略均可). 对于每到达一个点, 判断: 是否已经回到起始点, 是否经过重复的点. 若经过了重复了点, 则不再搜索. 若到达了起始点, 并且恰好经过了所有的点, 则找到了最优解.

算法实现: 深度优先搜索: 35

} 广度优先搜索:

!isVisited(startPoint, i, 37 2.考虑8-魔方问题. 分别用深度优先算法, 广度优先算法, 爬山法, 最佳优先方法判定上图所示的初始 格局能够通过一系列操作转换成目标格局, 将搜索过程的主要步骤书写清楚.

问题的部分解空间树状结构:

深度优先搜索: 搜索顺序为1 -> 2 -> 4 -> 10 -> … 广度优先搜索: 搜索顺序为1 -> 2 -> 3-> 4 -> 5 -> 6 -> … 爬山法: 基于深度优先搜索, 选取当前分支上最优解; 搜索顺序为1 -> 2 -> 4 -> 11 -> … 最佳优先方法: 基于深度优先搜索, 选取所有分支上最优解; 搜索顺序为1 -> 2 -> 4 -> 11 -> … 3.分别使用深度优先法和分支限界法求解子集和问题的如下实例. 输入: 集合S=7, 4, 6, 13, 20, 8和整数K=18. 输出: S’使得S’中元素之和等于K. 深度优先搜索: 问题的部分解空间如下如所示: 算法实现:

算法设计与分析大作业答案

算法设计技术与方法 大作业 学院电子工程学院 专业电路与系统 姓名 学号 导师姓名

1.分别实现多项式求值的四种运算，若针对不同规模的输入值a ，各算法的运行时间，问题 规模n 分别取10，50，100，150，200，300，400，500，10000，20000，50000，100000时绘制四种算法运行时间的比较图。 2.分别实现矩阵相乘的3种算法，比较三种算法在矩阵大小分别为2222?，3322?，4422?，5522?，6622?，7722?，8822?，9922?，101022?，111122?，121222?时的运行时间与MATLAB 自带的矩阵相乘的运行时间，绘制时间对比图。 3.利用遗传算法求解下面的问题： )20sin()4sin(5.21),(m ax 221121x x x x x x f ππ?+?+= ? ??≤≤≤≤-8.51.41.120.3..21x x t s 1、分析题意可知，该题要用四种不同的方法实现对多项式的求值计算，每种方法取从10-100000不同的规模。本文采用了以下方法进行求值：直接代入法和递归法。而其中递归法分三类不同思路进行递归： ① n n n n x a x P x P +=-)()(1； ② 0a P =,1=Q ,Q a P P Qx Q i +==,； ③ i n i i a x x P x P --+'=')()(1。 本文对上述四种方法进行了编程，具体代码如下： 程序1.1 文件名poly.m % 主程序：实现不同规模下多项式求值的四种运算 clc; close all ; clear all ; n=[10 50 100 150 200 300 400 500 10000 20000 50000 100000]; x=2; for i=1:12 a=rand(1,(n(i)+1)); % 产生多项式,最高次幂为n(i)+1 tic; p1(i)=polyval(a,x); % 直接代入法 t1(i)=toc; tic; p2(i)=0; for j=1:(n(i)+1) p2(i)=p2(i)+a(j)*x^(j-1); % 递归法1

算法设计与分析大作业西安电子科技大学

算法设计技术与方法 学院电子工程学院专业电子与通信工程学号 学生姓名 授课教师公茂果

问题一 1 问题描述 分别实现多项式求值的三种运算，针对不同规模的输入值a，各算法的运行时间，问题规模n分别取10, 50, 100, 150, 200, 300, 400, 500, 10000, 20000, 50000, 100000时绘制三种算法运行时间的比较图。 2 算法分析 1)算法1：P n(x) = P n-1(x) + a n x n→P i(x) = P i-1(x) + a i x i 该算法的伪代码表示如下： begin P := a0; for i=1 to n do P = P + a i x i; end end 该算法的时间复杂度为T(n) = O(n2)。 2)算法2：在上一算法中，可以看出xi重复计算了。如果 把上一次计算出的xi-1保存起来，直接乘以x,就可以得到xi，这样就可以避免重复计算。 该算法的伪代码表示如下： begin

P := a0; Q := 1; for i=1 to n do Q = Qx; P = P + a i Q; end end 该算法的时间复杂度为T(n) = O(n)。 3)算法3：P n(x) = P’n-1(x)x+a0, P’n-1(x)=a n x n-1+a n-1x n-2+…+a2x+a1 →P’i(x)=P’i-1(x)x+a n-i 该算法的伪代码表示如下： begin P := a n; for i=1 to n do P = xP + a n-i; end end 该算法的时间复杂度为T(n) = O(n)。 3 实验数据 下表为实验中所测得的数据：