信息工程学院算法分析实践环节习题集（2011年）
序号项目名
称任务描述设计要求指导教
师
人
数
1． 1
2．二进制
位串的
压缩树
算法设
计与实
现第一步
输入：二进制位串，例如：0000010000001111
输出：如下图1所示的二进制压缩树
第二步
输入：二进制压缩树，如图1
输出：二进制路径码数组如图2
第三步：输入两个路径码数组，如图2，图3
输出：相与后的路径码数组，如图4
两个路径码数组相与就是求子码的过程，对于两个路径码x,y，如果x是y
的前缀，那么y是x的子码，比如：0是0101的前缀，因此0101是0的子码。
所以图2和图3相与后的路径码数组是图4.
用Java语言，或者C语言，推
荐用Java语言。
要求：读文件，读取文件中所
有的项，得到二进制串，然后
构造每个项的二进制串的压缩
树，并得到每个项的路径码。
刘全中 1
图1
图2
图3
图4
3．
4．简单数
据集跳
跃显露
模式挖
掘算法
设计与
实现跳跃显露模式是指在样本的一个类别上发生次数为0，在另外一个类别上发生
次数大于等于一个支持度计数阈值ξ的模式。
例如下表中数据，假定2
=
ξ。那么在类别为1D上的跳跃显露模式有：}
,
{e
b，
}
,
,
{e
d
c
利用Java语言或者C语言实现
给定数据集、给定支持度阈值
的所有跳跃显露模式。
刘全中 1
5．简单数
据集频
繁关闭
模式挖
掘算法
设计与
实现频繁模式是指在数据集中，出现的次数大于等于给定阈值ξ的项集。如下表所
示的数据集，假设2
=
ξ。频繁模式：}
{a，}
{b，}
{c, …….., }
,
,
,
{m
f
c
a等
对于模式p，如果不存在模式'p,'p
p?. 使得包含p的事物和包含'p的事物
相同。那么p就是一个关闭频繁模式。
利用Java语言或者C语言实现
给定数据集、给定支持度阈值
的所有的频繁关闭
刘全中 1
例如，假设2=ξ，},,,{m f c a 就是一个关闭频繁模式。
6．
利用分治思想设计循环赛日程表
假设有n=2k 个运动员要进行网球循环赛。设计一个满足一下要求的比赛日程表：
(1). 每个选手必须与其他n-1个选手各赛一次 (2). 每个选手一天只能赛一次 (3). 循环赛一共进行n-1天
利用Java 语言开发一个界面，
输入运动员的个数，输出比赛日程表。
对于输入运动员数目不满足n=2k 时，弹出信息提示用户。
刘全中
1
7．
工作分配问题
设有n 件工作分配给n 个人。将工作i 分配给第j 个人所需的费用为cij 。试设计一个算法，为每一个人都分配1 件不同的工作，并使总费用达到最小。设计一个算法，对于给定的工作费用，计算最佳工作分配方案，使总费用达到最小。
刘全中
1
8．无分隔
符字典
问题设)
(,...,
2
,1k
α
α
α
=
∑是n个互不相同的符号组成的符号集。
}
1,
|
{,...,
2
,1k
i
L i
k
k≤
≤
∑
∈
=β
β
β
β是∑中字符组成的长度为k的字符串全体。
k
L
S∈是k L的1个无分隔符字典是指对任意S
a
a
a k∈
...
,2
1和S
b
b k∈
...
,b2
1，
则
}
S
..b
b
b
a
,...,
b
...b
a
a,
b
...a
a
{a1-k
2
1
k
2
1
4
3
1
k
3
2φ
=
无分隔符字典问题要求对给定的n和∑以及正整数k,编程计算k L的最大无分
隔符字典。
设计一个算法，对于给定的正
整数n和k,编程计算k L的最大
无分隔符字典
数据输入：有文件input.txt给出
输入数据。文件第1行有2个
正整数n和k
结果输出：
将计算出的k L的最大无分隔
符字典的元素个数输出到文件
output.txt.
输入文件示例：
2 2
输出：
2.
刘全中 1
9．
10．放行路
线选择
算法的
设计与
实现设有n个城市(或者景点),今从某市出发遍历各城市，使之旅费最少(即找出一条
旅费最小的路径)
输入：各城市间的旅费表有输入文件提供
输出：旅费最少的一条路径及总费用。
利用Java, C实现所要求的算
法。
时间充分，设计一个图形化界
面，读入文件后把N个城市的
带权(花费)显示在界面上，经过
求解后把旅费最小的路径求出
来，并显示在界面上
刘全中 1
11．N色方
柱问题设有n个立方体，每个立方体的每一面用红、黄、蓝、绿等n种颜色之一染色。
要把这n个立方体叠成一个方形柱体，使得柱体的4个侧面的每一侧均有n种
不同的颜色。试设计一个回溯算法，计算出n个立方体的一种满足要求的叠置
方案。
编程任务：
对于给定的n个立方体以及每个立方体各面的颜色，计算出n个立方体的一种
叠置方案，使得柱体的4个侧面的每一侧均有n中不同的颜色。
数据输入：
由文件input.txt给出输入数据。第1行有1个正整数n，0 方体个数和颜色均为n。第2行是n个大写英文字母组成的字符串。该字符串 的第k()n k≤ ≤ 0个字符代表第k种颜色。接下来的n行中，每行有6个数， 表示立方体各面的颜色。立方体各面的编号如图1所示： 刘全中 1 T L F R B D 5 0 2 1 3 4 图1 图1中F表示前面，B表示背面，L表示左面，R表示右面，T表示顶面，D 表示底面。相应地，2表示前面，3表示背面，0表示侧面，1表示右面，5表示顶面，4表示底面。 例如，在示例输出文件中，第3行的6个数0, 2 , 1, 3, 0, 0分别表示第1个立方体的左面的颜色为R，右面的颜色为Ｂ，前面的颜色为Ｇ，背面的颜色为Ｙ，底面的颜色为Ｒ，顶面的颜色为Ｒ． 结果输出：将计算的ｎ个立方体的一种可行的叠置方案输出到文件output.txt。每行6个字符，表示立方体个面的颜色。如果不存在所要求的叠置方案，输出“No Solution” 输入文件示例输出文件示例Input.txt output.txt 4 RBGYRR RGBY YRBGRG 0 2 1 3 0 0 BGRBGY 3 0 2 1 0 1 GYYRBB 2 1 0 2 1 3 1 3 3 0 2 2 12．N个自 然数中r 个数组 合求解 设计与 实现找出n个自然数(1,2,3,…n)中r个数的组合。输入n,和r,输出所有的组合数。 n个数中r的组合，其中每r个数中，数不能相同。另外，任何两组组合的数， 所包含的数也不应相同。 例如：当n=5,r=3时，所有组合为： 5 4 3 ； 5 4 2 ；5 4 1 5 3 2 ； 4 3 2 ；4 2 1 3 2 1；total=10； 分别用穷举搜索法、递归法、 回溯法实现所要求的功能，并 比较三者的时间复杂度 刘全中 1 13．猜比赛 名次问 题的求 解算法 设计与 实现五个学生A、B、C、D、E 参加某一项比赛。甲、乙两人在猜测比赛的结果。 甲猜的名次顺序为A、B、C、D、E，结果没有猜中任何一个学生的名次，也 没有猜中任何一对相邻名次（所谓一对相邻名次，是指其中一对选手在名次上 邻接。例如１与２，或者２与３等）。 乙猜的名次顺序为D、A、E、C、B，结果猜中了两个学生的名次，并猜对了 两对学生名次是相邻的。问比赛结果如何？ 利用穷举法，设计算法对以上问题求解。 利用Java或者C 对所描述任务 进行求解。 刘全中 1 14．计算合 数问题 的求解一个整数n（n<=100）可以有多种划分，使其分划得一列整数之和为n.例如： 输入:n=4 输出文件result.out，格式内容为： 4 3 1 2 2 2 1 1 1 1 1 1 要求输入一个整数n，把划分序 列输出到文件中。 刘全中 1 15．查找数 字对问 题求解 算法的 设计与 实现输入N（2<=N<=100）个数字(在0到9之间),然后统计出这组数中相邻两数字 组成的链环数字对出现的次数。 输入:N=20 0 1 5 9 8 7 2 2 2 3 2 7 8 7 8 7 9 6 5 9 输出：(7,8)=2 （8,7）=3{指(7,8)、(8,7)数字对出现次数分别是2次、3次 设计一个GUI界面，能够接受 用户的输入，也能够从文件中 读取数据。在界面上输出所要 求的结果，并把结果存储到文 件中 刘全中 1 16．无向图 最小代 价生成 树算法 的实现（1）掌握最小代价生成树算法思想。（kruskal算法），并利用贪心的思想改 进该算法，降低其时间复杂性。 （2）设计一个有10个顶点的无向图，并用随机数产生其各边的代价。 （3）利用最小代价生成树算法思想，对其所产生的无向图，找出其最小代 价生成树。 （1）设计一个界面，显示产 生的无向图。 （2）实现最小代价生成树 算法。 （3）在输出界面，显示结 果。 王湘桃 1 17．分治法在一个划分成网络的操场上，n名士兵散乱地站在网格点上。网格点由整数坐 标（x,y）表示。士兵们可以沿网格边上下左右移动一步，但在同一时刻任意 网格点上只能有一名士兵。按照军官的命令，士兵们要整齐的列成一个纵队， 及排列成（x,y）,(x+1，y)…（x+n-1,y）。如何选择x和y的值才能使士兵们 以最小的总移动步数排成一列。 设计一个分治算法，输出方 案。 王湘桃 1 18．有向图 单源最 短路径 分支限 界算法 实现（1）掌握单源最短路径分支限界算法思想。 （2）设计一个至少有10个顶点的有向图，并用随机数产生其各边的权值。 （3）利用单源最短路径分支限界算法思想，对其所产生的有向图，找出从某 源点出发，到其它各顶点的最短路。 （1）设计一个界面，显示产生 的有向图。 （2）实现单源最短路径分支限 界算法。 （3）在输出界面，显示结果（在 有向图中，标记出从源到各顶 点的路径）。 王湘桃 1 19．回溯算 法实现部落卫队问题。原始部落中的居民们为了争夺有限的资源，经常发生冲突。 几乎每个居民都有他的仇敌，部落酋长为了组织一只保卫部落的队伍，希 望从部落的居民中选出最多居民入伍，并保证队伍中任何两个人都不是仇 敌。给定该部落中居民间的仇敌关系，编程计算组成部落卫队的最佳方案。 （1）实现回溯法的设计 思想。 王湘桃 1 20．装载问 题的分 支限界 算法实 现（1）有一批集装箱共n个，要装上两艘载重量分别为c1和c2的轮船，其中， 集装箱i 的重量Wi，且2 1 1 c c Wi n i + ≤ ∑ = 。装载问题要求确定是否有一个合理 的装载方案可将这n个集装箱装上这两艘轮船 （2）使用分支限界算法的思想，设计一个解决该问题的算法。 （1）用文件导入集装箱的重 量，和两艘船的载重量。 （2）实现分支限界算法的设计 思想。 （3）设计一个输出界面，输出 装载方案。 王湘桃 1 21．最大团 问题的 回溯算 法实现（1）给定无向图G=(V,E)。如果V U?，且对任意U v u∈ ,有E v u∈ ) , (， 则称U是G的完全子图。G的完全子图U是G的团，当且仅当U不 包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多 的团。 （2）使用回溯算法的思想，设计一个解决该问题的算法。 （1）设计一个界面，显示产生 的无向图。（至少有5个顶点） （2）实现回溯法的设计思想。 （3）在输出界面，显示结果。 王湘桃 1 22．最大团 问题的 分支限 界算法 实现（1）给定无向图G=(V,E)。如果V U?，且对任意U v u∈ ,有E v u∈ ) , (，则 称U是G的完全子图。G的完全子图U是G的团，当且仅当U不包含在G的 更大的完全子图中。G的最大团是指G中所含顶点数最多的团。 （2）使用分支限界算法的思想，设计一个解决该问题的算法。 （1）设计一个界面，显示产生 的无向图。（至少有5个顶点） （2）实现分支限界算法的设计 思想。 （3）在输出界面，显示结果。 王湘桃 1 23．最佳调 度问题 的回溯 算法实 现（1）有n个任务由k个可并行工作的机器完成。完成任务i需要的时间为 Ti。找出完成这n个任务的最佳调度，使得完成全部任务的时间最少。 （2）使用回溯算法的思想，设计一个解决该问题的算法。 （1）用文件导入每个任务所需 要的时间Ti。（至少10个任务） （2）实现回溯法 （3）设计一个输出界面，输出 调度方案。 王湘桃 1 24．最佳调 度问题 的分支 限界算 法实现（1）有n个任务由k个可并行工作的机器完成。完成任务i需要的时间为Ti。 找出完成这n个任务的最佳调度，使得完成全部任务的时间最少。 （2）使用分支限界算法的思想，设计一个解决该问题的算法。 （1）用文件导入每个任务所需 要的时间Ti。（至少10个任务） （2）实现分支限界算法的设计 思想。 （3）设计一个输出界面，输出 调度方案。 王湘桃 1 25．N后问 题的回 溯法算 法实现（1）在n n?格的棋盘上放置彼此不受攻击的n个皇后。任何2个皇后不放 在同一行或同一列或同一斜线上。 （2）使用回溯算法的思想，设计一个解决该问题的算法。 （1）设计一个棋盘界面。（至 少有10个皇后） （2）实现回溯算法的设计思 想。 （3）在界面上，显示所有方案。 王湘桃 1 26．N后问 题的优 先队列 分支限 界算法 实现（1）在n n?格的棋盘上放置彼此不受攻击的n个皇后。任何2个皇后不放在 同一行或同一列或同一斜线上。 （2）使用分支限界算法的思想，设计一个解决该问题的算法。 （1）设计一个棋盘界面。（至 少有10个皇后） （2）实现分支限界算法的设计 思想。 （3）在界面上，显示所有方案。 王湘桃 1 27．N后问 题的拉 斯维加 斯算法 实现（1）在n n 格的棋盘上放置彼此不受攻击的n个皇后。任何2个皇后不放在 同一行或同一列或同一斜线上。 （2）使用拉斯维加斯算法的思想，设计一个解决该问题的算法。 （1）设计一个棋盘界面。（至 少有10个皇后） （2）实现拉斯维加斯算法的设 计思想。 （3）在界面上，显示结果。 王湘桃 1 28．套汇问 题的贪 心算法 实现（1）利用货币汇兑率的差异将一个单位的某种货币转换为大于一个单位的 同种货币。 例如：1美元=0.7英镑，1英镑=9.5法郎， 1法郎=0.16美元。 1美元=0.7*9.5*0.16=1.064美元 （2）利用贪心算法的设计思想，设计一个解决该问题的算法。 （3）说明算法能产生最优解。 （1）用文件导入每种货币的汇 兑率。 （2）实现贪心算法的设计思 想。 （3）设计一个输出界面，输出 汇兑方案。 王湘桃 1 29．设计一 个寻找 众数的 算法并 实现（1）众数：在一个由元素组成的表中，出现次数最多的元素为众数。 （2）设计一个至少100个元素组成的表，用随机函数产生（1~9）之间的数 作为表中的元素值。 （3）设计一个找众数的算法，并完成代码。 （1）设计一个至少100个元素 组成的表，用随机函数产生 （1~9）之间的数作为表中的元 素值。存入文件中。 （2）设计一个输出界面，输出 计算结果。 王湘桃 1 30．最优购 货方案 设计与 实现（1）每种商品都有标价，当单独销售时，按单价出售，如果和其他商品组 合促销，则每种物品都降价销售。 （2）设计一个算法，为顾客提供一种省钱的购买方案并完成代码。算法能 产生最优解。 （1）设计一个界面。（输入需 要购买的货物及数量） （2）实现设计的算法思想。（先 对5种商品进行处理，需要设 计各种组合促销价。然后扩展 到n种货物） （3）在界面上，显示结果。 王湘桃 1 31．网球循 环赛日 程表设有n个运动员要进行网球循环赛。设计比赛日程表： （1）每个选手必须与其他n-1个选手赛一次； （2）每个选手一天只能赛一次； （3）当n是偶数时，循环赛进行n-1天；当n是奇数时，循环赛进行n天； （1）要求掌握分治法或者 多边形方法； （2）设计一个界面，显示产 生的日程表； （3）编程语言不限； 李梅1 32．泊松分 酒 描述: 给你两个容量分别为A升和B升的壶。你可以进行如下操作： 1.装满壶A或壶B。 2.将壶A或壶B里的酒全部倒干净。 3.将壶A里的酒倒入壶B，直到壶B被装满或壶A被倒空为止。或将壶B里的 酒倒入壶A，直到壶A被装满或壶B被倒空为止。 提示: 类似于布线问题，这里每次有 六种走法。 编程语言不限； 李梅1 编写一个程序，算出得到C升酒需要的最少的操作次数。 输入: 输入仅一行，三个整数A、B、C(用空格隔开)。这三个整数都在1到100 之间，而且C<=max(A,B)。 输出: 如果可以得到容量为C升的酒则输出最少的操作次数，如果不能则输出”impossible”。 输入样例 3 5 4 输出样例 6 33． n段 合并排 序算法在合并排序算法的分割步骤中，将数组[]1 :0- n a划分为??n个子数组，每个 子数组中有()n O个元素。然后递归地对分割后的子数组进行排序，最后将得 到的??n个排好序的子数组合并成所要求的排好序的数组[]1 :0- n a。 （1）要求掌握分治法； （2）设计一个界面，显示计 算结果； （3）编程语言不限； 李梅1 34．坦克大 战 描述： 我们小时候大都玩过坦克大战游戏，而且现在仍有很多人在玩。 现在我们讨论这个游戏的简化版。题目给出一个由空地、河流、钢墙、砖墙组 成的地图。你的任务就是在没有敌人干扰你的情况下尽快地拿到奖励(看附录图 7)。 你的坦克不能穿过河流或墙，但是可以通过射击摧毁砖墙。当你轰击砖墙时， 它就会变成空地。但是你如果攻击钢墙，不会对它造成任何损害。在你所花费 的每一分钟里，你可以选择往四邻域的空地移动一步，你也可以选择不移动， 往四个方向之一开一炮，炮弹将会朝一个方向一直飞去直到轰击到墙为止。如 果炮弹打到砖墙，砖墙就会消失，变成空地。现在我们给出地图，以及你的坦 克的位置和目标位置，请你计算最短需要多长时间(以分钟计)才能到达目标位 置？ 输入： 输入的第一行包含两个整数M和N(2<=M,N<=300)代表地图的规模。第2行到 第M+1行为N个大写字母组成的字符串，这些字母为’Y’(你的坦克的位置)、’ T’(目标位置)、’S’(钢墙)、’B’(砖墙)、’R’(河流)、’E’(空地)之一。’ Y’和’E’仅出现一次。 输出： 输出仅一行，如果你可以到达目标位置，输出最短时间，如果不可到达，输出 -1。 （1）编程语言不限；李梅1 输入样例： 3 4 YBEB EERE SSTE 输出样例 8 35．集合划 分问题给定正整数n，计算出n个元素的集合{1,2，3……,n}可以划分为多少个不同 的非空子集。 （1）要求掌握分治法； （2）设计一个界面，显示计 算结果； （3）编程语言不限； 李梅1 36．漂亮打 印给定由n个英文单词组成的一段文章，每个单词的长度（字符个数）依序为 1 l， 2 l，……， n l。要在一台打印机上将这段文章“漂亮”地打印出来。打印机每 行最多可打印M个字符。这里所说的“漂亮”的定义如下：在打印机所打印的 每一行中，行首和行尾可不留空格；行中每个单词之间留一个空格；如果在一 行中打印从单词i到单词j的字符，则按打印规则，应在一行中恰好打印 （1）设计一个界面。 （2）实现动态规划算法的设计 思想。 （3）在界面上，显示最佳方案。 李梅1 网络教育课程考试复习题及参考答案算法分析与设计一、名词解释：1.算法 2.程序 3.递归函数 4.子问题的重叠性质 5.队列式分支限界法 6.多机调度问题7.最小生成树二、简答题： 1.备忘录方法和动态规划算法相 比有何异同？简述之。 2.简述回溯法解题的主要步骤。 3.简述动态规划算法求解的基本要素。 4.简述回溯法的基本思想。 5.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。 6.简要分析分支限界法与回溯法的异同。7.简述算法复杂性的概念，算法复杂性度量主要指哪两个方面？8.贪心算法求解的问题主要具有哪些性质？简述之。9.分治法的基本思想是什么？合并排序的基本思想是什么？请分别简述之。10.简述分析贪心算法与动态规划 算法的异同。三、算法编写及算法应用分析题： 1.已知有3个物品： (w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10),背包的容积M=20，根据0-1背包动态规划的递推式求出最优解。 2.按要求完成以下关于排序和查找的问题。①对数组A={15，29，135，18，32，1，27，25，5}，用快速排序方法将其排成递减序。②请描述递减数组进行二分搜索的基本思想，并给出非递归算法。③给出上述算法的递归算法。④使用上述算法对①所得到的结果搜索如下元素，并给出搜索过程：18，31，135。已知，=1，2，3，4，5，6，=5，=10，=3，=12，=5，=50，=6，kijr*r1234567ii1求矩阵链积A×A×A×A×A×A的最佳求积顺序（要求给出计算步骤）。1234564.根据分枝限界算法基本过程,求解0-1背包问题。已知n=3,M=20，(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。 5.试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少，请写出该算法。6.试用动态规划算法实现下列问题：设A和B是两个字符串。我们要用最少的字符操作，将字符串A转换为字符串B，这里所说的字符操作包括：①删除一个字符。②插入一个字符。③将一个字符改为另一个字符。请写出该算法。7.对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。be2g212ad323182cf2h 8.试写出用分治法对数组A[n]实现快速排序的算法。9.有n个活动争用一个活动室。已知活动i占用的时间区域为[s，f ]，活动i,j相容的条件是：sj≥f ii，问题的解表示为(x| x =1，2…，n,)，x表示顺序为i的活动编号活动，求一个相容的活动子集，iiii且安排的活动数目最多。xxx10.设、、是一个三角形的三条边，而且x+x+x=14。请问有多少种不同的三角形？给出解答过程。12312311. 算法设计与分析实验报告 学院信息科学与技术学院 专业班级软件工程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 。 四、实验源代码 一。选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ B ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、在下列算法中有时找不到问题解的是（ B ）。 A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 5. 回溯法解旅行售货员问题时的解空间树是（ B ）。 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、下列随机算法中运行时有时候成功有时候失败的是（C ） A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法 11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13.备忘录方法是那种算法的变形。（ B ） 经典图像边缘检测(微分法思想)——Sobel算子 2008-05-15 15:29Sobel于1970年提出了Sobel算子，与Prewitt算子相比较，Sobel算子对检测点的上下左右进一步加权。其加权模板如下： 经典图像边缘检测(微分法思想)——Roberts交叉算子 2008-05-14 17:16 如果我们沿如下图方向角度求其交叉方向的偏导数，则得到Roberts于1963年提出的交叉算子边缘检测方法。该方法最大优点是计算量小，速度快。但该方法由于是采用偶数模板，如下图所示，所求的(x,y)点处梯度幅度值，其实是图中交叉点处的值，从而导致在图像(x,y)点所求的梯度幅度值偏移了半个像素（见下图）。 上述偶数模板使得提取的点（x,y）梯度幅度值有半个像素的错位。为了解决这个定位偏移问题，目前一般是采用奇数模板。 奇数模板： 在图像处理中，一般都是取奇数模板来求其梯度幅度值，即：以某一点（x,y）为中心，取其两边相邻点来构建导数的近似公式： 这样就保证了在图像空间点(x,y)所求的梯度幅度值定位在梯度幅度值空间对应的(x,y)点上(如下图所示)。 前面我们讲过，判断某一点的梯度幅度值是否是边缘点，需要判断它是否大于设定的阈值。所以，只要我们设定阈值时考虑到加权系数产生的影响便可解决，偏导数值的倍数不是一个问题。 经典图像边缘检测(微分法思想)——Prewitt算子 2008-05-15 11:29 Prewitt算子 在一个较大区域中，用两点的偏导数值来求梯度幅度值，受噪声干扰很大。若对两个点的各自一定领域内的灰度值求和，并根据两个灰度值和的差来计算x,y的偏导数，则会在很 《算法分析与设计》作业( 一) 本课程作业由两部分组成。第一部分为”客观题部分”, 由 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、快速排序算法和线性时间选择算法的随机化版本是: 算法设计与分析 学院：计算机科学与技术 学号：129074106 姓名：张淼淼 2014 11 14 1、 当问题规模100 N 时，快速排序和插入排序各需多少时间？写清机器配置，列出五种 快速排序所需时间(ms) 插入排序所需时间（ms ） 两者相差多少 N=100 0.00600 0.019000 -0.013000 N=1000 0.074000 0.724000 -0.650000 N=10000 0.032000 64.657000 -64.625000 N=100000 13.300000 50.900000 -37.600000 N=1000000 53.500000 117.700000 -64.200000 Window 7 32位 Cpu ：Inter(R) Core(TM) i3-2120 cpu@3.30GHz AMD Radeon HD 6450 Graphics 程序： #include int b[1000000]; void QuickSort(int low ,int high) { long i,j; int x; i=low; j=high; x=a[i]; while(i 边缘检测原理的论述 摘要 数字图像处理技术是信息科学中近几十年来发展最为迅速的学科之一。图像边缘是图像最基本的一种特征，边缘在图像的分析中起着重要的作用。边缘作为图像的一种基本特征，在图像识别、图像分割、图像增强以及图像压缩等的领域中有较为广泛的应用，其目的就是精确定位边缘，同时更好地抑制噪声。目前，数字图像处理技术被广泛应用于航空航天、通信、医学及工业生产等领域中。图像边缘提取的手段多种多样，本文主要通过MATLAB语言编程分别用不同的算子例如Roberts算子、Prewitt算子、Sobel算子、Kirsch 算子、Laplacian算子、Log算子和Canny算子等来实现静态图像的边缘检测，并且和检测加入高斯噪声的图像进行对比。阐述了不同算子在进行图像边缘提取的特点，并在此基础上提出利用小波变换来实现静态图像的边缘检测。 【关键字】图像边缘数字图像边缘检测小波变换 背景 图像处理就是对图像信息加工以满足人的视觉心理或应用需求的方法。图像处理方法有光学方法和电子学方法。从20世纪60年 代起随着电子计算机和计算技术的不断提高和普及，数字图像处理进入了高速发展时期，而数字图像处理就是利用数字计算机或其它的硬件设备对图像信息转换而得到的电信号进行某些数学处理以提高图像的实用性。 计算机进行图像处理一般有两个目的：(1)产生更适合人观察和识别的图像。(2)希望能由计算机自动识别和理解图像。数字图像的边缘检测是图像分割、目标区域的识别、区域形状提取等图像分析领域的重要基础，图像处理和分析的第一步往往就是边缘检测。 边缘是图象最基本的特征.边缘检测在计算机视觉、图象分析等应用中起着重要的作用,是图象分析与识别的重要环节,这是因为子图象的边缘包含了用于识别的有用信息.所以边缘检测是图像分析和模式识别的主要特征提取手段。 所谓边缘是指其周围像素灰度后阶变化或屋顶状变化的那些像素的集合,它存在于目标与背景、目标与目标、区域与区域,基元与基元之间。因此它是图象分割所依赖的重要的特征,也是纹理特征的重要信息源和形状特征的基础;而图象的纹理形状特征的提取又常常依赖于图象分割。图象的边缘提取也是图象匹配的基础,因为它是位置的标志,对灰度的变化不敏感,它可作为匹配的特征点。 图象的其他特征都是由边缘和区域这些基本特征推导出来 的.边缘具有方向和幅度两个特征.沿边缘走向,像素值变化比较平缓;而垂直与边缘走向,则像素值变化比较剧烈.而这种剧烈可能呈 《算法分析与设计》作业（一） 本课程作业由两部分组成。第一部分为“客观题部分”，由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、快速排序算法和线性时间选择算法的随机化版本是：（ A ） A、舍伍德算法 B、蒙特卡罗算法 C、拉斯维加斯算法 D、数值随机化算法 主观题部分： 二、写出下列程序的答案（每题2.5分，共2题） 1、请写出批处理作业调度的回溯算法。 #include 算法设计与分析 实 验 报 告 班级： 姓名： 学号： (备注：共给出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.参考文献：列出在撰写过程中所需要用到的参考文献。 边缘检测对于灰度级间断的检测是最为普遍的检测方法。 当我们沿着剖面线从左到右经过时，在进入和离开斜面的变化点，一阶导数为正。在灰度级不变的区域一阶导数为0.在边缘与黑色一边相关的跃变点二阶导数为正，在边缘与亮色一边相关的跃变点二阶导数为负，沿着斜坡和灰度为常数的区域为0. 结论：一阶导数可以用于检测图像中的一个点是否是边缘的点（也就是判断一个点是否在斜坡上）。同样，二阶导数的符号可以用于判断一个边缘像素是在边缘亮的一边还是暗的一边。暗的为正，亮的为负。 二阶导数的两条附加性质（1）对图像中的每条边缘二阶导数生成两个值(一个不希望得到的特点)；（2）一条连接二阶导数正极值和负极值的虚构直线将在边缘中点附近穿过零点。二阶导数的这个过零点的性质对于确定粗边线的中心非常有用。 浅黑色和白色的线是如图所描述的正和负的分量。 灰色描绘了由于比例缩放而生成的零点。 结论：为了对有意义的边缘点进行分类，与这个点相联系的灰度级变换必须比在这一点的背景上的变换更为有效。由于我们用局部计算进行处理，决定一个值是否有效的选择方法就是使用门限。图像中的一阶导数用梯度计算，二阶导数使用拉普拉斯算子得到。 一幅数字图像的一阶导数是基于各种二维梯度的近似值。 边缘在（x,y）处的方向与此点的梯度向量的方向垂直。 所有模版中的系数总和为零，表示正如导数算子中所预示的，此时在灰度级不变的区域，模版响应为0. 拉普拉斯算子一般不以其原始形式用于边缘检测是由于存在下列原因：作为一个二阶导数，拉普拉斯算子对噪声具有无法接受的敏感性；拉普拉斯算子的幅值产生双边缘，这是复杂的分割不希望有的结果；最后，拉普拉斯算子不能检测边缘的方向。 拉普拉斯算子在分割中所起的作用：（1）利用它的零交叉的性质进行边缘定位（2）确定一个像素是在一条边缘暗的一边还是亮的一边。 函数edge（）是专门提取图像边缘的，输入原图像，输出是二值图像、边缘为1，其它像素为0。B=edge(A,F,T) A为输入灰度图像，F是算子，T是阈值，决定检测边缘的强度，T值小检出的边缘多，T值大检测出的边缘少。 图像病灶边缘检测。分别选用Roberts算子、Prewitt算子、Sobel算子、Laplacian算子和Canny算子对图像进行边缘提取发现病灶。 使用数学方法提取图像像元中具有亮度值（灰度）空间方向梯度大的边、线特征的过程。 《算法分析与设计》作业参考答案 作业一 一、名词解释： 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] 《计算机算法设计与分析》实验指导书（第一版） 前言 计算机算法分析与设计是面向设计的，它是计算机科学的核心。无论是计算机系统、系统软件和解决计算机的各种应用问题都可归结为算法的设计。通过本课程的学习，使学生掌握计算机领域中许多常用的非数值的算法描述：分治法、贪心法、动态规划、回溯法、分枝限界等算法，并掌握算法分析的方法，从而把学生的分析问题和解决问题能力提高到理论的高度。 前期课程为程序设计语言、数据结构、高等数学，即学生应该具备一门高级语言程序设计编程基础，学习基本的数据结构知识，还要求学生掌握较好的数学基础。 开发环境不限，本书采用C/C++语言的集成开发环境等。 实验完成后书写实验报告，包含实验问题、基本思想、关键算法流程图、测试数据及运行结果（截图）、调试心得和源程序。 总实验学时为16学时。 目录 预备实验验证算法的方法 (4) 实验目的： (4) 实验课时： (4) 实验原理： (4) 实验题目： (6) 基本题： (6) 提高题： (6) 实验一递归与分治 (7) 实验目的： (7) 实验课时： (7) 实验原理： (7) 实验题目： (7) 基本题： (7) 提高题： (8) 思考问题： (8) 实验二动态规划算法 (9) 实验目的： (9) 实验课时： (9) 实验原理： (9) 实验题目： (9) 基本题： (9) 提高题： (10) 思考问题： (10) 实验三贪心选择算法 (11) 实验目的： (11) 实验课时： (11) 实验原理： (11) 实验题目： (11) 基本题： (11) 提高题： (12) 思考问题： (12) 实验四回溯算法 (13) 实验目的： (13) 实验课时： (13) 实验原理： (13) 实验题目： (14) 基本题： (14) 提高题： (14) 思考问题： (14) Program算法设计与分析基础中文版答案 习题 5..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立. Hint: 根据除法的定义不难证明: 如果d整除u和v, 那么d一定能整除u±v; 如果d整除u,那么d也能够整除u的任何整数倍ku. 对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。 数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。故gcd(m,n)=gcd(n,r) 6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次? Hint: 对于任何形如0<=m 设sqrt(x)是求平方根的函数) 算法Quadratic(a,b,c) 描述将十进制整数表达为二进制整数的标准算法 a.用文字描述 b.用伪代码描述 解答： a.将十进制整数转换为二进制整数的算法 输入：一个正整数n 输出：正整数n相应的二进制数 第一步：用n除以2，余数赋给Ki(i=0,1,2...)，商赋给n 第二步：如果n=0，则到第三步，否则重复第一步 第三步：将Ki按照i从高到低的顺序输出 b.伪代码 算法 DectoBin(n) .n]中 i=1 while n!=0 do { Bin[i]=n%2; n=(int)n/2; i++; } while i!=0 do{ print Bin[i]; i--; } 9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略)对这个算法做尽可能多的改进. 算法 MinDistance(A[0..n-1]) 任务书 主要分析几种应用于数字图像处理中的边缘检测算子,根据它们在实践中的应用结果进行研究,主要包括:Robert 边缘算子、Prewitt 边缘算子、Sobel 边缘算子、Kirsch 边缘算子以及Laplacian 算子等对图像及噪声图像的边缘检测,根据实验处理结果讨论了几种检测方法的优劣. 关键词：数字图像处理;边缘检测;算子 图像的边缘是图像的重要特征之一, 数字图像的边缘检测是图像分割、目标区域识别、区域形状提取等图像分析领域十分重要的基础, 其目的是精确定位边缘, 同时较好地抑制噪声, 因此边缘检测是机器视觉系统中必不可少的重要环节。然而, 由于实际图像中的边缘是多种边缘类型的组合, 再加上外界环境噪声的干扰, 边缘检测又是数字图像处理中的一个难题。 目录 第一章边缘的概念 (3) 第二章边缘检测 (4) 第三章边缘检测算子的应用 (8) 第四章边缘检测方法性能比较 (12) 参考文献料 (15) 第1章：边缘检测 1．1 边缘的介绍 图像边缘是图像最基本的特征，边缘在图像分析中起着重要的作用。所谓边缘是指图像局部特性的不连续性。灰度或结构等信息的突变处称为边缘，例如：灰度级的突变，颜色的突变，纹理结构的突变等。边缘是一个区域的结束，也是另一个区域的开始，利用该特征可以分割图像。 边缘(edge)是指图像局部强度变化最显著的部分．边缘主要存在于目标与目标、目标与背景、区域与区域(包括不同色彩)之间，是图像分割、纹理特征和形状特征等图像分析的重要基础．图像分析和理解的第一步常常是边缘检测(edge detection)．由于边缘检测十分重要，因此成为机器视觉研究领域最活跃的课题之一．本章主要讨论边缘检测和定位的基本概念，并使用几种常用的边缘检测器来说明边缘检测的基本问题． 在讨论边缘算子之前，首先给出一些术语的定义： 边缘点：图像中具有坐标],[j i 且处在强度显著变化的位置上的点． 边缘段：对应于边缘点坐标],[j i 及其方位 ，边缘的方位可能是梯度角． 边缘检测器：从图像中抽取边缘(边缘点和边缘段)集合的算法． 轮廓：边缘列表，或是一条表示边缘列表的拟合曲线． 边缘连接：从无序边缘表形成有序边缘表的过程．习惯上边缘的表示采用顺时针方向序． 边缘跟踪：一个用来确定轮廊的图像（指滤波后的图像）搜索过程． 边缘点的坐标可以是边缘位置像素点的行、列整数标号，也可以在子像素分辨率水平上表示．边缘坐标可以在原始图像坐标系上表示，但大多数情况下是在边缘检测滤波器的输出图像的坐标系上表示，因为滤波过程可能导致图像坐标平移或缩放．边缘段可以用像素点尺寸大小的小线段定义，或用具有方位属性的一个点定义．请注意，在实际中，边缘点和边缘段都被称为边缘． 边缘连接和边缘跟踪之间的区别在于：边缘连接是把边缘检测器产生的无序边缘集作为输入，输出一个有序边缘集；边缘跟踪则是将一幅图像作为输入，输出一个有序边缘集．另外，边缘检测使用局部信息来决定边缘，而边缘跟踪使用整个图像信息来决定一个像素点是不是边缘． 1．2 边缘检测算子 边缘检测是图像特征提取的重要技术之一, 边缘常常意味着一个区域的终结和另一个区域的开始. 图像的边缘包含了物体形状的重要信息,它不仅在分析图像时大幅度地减少了要处理的信息量,而且还保护了目标的边界结构. 因此,边缘检测可以看做是处理许多复杂问题的关键. 边缘检测的实质是采用某种算法来提取出图像中对对象与背景间的交界线。图像灰度的变化情况可以用图像灰度分布的梯度来反映，因此可以用局部图像微分技术来获取边缘检测算子。经典的 边缘检测方法是对原始图像中的像素的某个邻域来构造边缘检测算子。以下是对几种经典的边缘检测算子进行理论分析，并对各自的性能特点做出比较和评价。 课程大作业实验报告 图像边缘检测方法的比较 课程名称：数字图像处理 指导教师 报告提交日期2010年05月项目答辩日期2010年05月 目录 1、项目要求 (3) 1.1、要求一 (3) 1.2、要求二 (3) 1.3、要求三 (3) 2、项目开发的环境 (3) 3、边缘检测的系统分析 (4) 3.1、系统模块分析 (4) 3.2、系统的关键问题以及解决方法 (4) 4、系统设计 (5) 4.1程序的流程图以及说明 (5) 4、2程序的主要功能模块 (7) 4.2.1 水平梯度算子模块 (7) 4.2.2 垂直梯度算子模块 (8) 4.2.3 水平垂直梯度算子模块 (8) 4.2.4 罗伯茨算法模块 (9) 4.2.5 Sobel模块 (10) 4.2.6 Prewitt模块 (11) 4.2.7 拉普拉斯边缘检测模块 (11) 4.2.8 基于Kirsch算子的快速边缘检测模块 (11) 4.2.9 Robinson算法模块 (12) 4.2.10 高斯LOG模块 (13) 4.2.11 梯度幅值自适应 (14) 5.实验结果与分析 (14) 5.1 实验结果和分析 (15) 5.2 项目的创新之处 (19) 5.3 存在问题及改进设想 (19) 6.心得体会 (20) 6.1 系统开发的体会 (20) 6.2 对本门课程的改进意见或建议 (20) 1 项目要求 1.1 对以下方法编程实现： （1）水平梯度算子； （2）垂直梯度算子； （3）水平垂直梯度算子； （4）罗伯茨梯度算子； （5）拉普拉斯算子； （6）柯西算子； （7）Prewitt算子； （8）Sobel算子； （9）拓展：其他的边缘检测算法 1.2 界面整合为菜单形式，在程序的主界面上显示每种方法的处理时间（利用C语言的 时间函数，计算出处理时间）。 1.3 有好的PPT和电子文档。 2 项目开发的环境 硬件部分：PC机 软件部分：CVI5.0、IMAQ vision（Imaq_CVI.fp、Imaq_CVI.h、Imaq_CVI.lib） 使用语言：C语言 《算法分析与设计》 学习中心： 专业： 学号： 姓名： 作业练习二 一、名词解释 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 }。 实验一、归并排序及各种排序算法性能比较 一、实验实习目的及要求 了解归并排序等各种排序算法，并能独立在计算机上实现，同时并能够计算它们的时间复杂度，并用计算机来验证。 二、实验实习设备（环境）及要求（软硬件条件） 计算机eclipse软件，执行环境JavaSE-1.8. 三、实验实习项目、内容与步骤(注意是主要关键步骤，适当文字+代码+截图说明) 项目：对10 4 6 3 8 2 5 7进行从小到大排序，采用几种排序方法，并统计这几种方法的运行时间，与归并排序比较。 内容及步骤： (1)归并排序：将序列每次分成两组，再进行合并，直到递归完成； 1、递归调用mergeSort对数组排序 2、merge将两个有序数组合并为一个有序数组 3、主函数调用mergeSort对数组排序 4、统计时间 (2) 选择排序：每次选择一个当前最小的并和当前的相对的第一个元素交换，直到最后 只有一个元素时结束；也可选择当前最大的并与当前的相对的最后一个 元素交换，直到最后只有一个元素时结束。 1、数组长度为n，需要选择n-1次；每次选择完成后，将数组中的最大值与最后一 个元素互换，调用java.util包中Arrays类。 2、主函数调用ChooseSort对数组排序。 3、统计运行时间。 (3)插入排序：从第二个元素开始，每次插入一个到当前有序序列中，使得有序，当 所有的元素插入完毕时，就排好序了； 1、从第二个元素开始，与之前序列比较，插入到合适的位置。 2、主函数调用sort对数组排序。 3、统计运行时间 (4) 快速排序：每次选择一个中间元素，并进行交换，使得中间元素的左边比它小，右 边比它大，然后对左右两边进行递归； 1、选取一个基准位，从右边向左边看，找比基准位小的元素，再从左边向右边看， 找比基准位大的元素，若两者均存在则交换；若两者相遇，则相遇元素与基准位元素交换，然后递归排序左右半数组。 经典边缘检测算子比较 张丽 南京信息工程大学信息与计算科学系，南京210044 摘要：图像边缘检测技术是图像分割、目标识别、区域形态提取等图像分析领域中十分重要的基础。本文简要介绍各种经典图像边缘检测算子的基本原理，用Matlab仿真实验结果表明各种算子的特点及对噪声的敏感度，为学习和寻找更好的边缘检测方法提供参考价值。 关键字：图像处理；边缘检测；算子；比较 引言 图像的边缘时图像最基本的特征之一。所谓边缘（或边沿）是指周围像素灰度有阶跃性变化或“屋顶”变化的那些像素的集合。边缘广泛存在于物体与背景之间、物体与物体之间、基元与基元之间，因此它是图像分割依赖的重要特征。图像边缘对图像识别和计算机分析十分有用，边缘能勾划出目标物体，使观察者一目了然；边缘蕴含了丰富的内在信息（如方向、阶跃性质、形状等）。从本质上说，图像边缘是图像局部特性不连续性（灰度突变、颜色突变、纹理结构突变等）的反应，它标志着一个区域的终结和另一个区域的开始。 边缘检测技术是所有基于边界分割的图像分析方法的第一步，首先检测出图像局部特性的不连续性，再将它们连成边界，这些边界把图像分成不同的区域，检测出边缘的图像就可以进行特征提取和形状分析。为了得到较好的边缘效果，现在已经有了很多的边缘检测算法以及一些边缘检测算子的改进算法。但各算子有自己的优缺点和适用领域。本文着重对一些经典边缘检测算子进行理论分析、实际验证并对各自性能特点做出比较和评价，以便实际应用中更好地发挥其长处，为新方法的研究提供衡量尺度和改进依据。 一各种经典边缘检测算子原理简介 图像的边缘对人的视觉具有重要的意义，一般而言，当人们看一个有边缘的物体时，首先感觉到的便是边缘。灰度或结构等信息的突变处称为边缘。边缘是一个区域的结束，也是另一个区域的开始，利用该特征可以分割图像。需要指出的是，检测出的边缘并不等同于实际目标的真实边缘。由于图像数据时二维的，而实际物体是三维的，从三维到二维的投影必然会造成信息的丢失，再加上成像过程中的光照不均和噪声等因素的影响，使得有边缘的地算法分析与设计复习题及参考答案
算法设计与分析(作业三)
算法设计与分析复习题目及答案
经典图像边缘检测
算法分析与设计作业及参考答案样本
算法分析与设计实验报告
边缘检测原理(内含三种算法)
最新算法分析与设计作业(一)及参考答案讲课讲稿
计算机算法设计与分析
边缘检测
《算法分析与设计》作业参考答案
《算法分析与设计》实验指导书
算法设计与分析基础课后习题答案
数字图像边缘检测的研究与实现
图像边缘检测方法的比较
算法分析与设计(线下作业二)
算法分析与设计实验报告
经典边缘检测算子对比
相关主题
文本预览