算法设计期中试卷平时作业参考解答
《算法分析与设计》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值，结束。
public static int Search(int [] a, int n) {
. <= a[n -1] 中搜索 a[i] = i
利用主方法给出下列递归式的渐近界，并用数学归纳法证明式(2)的渐近界。（20
分）
(1) ()()42T n T n n =+, (2) ()()242T n T n n =+, (3) ()()342T n T n n =+
解：(1) 24,2,log log 42,b a b a ==== ()(
)
2, if 0.5,f n n O n εε-===
因此，()()
2T n n =Θ. (2) 24,2,log log 42,b a b a ==== ()()22,f n n n ==Θ
因此，()()
2log T n n n =Θ.
(3) 24,2,log log 42,b a b a ==== ()(
)
32, if 0.5,f n n n εε+==Ω=
而且()()()3
33424234,f n n n n cf n ==≤=其中34n =，
因此，()()
3T n n =Θ.
证明：假设当k n <时，()2log T k ck k ≤，其中c 为常数。
()()()()()()2
2
22222242 42log 2 log 1 log 1 log if 1
T n T n n c n n n cn n n cn n c n cn n c =+≤+=-+=--≤≥
因此，命题得证。
5. 利用直接展开法求解下列递归式的渐近界。（20分）
(1) ()()242T n T n n =+, (2) (
)T n n =+
解：(1)
()()()()
()()()
()()()()()2
2222222
232423322log log 2222424422422442224234242log 1log log k k n n T n T n n T n n n T n n T n n n T n n T n kn T n n n n T n n O n n =+=++=+=++=+=
=+=
=+=+=
12
n
某超市中有i 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
?m(i, j – w i) 为新重量限制下，{1, …, i – 1}种商品装入购物车所产生的最大价值
因此，递归式如下：
()()()(){}0if 0 or 0,1,if max 1,,1,otherwise
i i i i j m i j m i j w j
m i j v m i j w ?==??
=->??-+--??
最优解：选择商品1,1’,3, 即选择两个商品1, 一个商品3 最优值 = 25+25+15=65
方法2
? 定义m (i , j )为购物车容量为j ，由第1, …, i 种商品装入购物车的最优值。 ? Case 1: 不选择第i 种商品
? 则m (i , j )为当重量限制为j 时，{1, …,i – 1}种商品装入购物车所产生的最大价值
? Case 2: 仅选择1格第i 种商品.
? 新的重量限制为 j – w i
? m (i , j – w i ) 为新重量限制下，{1, …, i – 1}种商品装入购物车所产生的最大价值
? Case 3: 选择两个第i 种商品
? 新的重量限制为 j – 2w i
? m (i , j – 2w i ) 为新重量限制下，{1, …,i – 1}种商品装入购物车所产生的最大价值
因此，递归式如下：
()(
)()(){}
()()()0
if 0 or 0
1,if max 1,,1,if <2,1,,1,,max if 221,2i i i i i i i i
i i i j m i j
j w m i j v m i j w w j w m i j m i j v m i j w j w v m i j w ==??-
-+--<=????-+--??
?>???+--?????
最优解：选择两个商品1, 一个商品3 最优值 = 25+25+15=65
第2章作业：算法分析基础 1. 算法与程序的区别
(1).算法特性之一是有穷性，程序不一定满足有穷性。
(2). 计算机程序是用来给计算机读的，而算法是给人来读的，直接将算法输入计算机是不能运行的。 (3).算法是解决问题的一种方法或一个过程，而程序则是算法用某种程序设计语言的具体实现。 2. 将下列函数按渐进增长率由低到高排列出来。
(
)()(
)()()()2
4/3
log 2log 123456,,(log )
,2,,n
n n
n f n f n n f n f n n n f n f n n ===
===
令log m n =，则有
()()()()()()()()()1113344266log ,
2
log log ,
3log log log ,log ,
g n f n m g n f n m g n f n m m m m n g n f n m ======+=Θ==
显然上述4个函数的渐近增长率排序为()()()()3146g n g n g n g n ≤≤≤；
()()()()()()22255266log log ,log 2,log log ,
n g n f n n n g n f n g n f n n ======
显然上述3个函数的渐近增长率排序为()()()625g n g n g n ≤≤；
因此，原函数的渐近增长率排序为()()()()()()314625f n f n f n f n f n f n ≤≤≤≤≤。
3. 已知()()()g n O f n =，证明()()()()f n g n O f n +=。
证明：因为()()()g n O f n =，存在正常数c 0和自然数n 0，使得对所有n ≥ n 0，有()()0g n c f n ≤成立。 令c 1 = c 0 + 1，则对所有的n ≥ n 0，有 f (n ) +g (n ) ≤ f (n ) + c 0f (n ) ≤ (1 + c 0)f (n ) = c 1f (n )
即()()()()f n g n O f n +=成立。
第3章作业：分治递归
1.画出T(n)=2T(n/2)+1的递归树，并给出其解的渐进界。然后用数学归纳法证明给出的界。
1
1
1
1
1
1
11
1
1
……
…
…
…
…
…
…
…
…
…
…
…
…
T (1)T (1)T (1)T (1)T (1)T (1)T (1)T (1)T (1)T (1)T (1)T (1)T (1)T (1)T (1)
122223
n
Total : O (n )
证明：假设当k n <时，()12T k c k c ≤-，其中c 1和c 2为常数。
()()()()1212122221 221 21 if 1
T n T n c n c c n c c n c c =+≤-+????=--≤-≥
因此，命题得证。
2.直接展开法求解递归式T(n)=T(n/2)+1
()()()()()()()()23log 21222322log =1log log k
n T n T n T n T n T n k
T n n T n O n =+=+=+=
=+=
=++=
3.用主方法求解递归式
(n)=4T(n/2)+n, (n)=4T(n/2)+n 2, (n)=4T(n/2)+n 3, (n)=3T(n/2)+ n 2
请参考期中测试答案。
第4章作业：动态规划
1、设计一个O(n*log k) 时间的分治递归算法，将k 个排好序的序列合并成一个排好序的序列，其中 k 个序列共计包含n 个元素。
将k 个有序数列两两合并排序，得到2k ????个有序数列，再次两两合并排序，得到4k ????个有序数列，重复操作直至得到一个长度为n 的有序数列。共计log k 次合并排序，每次合并排序数据的总体规模为n ，则时间复杂度为O(n log k )
2、给定数组a[1…n]，n 为偶数。设计一个算法，在最坏情况下用 3n/2 – 1 次比较找出a[1…n]中元素的最大值和最小值。
将a[1]…a[N]两两分成一组，即为a[1]和a[2] , a[3]和a[4] , a[5]和a[6] , … 共计N/2组，每组中的两个元素进行比较，得到最大值和最小值，共计N/2次比较；
上述每组中的最大值组成数组b[1…N/2]，冒泡排序(或其他排序方法)求得b[1…N/2]中的最大值，即为原数组a[1…N]的最大值，需N/2 – 1次比较；
同理，上述每组中的最小值组成数组c[1…N/2]，冒泡排序(或其他排序方法)求得c[1…N/2]中的最小值，即为原数组a[1…N]的最小值，需N/2 – 1次比较； 因此，共需3N/2 – 1次比较.
3、设计O(n 2)时间的动态规划算法，找出由n 个数组成的序列的最长单调递增子序列，要求给出分析过程和递归表达式。
原序列记为X, 对n 个数递增排序, 构造一个新序列Y , 对X, Y 求其最长公共子序列即可. 设序列X={x 1,x 2,…,x m }和Y={y 1,y 2,…,y n }的最长公共子序列为Z={z 1,z 2,…,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 且z k ≠x m ，则Z 是x m -1和Y 的最长公共子序列。 (3)若x m ≠y n 且z k ≠y n ，则Z 是X 和y n -1的最长公共子序列。
由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用c[i][j]记录序列和的最长公共子序列的长度。其中， X i ={x 1,x 2,…,x i }；Y j ={y 1,y 2,…,y j }。当i=0或j=0时，空序列是X i 和Y j 的最长公共子序列。故此时c[i][j]=0。其他情况下，由最优子结构性质可建立递归关系如下：
00 or 0[][][1][1]1
,0 and max{[][1],[1][]},0 and i j i j
i j c i j c i j i j x y c i j c i j i j x y ?==?
=--+>=??-->≠?
4、两个序列进行对齐时，匹配得1分，错配罚1分，空位罚2分。给定两个字符序列X=CT…CG 和Y=T…C…G ，如何对齐才能使得得分最大？根据递归公式自底而上求解上述问题，要求画出求解过程表格，并给出最大得分和相应的对齐方式。 OPT(i, j) = 对齐 x 1 x 2 … x i 和 y 1 y 2 … y j .最大的得分 Case 1: OPT 匹配 x i -y j .
x i -y j 配对的得分 + 对齐x 1 x 2 … x i -1 和y 1 y 2 … y j -1 最大的得分 Case 2a: OPT 留下 x i 不匹配
– 2 + 对齐 x 1 x 2 … x i -1 和 y 1 y 2 … y j 最大的得分 Case 2b: OPT 留下 y j 不匹配
– 2 + 对齐 x 1 x 2 … x i 和 y 1 y 2 … y j -1 最大的得分
2if 0(1,1)(,)max 2(1,)
otherwise 2(,1)2if 0
i j x y j i OPT i j OPT i j OPT i j OPT i j i j α?
??????
?????????-=+--=-+--+--=
最优对齐方式为
第5章作业：贪心算法
1、请叙述分治递归、动态规划、备忘录方法和贪心算法各自的特点和基本要素，并比较它们之间的相同之处及其差异。
分治递归法所能解决的问题一般具有以下几个特征:
(1) 该问题规模缩小到一定的程度就可以容易地解决；
(2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有递归子结构性质
(3) 利用该问题分解出的子问题的解可以合并为该问题的解；
(4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
动态规划与分治的比较
(1) 共同点：递归子结构
将待求解问题分解成若干个规模较小的相同类型的子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
(2) 不同点：重叠子问题
适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。
(3) 不同点：求解问题的顺序
分治递归、备忘录方法：自顶向下，动态规划：自底向上，
贪心算法的基本要素
(1) 贪心选择性质
(2) 最优子结构性质
贪心算法的特点
(1) 总是作出局部最优选择
(2) 不能保证得到全局最优解
贪心法与动态规划的比较
相同点：递推算法、最优子结构、局部最优解→全局最优解
不同点：
动态规划：自底向上，贪心算法：自顶向下
贪心算法：当前局部最优解←上一步局部最优解，动态规划：当前局部最优解←之前所有局部最优解 2、给定一个包含{b,e,f,n,o,t,y}字符集的文本文件，每个字符在文件中出现频率如下表所示，文件共有140个字符，试用huffman 编码对该文本文件进行编码，要求画出编码的huffman 树，给出每个字符的huffman 编码，并求解编码后文件的长度。
6
7
13
12
25
15
24
39
33
58
43
82
140
t :0000o :0001b :001f :01
n :100y :101e :110
000
00
1
1
11
11
编码后文件长度 = (6 + 7) × 4 + (12 + 15 + 24) × 3 + (33 + 43) × 2 = 357 bit
3、用Dijkstra 算法求下图中顶点1到其他所有顶点的最短路径，要求给出计算过程和最优解、最优值。
解1：
解2：
最短路径：
1→2：1,2
1→3：1,3
1→4：1,4
1→5：1,3,5
1→6：1,3,5,6
1→7：1,3,5,6,7
4、分别叙述用Prim算法和Kruskal算法求最小生成树的过程，并分别用上述两种算法求下图的最小生成树，要求给出最小生成树中边的生成顺序，画出最小生成树，并最小权重之和。（其中Prim算法从节点1开始执行）
Prim‘s 算法. 首先置S={1}，然后，只要S是V的真子集，就作如下的贪心选择：选取满足条件i∈S，j∈V-S，且c[i][j]最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止
Kruskal‘s 算法. 首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小到大排序。然
后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止。
Prim‘s 算法.(1,3), (3,5), (5,6), (6,7), (6,4), (4,2)
Kruskal‘s 算法. (6,7), (5,6), (1,3), (6,4), (4,2), (3,5)
权重之和为15。
算法设计与分析课程期末试卷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、二分搜索算法是利用（ 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 ）。
算法设计分析期中试题
《算法设计与分析》期中试卷 一、叙述分治算法的基本思想及一般算法设计模式； 二、叙述动态规划算法的基本步骤及动态规划算法的基本 要素； 三、改进课本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。 试设计一个解此问题的动态规划算法，并分析算法的计算复杂性。
算法设计与分析课后部分习题答案
算法实现题3-7 数字三角形问题 问题描述： 给定一个由n行数字组成的数字三角形，如图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。编程任务： 对于给定的由n行数字组成的数字三角形，编程计算从三角形的顶至底的路径经过的数字和的最大值。数据输入： 有文件input.txt提供输入数据。文件的第1行是数字三角形的行数n，1<=n<=100。接下来的n行是数字三角形各行的数字。所有数字在0-99之间。结果输出： 程序运行结束时，将计算结果输出到文件output.txt中。文件第1行中的数是计算出的最大值。 输入文件示例输出文件示 例 input.txt output.txt 5 30 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 源程序： #include "stdio.h" voidmain() { intn,triangle[100][100],i,j;//triangle数组用来存储金字塔数值,n表示行数 FILE *in,*out;//定义in，out两个文件指针变量 in=fopen("input.txt","r"); fscanf(in,"%d",&n);//将行数n读入到变量n中
for(i=0;i
北航数值分析大作业第一题幂法与反幂法
《数值分析》计算实习题目 第一题： 1. 算法设计方案 （1）1λ，501λ和s λ的值。 1)首先通过幂法求出按模最大的特征值λt1，然后根据λt1进行原点平移求出另一特征值λt2，比较两值大小，数值小的为所求最小特征值λ1，数值大的为是所求最大特征值λ501。 2)使用反幂法求λs ，其中需要解线性方程组。因为A 为带状线性方程组，此处采用LU 分解法解带状方程组。 （2）与140k λλμλ-5011=+k 最接近的特征值λik 。 通过带有原点平移的反幂法求出与数k μ最接近的特征值 λik 。 （3）2cond(A)和det A 。 1）1=n λλ2cond(A)，其中1λ和n λ分别是按模最大和最小特征值。 2）利用步骤（1）中分解矩阵A 得出的LU 矩阵，L 为单位下三角阵,U 为上三角阵，其中U 矩阵的主对角线元素之积即为det A 。 由于A 的元素零元素较多，为节省储存量，将A 的元素存为6×501的数组中，程序中采用get_an_element()函数来从小数组中取出A 中的元素。 2.全部源程序 #include
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）二对分算法思路：
软件系统分析与设计大作业
《软件系统分析与设计》 期末大作业 选题名称：游戏平台管理系统设计人：徐文豪刘青海 赖超宇甘智宏 班级：软工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、问题分析 2、数学模型建立 3、算法设计与选择 4、算法指标 5、算法分析 6、算法实现 7、程序调试 8、结果整理文档编制 （2）算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程 （3）算法的三要素 1、操作 2、控制结构 3、数据结构算法具有以 下5 个属性： 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间完成。确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。 输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。 输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。 算法设计的质量指标：正确性：算法应满足具体问题的需求；可读性：算法应该好读，以有利于读者对程序的理解；健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。 效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。 经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法 迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。 利用迭代算法解决问题，需要做好以下三个方面的工作：一、确定迭代模型。在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。 二、建立迭代关系式。所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。 三、对迭代过程进行控制。在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。 编写计算斐波那契（Fibonacci）数列的第n 项函数fib（n）。
算法设计与分析第2版 王红梅 胡明 习题答案
精品文档习题胡明-版)-王红梅-算法设计与分析(第2答案 1 习题）—1783Leonhard Euler，17071.图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（提 出并解决了该问题。七桥问题是这样描述的：北区一个人是否能在一次步行中穿越哥尼斯堡（现东区在叫加里宁格勒，在波罗的海南岸）城中全部岛区的七座桥后回到起点，且每座桥只经过一次，南区是这条河以及河上的两个岛和七座桥的图1.7 1.7 七桥问题图草图。请将该问题的数据模型抽象出来，并判断此问题是否有解。 七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点一次步行1，经过七座桥，且每次只经历过一次2，回到起点3，该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。）用的不是除法而是减最初的欧几里德算法2．在欧几里德提出的欧几里德算法中（即法。请用伪代码描述这个版本的欧几里德算法 1.r=m-n r=0 循环直到2.m=n 2.1 n=r 2.2 r=m-n 2.3 m 输出3 ．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代3++描述。C码和 采用分治法// //对数组先进行快速排序在依次比较相邻的差//精品文档． 精品文档 #include
软件设计大作业
一需求分析 此系统是一个类似于淘宝网的在线衣服销售系统，相当于淘宝网上的一个专门买衣服的网店，它具有用户注册，用户登录，修改密码，显示系统功能，查看订购历史以及订货。 1.1需求列表： （1）用户管理：用户管理的需求包括用户注册，用户登录以及修改密码。 用户注册是添加一个我们网上衣店的新用户；用户登录是用户想要进 入系统时必须采取验证身份的步骤；修改密码是为了用户的安全性考 虑，当密码存在不安全的因素时，适时修改密码。 （2）商品衣服的管理：商品管理包括订购衣服和查看订购衣服的历史。订购衣服是当我们衣店的库存数量不足时必须采取的；查看订购衣服的 历史有助于我们更好地了解衣服的订购情况。 （3）显示系统功能：此功能是用来让用户能很清楚地了解此系统所实现的各种功能。 1.2系统用例图：
1.3用例分析及场景描述： 用户注册用例： 这部分主要是新用户进行注册的过程，首先用户进入到注册页面，填写注册信息并提交，如果无误的话系统会给予注册成功的提示，如果注册失败会提示注册失败信息。 用户登录用例： 此功能模块针对的对象是本网站的会员既已经注册的会员，会员首先填写用户名和密码，然后点击登录按钮，如果网站数据库中存在此会员并且密码正确则提示登录成功提示，如果网站不存在此用户或密码不正确，系统会提示用户登录失败。 修改密码用例： 此用例针对注册会员进行操作。用户登录成功会可以进入网站主页面，如果用户想修改密码的话可以单击修改密码按钮，进行密码修改，用户输入新密码单击修改按钮即可完成密码修改。
显示系统功能用例： 此功能针对注册会员，会员首先登录到网站，进入主页，主页会有相关操作的按钮，显示系统所提供给会员操作的功能，用户可以针对自己的需要选择系统提供的功能。 订货衣服用例： 此功能针对注册登录会员，网站提供两种订购方案：单件订购和定制套装。用户可以根据自己的需求来选择。 单件订购方案：用户选择是上衣还是裤子，并填写订购的数量，确认无误后单击订购按钮即可，如果订购成功，系统会提示订购成功，失败则会提示订购失败。 定制套装方案：用户选择定制套装的档次（高、中、低），并填写订购的数量，确认无误后单击订购按钮即可，如果订购成功，系统会提示订购成功，失败则会提示订购失败。 显示订购历史用例： 此功能针对注册会员，用户登录到系统后，主页显示系统功能中包括历史查看选项，用户可以单击进入历史交易记录页面，页面将显示用户所有的交易记录。 二设计模式 2.1单件模式 2.1.1单件模式的定义
算法设计与分析考试题及答案
1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。 2.算法的复杂性有_____________和___________之分，衡量一个算法 好坏的标准是______________________。 3.某一问题可用动态规划算法求解的显著特征是 ____________________________________。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y的一个最长公共子序列_____________________________。 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。 6.动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为_____________。 8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。 9.动态规划算法的两个基本要素是___________和___________。 10.二分搜索算法是利用_______________实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 2.流水作业调度问题的johnson算法的思想。
算法分析大作业动态规划方法解乘法表问题和汽车加油行驶问题#精选.
算法分析大作业 动态规划方法解 乘法表问题和汽车加油行驶问题目录 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];
算法设计与分析期末试题答案解析
1、用计算机求解问题的步骤： 1、问题分析 2、数学模型建立 3、算法设计与选择 4、算法指标 5、算法分析 6、算法实现 7、程序调试 8、结果整理文档编制 2、算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程 3、算法的三要素 1、操作 2、控制结构 3、数据结构 算法具有以下5个属性： 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口 可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。 输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。 输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。 算法设计的质量指标： 正确性：算法应满足具体问题的需求； 可读性：算法应该好读，以有利于读者对程序的理解；
健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。 效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。 经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法 迭代法 基本思想：迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。 解题步骤：1、确定迭代模型。根据问题描述，分析得出前一个（或几个）值与其下一个值的迭代关系数学模型。 2、建立迭代关系式。迭代关系式就是一个直接或间接地不断由旧值递推出新值的表达式，存储新值的变量称为迭代变量 3、对迭代过程进行控制。确定在什么时候结束迭代过程，这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一
算法设计与分析试卷及答案
湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型：开卷 试卷类型：C 卷 考试时量：120 分钟 1. 用O 、Ω和θ表示函数f 与g 之间的关系______________________________。 ()()log log f n n n g n n == 2. 算法的时间复杂性为1, 1()8(3/7), 2 n f n f n n n =?=? +≥?，则算法的时间复杂性的阶 为__________________________。 3. 快速排序算法的性能取决于______________________________。 4. 算法是_______________________________________________________。 5. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是_________________________。 6. 在算法的三种情况下的复杂性中，可操作性最好且最有实际价值的是_____情况下的时间复杂性。 7. 大Ω符号用来描述增长率的下限，这个下限的阶越___________，结果就越有价值。。 8. ____________________________是问题能用动态规划算法求解的前提。 9. 贪心选择性质是指________________________________________________________ ____________________________________________________________。 题 号 一 二 三 四 五 总分 统分人 得 分 阅卷人
算法设计期中试卷平时作业参考解答
《算法分析与设计》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值，结束。
湖南大学算法设计与分析期中试题及答案
一、函数渐进阶。对于下列各组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≤i 第一章作业 1.证明下列Ο、Ω和Θ的性质 1）f=Ο(g)当且仅当g=Ω(f) 证明：充分性。若f=Ο(g)，则必然存在常数c1>0和n0，使得?n≥n0，有f≤c1*g(n)。由于c1≠0，故g(n) ≥ 1/ c1 *f(n)，故g=Ω(f)。 必要性。同理，若g=Ω(f)，则必然存在c2>0和n0，使得?n≥n0，有g(n) ≥ c2 *f(n).由于c2≠0，故f(n) ≤ 1/ c2*f(n)，故f=Ο(g)。 2）若f=Θ(g)则g=Θ(f) 证明：若f=Θ(g)，则必然存在常数c1>0，c2>0和n0，使得?n≥n0，有c1*g(n) ≤f(n) ≤ c2*g(n)。由于c1≠0，c2≠0，f(n) ≥c1*g(n)可得g(n) ≤ 1/c1*f(n)，同时，f(n) ≤c2*g(n)，有g(n) ≥ 1/c2*f(n)，即1/c2*f(n) ≤g(n) ≤ 1/c1*f(n)，故g=Θ(f)。 3）Ο(f+g)= Ο(max(f,g))，对于Ω和Θ同样成立。 证明：设F(n)= Ο(f+g)，则存在c1>0，和n1，使得?n≥n1，有 F(n) ≤ c1 (f(n)+g(n)) = c1 f(n) + c1g(n) ≤ c1*max{f,g}+ c1*max{f,g} =2 c1*max{f,g} 所以，F(n)=Ο(max(f,g))，即Ο(f+g)= Ο(max(f,g)) 对于Ω和Θ同理证明可以成立。 4）log(n!)= Θ(nlogn) 证明： ?由于log(n!)=∑=n i i 1 log ≤∑=n i n 1 log =nlogn ，所以可得log(n!)= Ο(nlogn)。 ?由于对所有的偶数n 有， log(n!)= ∑=n i i 1 log ≥∑=n n i i 2 /log ≥∑=n n i n 2 /2/log ≥(n/2)log(n/2)=(nlogn)/2-n/2。 当n ≥4，(nlogn)/2-n/2≥(nlogn)/4，故可得?n ≥4，log(n!) ≥(nlogn)/4，即log(n!)= Ω(nlogn)。 综合以上两点可得log(n!)= Θ(nlogn) 2. 设计一个算法，求给定n 个元素的第二大元素，并给出算法在最坏情况下使用的比较次数。（复杂度至多为2n-3） 算法： V oid findsecond(ElemType A[]) { for (i=2; i<=n;i++) if (A[1] 深圳大学研究生课程论文 题目大作业：变位词实验成绩 专业计算机与软件学院软件工程 课程名称、代码 年级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-1 加减得1的数学游戏 西西很喜欢数字游戏，今天他看到两个数，就想能否通过简单的加减，使最终答案等于1。而他又比较厌烦计算，所以他还想知道最少经过多少次才能得到1。 例如，给出16,9：16-9+16-9+16-9-9-9+16-9-9=1，需要做10次加减法计算。 设计算法，输入两个不同的正整数，输出得到1的最少计算次数。（如果无法得到1，则输出-1）。 （1）若输入两个不同的正整数a,b均为偶数，显然不可能得到1。 设x*a与y*b之差为“1”或“-1”,则对于正整数a,b经n=x+y-1次加减可得到1。 为了求n的最小值，令n从1开始递增，x在1——n中取值，y=n+1-x： 检测d=x*a+y*b，若d=1或-1，则n=x+y-1为所求的最少次数。 （2）算法描述 // 两数若干次加减结果为1的数学游戏 #include 算法设计与分析习题解答
算法分析大作业 寻找变位词
《算法设计与分析实用教程》习题参考解答
相关文档
- 算法设计与分析 期末试卷 A卷 完整含答案
- 2005.6算法设计与分析课程期末试卷
- 算法设计与分析期末试题考试版
- 《算法设计与分析》历年期末试题整理-含答案-
- 计算机算法设计与分析期末试题4套(含答案)
- 算法设计与分析课程期末试卷A卷自测
- 《算法设计与分析》历年期末试题整理_含答案_
- 算法设计分析期末考试试卷
- 算法设计期中试卷、平时作业参考解答
- 算法设计与分析期末试题考试册
- 武汉工程大学算法设计与分析期中试卷
- 算法设计期中试卷、平时作业参考解答
- 算法设计期中试卷
- 算法设计与分析期末试卷A卷学习资料
- 算法设计与分析期末试题_考试版
- 算法设计期中试卷
- 算法设计与分析期末试题
- 算法设计期中试卷、平时作业参考解答知识讲解
- 算法设计与分析期中考试试题
- 2015武汉大学《算法设计与分析》期中试卷