当前位置：搜档网 › 算法设计期中试卷、平时作业参考解答

算法设计期中试卷、平时作业参考解答

《算法分析与设计》2012-2013-2学期期中测试（信息安全专业DQ 教学班）

姓名：学号：得分：

1. 证明()()()()()()()O f n O g n O f n g n +=+。（10分）

证明：对于任意f 1(n ) ∈ O (f (n ))，存在正常数c 1和自然数n 1，使得对所有n ≥ n 1，有f 1(n ) ≤ c 1f (n )成立。类似，对于任意g 1(n ) ∈ O (g (n ))，存在正常数c 2和自然数n 2，使得对所有n ≥ n 2，有g 1(n ) ≤ c 2g (n )成立。

令c 3 = max{c 1, c 2}，n 3 = max{n 1, n 2}，则对所有的n ≥ n 3，有

f 1(n ) +

g 1(n ) ≤ c 1f (n ) + c 2g (n )

≤ c 3f (n ) + c 3g (n )

= c 3(f (n ) + g (n ))

即()()()()()()()O f n O g n O f n g n +=+成立。

2. 将下列5个函数按渐近增长率由低至高进行排序，要求写出比较过程。（15分）解： 100log 2log log log 24()log 100log ,()2log ,n n n f n n n f n n n +====

(1) 2()f n 是对数函数的幂，5()f n 是幂函数，因此()25()()f n O f n =;

(2) ()()

()491105log lim lim lim log n n n f n n n n n f n n →∞→∞→∞===∞，因此()54()()f n O f n =; (3) ()

()423log 1lim lim

lim 0log n n n f n n n f n n n n →∞→∞→∞===，因此()43()()f n O f n =; (4) 对1()f n 和3()f n 取对数，有

()()() 13log ()log loglog loglog ,log ()2log loglog log f n n n n n n n f n n n n =+=Θ=Ω=+=Θ，因为()log n O n =，所以()31()()f n O f n =;

因此，5个函数按渐近增长率由低至高排序为25431(),(),(),(),()f n f n f n f n f n 。

3. 给定按升序排列的n 个不同整数存于数组a [1:n ]中，请设计()log O n 的算法找到下标i ，1i n ≤≤，使得a [i ] = i ，如不存在这样的下标，则返回0。（15分）

解：

令head = 1, rear = n .

(1) 当head <= rear 时，令mid = ?(head + rear)/2?；

(2) 如果a [mid] = mid ，返回mid 值，结束。

如果a [mid] > mid ，令rear = mid – 1，返回(1)继续执行；

如果a [mid] < mid ，令head = mid + 1，返回(1) 继续执行；

(3)返回0值，结束。

public static int Search(int [] a, int n)

{

// 在 a[0] <= a[1] <= ... <= a[n -1] 中搜索 a[i] = i

// 找到a[i] = i 时返回i ，否则返回0

int left = 0; int right = n – 1;

while (left <= right)

{

int mid = ?(left + right)/2?;

if (a[mid] == mid) return mid;

if (a[mid] > mid) right = mid – 1;

else left = mid + 1;

}

return 0; // 未找到a[i] = i

}

4. 利用主方法给出下列递归式的渐近界，并用数学归纳法证明式(2)的渐近界。（20分）

(1) ()()42T n T n n =+, (2) ()()242T n T n n =+, (3) ()()3

42T n T n n =+解：(1) 24,2,log log 42,b a b a ==== 因此，()()2T n n =Θ. (2) 24,2,log log 42,b a b a ==== 因此，()()2log T n n n =Θ. (3) 2

4,2,log log 42,b a b a ==== 而且()()()333424223,

f n n n n cf n ==≤=其中34n =，

因此，()()3T n n =Θ. 证明：假设当k n <时，()2log T k ck k ≤，其中c 为常数。

因此，命题得证。5. 利用直接展开法求解下列递归式的渐近界。（20分）

(1) ()()242T n T n n =+, (2) (

)T n n =+解：(1)

(2) (

)T n n =+ 其中122k n '=，则所以，()()()2log log 1log log 2

T n T n n n =+=Θ+，即()()loglog T n O n n =.

6. 某超市中有n 种商品搞活动，每种商品i 的重量是w i ，其价格为v i ，现在给你发一个容量为C 的购物车，你可以在这n 种商品中选一些放入你的购物车中免费带走。但是要求所选的商品重量之和不能大于购物车容量C ，而且超市中每种商品每人最多选两件。请问在这种情况下你如何选择商品使得你能带走的免费商品的价格达到最大？（20分）

(a) 为该问题设计一个动态规划算法，要求写出分析过程和递归式。

(b) 若该超市共有3种商品搞活动，商品的价值依次为v = (25, 30, 15)，商品的重量依次为w = (2, 3, 1)，购物车容量为C = 5。运用自底而上的方法求解上述问题，要求画出表格，并给出最优解与最优值！

解：

方法1 ?

将n 种商品全部复制一份得到2n 种商品，这样每种商品最多只能选择1件。 ?

定义m (i , j )为购物车容量为j ，由第1, …, i 种商品装入购物车的最优值。 ?

Case 1: 不选择第i 种商品 ? 则m (i , j )为当重量限制为j 时，{1, …,i – 1}种商品装入购物车所产生的最大价值 ? Case 2: 选择第i 种商品.

? 新的重量限制为 j – w i

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

算法设计与分析实验报告学院信息科学与技术学院专业班级软件工程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 。四、实验源代码

算法设计与分析课程期末试卷A卷自测

华南农业大学期末考试试卷（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 （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．（，0）B．（，）C．（5，5）D．（5，0）个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，水桶必须打满水，水流恒定。如下说法不正确 A．让水桶大的人先打水，可以使得每个人排队时间之和最小 B．让水桶小的人先打水，可以使得每个人排队时间之和最小

(整理)投资分析平时作业1-4答案

《投资分析》课程平时作业1 一、单项选择题（每小题2分，共20分） 1．项目市场分析（C ） A、只在可行性研究中进行 B、只在项目评估中进行 C、在可行性研究和项目评估中都要进行 D、仅在设计项目产品方案时进行2．计算项目的财务净现值所采用的折现率为（ B ） A、财务内部收益率 B、基准收益率 C、财务净现值率 D、资本金利润率 3．已知终值F，求年金A应采用（ C ） A、资金回收公式 B、年金终值公式 C、偿债基金公式 D、年金现值公式 4．项目分为基本建设项目和更新改造项目，其分类标志是（A ） A、项目的性质 B、项目的用途 C、项目的规模 D、项目的资金来源 5．在下列说法中，错误的是（ B ） A、基本建设项目属于固定资产外延式扩大再生产 B、更新改造项目属于固定资产外延式扩大再生产 C、项目的规模一般是按其总投资额或项目的年生产能力来衡量的 D、生产性项目主要是指能够形成物质产品生产能力的投资项目 6．在进行项目市场预测时，如果掌握的是大量相关性数据，则需选用（C ）A、德尔菲法B、时间序列预测法 C、回归预测法 D、主观概率法

7．二次指数平滑法主要用于配合（A ） A、直线趋势预测模型 B、次抛物线趋势预测模型 C、三次抛物线趋势预测模型 D、季节变动预测模型 8．下列说法中错误的是（B ） A、当FNPV＞0时项目可行； B、当FIRR≥ic时项目不可行； C、当Pt＞PC时项目不可行； D、当FCE＞官方汇率时项目不可行。9．已知现值P，求年金A应采用（ D ） A、年金现值公式 B、年金终值公式 C、偿债基金公式 D、资金回收公式 10．下列影响项目建设经济规模的因素中，最重要的是（D ） A、市场需求总量 B、市场供给总量 C、项目投资者可能获得的产品市场份额 D、A和C 二、多项选择题（每题2分，共12分） 1．项目市场分析的主要内容包括（ABCDE ） A、市场需求分析 B、市场供给分析 C、市场竞争分析 D、二项目产品分析 E、市场综合分析 2．项目市场调查的原则（ABCD ） A、准确性原则 B、完整性原则 C、时效性原则 D、节约性原则 E、科学性原则 3．项目市场调查的方法主要有（ABC ） A、观察法 B、询问法 C、实验法 D、网络调查法 E、面谈法

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

《算法分析与设计》作业( 一) 本课程作业由两部分组成。第一部分为”客观题部分”, 由 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、快速排序算法和线性时间选择算法的随机化版本是:

算法设计分析期中试题

《算法设计与分析》期中试卷一、叙述分治算法的基本思想及一般算法设计模式；二、叙述动态规划算法的基本步骤及动态规划算法的基本要素；三、改进课本P74的Lcs算法，使改进算法不用数组b亦可在O（m+n）的时间内构造最长公共序列；四、求下列函数的渐近表达式 (1). 3n2+10n (2).n2/10+2n (3)21+1/n (4)logn3 (5)10log3n 五、对于下列各组函数发f（n）和g（n），确定f（n）=O(（g(n)）) 或者f（n）= (（g(n)）)或者f（n）=θ(（g(n)）)，并简述理由 (1). f（n）=logn2 , g(n)=logn+5; (2). f（n）=logn2 , g(n)= √n; (3), f（n）=n, g(n)= logn2; (4). f（n）=nlogn+n,g(n)=logn; (5). f（n）=10.g(n)=log10; (6). f（n）=log2n g(n)=logn (7). f（n）=2n g(n)= 3n; (8). f（n）=2n g(n)= 100n2;

六、设a[0:n-1]是已排好序的数组，请改写二分搜索算法，使得当搜索元素x不再数组中时，返回小于x的最大元素位置i和大于x 的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x 在数组中的位置七、设a[0:n-1]是有n个元素的数组，k（0<=k<=n-1）是非负整数。试设计一个算法将子数组a[0:k]与a[k+1:n-1]换位。要求算法在最坏的情况下耗时O(n),且只用到O(1)的辅助空间。八、在一个由元素组成的表中出现次数最多的元素称为众数。试写一个寻找众数的算法，并分析其计算复杂性。九、设计一个O(n2)时间的算法，找出由n个数组成的序列的最长单调递增子序列。十、给定n中物品和一背包，物品i的重量是ω，体积是b i，其价值为v i ，背包的容量为C，容积为D。问：应该如何选择装入背包中的物品，使得装入背包中的物品的总价值最大？在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包，不能将物品i装入背包多次，也不能只装入部分的物品i。试设计一个解此问题的动态规划算法，并分析算法的计算复杂性。

现代软件工程平时作业及答案

（一）名词解释 1.软件 2.软件危机 3.数据流图 4.数据字典 5.变换流 6.事务流 7.耦合性 8.内聚性 9.程序设计语言（PDL）（二）填空题 1. 在信息处理和计算机领域内，一般认为软件是_____、_____ 和_____ 。 2. 数据流图的基本组成部分有_____、_____、_____、_____。 3. 数据流图和数据字典共同构成了系统的_____模型，是需求规格说明书的主要组成部分。 4. 数据流图一般可分为_____和_____两类。 5. 结构化设计方法中，要把数据流图转换成软件结构，若某个加工将它的输入流分离成许多发散的数据流，形成许多加工路径，并根据输入的值选择其中一个路径来执行，这种特征的DFD称为_____数据流图。 6. PDL是描述处理过程“_____ ”的细节，结构化语言是描述加工“_____ ”的。（三）选择题 1. 软件工程的概念是哪年提出的( )。 A. 1988 B. 1968 C. 1948 D. 1928 2. 影响输入输出风格的因素不包括( )。 A. 数据状态 B. 通信环境 C. 用户经验 D. 输入/输出设备 3. 符合数据说明顺序规范的是( )。 A. 全程量说明、局部量说明、类型说明、常量说明 B. 全程量说明、局部量说明、常量说明、类型说明 C. 类型说明、常量说明、全程量说明、局部量说明 D. 常量说明、类型说明、全程量说明、局部量说明 4. 瀑布模型的关键不足在于( )。 A. 过于简单 B. 各个阶段需要进行评审 C. 过于灵活 D. 不能适应需求的动态变更 5. 以下哪一项不是软件危机的表现形式( )。 A. 开发的软件不满足用户需要 B. 开发的软件可维护性差 C. 开发的软件价格便宜 D. 开发的软件可靠性差 6. 软件可行性研究实质上是要进行一次( )需求分析、设计过程。 A. 简化、压缩的 B. 详细的 C. 彻底的 D. 深入的 7. 结构化设计是一种面向( )的设计方法。 A. 数据流 B. 模块 C. 数据结构 D. 程序 8. 与确认测试阶段有关的文档是( )。

2015武汉大学《算法设计与分析》期中试卷

武汉大学计算机学院算法设计与分析期中测试姓名：学号：学院：专业：一、请用大“O(·)”记号求下列函数的渐进表达式：3n 2 + 10n -1; n 2/10 + 2n +1/n; 14 + 5/n + 1/n 2 ; n n +2log ; 20log3n （10分,每小题2分）解答：上述渐进表达式的时间复杂度分别为： 3n 2 + 10n -1 =O(n 2); n 2/10 + 2n + 1/n =O(2n ); 14 + 5/n + 1/n 2=O(1); n n +2log =O(logn); 20log3n =O(n) 二、令{1},{2},{3},…,{8}是n 个单元素集合，每个集合由一棵仅有一个结点的树表示。请用按秩合并和路径压缩措施的UNION-FIND 算法来执行以下操作序列，并画出每一步操作完成后的树表示。（总分20分）合并和查找操作序列如下所示：UNION （1,2）；UNION （4,3）；UNION （5,6）；UNION （7,8）；UNION （2,6）；FIND （1）；UNION （3,8）；UNION （8,6）；FIND （4）；FIND （5）。要求：UNION 操作在同秩情况下，以后一个结点作为根结点。如UNION （1，2），生成以2为根结点的树。解答：

(b) (a) UNION （1,2）;UNION （4,3）;UNION （5,6）;UNION （7,8）; (c) UNION （2,6）; (d) FIND （1）; (e) UNION （3,8）;(g)FIND （4 ）; (h) FIND （5）; (f) UNION （8,6）; 三、设有n 个小球，其中一个是劣质球，其特征是重量较轻，给你一个天平，设计一个分治算法，找出劣质球。（总分15分）（1) 写出算法的主要思路；（5分）（2) 试分析算法的时间复杂度；（5分）（3) 试分析n=9和10，即n 分别为奇数和偶数，两种情形下的分治过程。（5分）解法：（1）二对分算法思路：

《算法设计与分析》历年期末试题整理_含答案

《算法设计与分析》历年期末试题整理(含答案) （1）用计算机求解问题的步骤： 1、问题分析 2、数学模型建立 3、算法设计与选择 4、算法指标 5、算法分析 6、算法实现 7、程序调试 8、结果整理文档编制（2）算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程（3）算法的三要素 1、操作 2、控制结构 3、数据结构算法具有以下5 个属性：有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间完成。确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。算法设计的质量指标：正确性：算法应满足具体问题的需求；可读性：算法应该好读，以有利于读者对程序的理解；健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。利用迭代算法解决问题，需要做好以下三个方面的工作：一、确定迭代模型。在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。二、建立迭代关系式。所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。三、对迭代过程进行控制。在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。编写计算斐波那契（Fibonacci）数列的第n 项函数fib（n）。

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

《算法分析与设计》作业参考答案作业一一、名词解释： 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]

西安电子科技大学平时作业-计算方法

《计算方法》平时作业一选择（每题3分，合计42分） 1. x* ＝ 1.732050808，取x ＝1.7320，则x 具有 B 位有效数字。 A 、3 B 、4 C 、5 D 、6 2. 取7 3.13≈（三位有效数字），则 ≤-73.13 B 。 A 、30.510-? B 、20.510-? C 、10.510-? D 、0.5 3. 下面_ D _不是数值计算应注意的问题。 A 、注意简化计算步骤，减少运算次数 B 、要避免相近两数相减 C 、要防止大数吃掉小数 D 、要尽量消灭误差 4. 对任意初始向量) 0(x 及常向量g ，迭代过程g x B x k k +=+)()1(收敛的充分必要条件是_ C_。 A 、11< B B 、1<∞ B C 、1)(

算法设计与分析期末试题答案解析

1、用计算机求解问题的步骤： 1、问题分析 2、数学模型建立 3、算法设计与选择 4、算法指标 5、算法分析 6、算法实现 7、程序调试 8、结果整理文档编制 2、算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程 3、算法的三要素 1、操作 2、控制结构 3、数据结构算法具有以下5个属性：有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。算法设计的质量指标：正确性：算法应满足具体问题的需求；可读性：算法应该好读，以有利于读者对程序的理解；

健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法迭代法基本思想：迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。解题步骤：1、确定迭代模型。根据问题描述，分析得出前一个（或几个）值与其下一个值的迭代关系数学模型。 2、建立迭代关系式。迭代关系式就是一个直接或间接地不断由旧值递推出新值的表达式，存储新值的变量称为迭代变量 3、对迭代过程进行控制。确定在什么时候结束迭代过程，这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一

算法设计期中试卷平时作业参考解答

《算法分析与设计》2012-2013-2学期期中测试（信息安全专业DQ 教学班）姓名：学号：得分： 1. 证明()()()()()()()O f n O g n O f n g n +=+。（10分）证明：对于任意f 1(n ) ∈ O (f (n ))，存在正常数c 1和自然数n 1，使得对所有n ≥ n 1，有f 1(n ) ≤ c 1f (n )成立。类似，对于任意g 1(n ) ∈ O (g (n ))，存在正常数c 2和自然数n 2，使得对所有n ≥ n 2，有g 1(n ) ≤ c 2g (n )成立。令c 3 = max{c 1, c 2}，n 3 = max{n 1, n 2}，则对所有的n ≥ n 3，有 f 1(n ) +g 1(n ) ≤ c 1f (n ) + c 2g (n ) ≤ c 3f (n ) + c 3g (n ) = c 3(f (n ) + g (n )) 即()()()()()()()O f n O g n O f n g n +=+成立。 2. 将下列5个函数按渐近增长率由低至高进行排序，要求写出比较过程。（15分） 100log 2log loglog 12345()(log ),()log ,()log ,()2,()n n n n f n n n f n n f n n n f n f n +===== 解： 100log 2log log log 24()log 100log ,()2log ,n n n f n n n f n n n +==== (1) 2()f n 是对数函数的幂，5()f n 是幂函数，因此()25()()f n O f n =; (2) ()()()491105log lim lim lim log n n n f n n n n n f n n →∞ →∞→∞===∞，因此()54()()f n O f n =; (3) ()() 423log 1lim lim lim 0log n n n f n n n f n n n n →∞ →∞→∞===，因此()43()()f n O f n =; (4) 对1()f n 和3()f n 取对数，有 ()()() 13log ()log loglog loglog ,log ()2log loglog log f n n n n n n n f n n n n =+=Θ=Ω=+=Θ，因为()log n O n =，所以()31()()f n O f n =; 因此，5个函数按渐近增长率由低至高排序为25431(),(),(),(),()f n f n f n f n f n 。 3. 给定按升序排列的n 个不同整数存于数组a [1:n ]中，请设计()log O n 的算法找到下标i ，1i n ≤≤，使得a [i ] = i ，如不存在这样的下标，则返回0。（15分）解：令head = 1, rear = n . (1) 当head <= rear 时，令mid = ?(head + rear)/2?； (2) 如果a [mid] = mid ，返回mid 值，结束。如果a [mid] > mid ，令rear = mid – 1，返回(1)继续执行；如果a [mid] < mid ，令head = mid + 1，返回(1) 继续执行； (3)返回0值，结束。

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

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

作业练习二一、名词解释 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 }。

湖南大学算法设计与分析期中试题及答案

一、函数渐进阶。对于下列各组f(x)和g(x)，确定他们的关系（15分） a)f(x)=log n10+1；g(x)= log n – 10 b)f(x)=5 n10；g(x)=10n c)f(x)=；g(x)= log n +5 二、设n个不同的整数排好序后存于T[0:n-1]中。若存在下标i，0≤i

1函数渐进阶。对于下列各组f(x)和g(x)，确定他们的关系（15分） a)f(x)=log n10+1；g(x)= log n – 10 b)f(x)=5 n10；g(x)=10n c)f(x)=；g(x)= log n +5

2设n个不同的整数排好序后存于T[0:n-1]中。若下标i，0≤imid在0到mid-1之间进行上述操作。 Int Findi(int T[],int m,int n) { Int mid=(m+n)/2; If (T[mid]==mid) return mid; else if(T[mid]>mid) return Findi(T[],m,mid-1); else return Findi(T[],mid+1,n); }

算法设计与分析读书笔记

<<算法引论>> ------- 一种创造性方法 ---读书笔记【美】Udi Mander 计算1314 苏帅豪 201321121109 Chapter 1: （引论）广义地说，算法是按部就班解决一个问题或完成某个目标的过程。数学归纳法其原理的主要思想是命题无须从什么都没有开始证明，可以通过先证明对于一个小的基本实例集命题是正确的，然后由?若对相对较小的命题实例成立则可导出较大的命题实例成立?的方式，来证明对所有实例来说命题都是成立的。因此它的基本思想是如何扩充一个解决方案而不是从零开始进行构造。 Chapter2: (数学归纳法) 显而易见与真知灼见水火不容。——伯特兰·罗素每次用归纳法证明都分成两步：归纳基础和规约。归纳基础一般都比较容易，偶尔也有不太简单的，但我们往往不太在意。归纳法证明的核心就是规约，有多种规约方法，其中最常用的就是把命题从N规约到N—1 ，从N+1规约到N也比较常见。强归纳法会把命题从N规约到比N小（但不一定是N-1）的一个或多个命题。其它变形还有从2N规约到N，以及逆向归纳法，也就是命题在N时的情况是由N+1的情况推出的，而归纳基础是个已被证明的无限集。规约的要点在于要完整保留原命题，不能在规约后的命题中加入多余的假设，除非这些假设是特别包含在归纳假设中的。增量：很明显，增量就是和我们平时的数学归纳法一样，特殊点的就是证明起始条件；假设对于K，证明成立；用假设去证明对K+1，证明成立证明的重点就这如何利用‘K’证明‘(K+1)’ 当然也可以认为是利用某种性质去推广其实这个就是动态规划和贪心的基本性质，最优子结构性质以及重叠子问题性质(贪心选择性质)中的最优子结构性质；现在举个"不同"例子找多数元素(多数元素的定义：在给定有限个序列内，某元素的个数大于序列个数的1/2(比如 {1 2 3 3 3}中的3)) 首先我们第一会想到枚举，很简单，时间复杂度为O(n^2)；最好的情况是一遍遍历就找到了:O(n) 最坏的情况是序列中没有多数元素：O(n^2) 平均情况:O(n^2) 现在让我们想下对于多数元素有什么性质，设序列元素个数为N，多数元素个数为m，接下来给出一个很直接的性质(虽说很直接但是对我来说是不容易自己想出来的)：性质1：删除序列中的两个不同的数，若存在多数元素，多数元素依然存在且不变。现在我可以想出一个算法: 集合A:序列循环：i：1->n-1 if(A[i]==A[i+1]||A[i]不存在) continue;

《算法设计与分析》实验指导

《算法分析与设计》实验指导.

实验一锦标赛问题 [实验目的] 1.基本掌握分治算法的原理. 2.能用程序设计语言求解锦标赛等问题的算法; [预习要求] 1.认真阅读数据结构教材和算法设计教材,了解分治算法原理; 2.设计用分治算法求解背包问题的数据结构与程序代码. [实验题] 【问题描述】设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其他n-1个选手各赛一次；（2）每个选手一天只能参赛一次；（3）循环赛在n-1天内结束。请按此要求将比赛日程表设计成有n行和n-1列的一个表。在表中的第i行，第j列处填入第i个选手在第j天所遇到的选手。其中1≤i≤n，1≤j≤n-1。 [实验提示] 我们可以按分治策略将所有的选手分为两半，则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手时，比赛日程表的制定就变得很简单。这时只要让这两个选手进行比赛就可以了。 1 2 3 4 5 6 7 1 （1）（2）（3）图1 2个、4个和8个选手的比赛日程表图1所列出的正方形表（3）是8个选手的比赛日程表。其中左上角与左下角的两小块分别为选手1至选手4和选手5至选手8前3天的比赛日程。据此，将左上角小块中的所有数字按其相对位置抄到右下角，又将左下角小块中的所有数字按其相对位置抄到右上角，这

样我们就分别安排好了选手1至选手4和选手5至选手8在后4天的比赛日程。依此思想容易将这个比赛日程表推广到具有任意多个选手的情形。 [实验步骤] 1.设计并实现算法并准备测试用例,修改并调试程序,直至正确为止; 2.应用设计的算法和程序求锦标赛问题; 3.去掉测试程序,将你的程序整理成功能模块存盘备用. [实验报告要求] 1.阐述实验目的和实验内容; 2.阐述分治算法原理; 3.提交实验程序的功能模块; 4.记录最终测试数据和测试结果。 [思考与练习] 【金块问题】老板有一袋金块(共n块，n是2的幂（n>=2）），将有两名最优秀的雇员每人得到其中的一块，排名第一的得到最重的那块，排名第二的雇员得到袋子中最轻的金块。假设有一台比较重量的仪器，请用最少的比较次数找出最重和最轻的金块。

相关主题

算法与分析平时作业

算法设计分析期中试题

算法设计期中试卷

投资分析平时作业四

算法分析与设计作业

算法分析与设计大作业

相关文档

投资分析平时作业1-4答案

算法设计方案与分析课程期末试卷

算法设计与分析平时成绩细则

2017算法设计与分析课程大纲

算法设计期中试卷、平时作业参考解答

投资分析平时作业1-4答案

算法分析与设计作业(一)及参考答案

空间分析课程作业

算法设计期中试卷平时作业参考解答

算法设计与分析ppt

算法设计与分析

算法设计期中试卷、平时作业参考解答知识讲解

现代软件工程平时作业及答案

投资分析平时作业1-4答案

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

算法与分析平时作业 - 答案

算法与分析平时作业 - 答案

算法与分析平时作业-答案

西安电子科技大学平时作业-计算方法

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

最新文档

幼儿园小班科学《小动物过冬》PPT课件教案

2021年春新青岛版(五四制)科学四年级下册 20.《露和霜》教学课件

自然教育课件

小学语文优质课火烧云教材分析及课件

(超详)高中语文知识点归纳汇总

高中语文基础知识点总结(5篇)

高中语文基础知识点总结(最新)

高中语文知识点整理总结

高中语文知识点归纳

高中语文基础知识点总结大全

超详细的高中语文知识点归纳

高考语文知识点总结高中

高中语文知识点总结归纳

高中语文知识点整理总结

高中语文知识点归纳

高中语文知识点归纳(大全)

高中语文知识点总结归纳(汇总8篇)

高中语文基础知识点整理

化工厂应急预案

化工消防应急预案(精选8篇)