《算法的设计与描述》教学设计

《算法的设计与描述》教学设计（精选9篇）

篇1：《算法的设计与描述》教学设计

《算法的设计与描述》教学设计

一、教材内容、学情分析（1）教材分析

本节内容为教科版算法与程序设计第一章第二节，通过1.1 节的学习，学生已经了解了计算机解决问题的基本过程，并知道算法是程序设计的灵魂，只要算法正确，就可以用任何一种语言编写程序，再加之本节的学习，更加加深的学生对算法的了解。为后续章节学习程序设计、算法的程序实现打下一定的基础。（2）学情分析

此阶段学生为高二第一学期的学生，在高一的基础上已经对计算机的基本操作及信息的获取处理方法有了一定的掌握。数学方面也已经具备了函数、数列等方面的知识，能够解决计算机中遇到的一些问题。但我校学生很大一部分都是农村学生，基础差，知识的掌握程度差，所以要更加注重基础，课堂用例不能太难，注重循序渐进的教学，分层教学。

二、教学目标

知识与技能：进一步理解什么是算法，知道算法的多样性；能够对设计的算法做简单的评价；学会利用自然语言、流程图和伪代码来描述算法。

过程与方法：培养学生用算法描述问题的能力和正确解决问题的过程。

情感态度价值观：使学生养成遇到问题，找出算法，分析算法的意识。培养学生的高阶思维能力，如综合、评价、分析、思辨。

三、教学重难点

重点：用自然语言流程图伪代码描述算法

难点：用流程图描述算法

四、教学方法及策略

本节课主要通过大量实例及一题多解的方法，帮助学生理解学习，对比式学习，问题引导，先实例展示，后讲解，后总结的方法，适合学生的学习认知顺序，是知识点之间的衔接浑然天成。由易到难的顺序，不至于使学生产生思维跨度。知识点纲要、图文并茂、表格的形式使知识点形象直观容易理解。适当的讨论交流学习，让同学们很好的纠正自己的错误。以上各种方法让学生学会如何利用自然语言、流程图和伪代码来描述算法。引课实例为“农夫过河”的趣味游戏，它一方面可以激发学生的学习兴趣，另一方面可使学生清楚算法的概念，学会利用自然语言描述算法的方法；第一个实践活动“找出1+2+3+……100的方法”，让同学们对不同的算法进行比较，能对不同的算法做出评价，感受算法的多样性与复杂性；第二个实践活动“用自然语言描述求解ax+b=0的过程”，进一步巩固自然语言的描述方法，为后面的学习用流程图描述做铺垫；流程图学习阶段，与自然语言描述进行对比，贯之以实践三“读解一元二次方程流程图，填空”，典型的数学问题，使学生掌握用流程图描述算法的方法；伪代码学习阶段，采用循序渐进的方法，引导学生学习，冠之以实例帮助学生理解。最后对知识点进行小结，完成课后实践

五、教学过程 1.课堂引入

老师：由“农夫过河”游戏引入：算法的概念，算法是程序设计的灵魂，找到合适的算法是程序设计的前提 , 算法的设计分为两个内容：一是寻找一种方法；二是描述实现这个方法的步骤，我们这节课的重点是学习如何描述算法。算法特征的讲解。

学生：玩趣味游戏，找出解决农夫过河问题的方法和步骤，理解算法的概念，特征，地位。

设计意图：通过游戏，激发学生的学习兴趣，顺理成章的引入对本节内容的学习。适当的扩展算法的特征，帮助学生理解。2.学生自主讨论完成实践活动一

学生讨论：学生找出求解“1+2+3+4……+100”的不同算法，看看哪种算法的效率高，体会算法的多样性与复杂性。

老师总结结论。3.用自然语言描述算法

老师讲授：

（1）自然语言 —— 人们日常生活中使用的语言。

（2）自然语言的特点：通俗易懂，缺乏直观性，不简洁，且易产生歧义。如很多同学的描述语句和说法相差较大。使用自然语言的注意事项：描述要尽可能精确，详尽。

学生活动： 实践活动二：用自然语言描述求解ax+b=0的过程，巩固所学，为学习流程图做一定的铺垫。4.流程图描述

老师活动：

用自然语言描述算法比较容易接受，但叙述冗长，容易产生 “ 歧义 ”。下面我们再来学习另外一种最常见的算法描述方式——流程图。

（1）给学生展示求解方程ax+b=0的流程，对比自然语言描述，产生共鸣。（2）结合具体实例讲解组成流程图的各种元素，之后列出组成流程图基本元素。（3）总结流程图优缺点：用流程图描述算法直观易懂、逻辑关系清晰，不容易产生歧义。

（4）结合求解ax2+bx+c=0的流程图，巩固讲解流程图相关知识。

学生活动：

（1）看解ax+b=0的自然语言和流程图，感受流程图描述的优势，完成对比表格。（2）实践活动三：读解一元二次方程流程图，填空。

设计意图：由简到难，逐步引导，图文并茂，帮助理解，对比学习，产生共鸣。

5.用伪代码描述算法

老师活动：

（1）伪代码表示举例讲解

（2）两个实例讲解

①判断某个数是否偶数

②伪代码描述求解ax+b=0的过程（3）总结式讲解

伪代码(Pseudocode)是介于自然语言和计算机程序设计语言之间的一种算法描述。它也是专业软件开发人员描述算法的一种常用方法。没有严格的语法限制，书写格式也比较自由，描述的算法简单、易懂，容易修改，且容易转化为程序语言代码。

学生活动：听老师讲解，在老师的引导下，完成对两个实例的讲解，对知识点的掌握 6.课堂总结

（1）算法是指解决问题的方法和思路。（2）算法的特征（2）描述算法的形式有多种，常用的有自然语言、流程图和伪代码。展示同一个问题的三种描述方法，学生对比感受，起到对知识点升华的作用。（3）好的算法需要我们分析、比较、挑选。

六、教学反思

通过本节的教学好的地方在于：以游戏的方式引课，调动学生的学习兴趣。整堂课贯穿着大量的实例帮助学生学习巩固，实例都是由易到难，老师适当引导，帮助各类学生理解，充分的考虑到学生的学情。在讲解三类方法时，始终都是对比式学习，并没有把某个知识点孤立起来。适当的给学生扩展了一些知识点。整堂课程脉路比较清晰。再者就是课堂气氛比较活跃。

不足之处就是：课堂有些地方语言不够精炼。学生活动不是很充分，学生活动的设计不是很到位，课堂上老师与学生的互动较少。学生与学生之间的互动交流也较少，由于受到学生基础的限制，如打字，有部分学生没有很好的完成实践活动。有些知识点没有讲透。由于实践贯穿在课堂，学生做完后只是做了简单的评价，没有详细的评价，课后也没有系统的评价，没能给学生纠正出常见的错误，实践活动的重难点也没有突出出来，没有把知识点做出全方位的诠释。

优点是可以看到的，但存在的缺点也很多，希望在以后的教学中自己能够多多锻炼，慢慢的改掉自己的不足的地方，多多向有经验的前辈请教，希望自己的课能够越上越好。

篇2：《算法的设计与描述》教学设计

教学目标：

1.进一步理解什么是；算法，知道算法的多样性

2.能够对设计的算法做简装的评价

3.学会利用自然语言、流程图和伪代码来描述算法

教学内容

1.了解什么是算法及其特征 2.学习三种描述算法语言

教学重点:通过例子设计算法

教学难点:三种描述算法语言的使用

课时数：1课时

正课讲解

一、算法是“灵魂”

1.算法存在于人们生活中，如：上街购物、顾客付款、营业员（主）找银等。

2.“韩信点兵问题”有不同的求解过程，就有不同的算法。

有N个人，除以3，5，7，分别余2，3，2，求N。

3.算法——解决问题的方法和步骤。

算法是尼克劳斯.沃斯（N.Writh）提出的，他指出：算法+数据结构=程序。

（即算法不能单独构成程序，它必须和数据结构合二为一）

4.算法的发现

时间：公元前3000年~公元前1500年 地点：巴比伦

巴比伦人求解“算法”的过程：先用解代数方法，再计算实际数目，最后写上一句短句“这就是一个过程”。

5.算法的特征

我们曾在必须修课中提过一点算法，如：冒泡排序法。

例：计算1+2+3+„„+100=？

分析：这个算法有限制范围，可以在有限时间内完成，这是算法的第一个特征：有穷性。计算此算法可以用纸笔、算盘、运算器

和计算机来完成，且计算过程是多样的，但结果是唯一的。这就是算法的可行性、确定性。

计算方法：

⑴把这100个数按顺序相加。

⑵用凑数法：1+99=100，2+98=100，3+97=100，„„，49+51，最后只剩下50和100。

⑶令S=0，使1≤n≤100，先执行S=S+n ⑴，再执行n=n+1 ⑵

n=1，S=0时，S（0）=1 n=2，S=1时，S（0）=3 n=3，S=3时，S（0）=6

n=4，S=6时，S（0）=10 n=5，S=10时，S（0）=15 n=6，S=15时，S（0）=21„„

算法的另外一个特征：输入、输出。

练习：水仙花数问题，如153=1^3+5^3+3^3，分析它应满足什么条件才能使用此方法？

二、如何描述算法

1.用自然语言描述算法

⑴自然语言——人们日常生活中使用的语言。

⑵此种语言的特点：通俗语易懂，缺乏直观性和简洁，且易产生歧义。

使用此种语言的注意事项：描述要求尽可能精确，详尽。

例：用自然语言描述凯撒密码的原理

第1步：输入26个英文字母，它们分别对应1~26个数学。

第2步：令a=1，k=3，n=26。

第3步：使a的取值范围为1≤a≤26，F(a)=(a+k)mod n，转第5步。

第4步：a=a+1，转第3步。

第5步：输出F(a)相对应的数字。

第6步：把数学转化成相当的字母，输出字母。

第7步：累计字母出现顺序，转第4步。

练习：现有一串字母“PROGRAM”给它加密，请设计算法，用自然语言描述。

2.用流程图描述算法

⑴特点：描述算法形象、直观，容易理解。

⑵流程图符号

3.用伪代码描述算法

特点：描述的算法简、易懂，修改容易，容易转化为程序语言代码。

例：分析课本经9页算法描述

第一个条件：y mod 4=0

判断闰年的条件：⑴y不能被100整除；⑵y能被400整除且y能被400整除。

判断不是闰年的条件：⑴y mod 4=0 且y mod 100=0,但y不能被400整除；⑵y不能被4整除。

表示条件判断语句 表示循环处理语句：

IF 条件 THEN 执行语句一 Do While 条件循环语句

ELSE执行语句二 Loop

END IF

条件语句中可以包含多个子语句

篇3：《算法的设计与描述》教学设计

为了能够精确检测红外弱小目标,各国研究人员设计了相应的红外目标检测追踪算法,如林红等[4]为了解决传统红外目标检测算法存在的不足,提出了在红外目标检测中引入形态学和信息熵算法,通过使用多结构形态学滤波算法,有效抑制小目标红外图像的背景和噪声,然后通过信息熵进行分割,确定目标区域,实验结果显示其算法具有较好的检测精度与效率。毋亚北等[5]为了实现复杂背景下红外小目标的检测与跟踪,设计了基于形态学梯度的目标检测算法,先计算红外图像的形态学梯度特征,并根据各种地物背景的形态学梯度特征提取天空区域,然后进行目标检测。Zheng Cui等人[6]为了精确检测与快速追踪微弱信号的红外点目标,设计了基于高速局部对比度的红外微小目标检测追踪算法,通过高速局部对比度技术,提取目标重要信息,定位感兴趣区域,随后利用人类视觉系统,将目标从复杂背景中分割出来,实验结果显示其算法具有较好的检测与追踪精度。

然而,当前的红外弱小目标检测追踪技术因目标尺寸较小,通常将红外目标的纹理特征忽略,没有考虑纹理信息(角点、线端以及边缘)等重要特征,主要是利用方差权重信息熵或对比度特征等单一图像复杂特征将红外目标从复杂背景凸显出来,使其难以将红外图像背景中的伪目标像素消除,在杂波与噪声干扰下,无法精确区分弱小目标与复杂背景,导致其追踪精度不佳。

对此,现提出基于复杂融合特征与联合灰度-纹理直方图描述子的红外弱小目标检测与追踪算法。通过对红外图像不同特征的背景干扰因素进行分类,并引入不同的腐蚀操作结构元素,改进了Top-Hat变换算子,将弱小目标从复杂背景中凸显出来;再构建复杂融合特征分割机制,确定候选目标区域;引入管道滤波模式,识别候选目标区域中的真实弱小目标;综合考虑弱小目标的灰度与纹理特征,联合LBP技术,设计了灰度-纹理直方图描述子,充分描述红外弱小目标的鲁棒性特征,有效剔除图像背景中的伪目标像素;再引入均值漂移算法,对弱小目标进行精确追踪。最后,测试了本文算法的小目标检测精度。

1 红外弱小目标检测与追踪算法

红外弱小目标检测与追踪算法过程见图1,主要包括两大部分:(1)基于方差权重信息熵的弱小目标检测;(2)基于灰度-纹理直方图描述子的弱小目标追踪。通过设计分类Top-Hat变换算子增强弱小目标,随后构建复杂融合特征分割机制,确定候选目标区域;联合管道滤波模式与灰度-纹理直方图描述子,基于均值漂移算法,完成红外目标追踪。

1.1 基于分类Top-Hat变换的弱小目标增强

在红外图像中,通常伴有严重的杂波与噪声,这些背景干扰因素会将弱小目标淹没,导致其定位追踪检测较为困难,因此,考虑红外弱小目标与背景特征的差异,引入相应的腐蚀操作结构元素,设计了分类Top-Hat变换算子,充分抑制背景杂波与噪声。在传统Top-Hat变换中,白Top-Hat操作TW可突出初始红外图像中比周围亮且比结构元素模板小的区域,而黑Top-Hat变换TB可凸显红外图像中比周围暗且比结构元素模板小的区域[7]。因此,Top-Hat变换能否精确检测弱小目标,关键在于择取较优的腐蚀-膨胀结构元素,达到抑制杂波与噪声,以凸显弱小目标。

文献[8]充分考虑目标区域和背景区域的差异性,将目标周围区域的像素引入到传统的Top-Hat变换中,达到了更好的抑制背景杂波与噪声的效果,其变换结构元素见图2。在该图中的Bi,B0,Bb属于同心圆。B0是大于目标区域尺寸的结构元素;Bi为低于目标区域尺寸的结构元素;Bb为中间结构元素;ΔB=B0-Bi是介于B0,Bi二者之间的圆形区域。假设红外图像为f,则Top-Hat变换中的开运算fB0i与比闭运算f·B0i(x,y)模型为[8]

式中,b为结构元素;B0i(x,y)代表同时包含Bi与ΔB两个区域的元素;0,·分别代表开运算与闭运算操作;⊕,Θ分别代表膨胀与腐蚀算子;(x,y)代表红外图像中的像素点。

联合式(1)与式(2),则其Top-Hat变换算子为[8]

式中,TW代表白Top-Hat操作;TB代表黑Top-Hat操作;其余参数的物理意义见式(1)和式(2)。

但是,文献[8]设计的Top-Hat变换算子的腐蚀操作为单一结构,易腐蚀亮度值较大的背景边缘信息,使其成为伪目标像素。故本文基于文献[8]的Top-Hat变换模型,定义不同的腐蚀操作结构元素,设计了分类Top-Hat变换算子。新的不同方向的腐蚀操作结构:

式(5)中,Bi代表0°,45°,90°,135°4个方向的腐蚀结构操作元素。max代表取4个腐蚀操作中的最大值。其余参数的物理意义见式(1)和式(2)。

由式(5)可知,设计的腐蚀结构包含了4个不同方向的线性9×1元素,并取其中最大值视为输出结果。在红外图像中,赋予那些亮度值较大的背景区域,其所含的像素数量也比较多,在空间内某个方向的像素数量会大于9。而根据式(5)的腐蚀结构,能够确保红外图像的线性结构元素不会腐蚀背景像素,从而完整地保持了背景信息,利用Top-Hat变换后,有效避免了背景信息的干扰。同样地,对于弱小目标,4个方向的9×1线性元素都可将其腐蚀,且将腐蚀结果的最大值作为最终输出,仍可较好地腐蚀目标,利用Top-Hat变换后,能够较好地抑制背景,显著增强目标。

因此,基于文献[8]的Top-Hat变换机制,联合本文定义的不同方向的腐蚀操作结构,设计了分类Top-Hat变换算子:

式中,所有参数的物理意义见式(1)~式(5)。

由式(5)~式(7)可知,定义的分类Top-Hat变换算子能够利用不同方向的腐蚀操作元素对红外图像中的不同特性背景信息以及目标进行分类处理,从而避免腐蚀背景区域像素,有效剔除了伪目标像素。以图3(a)为目标,由于弱小目标尺寸较小,可视为点目标,依据文献[8],取结构元素B0、ΔB的半径均为1,再利用本文分类Top-Hat变换与文献[8]的Top-Hat变换对其进行目标增强,结果见图3(b)和图3(c)。由图可知,本文分类Top-Hat变换具有更好的凸显效果剔除了大部分背景中的伪目标像素,见图3(c);而文献[8]的Top-Hat变换算子采用了单一方向的腐蚀操作元素,易腐蚀亮度值较大的背景边缘信息,从而将其混入目标检测中,产生了较多的伪目标像素,见图3(b)。

1.2 基于复杂融合特征的候选目标区域确定

依据图3的测试结果可知,虽然分类Top-Hat变换能够凸显红外弱小目标,但是难以完全剔除全部背景伪目标像素以及背景中存在的无规律随机噪声,且无法定位弱小目标的中心点。故联合方差权重信息熵、对比度特征以及梯度方向特征,构建了复杂融合特征,确定候选目标区域:

式中,G(i,j)代表复杂融合特征;a,b,c均为权重因子,为常量,根据3个复杂特征在检测弱小目标时的重要程度进行调整其值大小,a+b+c=1;ps∈[0,1]代表像素灰度值s出现的概率;s代表红外图像的灰度值集合;珋s代表区域像素灰度均值;(i,j)代表选择像素的位置;gr(i,j)代表(i,j)处像素点的梯度;C为候选区域尺寸;p(i,j)为当前像素点的灰度值;为选择区域内的最小灰度值;为选择区域内的最大灰度值。

依据模型(8)可知,复杂融合特征充分结合了方差权重信息熵gh(s)、对比度特征gw(i,j)以及梯度方向特征gr(i,j)的优势,利用gh(s)可显著区分红外图像中的平坦像素与复杂像素,而gr(i,j)在保持gh(s)特征基础上,增强算法对红外图像中的突变点的敏感度,通过利用gw(i,j)特征,在gh(s)与gr(i,j)优势基础上,充分考虑了目标的轮廓特性,有效剔除相交区域的伪目标像素。

依据模型式(8),则候选目标区域确定的具体步骤为:

(1)首先将尺寸为M×N的红外图像f分割为大小均等的子图像F(x,y),其尺寸为m×n;

(2)依据式(8),计算每个子图像F(x,y)的复杂融合特征值G;

(3)若所有子块中的最大复杂融合特征值为max(G),且max(G)>GT=μ+α×σ(μ,σ分别为式(9)的均值与方差,α为常量),则将此图像子块F(x,y)视为种子子图像;若max(G)<GT=μ+α×σ,则令,重新执行步骤(1)与步骤(2),直到最大复杂融合特征值为G满足max(G)>GT=μ+α×σ。

(4)判别目标区域的存在。设定阈值T=k×m ean(G),若G>T,则在红外图像中存在目标区域,随后,执行步骤(5);否则,检测过程结束。

(5)利用区域生长法[9],并将步骤(3)的种子子图像作为生长点,且其4个相邻像素被反复地添加到增长区域,从而确定候选目标区域,输出一个包含弱小目标的矩形块。

利用区域生长法与本文构建的复杂融合特征,对图3(a)进行测试,候选区域目标检测结果见图4。依图可知,复杂融合特征机制有效剔除全部的背景伪目标像素,精确地确定了候选目标区域,为后续弱小目标检测提高了效率。

1.3 基于管道滤波模式的真实目标像素筛选检测

通常情况下,红外图像具有复杂的背景,且目标亮度较暗,与背景形成的对比度较小[10],因此,仅凭单帧检测来确定候选目标区域,会导致该区域不但含有真实的弱小目标,而且还可能存在虚假目标。所以,需要在候选目标区域中,对该区域的真实目标像素进行筛选识别。利用序列图像中弱小目标运动的非间断性以及轨迹一致性,对候选目标区域内的真实目标像素进行检测,将伪目标像素进行过滤[11]。对此,引入管道滤波模式[11],利用其流水线性结构,对候选目标区域内的像素进行筛选,见图5。假设在检测时间内有N帧图像,并以序列图像的空间上的目标为中心,构建管道(其长度代表检测时耗的长度;直径代表其作用范围)。将最先管道内的第一帧图像进行二值化处理,并将其8连通区域标记出来,视为子候选区域,将该区域的质心坐标计算出来;再以质心为中心,构建一个管道,依据文献[11]的检测阈值条件,将候选目标区域内的虚假目标过滤,保留真实弱小红外目。详细的管道滤波模式识别真实目标的步骤见文献[11]。

以图4为测试对象,利用管道滤波模式,对其完成筛选,结果见图6。依图可知,经过管道滤波模式识别后,精确检测出完整的弱小红外目标,有效剔除了虚假目标。

1.4 红外弱小目标追踪

1.4.1 基于灰度-纹理直方图的目标描述

完成弱小目标检测检测后,为了实现对移动目标的精确追踪,需要对其特征进行描述。文献[12]指出,利用红外目标的灰度直方图特性能够较好地追踪目标;但是灰度直方图忽略了目标的空域特性,使其追踪精度不理想。而纹理模式却能够较好地反映目标的空域结构,对此,联合目标灰度与纹理特性,基于LBP技术[13](local binary pattern),定义了灰度-纹理直方图描述子。对于任意红外图像,若其中心像素为gc,则LBP算子[13]为:

式(12)中,gc是中心位置(xc,yc)像素的灰度值;R代表半径;P代表纹理模式种类;s为分类函数:

但是,利用式(12)来描述图像纹理,存在较大的不足,为了实现各种复杂的红外目标图像,引入局部旋转不变的LBPP,R算子[14]:

式(15)中,所有参数的物理意义见参考文献[14]。

模型式(14)是模型式(12)的拓展模式均值模式,令P=8,R=1,则模型式(14)具有9种均匀纹理模式,见图7。模型式(14)可充分描述图像的点,平坦区域,边缘,线端和角等特征。而边缘,线端和角这三种特征,是描述红外弱小目标的主要特征,可以从背景干扰中区分出目标。虽然模型式(14)能够较好地描述目标纹理特征,但其没有充分利用目标灰度直方图特性。故将目标的2D灰度特性H嵌入式(14),定义了灰度-纹理描述子:

式中,H代表红外目标的灰度直方图;b(x)代表目标像素x的灰度特征;N是目标区域像素的数量;δ是Kronecker函数;A代表LBPP,R算子中能描述边缘,线端和角等鲁棒性特征的纹理模式,在P=8,R=1中,A={2,3,4,5,6}。其余参数与式(12)~式(15)相同。

1.4.2 基于均值漂移算法的弱小目标追踪

均值漂移算法[15]是寻找点样本分布最近模式的非参数统计方法,找出与目标模型最相似的区域。若红外弱小目标运动中心在x0处,则与目标区域对应的目标模型q为:

式(18)中,C为归一化常量;qu是特征u在目标模型q中出现的概率;N代表红外图像的特征空间;K代表各向同性核函数的轮廓;T(xi)代表像素xi的灰度值;

同样地,可得到候选目标模型为

式(19)中,h表示带宽;y代表候选特征。

则红外目标追踪问题可转换为确定pu(y)与qu的最大似然解y。对此,引入巴氏系数[15]来表征

式(20)中,所有参数的物理意义与式(18)~式(19)相同。p[p(y),q]值越大,则显示qu与pu(y)更相似。

基于式(20),可得到qu与pu(y)的距离为

式(21)中,d代表相似距离;其余参数的物理意义与式(18)~式(19)相同。

为最小化目标模型qu与候选目标模型pu(y)的距离d,必须要使式(20)的巴氏系数最大,故对式(20)进行泰勒展开

式(22)中,其余参数的物理意义与式(18)~式(19)相同;wi是红外图像的权重矢量

在最小化qu与pu(y)的距离d后,利用均值漂移算法进行迭代,在此期间,候选目标的新位置y1的更新模型为

式(24)中,ε代表算法运行终止阈值。其余参数的物理意义与式(18)~式(19)相同。

当(用户设置的一个极小值)或者运行次数达到最大值N时,算法结束,此时可以在当前图像中确定一个与目标最相似的区域。否则,令y1=y0,重新执行式(19)~式(24)的计算过程,直到为止。

2 实验结果与分析

利用仿真工具MATLAB测试来验证本文红外小目标检测与追踪精度。算法运行条件为:DELL,2.5 GHz双核CPU,400GB硬盘;8GB的内存;电脑系统为Windows XP。同时,为了体现该小目标检测算法(尺寸为4×4像素)的优越性能,将文献[4]、文献[6]视为对照组。以图8(a)、图9(a)视为测试目标,灰度水平为256。其中,LBP描述子的P=8,R=1ε=10-7,A={2,3,4,5,6},a=0.3,b=0.3,C=0.4,Top-Hat算子中的Bo与ΔB的半径均为1。测试实验分为两部分:先对单帧红外图像经常目标检测;再对序列红外图像完成目标追踪。

2.1 单帧红外弱小目标检测分析

利用本文算法与文献[16,17]技术对图8(a)、图9(a)进行目标检测,结果见图8(b)~图8(d)、图9(b)~图9(d)。依图可知,面对噪声干扰的红外弱小目标,本文算法的检测精度更高,能够较好地检测出目标,而文献[4]、文献[6]两种算法的单帧检测精度不佳,无法将完整的弱小目标识别出来。原因是本文算法通过引入不同方向的腐蚀操作结构元素,设计了分类Top-Hat变换算子,避免将目标周围的背景像素腐蚀,且充分利用了方差权重信息熵、对比度特征以及梯度方向特征的优势,构建了复杂融合特征,精确分割候选目标区域,通过管道滤波模式的过滤作用,对候选目标区域中的真实弱小目标与伪目标进行筛选,将虚假目标过滤,使得本文算法的目标检测精度更高。而文献[4]是利用Top-hat变换来抑制背景干扰因素,再通过目标信息熵将目标分割出来,但是该Top-hat变换是单一方向的腐蚀元素,易将背景腐蚀掉,成为干扰因子,且信息熵难以将背景与目标交界处的相似像素过滤,从而导致其检测精度不佳,在检测目标的同时,也含有少量的虚假目标,见图8(c)、图9(c);而文献[6]主要是根据目标的局部对比度特征来实现目标检测,在噪声干扰下,难以将区分背景中与目标相似的像素,使得这些伪像素成为干扰因子,从而导致检测精度不佳,没有完整地将目标检测出来,见图8(d)、图9(d)。

2.2 红外图像的弱小目标追踪分析

实验条件与节2.1相同,为了体现本文算法的追踪精度优势,将当前目标跟踪精度较高的算法:文献[16]、文献[17]视为对照组,利用3种算法对长为200帧的红外图像完成目标追踪,结果见图10。依图可知,本文算法的追踪精度最高,在200帧序列图像测试中,都能精确追踪目标;而文献[16]只有第8帧、第44帧以及第200帧追踪正确,其余序列图像的目标追踪均失败;而文献[17]只有第8帧追踪正确。原因是本文算法设计了灰度-纹理直方图描述子,充分描述红外弱小目标的鲁棒性特征,有效剔除图像背景中的伪目标像素,使得算法具有更强鲁棒性;而文献[16]虽然也利用利用局部二值模式LBP算子对红外目标的纹理进行描述,能够充分利用目标的边缘、角点等特征,但是该技术忽略了目标的灰度直方图特性,使其描述能力不佳。文献[17]仅适用了目标的灰度直方图来描述目标,忽略了目标的纹理信息,使其描述能力较弱,继而导致算法的追踪精度较低。

为了量化3种算法的追踪误差,本文以图10中的长度为200帧的红外运动目标进行测试,依据文献[18]的方法,测试3种算法的追踪误差,结果见图11。从图11可知,本文算法的追踪误差水平更低,约为1.6像素,而文献[16]、文献[17]两种算法的追踪误差均大于本文算法。原因是所提算法联合了目标灰度直方图与纹理特性,具有更强的特征描述能力,而文献[16]、文献[17]均是利用单一目标特征来对其进行描述,使得算法的描述能力不高,无法充分利用目标的重要特征对其进行追踪,导致追踪误差较大。

3 结论

篇4：《算法的设计与描述》教学设计

关键词 教学资源描述 元数据 RDF

中图分类号：G642 文献标识码：A

0 引言

信息化是教学改革的重要组成部分，在教师课前备课、课中授课、课后复习等教学环节中充分利用互联网络的便捷性和计算机展示技术的多样性，已形成广泛的共识。而目前已建成的各类网络教学资源，由于建设形式多样，技术不统一，缺乏必要的建设指导规范和标准，共享率及利用率普遍比较低，无法对已建的各类教学课件资源进行有效的检索查询，极大地制约着教学资源的实际使用，也阻碍着多媒体教学工作往深层次的优化。本文研究教学资源的共性语义描述，在都柏林核心元数据的基础上，实现对教学资源的扩展元数据规范定义，给出适用于Web实现的RDF框架描述。

1 元数据及RDF框架

元数据（Metadata），一般认为是描述数据的数据（data about data），主要是描述数据属性（property）的信息，用来实现如存储位置、历史数据、资源查找、文件纪录等功能。元数据能为各种形态的数字化信息单元和资源集合提供规范、普遍的描述基准和方法，对资源的组织和管理具有重要作用。网络教学资源的元数据的主要目的是描述网络教学资源的属性信息，用来快速地识别资源、评价资源、追踪资源、过滤资源和使用资源，是教学资源的特征属性数据。

资源描述框架（Resource Description Framework，缩写 RDF），是万维网联盟（W3C）提出的一组标记语言的技术标准，以便更为丰富地描述和表达网络资源的内容与结构。RDF 定义一套可描述知识概念和实例的规范标准，专门用于表达网络资源的元数据，在语义表达和交换上更灵活。它提供了一种用于表达信息，并使其能在应用程序间交换而不丧失语义的通用框架。RDF用形如 （classes—properties—values）类似于面向对象（类—属性—值）的三元组来描述Web 上的各种资源和它们之间的关系，并提供了固有的语义单元。应用领域专用的类和属性需要通过对 RDF 的扩展来定义，这种扩展通过RDF Schema来实现，RDFS不提供实际的应用程序专用的类和属性，而是提供了描述应用程序专用的类和属性的框架。

2 网络教学资源元数据框架设计

网络教学资源元数据是构建基于Web的学习门户的基础数据规范，主要解决异构类型多的网络学习资源的整合以及系统间的通信规范，可促进网络教学资源的高效配置和综合利用。框架设计核心元数据规范、知识点元数据规范、图像通用元数据规范、动画通用元数据规范、音视频通用元数据规范，核心元数据规范是框架的核心，遵循柏林核心元数据规范扩展。

3 核心元数据规范

核心元数据规定了网络统一学习服务门户所需的核心元数据、各元素的语义定义，以及学习资源的信息标识、内容、管理和维护等描述信息。

（1）标识符

URI：http：//www.***.com/core/terms/identifier

中文名称：标识符

英文名称：identifier

定 义：资源的唯一标识

数据类型：字符串

值 域：自由文本

（2）名称

URI：http：//www.***.com /core/terms/title

中文名称：名称

英文名称：title

定 义：资源的名字或称谓

数据类型：字符串

值 域：自由文本

注 释：必选项，最大出现次数为1

（3） 创建日期

URI：http：//www.***.com core/terms/create_time

中文名称：创建日期

英文名称：create_time

定 义：资源最初的创建日期

数据类型：日期型

值 域：日期，按GB/T 7408执行

注 释：必选项，最大出现次数为1

（4） 最新修改日期

URI：http：//www.***.com /core/terms/last_modify_time

中文名称：最新修改日期

英文名称：last_modify_time

定 义：最近一次修改资源信息的日期

数据类型：日期型

值 域：日期，按GB/T 7408执行

注 释：必选项，最大出现次数为1

（5） 描述

URI：http：//www.***.com /core/terms/description

中文名称：描述

英文名称：description

定 义：资源内容的综述性介绍

数据类型：字符串

值 域：自由文本

注 释：必选项，最大出现次数为1

（6）关键字

URI：http：//www.***.com /core/terms/keywords

中文名称：关键字

英文名称：keywords

定 义：用于描述资源主题的通用词、形式化词或短语

数据类型：字符串

值 域：自由文本

注 释：必选项，最大出现次数为N

（7）访问控制

URI：http：//www.***.com /core/terms/view_control

中文名称：访问控制

英文名称：view_control

数据类型：字符串

值 域：1或2

注 释：必选项，最大出现次数为1

（8） 创建者

URI：http：//www.***.com /core/terms/creator

中文名称：创建者

英文名称：creator

定 义：创建资源对象的主要责任人或组织机构

数据类型：复合型

可 选 性：必选

最大出现次数：N

4 结论

本文分析并实现了网络多媒体教学资源的元数据框架，定义了框架的核心元数据、各元素的语义定义。该框架通用性高，便于资源的管理和共用。

参考文献

[1] 孙默.网络多媒体教学资源建设中的问题与对策.中国电化教育，2011.7.

[2] 张靖.基于XML/RDF的MARC元数据描述研究.微计算机信息，2007.36.

篇5：算法与程序设计的教案

一、学情分析

通过上学期《算法与编程》部分的学习，学生初步了解算法及其表示、比较熟悉流程图设计;

本学期课程为《算法与程序设计》，对算法的理解更加深入，要求能通过visual basic实现简单算法;

在本课之前，学生应了解了流程图的应用，熟悉在一组数中求极值算法，对于排序及冒泡排序，学生比较熟练。

对于本部分，学生可能会对选择排序算法的原理理解较为困难，需要教师的引导学习。学生应当在学习过程中认真听取教师对于算法的分析，在教师指导下能解释该算法的流程图，进而实现程序。

二、教学目标

知识性目标：

了解排序的概念、能在现实生活中列举出关于排序的实例

能对照冒泡排序，解释选择排序的优势，指出选择排序的策略，找出数字之间的逻辑联系

有迁移应用能力，能由此及彼，归纳排序中的数字规律，探索更有效率的排序算法

技能性目标：

具有模仿水平，在教师指导下可以表达出选择排序的思想，能对流程图作出解释

能独立完成流程图的绘制，对选择排序的各个环节比较熟练，并能在visual basic环境中规范地编写程序

情感、态度、价值观目标：

学生在学习过程中，通过亲身经历体验选择排序的实现过程，获得对此算法的感性认识

利用信息技术手段，开展交流合作，把自己对此算法的心得与他人交流，培养良好的信息素养，提升热爱科学的理念

三、重点难点

重点：对选择排序原理的理解，绘制流程图，数据交换，调试程序

难点：分析流程图

四、教学策略与手段

把握重点，先导入问题，复习排序定义，分析冒泡中数据交换次数多的问题，指出冒泡排序法效率不高，从而引出数据交换次数较少的选择排序算法

在教学过程中，可通过flash演示材料，比较直观地把抽象的问题简单化，由“流程图雏形绘制”-“逐步完善流程图”-“程序实现”-“调试”的过程，让学生熟练此算法与程序实现。

在教学中可灵活运用小组合作、分组讨论、小组间竞赛等手段进行教学，通过发散性思维的培养，增强学生对知识的探索能力。

五、课前准备

1.学生的学习准备：对流程图的绘制方法、vb语法作巩固，对选择排序算法作预习;学生分组：4人一组

2.教师的.教学准备：准备充分的演示材料、相关数据、相关软件安装。

3.教学环境的设计与布置：计算机教室

六、教学过程

简要点拨排序的概念。

演示已经学习过的冒泡排序flash动画。

[小组讨论]在冒泡排序算法中，我们知道冒泡排序是依次把数组中相邻两个数据进行比较，通过交换数据，把较小的数据逐次向上移动的算法。由于数据的移动是逐次进行的，数据交换的次数相当多。大家想想它的实质既然是将一堆数据中的最小数据移动到某个位置，有没有必要让这个数字逐个移动?比如，对于数组：4、8、3、9、6、5、11、10、2、9，如果要用冒泡法实现排序，第一遍冒泡其实是把这组数据中最小数“2”移动到最前边，第二遍冒泡把“3”逐次移到第二个位置，其它类推。它们的过程是逐次向前的，这样做很多无谓的交换。为了达到移动2到最前边的目的我们可以怎么简化这个过程?

[学生]直接把2最前面的数4交换，再把3与第二个位置的数8交换，其它类推

篇6：《算法的设计与描述》教学设计

卫星主动控温回路的设计模型与算法

使用电加热器的卫星主动控温回路是一种重要的主动热控措施,通过简明扼要的机理分析建立起该主动控温过程中受控对象温度变化的动态方程,得出了稳态控温、瞬态控温两种基本的控温模式下主动控温回路电加热器功率需求的计算表达式,给出了进行主动控温回路电加热器热功率设计计算的`一般流程,较详细地分析了一个具体设计算例,为卫星主动控温回路设计计算提供了简便的计算模型和方法.

作 者：李运泽 杨娟 宁献文 王晓明 石晓波 Li Yunze Yang Juan Ning Xianwen Wang Xiaoming Shi Xiaobo  作者单位：北京航空航天大学航空科学与工程学院,北京,100083 刊 名：中国工程科学  ISTIC英文刊名：ENGINEERING SCIENCE 年，卷(期)： 10(7) 分类号：V416 关键词：卫星   主动热控制   主动控温回路   模型与算法  

篇7：算法与程序设计

作者：赵濮民

摘要：研究性学习是教育科研领域中一个崭新的课题。信息技术教学作为以培养创新精神、研究能力和实践能力为目标取向的必修课程，它强调让学生通过研究性学习，提出问题，收集材料，对研究性课题进行探索、分析、研究，最后基于问题解决模式，在实践操作中培养学生科学的态度和价值观以及创新精神、创新思维、创造能力，并学会解决生活中与信息技术学习有关的实际问题。职业学校的学生，不仅应具有独立接受知识的能力，更应具有独立探索知识的能力，由“研究性学习”补充原有的“接受式学习”，使学习方式更趋完善，只有当这两种学习方式结合起来，优势互补，才能使基础教育适应时代对人才培养的要求。

关键词：程序设计；研究性学习；求真；求全；求变；求新；优势互补

《算法与程序设计》是职业学校信息技术教学中的一个重点，也是难点。传统的程序设计教学以老师讲授型为主，由于算法与程序设计的内容逻辑性强，普遍认为在程序设计教学中难以实施研究性学习。

研究性学习是以“培养学生具有永不满足、追求卓越的态度，培养学生发现问题、提出问题、从而解决问题的能力”为基本目标，以学生从学习中获得作品设计与制作方法的困惑为方向，以在提出问题和解决问题的全过程中学习到算法与程序设计为学习方法的课程。经过反复研究，我们认为研究性学习可以应用于程序设计教学中。实施研究性学习的关键是要确定一个目标，要鼓励学生主动地发现问题，并且通过探究或实践活动去试图解决问题。在课题研究的过程中采用分组交流讨论、查阅资料、协作探究、归纳总结等方式，一步步引领学生深刻掌握算法与程序设计的精髓。

一、通过研究性学习，重构算法知识体系，要求真 研究性学习是学生在老师的指导下，结合真实生活，选定主题，然后搜集相关材料，对材料进行归纳、加工处理、分析、总结，得到相应结论的学习活动。在《算法与程序设计》教学中，根据教学内容，经过反复研究，确定了研究主题《搜索算法的应用研究》和《动态规划算法的解题应用研究》，并根据学生的自愿报名成立了两个研究小组。然后各小组根据自己研究的算法，重新整理相应的知识，对知识进行认知、归纳、总结。如《搜索算法的应用研究》小组，对搜索算法从以下几方面进行整理：

1、搜索算法的算法思想、分类；

2、深度优先搜索的算法思想与算法结构；

3、广度优先搜索的算法思想与算法结构；

4、深度优先搜索的优先策略；

5、广度优先搜索的优化策略；

6、深度优先搜索与广度优先搜索的异同。学生通过对搜索算法知识进行整理、分类、小结，加深了对搜索算法的理性理解与感性认知。

二、通过研究性学习，同学之间取长补短，要求全

每个学生都有所长，也有所短，研究性学习一个重要的特点就是：分工合作，共同讨论，共同提高，使参与的学生全面发展。我们的“搜索算法的应用研究”小组共有五个成员，根椐学生的特点、特长，对他们进行分工，每位学生研究上述其中一个问题，然后整个小组一起讨论，每位学生介绍自己的研究情况、研究成果，然后其他同学进行补充，发表自己的见解，这样每个同学都使自己的研究内容得到补充，同时也学习到了其他同学研究方面的知识，可以取长补短，共同提高，得到全面发展。

三、通过研究性学习，总结算法的应用规律，要求变

研究性学习的目的，是要求学生搜集与主题有关的资料，归纳整理相关资料，根据相关材料和知识，对主题进行研究，提出自己的观点或结论。我们在程序设计教学中进行算法专题研究也是这样，除要求学生归纳、整理专题算法知识外，还要总结出算法的应用规律、应用算法解题的步骤和算法的框架，能根据实际情况，随机应变。如在“动态规划的应用研究”中，学生总结出：动规划是解符合“无后效性原则”的最优问题的一种算法思想；用动态规划解题的一般步骤是：（1）判断题目是否为求最优问题，是否符合“无后效性原则”；（2）确定如果划分阶段；（3）确定每个阶段有几种状态；（4）找出状态转移方程和边界条件；（5）用算法语言实现算法过程。又如在“搜索算法的应用研究”中，研究小组的同学总结出：（1）广度优先搜索算法通常应用于解最少步数问题，而深度优先搜索算法则通常用来解所有路径问题；（2）深度优先搜索和广度优先搜索都是搜索算法，前者时间复杂度较大，而后者则占用的内存较大；（3）深度优先搜索在实现时用递归或用堆栈来实现，而广度优先搜索是用队列来实现，实现两种算法所用的数据结构不同；（4）深度优先搜索和广度优先搜索都是搜索算法，但两者的算法结构有较大的不同。学生通过自己对算法应用规律的总结，对算法的应用得到升华，进一步提高算法的应用能力和程序设计能力。

四、通过研究性学习，提高分析、归纳和综合能力，要求新

对算法的专题研究，不仅要对算法理论进行总结，算法应用的研究也是很重要的一方面，通过算法的解题应用，既提高了学生分析问题的能力，也加深了学生对算法的理解，提高了学生的算法应用能力，进而得到对学生创新能力的培养。另外，我们在算法研究过程中，要求学生透切理解算法内容，用算法语言准确描述算法，通过这种途径，进一步加深学生对算法的理解，同时也提高了学生的算法表达能力和归纳、总结的能力。

通过对算法进行专题研究，可以进一步加深学生对算法知识的理解，也可以提高学生的算法应用能力和程序设计能力。实践告诉我们：在整个研究过程中要注意以下几个问题：

1、课题不宜太大。研究课题的确定是研究性学习实施过程中重要的一环，课题选择恰当与否，直接关系到整个课题研究的成败。在程序设计教学中进行研究性学习活动，选题要遵循下面的原则：（1）课题的范围不宜太大；（2）有一定的应用价值；（3）结合学生的实际。一个好的开始是成功的一半，在研究性学习活动中也是如此。

2、要理论研究与算法应用相结合。对算法的专题研究，算法应用是重点。在算法知识归纳总结的基础上，重点应研究算法应用的一般规律、算法结构、应用算法解题的一般步骤等。不应该只是对算法理论的空洞论述，否则效果不好、意义也不大。

3、充分发挥教师的引导作用、学生的主体作用。在算法研究活动中，应充分发挥教师的引导和指导作用，既不能放任自由，也不能包办代替，要充分发挥学生的主体作用。当学生遇到问题和困难时，老师应当引导和启发学生，让学生去探索和研究，而不是直接告诉学生答案，老师始终是学生的引导者，学生是真正的参与者，使学生通过算法研究，加深对算法的理解，提高算法应用能力和程序设计能力。

篇8：《算法的设计与描述》教学设计

本节教学内容选自广东教育出版社信息技术选修模块教材《算法与程序设计》。面对初学程序和算法的高中二年级学生而言, 本节内容偏理论、较抽象。如果直接讲算法, 学生很难建立新旧知识的联系, 更难真正理解算法的含义。笔者遵循认知规律, 从学生的感性认识入手, 从他们的兴趣出发, 通过对现实生活具体问题的讨论, 使他们明白解决任何问题都需要有清晰的解决思路和步骤, 很自然地引入了算法的概念;学生独立进行算法设计的实践环节, 有利于学生从生活算法设计中的思维模式向计算机算法设计 (描述) 的转变, 更有利于学生接受和理解下一节的“计算机解决问题的过程”和“程序设计语言”。

一、教学目标

知识与技能:理解算法的概念及其特征;能够理论联系实际, 初步利用算法解决简单的问题;培养自我探索信息、高效获取信息、分析评价信息、处理运用信息、表达呈现信息的能力, 进一步提高信息素养。

过程与方法:培养发现旧知识的规律、方法和解决问题的思路, 并把它运用到新知识中去。

情感、态度与价值观:通过算法与算法设计在日常生活中的实际应用, 启发思维, 养成主动探究问题、解决问题的思维习惯, 从而解决生活中的现实问题。

二、教学重点、难点

重点:理解算法的概念及其特征。

难点:算法设计思想及实践。

三、教学过程

1. 创设情境

师:大家在生活中会碰到许多困难和问题。当遇到问题时, 你会怎么办?

生:解决问题。

师:对。从遇到问题到解决问题, 中间要经历哪些步骤?

生:分析问题→找出解决问题的方法→解决问题。

师:很好。比如说, 早上谁叫你起床?

生:闹钟、别人或生物钟。

师:这些都是解决“早上起床”这个问题的方法。培根的《论读书》说:“读史使人明智。”就让我们来看看古人在遇到实际问题时是怎样解决的。思考一下, 我们能从中受到怎样的启发。

问题一:曹冲称象 (略)

问题二:田忌赛马 (略)

2. 得出算法概念

师:通过对上述问题的分析, 我们对算法有了一个初步的了解。在解决某些问题时, 需要设计出一系列可操作或可计算的步骤, 通过实施这些步骤来解决问题, 通常把这些方法和步骤称为解决问题的算法。

师生得出概念:为了解决某一问题而采取的方法和步骤, 就称之为算法。算法设计分两部分内容:一是找方法;二是描述实现方法的步骤。

师:做任何事情都有一定的步骤。例如刚才我们提到的“早上起床”的问题, 如果采用的方法是闹钟, 那么步骤是先调好时间, 再打开开关。等时间到了, 闹钟就响。又如描述太极拳动作的图解, 就是太极拳的算法。再如一首歌的乐谱, 也可以称之为该歌曲的算法。推而广之, 厨师的菜谱实际上也是一个算法。

3. 师生探讨

问题三:数学问题

问题详述:使用一根长度为L厘米的铁丝, 制作一个面积为S平方厘米的矩形框, 要求计算该矩形框的高h和宽w。

【解题方法】

【步骤】

第一步:输入数据L、S;

第二步:判断d=L 2-1 6 S;

第三步:根据d的取值范围, 计算公式;

第四步:输出运算结果。

4. 算法的特征

根据问题三, 师生归纳算法的特征如下:

有穷性:一个算法必须保证它的执行步骤是有限的、能终止的。

确定性:算法中的每个步骤必须有确切的含义, 不应该是含糊的、模棱两可的。

可行性:算法的每一步都应当能有效地执行, 并得到确定的结果。

输入:有0个或多个输入。

输出:有1个或多个输出。

5. 分组活动

问题四:过河游戏

问题详述：有三个牧师和三个野人过河，牧师和野 人 都 会 撑船，他们都要到 河 的 对 岸 。只有一条能装下 两 个 人 的船，在河的任何一方或者船上，如果野人的人数大于牧师的人数，那么牧师就会有被吃掉的危险。你能不能找出一种安全的渡河方法呢?请写一写你的渡河方案(如图 1 )。

学生分组讨论回答, 并上讲台演示。

【方法】:确保在河的任意一边 (包括船上和岸上) 的牧师人数大于或等于野人的人数。

【步骤】

第一步:两个野人先过河, 一个野人回来;

第二步:再两个野人过河, 一个野人回来;

第三步:两个牧师过河, 一个野人和一个牧师回来;

第四步:两个牧师过河, 一个野人回来;

第五步:两个野人过河, 一个野人回来;

第六步:两个野人过河。

师:从事各种工作和活动, 都要事先想好解决问题的方法和工作的步骤, 然后按部就班地进行, 这样就可以避免产生错误。

问题五:“烧水泡茶”的算法

【方法与步骤】

师:在数学、物理、化学的各种习题中, 我们经常遇到一题多解的现象。在处理此类问题时, 要注意从多种正确解法中寻找最简单、最快捷的解法, 这就是我们算法中的最优算法了。

6. 巩固运用

练习:货场上堆放着直径为d厘米的钢管, 请设计一个算法, 根据这堆钢管的层数n, 计算并输出这堆钢管的高度h (如图2) 。

教师让学生在黑板上写出自己的解题答案, 并在讲台上说出自己的解题思路:如何分析问题, 得出解决问题的方法, 并描述如何实现方法的步骤。

学生根据题意, 找出方法:

【步骤】

第一步:输入数据n、d;

第二步:计算

第三步:输出运算结果。

7. 回顾小结思考拓展

师生共同回顾算法的概念以及特征, 教师留下问题让学生进行拓展思考。

师:你还有别的称大象的方法吗, 你的方法比曹冲的好吗?这节课, 我们学了如何进行算法设计 (方法和步骤) , 那么计算机是怎样解决问题的呢?

四、教学反思

篇9：《算法的设计与描述》教学设计

关键词：算法设计与分析课程；动态演示；WPF；C#

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2016）20-0078-02

Abstract： A learning software of algorithm design and analysis course is designed and implemented by using WPF and C# language under the environment of Visual Studio 2010. The bubble sort， the eight queen problem， the tower of Hanoi problem and the knapsack problem are chosen as demonstration of the greedy method， backtracking method， divide and conquer method and dynamic programming， trying to vividly display the demonstration process of above classical algorithms.

Key words： Algorithm design and analysis course； Dynamic demonstration； WPF； C#

算法演示程序是以圖形解释算法，动态演示能够帮助学生加深算法理解，在脑海中形成算法执行过程的直观生动的印象，进而提高算法的教学效果[1]。许多算法演示系统的设计与实现的思想都来源于M.Brown等制作的BLASA系统[2]，随着可视化技术的发展，算法演示程序能够更加生动地展现出求解问题的过程。一个良好的演示系统应当具有丰富的媒体表现力、深入的细节演示效果、灵活的交互能力以及适当的游戏功能四个特性[3]。

1 整体框架

本软件基于微软推出的用户界面框架WPF[4-5]，并在Visual Studio 2010平台下设计与开发的。它提供了可视化界面，用户可直观看到分治法、贪心法、动态规划法和回溯法四种经典算法策略的求解过程[6]，软件的整体框架如图1所示。

2 具体实现

2.1 分治法

本文选择了汉诺塔问题进行分治算法的演示。汉诺塔问题中，每个盘子在柱子上的运作方式与栈结构非常类似：只能移动最上面的盘子。程序中设置了三个栈用于模拟当前三个柱子的状态。

盘子在移动过程中只涉及了四个方向：向上出盘、向左或右边移动、向下入盘。程序设置了一个方向变量direction，出盘过程中，盘子在越过柱子顶部时始终保持了方向direction=0。进程在发现direction为0时会控制盘子一次向上移动一个单位，当盘子的下边界越过了柱子的上边界，direction改变，根据相应信息，将direction设置为向左或者向右方向，左右移动过程以及向下入盘过程的移动方式和判断方法和出盘过程类似，不再赘述。

2.2 贪心法

选取冒泡排序演示贪心算法。我们采用球来表示每一个待排元素[7]，并用其透明度表示元素值的大小。用户输入球体的数目和初试排列状态（程序提供了三种状态：随机排列、逆序排列、正序排列）后，系统内部动态分配等长的球体数组。这些元素都是实例化的对象，能够被添加到画布上。

利用WPF中的Double Animation动画类来实现，它通过指定一个double类型的初始值From和同类型的终值To，使被关联的控件形成动画。如：以下代码可实现Name为lblTest的控件在一秒钟的时间内宽度增加50的动态效果。同样，球体在画布中的位置也是属性，可用动画改变。

一般排序算法都分为两个基本操作：比较和交换。本软件的冒泡排序演示程序就是利用这两个基本操作来进行演示的。如图2所示，若无需交换，则给出提示文字；若需要交换，则利用动画将相应两个球的位置颠倒。

2.3 动态规划法

本文选择0-1背包问题演示动态规划法。具体演示过程：用户完成输入后，点击演示进入演示状态。程序采用单步演示的方式，用户单击按钮，程序演示一步。利用二维数组的列数代表背包的总重量，用户可以修改。程序中使用Grid控件模拟二维数组，Grid内部的Label控件需要动态生成，见如下代码。其中thingCount为物品总数，bagWeight为背包承重，lblC是用于方便访问指定单元格的Label而设置的Label类型数组。

动态规划求中间值的代码如下。其中，第005行的判断表示当前第i个物品的价值与前i-1个物品在背包承重为j-W_arr[i]时的最大价值之和，是否比前i-1个物品在背包承重为j时的最大价值高。

2.4 回溯法

本文选择8皇后问题演示回溯法，图3和4是8皇后问题的相关演示效果图。演示程序中有一个皇后放置的试探过程，如图3所示，黑色棋子表示当前已放好的皇后位置，红色的棋子表示正在试探中。若红色棋子试探成功，则将黑色棋子放在该位置。

在该程序的另一个功能中，用户可以自己放置棋子，来感受8皇后的探索过程。本程序提供了一个错误提示的小功能，若当前棋子与棋盘上某个棋子有冲突，即在同行同列或者同一对角线，那么就会有红线闪烁，表明无法放置，如图4所示。

3 结束语

本软件在设计过程中，参照良好算法演示系统的设计要求，提供了交互功能和图形演示跟踪的功能。在算法的教学过程中能让学生接触直观的操作演示，可更好地让学生知其所以然[8]，也更快地让学生具有利用计算机解决问题的思维方式。不足之处在于它不支持算法跟踪功能，无法从代码上深刻认识算法。

参考文献：

[1]Matthew MacDonald著， 王德才 译. WPF编程宝典——C#2010版[M].

[2]刘铁猛. 深入浅出WPF[M]. 北京： 水利电力出版社， 2010.

[3]陈慧南. 算法设计与分析——C++语言描述[M]. 2版.北京： 电子工业出版社， 2012.

[4]孙永新， 闫大顺. 动画演示与算法教学研究[J]. 现代计算机， 2009（10）： 81-83

[5]张文升， 周青云， 周晓聪. 算法演示系统研究与应用[J]. 计算机应用与软件， 2008， 10：41-43.

[6]李健. 汉诺塔算法演示系统的设计与实现[J]. 现代计算机， 2011（24）： 76-80.

[7]田军， 李丰军. 基于VB程序的冒泡排序算法演示[J]. 电脑知识与技术， 2011（36）： 9410-9412.