当前位置：搜档网 › 中科院计算机算法设计与分析各章作业+历年习题

中科院计算机算法设计与分析各章作业+历年习题

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

《计算机算法设计与分析》习题及答案一．选择题 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 ）。

算法设计与分析(作业三)

算法设计与分析实验报告学院信息科学与技术学院专业班级软件工程3班学号 20122668 姓名王建君指导教师尹治本 2014年10月

实验四矩阵相乘次序一、问题提出用动态规划算法解矩阵连乘问题。给定n 个矩阵{A 1,A 2,…,A n }，其中A i 与A i+1是可乘的，i=1,2,…,n-1。要算出这n 个矩阵的连乘积A 1A 2…A n 。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为：（1）单个矩阵是完全加括号的；（2）矩阵连乘积A 是完全加括号的，则A 可表示为2个完全加括号的矩阵连乘积B 和C 的乘积并加括号，即A=(BC)。例如，矩阵连乘积A 1A 2A 3A 4有5种不同的完全加括号的方式：（A 1（A 2（A 3A 4））），（A 1（（A 2A 3）A 4）），（（A 1A 2）（A 3A 4）），（（A 1（A 2A 3））A 4），（（（A 1A 2）A 3）A 4）。每一种完全加括号的方式对应于一个矩阵连乘积的计算次序，这决定着作乘积所需要的计算量。若A 是一个p ×q 矩阵，B 是一个q ×r 矩阵，则计算其乘积C=AB 的标准算法中，需要进行pqr 次数乘。（3）为了说明在计算矩阵连乘积时，加括号方式对整个计算量的影响，先考察3个矩阵{A 1,A 2,A 3}连乘的情况。设这三个矩阵的维数分别为10×100，100×5，5×50。加括号的方式只有两种：（（A 1A 2）A 3），（A 1（A 2A 3）），第一种方式需要的数乘次数为10×100×5＋10×5×50＝7500，第二种方式需要的数乘次数为100×5×50＋10×100×50＝75000。第二种加括号方式的计算量时第一种方式计算量的10倍。由此可见，在计算矩阵连乘积时，加括号方式，即计算次序对计算量有很大的影响。于是，自然提出矩阵连乘积的最优计算次序问题，即对于给定的相继n 个矩阵{A 1,A 2,…,A n }（其中矩阵Ai 的维数为p i-1×p i ，i ＝1,2,…,n ），如何确定计算矩阵连乘积A 1A 2…A n 的计算次序（完全加括号方式），使得依此次序计算矩阵连乘积需要的数乘次数最少。二、求解思路本实验采用动态规划算法解矩阵连乘积的最优计算次序问题。本实验的算法思路是： 1)计算最优值算法MatrixChain()：建立两张表（即程序中的**m 和**s ，利用二维指针存放），一张表存储矩阵相乘的最小运算量，主对角线上的值为0，依次求2个矩阵、3个矩阵…、直到n 个矩阵相乘的最小运算量，其中每次矩阵相乘的最小运算量都在上一次矩阵相乘的最小运算量的基础上求得，最后一次求得的值即为n 个矩阵相乘的最小运算量；另一张表存储最优断开位置。 2)输出矩阵结合方式算法Traceback()：矩阵结合即是给矩阵加括号，打印出矩阵结合方式，由递归过程Traceback()完成。分三种情况：（1）只有一个矩阵，则只需打印出A1；（2）有两个矩阵，则需打印出（A1A2）；（3）对于矩阵数目大于2，则应该调用递归过程Traceback()两次，构造出最优加括号方式。三、算法复杂度该算法时间复杂度最高为）（n 3 O 。四、实验源代码

中科院矩阵分析与应用大作业

中科院矩阵分析与应用大作业实现LU分解 QR分解 Householder reduction、Givens reduction Matlab 代码： function [] =juzhendazuoye A=input('请输入一个矩阵A='); x=input('请输入序号 1 LU分解 2 Gram-Schmidt分解 3 Householder reduction 4 Givens reduction:' ); if(x==1) %%*************LU分解*****************%% disp('PA=LU') m=size(A,1); % m等于矩阵A的行数 n=size(A,2); % n等于矩阵A的列数 if(m==n) % 判断矩阵A是不是方阵 % 如果矩阵A不是方阵那么就输出“error” U=A; % 把矩阵A赋值给矩阵U L=zeros(n); % 先将L设为单位阵 P=eye(n); % 首先将交换矩阵P设为单位矩阵 for j=1:n-1 for i=j+1:n if (U(j,j)~=0) %判断主元元素是否不为0

L(i,j)=U(i,j)/U(j,j); U(i,:)=U(i,:)-U(j,:)*U(i,j)/U(j,j); % U(j,j)为主元元素 else a=j+1; % 令a等于j+1 while((U(a,j)==0)&&(a

《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

算法分析与设计作业及参考答案样本

《算法分析与设计》作业( 一) 本课程作业由两部分组成。第一部分为”客观题部分”, 由 15个选择题组成, 每题1分, 共15分。第二部分为”主观题部分”, 由简答题和论述题组成, 共15分。作业总分30分, 将作为平时成绩记入课程总成绩。客观题部分: 一、选择题( 每题1分, 共15题) 1、递归算法: ( C ) A、直接调用自身 B、间接调用自身 C、直接或间接调用自身 D、不调用自身 2、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的字问题, 这些子问题: ( D ) A、相互独立 B、与原问题相同 C、相互依赖 D、相互独立且与原问题相同 3、备忘录方法的递归方式是: ( C ) A、自顶向下 B、自底向上 C、和动态规划算法相同 D、非递归的 4、回溯法的求解目标是找出解空间中满足约束条件的: ( A )

A、所有解 B、一些解 C、极大解 D、极小解 5、贪心算法和动态规划算法共有特点是: ( A ) A、最优子结构 B、重叠子问题 C、贪心选择 D、形函数 6、哈夫曼编码是: ( B) A、定长编码 B、变长编码 C、随机编码 D、定长或变长编码 7、多机调度的贪心策略是: ( A) A、最长处理时间作业优先 B、最短处理时间作业优先 C、随机调度 D、最优调度 8、程序能够不满足如下性质: ( D ) A、零个或多个外部输入 B、至少一个输出 C、指令的确定性 D、指令的有限性 9、用分治法设计出的程序一般是: ( A ) A、递归算法 B、动态规划算法

C、贪心算法 D、回溯法 10、采用动态规划算法分解得到的子问题: ( C ) A、相互独立 B、与原问题相同 C、相互依赖 D、相互独立且与原问题相同 11、回溯法搜索解空间的方法是: ( A ) A、深度优先 B、广度优先 C、最小耗费优先 D、随机搜索 12、拉斯维加斯算法的一个显著特征是它所做的随机选性决策有可能导致算法: ( C ) A、所需时间变化 B、一定找到解 C、找不到所需的解 D、性能变差 13、贪心算法能得到: ( C ) A、全局最优解 B、 0-1背包问题的解 C、背包问题的解 D、无解 14、能求解单源最短路径问题的算法是: ( A ) A、分支限界法 B、动态规划 C、线形规划 D、蒙特卡罗算法 15、快速排序算法和线性时间选择算法的随机化版本是:

计算机算法设计与分析

算法设计与分析实验报告班级：姓名：学号： (备注：共给出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.参考文献：列出在撰写过程中所需要用到的参考文献。

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

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 -

中科院-模式识别考题总结(详细答案)

1.简述模式的概念及其直观特性，模式识别的分类，有哪几种方法。（6’）答（1）：什么是模式？广义地说，存在于时间和空间中可观察的物体，如果我们可以区别它们是否相同或是否相似，都可以称之为模式。模式所指的不是事物本身，而是从事物获得的信息，因此，模式往往表现为具有时间和空间分布的信息。模式的直观特性：可观察性；可区分性；相似性。答（2）：模式识别的分类：假说的两种获得方法（模式识别进行学习的两种方法）： ●监督学习、概念驱动或归纳假说； ●非监督学习、数据驱动或演绎假说。模式分类的主要方法： ●数据聚类：用某种相似性度量的方法将原始数据组织成有意义的和有用的各种数据集。是一种非监督学习的方法，解决方案是数据驱动的。 ●统计分类：基于概率统计模型得到各类别的特征向量的分布，以取得分类的方法。特征向量分布的获得是基于一个类别已知的训练样本集。是一种监督分类的方法，分类器是概念驱动的。 ●结构模式识别：该方法通过考虑识别对象的各部分之间的联系来达到识别分类的目的。（句法模式识别） ●神经网络：由一系列互相联系的、相同的单元（神经元）组成。相互间的联系可以在不同的神经元之间传递增强或抑制信号。增强或抑制是通过调整神经元相互间联系的权重系数来（weight）实现。神经网络可以实现监督和非监督学习条件下的分类。 2.什么是神经网络？有什么主要特点？选择神经网络模式应该考虑什么因素？（8’）答（1）：所谓人工神经网络就是基于模仿生物大脑的结构和功能而构成的一种信息处理系统（计算机）。由于我们建立的信息处理系统实际上是模仿生理神经网络，因此称它为人工神经网络。这种网络依靠系统的复杂程度，通过调整内部大量节点之间相互连接的关系，从而达到处理信息的目的。人工神经网络的两种操作过程：训练学习、正常操作（回忆操作）。答（2）：人工神经网络的特点： ●固有的并行结构和并行处理； ●知识的分布存储； ●有较强的容错性； ●有一定的自适应性；人工神经网络的局限性： ●人工神经网络不适于高精度的计算； ●人工神经网络不适于做类似顺序计数的工作； ●人工神经网络的学习和训练往往是一个艰难的过程； ●人工神经网络必须克服时间域顺序处理方面的困难； ●硬件限制； ●正确的训练数据的收集。答（3）：选取人工神经网络模型，要基于应用的要求和人工神经网络模型的能力间的匹配，主要考虑因素包括：

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

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

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

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

算法设计大作业—求解Tsps问题

基于贪心算法求解TSP问题一、TSP问题 TSP问题（Travelling Salesman Problem）即旅行商问题，又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。 TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。TSP问题可以分为两类，一类是对称TSP问题（Symmetric TSP），另一类是非对称问题（Asymmetric TSP）。所有的TSP问题都可以用一个图（Graph）来描述： V={c1, c2, …, ci, …, cn}，i = 1,2, …, n，是所有城市的集合.ci表示第i个城市，n为城市的数目； E={(r, s): r,s∈V}是所有城市之间连接的集合； C = {crs: r,s∈V}是所有城市之间连接的成本度量（一般为城市之间的距离）；如果crs = csr, 那么该TSP问题为对称的，否则为非对称的。一个TSP问题可以表达为：求解遍历图G = (V, E, C)，所有的节点一次并且回到起始节点，使得连接这些节点的路径成本最低。二、贪心算法贪心算法，又名贪婪算法，是一种常用的求解最优化问题的简单、迅速的算法。贪心算法总是做出在当前看来最好的选择，它所做的每一个在当前状态下某种意义上是最好的选择即贪心选择，并希望通过每次所作的贪心选择导致最终得到问题最优解。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。 1、贪心算法的基本思路从问题的某一个初始解触发逐步逼近给定的目标，以尽可能快地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。大致步骤如下： 1）建立数学模型来描述问题； 2）把求解的问题分成若干个子问题 3）对每一个子问题求解，得到子问题的局部最优解 4）把子问题的局部最优解合成原问题的一个解 2、贪心算法的实现框架贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择，而贪心策略适用的前提是：局部最优策略能导致产生全局最优解。从问题的某一初始解出发； while （能朝给定总目标前进一步） { 利用可行的决策，求出可行解的一个解元素； } 由所有解元素组合成问题的一个可行解； 3、贪心算法存在的问题 1）不能保证求得的最后解是最佳的；

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

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 ）。

《算法分析与设计》作业参考答案

《算法分析与设计》作业参考答案作业一一、名词解释： 1.递归算法：直接或间接地调用自身的算法称为递归算法。 2.程序：程序是算法用某种程序设计语言的具体实现。二、简答题： 1.算法需要满足哪些性质？简述之。答：算法是若干指令的有穷序列，满足性质：（1）输入：有零个或多个外部量作为算法的输入。（2）输出：算法产生至少一个量作为输出。（3）确定性：组成算法的每条指令清晰、无歧义。（4）有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。 2.简要分析分治法能解决的问题具有的特征。答：分析分治法能解决的问题主要具有如下特征：（1）该问题的规模缩小到一定的程度就可以容易地解决；（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 3.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。答：将递归算法转化为非递归算法的方法主要有：（1）采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。（2）用递推来实现递归函数。（3）通过Cooper 变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。后两种方法在时空复杂度上均有较大改善，但其适用范围有限。三、算法编写及算法应用分析题： 1.冒泡排序算法的基本运算如下： for i ←1 to n-1 do for j ←1 to n-i do if a[j]

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

算法分析大作业动态规划方法解乘法表问题和汽车加油行驶问题目录 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];

中科院矩阵分析chapt3

矩阵分析及其应用 3.1矩阵序列定义3.1设矩阵序列｛A (k )｝,其中A(k)=( a (k ) ) C m n ,当k a j" a u 时，称矩阵序列｛A (k)｝收敛，并称矩阵 A=( a ij )为矩阵序列｛A (k)｝的极限，或称｛A (k)｝收敛于A,记为 lim A (k) A 或 A (k) A k 不收敛的矩阵序列称为发散的。由定义，矩阵序列 A (k )发散的充要条件为存在 j 使得数列a (k)发散。类似地，我们可以定义矩阵收敛的 Cauchy 定义定义3.1'矩阵序列｛A (k)｝收敛的充要条件为对任给>0存在N()，当k, l N()时有 ||A (k) A (l)|| < 其中||.|为任意的广义矩阵范数。 sin 』) n n sin(k) 如果直接按定义我们因为求不出 A (n)的极限从而从而只要I 充分大，则当m, n > l 时就有 sin(k) k 2 这样A (l)收敛。定理3.1 A (k) A 的充要条件为 ||A (k) A|| 0 证明：利用广义矩阵范数的等价性定理，仅对范数可以证明。即c 1 IL A (k) A|| ||A (k) AII C 2 ||A (k) AII 性质 0 若 A (k) A ，则 ||A (k) II IIAII 成立。性质 1. 设 A (k) A m n ， B (k) B m n , 则 A (k)+ B (k) A+ B ， ,C 性质 2. 设 A (k) A m n ， B (k ) B n l ,贝U A (k) B (k) A B 证明：由于矩阵范数地等价性，我们可以只讨论相容的矩阵范数。 ||A (k )B (k) A B|| || A (k) B (k) A B (k)||+||AB (k) A B|| || A (k) A|| ||B (k)||+||A||||B (k) B|| 例 1 A (n) k m 1 k(k 1) 相反，由于

算法分析与设计(线下作业二)

《算法分析与设计》学习中心：专业：学号：姓名：

作业练习二一、名词解释 1、MST性质 2、子问题的重叠性质递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次，这种性质称为子问题的重叠性质。二、简答题 1、简述动态规划算法求解的基本要素。答：动态规划算法求解的基本要素包括： 1)最优子结构是问题能用动态规划算法求解的前提； 2)动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果，即重叠子问题。 2、备忘录方法和动态规划算法相比有何异同简述之。答：备忘录方法是动态规划算法的变形。与动态规划算法一样，备忘录方法用表格保存已解决的子问题的答案，在下次需要解此问题时，只要简单地查看该子问题的解答，而不必重新计算。备忘录方法与动态规划算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上递归的。因此，备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同的子问题的重复求解，而直接递归方法没有此功能。

3、贪心算法求解的问题主要具有哪些性质简述之。答：贪心算法求解的问题一般具有二个重要的性质：一是贪心选择性质，这是贪心算法可行的第一个基本要素；另一个是最优子结构性质，问题的最优子结构性质是该问题可用贪心算法求解的关键特征。三、算法编写及算法应用分析题 1、设计求解如下最大子段和问题的动态规划算法。只需给出其递推计算公式即可。最大子段和问题：给定由n 个整数（可能为负整数）组成的序列a1a2 … an，求该序列形如Σi≤k≤j ak的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。依次定义，所求的最优值为max{0, max1≤i≤j≤n Σi≤k≤j ak }。

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

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

目录《算法设计与分析》课程大作业.................................................................... 错误!未定义书签。一．动态规划算法解决流水作业调度. (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