1算法就是一组有穷的1算法就是一组有穷的
第一章 绪 论
一 填空
1(算法就是一组有穷的 , 它们规定了解决某一特定类型问题的
2..算法具备五个重要特性: 、 、 、 、 3. 要制定一个算法,一般要经过 、 、 、 、 等阶段。
4. 算法的复杂性是 的度量,是评价算法优劣的重要依据。 5(一个算法的复杂性的高低体现在运行该算法所需要的 的多少上。 6(计算机的资源,最重要的是 和 资源。因而,算法的复杂性有 和 之分。
7. 算法的时间复杂性函数用T(n)表示,它是 的函数。 8. T(n)中的n对于不同的问题,有不同的表现形式...
1算法就是一组有穷的
第一章 绪 论
一 填空
1(算法就是一组有穷的 , 它们
了解决某一特定类型问
的
2..算法具备五个重要特性: 、 、 、 、 3. 要制定一个算法,一般要经过 、 、 、 、 等阶段。
4. 算法的复杂性是 的度量,是评价算法优劣的重要依据。 5(一个算法的复杂性的高低体现在运行该算法所需要的 的多少上。 6(计算机的资源,最重要的是 和 资源。因而,算法的复杂性有 和 之分。
7. 算法的时间复杂性函数用T(n)表示,它是 的函数。 8. T(n)中的n对于不同的问题,有不同的表现形式。指出下列问题中n的计量。
1) 在数组中找值为c的分量 , n表示
2) 两个矩阵相乘 , n表示
3) 一个数表的排序,n表示
4) 遍历一棵二叉树,n表示
9.最坏情况下的时间复杂性定义: 10. 平均情况下的时间复杂性定义: 11.最具有可操作性和实际价值的是 复杂性。教材中没有特殊说明时,T(n)一般指的就是 。
12(f(n)=O(g(n))表示
当且仅当存在正的常数C和N,使得对于所有的n ,有f(n) 。 0
13. 写出下列f(n)的渐进性态:
1) f(n)=C,为常数:f(n)= O( )。 0
2) f(n)= 3n+2:f(n)= O( )。
n3) f(n)= 6×2+n:f(n)= O( )。
4) f(n)= nlog n:f(n)= O( )。
二
算法复杂性
1. 已知不重复且已经按从小到大排好的m个整数的数组A[L(m](为简单起
k见,设m,2,k是一个确定的非负整数)。对于给定的整数c,要求寻找一个下标i,使得A[i]=c,若找不到,则返回一个0。算法如下:
procedure search( c)
/*c是整型数 */
{ i?0; j?l;
while A[j]
r then
10 for to by-l do
11 ;
12 repeat
13 ;k?k+1
14 endif
15 repeat
16 end JS
二 设计算法
n
a,L1(有n 个程序和长度为L的磁带,程序i的长度为a,已知,求最i,i,1i优解(x,x ,...,x,…, x),x =0,1, x =1,表示程序i存入磁带,x =0,i2iniii
n
xa,L表示程序i不存入磁带,满足,且存放的程序数目最多。 ,ii,1i
2.有n 个活动争用一个活动室。已知活动i占用的时间区域为[s,f ),活动i,jii相容的条件是:sj?f ,问题的解表示为(x| x =1,2…,n,),x表示顺序为i的iiii活动编号活动,求一个相容的活动子集,且安排的活动数目最多。
第四章 动态规划
一. 填空
1.最优化原理:无论过程的 是什么,其余的决策都必须相对于初始决策所产生的状态 。
2(最优子结构性质: 。 3.子问题重叠性质:每次产生的子问题并不总是 ,有些子问题被 。
4(多段图动态规划算法
procedure FGRAPH(E,k,n,P)
1 real COST(n),integerD(n一1),P(k),r,j,k,n 2 ;
3 for to 1 by,1do
4 设r是一个这样的结点,(j,r)E且使c(j,r)+COST(r)取最小值 5 COST(j)? ; 6 ;
7 repeat
8 P(1)?1; ;
9 for do 10 P(j)?D ( P(j-1) ) 11 repeat
12 end FGRAPH
二(回答问题
1.写出0/1背包问题的递推式,并简述其表述的意义。 2.写出多段图的向后递推式,并简述其表述的意义。 三.解题
1.有一多段图如图所示,按算法4.1的步骤求出最短路经及其代价。
2 5 21 6 4 2 3 1 8 3 2 8 4 1 3 6 10 5 6 2 2 9 7 7 9 4 7
2. 已知有3个物品:(w1,w2,w3)=(12,10,6), (p1,p2,p3)=(15,13,10), 背包的容积M=20,根据0/1背包动态规划的递推式求出最优解。
第五章 回溯法
一.回答问题
1. 简述 回溯法的基本思路。
2(什么是显约束条件,什么是隐式约束条件,
3(以一棵深度为3的3叉树为例,说明代约束条件的深度优先过程。
高度为n=3,m=3的状态空间树 i
4(说明N皇后的解向量所表示的意义。
5(N皇后算法的过程PLACE(k)的功能。并分析最坏情况下的时间复杂性。 6(说明子集和数问题的回溯法所用的约束条件为什么提高了搜索效率。
二,设计算法
1(写出0/1背包问题的递归形式的回溯算法。
2(写出子集和数的非递归形式的算法。
第6章 分枝-限界法
一. 回答问题
1. 简述FIFO检索和LIFO检索
,
2(代价估值函数 (X)的定义。 c
3(最小代价搜索( LC检索)的基本思想。
4(用最小代价搜索法解9宫问题,代价估值函数是如何选取的, 5(怎样判断LC-找到的答案结点是最小成本的答案节点?为什么, 6(分枝—限界算法的上界函数的作用是什么,
二(根据分枝—限界算法基本过程,求解0/1背包问题。已知,n=3,M=20,(w1,w2,w3)=(12,10,6), (p1,p2,p3)=(15,13,10)。
本文档为【1算法就是一组有穷的】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。