教案算法与程序设计思想

2024-04-28

教案算法与程序设计思想（精选14篇）

篇1：教案算法与程序设计思想

算法与程序设计思想

【课标要求】

（一）利用计算机解决问题的基本过程

（1）结合实例，经历分析问题、确定算法、编程求解等用计算机解决问题的基本过程，认识算法和程序设计在其中的地位和作用。

（2）经历用自然语言、流程图或伪代码等方法描述算法的过程。

（4）了解程序设计语言、编辑程序、编译程序、连接程序以及程序开发环境等基本知识。

【学情分析】

高一年级的学生已具备了一定的观察、思考、分析和解决问题能力，也已有了顺序结构、分支结构、循环结构等知识的储备。因此，对于如何将解决问题的思路画成流程图已有一定的基础，但可能还不很熟练，尤其对刚学过的循环结构，教师在课堂上要注意引导。『此处说“已有了顺序结构、分支结构、循环结构等知识的储备”，应该是指在必修部分对“计算机解决实际问题的基本过程”已有所体验与了解，或是指已学习过数学中相关模块的知识，这是本案例教学得以实施的必不可少的前提条件。』

【教学目标】

1.知识与技能：

建立求一批数据中最大值的算法设计思想，并将算法的设计思想用流程图表示出来。2.过程与方法：

利用现实生活中比较身高的活动，以及对武术比赛中“打擂台”流程的逐步梳理，让学生学会从此类生活实际中提炼出求最大值的思想方法，即算法思想。培养学生分析问题、解决问题的能力，让学生学会在面对问题时能梳理出解决问题的清晰思路，进而设计出解决某个特定问题的有限步骤，从而理解计算机是如何解决、处理某种问题的。

『在过程上，通过现实生活中的实例来引导学生总结“求最大值”的算法思想。过程的实现关键在于实例引用是否贴切，是否有利于学生向抽象结论的构建。本案例的实例选择是符合这一要求的。在方法上，注重培养学生分析、解决问题的一般能力，再次体验与理解应用计算机解决问题的基本过程，为后面更一步的学习打下基础，积累信心。』

3.情感态度与价值观：

让学生全身心地投入到教学活动中，积极与同伴合作交流，进行探索活动。培养学生良好的思维品质，发展他们的创新思维，并养成积极的学习态度和良好的学习习惯。

创设情境，以激发学生的学习兴趣。努力营造一个可以接纳的、支持性的、宽容的课堂学习环境，让学生置身于民主和愉悦的课堂氛围中放飞思维、潜心研究、快乐创造。

『本案例对“情感、态度与价值观”目标的设计，更多的是试图建立一个活跃、民主、快乐的学习环境。良好的学习环境是学生乐学好学、教师提高课堂效率的重要条件。如果真能实现这样一个环境，营造出理想状态中的学习氛围，无疑会使学生在学到“知识与技能”的同时收获到更多的东西——合作、分享、成就。而且如果能够结合教学内容来描述目标，则会使目标显得更具体，更有针对性。』

【重点难点】

教学重点：建立求一批数据中最大值的算法设计思想，并将此算法设计思想用流程图表示出来。

教学难点：上述重点问题同样是本课教学的难点。另外，如何把人解决问题的思路、步骤用计算机语言描述出来也是本课的难点之一。

『建议，此处可添加关于教学重、难点的确立依据，以及解决教学难点的关键方法方面的描述。同一段知识内容的教学重、难点对于同类教师基本上是一致的，不同的是对教学重、难点的认识与处理方法。应该说，对教学重、难点认识的越深刻就越有可能找到更好的处理方法。』

【教学思路】

利用现实生活中比较一组学生身高这一事件，引导学生去发现求最大值的一种方法。如何设计求一批数据中最大值的算法？我认为让学生自己去经历整个探究过程，要比直接把现成的算法告诉学生有意义得多。它能迅速、有效地帮助学生建立程序设计思想。在完成这个任务的过程中，教师的循循善诱起到了非常关键的作用。找出一批数据中的最大者，从表面上来看是一个很简单的问题。在比较数的过程中，人因为动用了眼睛，比较大小的思维过程一闪而过，所以能很快求出一批数据中的最大值。而计算机与人不同，它对这些数据看不见、摸不着，怎么来完成这一任务呢？其实，计算机解决问题的关键，就是要把人解决问题的思维过程用计算机语言描述出来，即为大脑思维的每一步“拍照”。这是计算机程序设计教学的一个重点，也是一个难点，需要教师在教学过程中逐步引导和训练学生，使学生逐渐学会分析问题，寻求解决问题的方法和步骤。本案例运用生活中“打擂台”的实例引导学生分析求最大值的方法，通过对这一现象的分析，逐步引出求最大值的算法设计思想。

『作者在此处点出了解决教学难点的方法，即采用“逐步引导和训练”的方法。其意图就是希望学生经历整个过程，从而锻炼、提升探究能力，领悟、理解其中的思想，实现授人以渔的目的。』

【教学过程】

1．情境创设___________如何建立支架的？师（提问）：今天在第一排就座的有10 多位同学，谁是我们第一排在座各位中的最高者呢？师（引导）：大家思考，通常这个任务我们是怎样去完成的？教师根据学生对问题的回答进行分析。引导学生往古时候比武时常常采用的“打擂台”的方式上想，提示学生可参考电视上经常播放的“挑战主持人”节目。师生：打擂的过程可以描述为：

（1）确定一个擂主（讨论第一个擂主是如何确定的）；

（2）挑战者上台；

（3）擂主和挑战者比较；

（4）挑战者胜的话，挑战者做擂主，否则擂主卫冕；

（5）重复执行（2）～（4）步骤，直到最后一个挑战者。

师：在打擂的过程中，我们看到（2）～（4）步骤是要重复做的，所以我们该怎么办呢？生：需要循环结构来实现。师：这几个步骤序列重复到什么时候结束呢？由学生讨论结束的办法，很显然，需要在最后加上一个能判断什么时候结束的判断框。

根据讨论的步骤，最后师生共同得出打擂台的算法和流程图（如图1）。

『作者的引导可以总结为：比身高（学生的回答可能多种多样，也可能偏离预设方向）——比武、“打擂台”（将学生发散出去的思考往预设方向上牵引）——“挑战主持人”节目（进一步将学生的思考引到其头脑中已有的认识上，前提是学生要看过该节目）——用自然语言的方式整理出比赛的规则（即算法的自然语言描述）——得到表示算法的流程图。应该说，这样的引导方式完全可以达到作者的预设目标。』 2．求一般情况下的最大值的算法师（引导）：如果我们面对的是一堆数据，现在希望我们求出这一堆数据中的最大值该怎么办？通过教师和学生的共同分析，把问题进一步细化为：

（1）从第一个数据开始看起；

（2）把第一个数据的值在变量中记下来；

（3）再取一个数据；

（4）比较这个数据与变量中记下的数据的值；

（5）如果这个数据的值比记下的数据的值大，则去掉变量中原来那个数据，记下新数据的值；

（6）重复执行（2）～（4），继续比较，直到最后一个数据。

也就是说，计算机的变量始终记着当前比较过数据中的最大者（我们不妨用X 表示它），当取完最后一个数据时，X 中留下的也就是最大值了。求最大值的算法设计思想用下图表示。

『教学在上一环节的基础上再做进一步的深入，即扩大数据的比较范围，讨论一般的情况。由于学生已经经历了上一环节的思考过程，因此，再次思考一般性问题的解决方案就变得容易多了，这又是另一维度的“逐步引导和训练”，即具体到一般的过渡。这是作者对教学策略设计的准确实现。』注意：

a．再次让学生讨论变量的意义，弄清赋值语句的意义。b．一些物理量用变量表达的意义。如X 表示最大值，X 表示输入的一个值，且每次循环时都用同一个变量X。

c．为了控制循环结束，必须加入一个控制循环次数的计数器I，当I 达到一定的次数后，循环工作结束。

『除了对教学目标宏观上的关注与设计之外，也注意到了教学内容细节上的把握。作者在此处提出的三点注意都是编程语言细节上的问题，应该说，这“三点注意”是作者多年或是本案例实践过后总结的教学经验，当然也可能是教师在教学设计时预先设想的教学问题。这些要“注意的点”正是教学实践或设计中的精华所在，也是值得我们借鉴与学习的内容之一。』

3．回顾小结

师生共同总结算法设计的过程，就是将大脑思维的每一步都记录下来，并且用计算机能达到的功能来实现人解决问题的思路。

『最后带领学生总结本节课的中心思想，即回答“算法设计的过程是怎样的？”这一问题。使整节课有了一个明确的结论。』

篇2：教案算法与程序设计思想

一、教学目标 1.知识与技能：

求一批数据中最大值的算法设计思想，并将算法的设计思想用流程图表示出来。2.过程与方法：

利用现实生活中比较身高的活动，以及对武术比赛中“打擂台”流程的逐步梳理，让学生学会从此类生活实际中提炼出求最大值的思想方法，即算法思想。

培养学生分析问题、解决问题的能力，让学生学会在面对问题时能梳理出解决问题的清晰思路，进而设计出解决某个特定问题的有限步骤，从而理解计算机是如何解决、处理某种问题的。

3.情感、态度与价值观：

二、教学重点、难点教学重点：建立求一批数据中最大值的算法设计思想，并将此算法设计思想用流程图表示出来。

教学难点：上述重点问题同样是本课教学的难点。另外，如何把人解决问题的思路、步骤用计算机语言描述出来也是本课的难点之一。

三、教学对象分析

高一年级的学生。他们已具备了一定的观察、思考、分析和解决问题能力，也已有了顺序结构、分支结构、循环结构等知识的储备。因此，对于如何将解决问题的思路画成流程图，学生已有一定的基础，但可能还不很熟练，尤其对刚学过的循环结构，教师在课堂上要注意引导。

四、教学策略及教法设计

五、教学过程 1．情境创设师（提问）：今天在第一排就座的有10 多位同学，谁是我们第一排在座各位中的最高者呢？

师（引导）：大家思考，通常这个任务我们是怎样去完成的？教师根据学生对问题的回答进行分析。引导学生往古时候比武时常常采用的“打擂台”的方式上想，提示学生可参考电视上经常播放的“挑战主持人”节目。

师生：打擂的过程可以描述为：

（1）确定一个擂主（讨论第一个擂主是如何确定的）；（2）挑战者上台；

（3）擂主和挑战者比较；

（4）挑战者胜的话，挑战者做擂主，否则擂主卫冕；（5）重复执行（2）～（4）步骤，直到最后一个挑战者。

师：在打擂的过程中，我们看到（2）～（4）步骤是要重复做的，所以我们该怎么办呢？

生：需要循环结构来实现。

师：这几个步骤序列重复到什么时候结束呢？由学生讨论结束的办法，很显然，需要在最后加上一个能判断什么时候结束的判断框。

根据讨论的步骤，最后师生共同得出打擂台的算法和流程图（如图1）。

2．求一般情况下的最大值的算法师（引导）：如果我们面对的是一堆数据，现在希望我们求出这一堆数据中的最大值该怎么办？通过教师和学生的共同分析，把问题进一步细化为：

（1）从第一个数据开始看起；

（2）把第一个数据的值在变量中记下来；（3）再取一个数据；

（4）比较这个数据与变量中记下的数据的值；

（5）如果这个数据的值比记下的数据的值大，则去掉变量中原来那个数据，记下新数据的值；

（6）重复执行（2）～（4），继续比较，直到最后一个数据。也就是说，计算机的变量始终记着当前比较过数据中的最大者（我们不妨用X 表示它），当取完最后一个数据时，X 中留下的也就是最大值了。

求最大值的算法设计思想用图2 表示。

注意：

a．再次让学生讨论变量的意义，弄清赋值语句的意义。

b．一些物理量用变量表达的意义。如X 表示最大值，X 表示输入的一个值，且每次循环时都用同一个变量X。

c．为了控制循环结束，必须加入一个控制循环次数的计数器I，当I 达到一定的次数后，循环工作结束。

3．回顾小结

篇3：教案算法与程序设计思想

1 优化下料算法

工业当中, 关于优化下料的问题, 在国外称为CSP, 包括材料的排样问题、切割问题和装箱问题。根据是否为空间尺寸下料问题可划分为广义下料问题和狭义下料问题。在工业领域当中, 下料问题存在的比较广泛。对于下料问题的不断深入的研究, 可以得出目前主要的求解手段有两大类:

1.1 最优解法

数学模型中一维下料问题是一个对整数进行规划的问题, 一般的下料优化方法是通过将整数变量松弛后, 看做是线性规划, 运用单纯形方法进行求解, 然后将得到的结果圆整, 但是这样不能确保一定得到最优解, 并且进行圆整后会导致零件生产过量或者生产不足, 这就需要对其进行再处理;也可以运用针对整数规划求解的割平面和分支定界法进行求解;与此之外还可以采用枚举法, 通过比较可行解空间内所有点的目标函数从而找出下料问题的最优解;但是这些方法计算效率比较低, 经常因为解空间太大而对实际问题的处理束手无策, 所以这些方法只能对小规模问题进行优化。

1.2 启发式算法

优化下料问题作为一个NPC难的问题, 有复杂的计算程度, 求解时间根据问题规模呈现指数级的增长, 所以通常没有多项式算法。由于存在复杂的实际情况, 所以不能通过最优算法来求得每个问题实例中的最优解, 因此启发式算法的求解比较常用。针对最优算法, 可以用启发式算法来这样进行定义:如果算法是基于经验或直观构造, 那么在能够接受的花费下为待解决优化问题的每一个实例给出一个可行解, 是无法事先预约这个可行解与最优解存在的偏离程度的。通过启发式算法寻找出最优解的近似解, 可以在可接受的花费的前提下得到一个满意的问题解, 使得生产实际中能够应用优化下料技术, 所以启发式算法在现阶段的研究较多, 根据规则的不同, 启发式算法的构成也不同。

2 设计优化步骤

2.1 零件分组

对于下料的实际生产当中, 我们需要安排许多种类的零件, 通过长度对零件进行分组, 对每组的四个零件优化, 这种方法所得到的最优解只是每组内的一部分的最优解而不是得到整体的。我们可以运用这样的分组原则:将截面规格相同的零件按照尺寸长多进行从大到小的排列, 取出两个最小长度零件和最大长度零件, 将取出的这四个零件合成一组, 使得零件可以长短搭配。根据这种分组原则, 不仅可以使安排所有这四种零件的概率得到提高, 使原材料的消耗得到降低, 还使下料的排列方式数量得到减少, 并提高了优化计算程序总体运行速度, 使系统的稳定性得到了加强。

2.2 求全部下料方式

分组后可通过下面步骤求出下料方式: (1) 零件的种类数不大于4时, 可以直接进行数学模型的计算, 如果零件不少于1种时, 根据前面的分组原则对零件进行分组。 (2) 对截面规格相同的原材料的尺寸长度种类数进行判断, 如果种类数是1时, 可以直接求得所有下料方式, 如果种类数比1大时, 要先将对应的1种原材料尺寸的所有下料方式求出, 这时所求的4种零件只剩下3种零件了, 依次进行判断, 可以得到全部的下料方式, 也就是4种零件所对应1种原材料的尺寸长度的所有下料方式。 (3) 将每组零件对应的原材料的所有下料方式相互混合在一起, 就可以得到了每组零件对应于所有原材料的各种下料方式, 线性规划方程组当中的系数矩阵正是由这些下料方式组成。

2.3 关于整数线性规划

求出下料方式以后就可以建立整数线性规划的相关模型了, 对于设计角钢的优化下料, 决策变量要求只取出整数值, 求出的解中不能够出现小数或分数, 使所用原材料总根数最小等于目标函数和以达到零件需要量为约束条件所进行的数学规划问题就是角钢优化下料问题。可表示为:MAXZ=CX;Aχ≤b;χ≥0。

其中, C代表下料方式的最大可利用长度。

对与不等式约束条件极值问题, 最普通的算法和一般求解的方法是单纯形法, 总体思路:先要引进人工的变量, 把数学整体模型转变成标准的线性规划方面的问题。通过已经得到的等式相互约束条件将目标函数当中的某些自变量约去, 使得非基变量变成零, 求出一组基向量所对应的基本可行解, 通过这种基本可行解进行考察, 看使目标函数达到最小值的是不是这一点。不是话, 再去考察其他的基本可行解使得目标函数达到最小值。

对于原始单纯形法, 每次进行迭代都要将整个单纯形表改写, 对于单纯形表上的所有数据, 都要参与到运算当中, 某些运算其实是不必要的, 如果约束方程的变量个数n和个数m比较大时, 对于计算机的计算量和储存量要求都很大, 会导致计算量和储存量方面的浪费, 对单纯形法进行改进, 将单纯形法当中需要的计算依次按格式排列, 防止出现不必要的计算。

3 结束语

对于角钢的优化下料系统, 整个系统的核心是优化计算模块, 所以想要实现计算功就要有高性能的算法。我们要加大对下料系统的算法研究, 以确保满足当前阈值的下料方式, 兼顾加工难度、利用率以及整体计算时间。本篇文章将铁塔厂角钢优化下料工作做为应用的背景, 不断提高原材料利用率和下料车间工作效率, 从生产管理和下料技术两个的角度出发, 探究了角钢的优化下料系统, 优化了下料工作的整体性, 加大了市场竞争力和企业快速反应能力。

摘要：国家不断加大对电力建设的投入, 使市场对电力铁塔的需求也不断增加, 所以必须提高对铁塔设计制造技术要求, 以达到相应水平。目前许多企业原材料利用率和生产效率不够高、信息化水平比较低、生产成本居高不下、工作流程不合理, 怎样去解决这些难题, 并不断提高自身竞争力是现在需要解决的主要问题。

关键词：铁塔制造,下料问题优化算法,生产管理下料系统

参考文献

[1]李琼, 金升平.一维优化下料问题的模型与算法的综合比较[J].武汉交通科技大学学报, 1998.

[2]华中平, 张立.基于线性规划的角钢优化下料算法研究.湖北工业大学学报, 2005.

篇4：教案算法与程序设计思想

将数学归纳法的思想引入算法与程序设计的教学中可以结合数学和信息技术两门课程优势,使学生利用已有的知识和技能去设计正确的算法,达到培养信息素养的目的。同时,可以开辟新的教学方法,从有别于传统程序设计教学的角度,快速高效地在中学生中普及算法知识。

以下是数学归纳法教学思路与传统程序设计思路的对比。

数学归纳法是一种数学证明方法,典型地用于确定一个表达式在所有自然数范围内是成立的或者用于确定一个其他的形式在一个无穷序列是成立的。

用数学归纳法进行证明的步骤:

1.(归纳奠基)证明当取第一个值时命题成立;证明了第一步,就获得了递推的基础

2.(归纳递推)假设当前命题成立,证明后续命题也成立;证明了第二步,就获得了递推的依据,但没有第一步就失去了递推的基础。只有把第一步和第二步结合在一起,才能获得普遍性的结论;

3.下结论:从第一个值开始的所有后续命题都成立

数学归纳法的第二种形式:第二数学归纳法原理是设有一个与自然数n有关的命题,如果:

(1)当n=1回时,命题成立;

(2)假设当n≤k时命题成立,则当n=k+1时,命题也成立。

从上可以看出数学归纳法有着很强的递推关系,而计算机的很多算法都具备递推关系。由此,我们可以考虑,在中学NOIP的教学过程中,可以利用数学归纳法来进行教学。

一、用于递归的教学

程序调用自身的编程技巧称为递归。这种编程技巧可以解决很多算法问题。它也是算法的核心思想和描述方法。

一般来说,递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。

对比数学归纳法,我们可以这样理解:递归的边界条件即为数学归纳法的第一步,也就是当取第一个值时命题成立。递归的过程就是归纳递推的方法。即假设当前命题成立,证明后续命题也成立。

例如:阶乘计算

递归的思考方式:

1.边界条件n=1时:n!=1。

2.递归过程n!=n*(n-1)!

数学归纳法的思考方式:

1.n=1时,1!=1成立

2.假设(n-1)!可以求出,则n!=

n*(n-1)!必定可以求出。

我们可以看出,递归的思考方式和数学归纳法是有一定相似之处的。

使用数学归纳法,除了可以引入解题的方法之外,还可以同时在数学上证明该思路是正确的。可以加深初学者对递归的认识并降低难度。

又例如汉诺塔问题的思考:

递归的思考方式:

1.边界条件

只有一个盘子时,盘子从A柱移到C柱

2.递归过程

n-1个盘子从A柱移到B柱,剩下的盘子从A柱移到C柱,n-1个盘子从B柱移到C柱

数学归纳法的思考方式:

1.n=1时盘子可移,盘子从A柱移到C柱

2.假设n-1个盘子可以从一个柱子移动到另一个柱子,寻找n个盘子从一个柱子移动到另一个柱子的方法。

在初学递归的同学中,汉诺塔问题是学习的难点和重点。我们需要从栈、函数的调用原理、题目的思考方法来讲述。从数学归纳法的思考方式来看,我们可以更好的加深学生对递归的理解。同时引入数学归纳法的思考方式可以更容易的证明解题的正确性。

二、用于分治的教学

一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。这是分治算法的核心思想。

我们也可以看到:“最后子问题可以简单的直接求解”即为数学归纳法中命题n=1时的阶段,“问题的解的合并”即为数学归纳法中当n≤k时命题成立推n=k+1时命题成立的阶段。

例如:二分排序算法利用数学归纳法的讲解思路

1.n=20=1时,1个数据自然排序成功。

2.假设n=2k-1时,2组2k-1个数据分别有序,则n=2k时,可将两组分别有序的数据通过归并排序合并,使之有序。

可以看到,数学归纳法的讲解思路不同于普通的分治排序的思考方式。但这可以激发学生从多方面思考算法的求解思路。

(3)用于动态规划的教学

动态规划是一种在数学和计算机科学中使用的,用于求解包含重叠子问题的最优化问题的方法。其基本思想是,将原问题分解为相似的子问题,在求解的过程中通过子问题的解求出原问题的解。动态规划的思想是多种算法的基础。

动态规划思想中“将原问题分解为相似的子问题,在求解过程中通过子问题的解求出原问题的解”所具备的递推性质,决定了动态规划的问题思考中也可以使用数学归纳法的思想。其中的状态转移方程,便是第二数学归纳法中当n≤k时命题成立,推n=k+1时,命题成立的步骤。这里的性质决定了使用数学归纳法来思考,可以解决子结构和多阶段规划(无后效性)问题。

如题:

3 8

8 1 0

2 7 4 4

4 5 2 6 5

请编一个程序计算从顶至底的某处的一条路径,使该路径所经过的数字的总和最大。规定:

●每一步可沿直线向下或右斜线向下走;

●1<三角形行数≤100;

●三角形中的数字为整数0,1,…,99;

在动态规划的题目中,数学归纳法的归纳奠基思想起到了寻找边界条件的作用;其递推思想则起到了划分阶段,定决策并写出状态转移方程的作用。

从这里可以想到,当三角形只有一个结点时,问题自然解决。需要解决的命题是从已知1个结点的三角形结果推出具有3个结点的三角形的结果。从已知3个结点的三角形结果推出具有6个结点的三角形的结果,以此类推;即由n=k-1时命题成立推出n=k时命题成立。这样,我们就可以引入顺推和逆推的方法。最终得到该题的状态转移方程。

在整个的教学过程中,学生所学的知识始终由原有的知识进行迁移转化,利于学生的理解和接受。可以大大简化动态规划的教学难度,加快学生入门的速度。

从这里可以看到,凡是具备分层和递推形式的问题都可以使用数学归纳法的思想。所以在进行算法教学中,可以将数学归纳法思想作为主线,贯穿于递归、分治和动态规划的教学中。使学生从纵向上加深对算法的理解。学生在学习过程中,整合了数学和程序设计。

篇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：《算法的基本思想》教案

第二章算法初步

《算法的基本思想》教案（第１课时）

一、教学目标：

1．知识与技能

（1）通过对解决具体问题过程与步骤的分析，体会算法的思想，了解算法的含义；

（2）能够用语言叙述算法；

（3）会写出将自然数分解成素因数乘积的算法；

（4）会写出求两个自然数的最大公因数的算法和两个自然数的最小公倍数的算法。

2．过程与方法

通过对物品价格的猜测，体会猜测者的基本思路，得到一个一般步骤，而这个步骤就是一个算法。结合具体问题，模仿算法步骤，写出将自然数分解成素因数乘积的算法和求两个自然数的最大公因数的算法，从而体会算法的基本思想，了解算法的含义。

3．情感态度与价值观

通过本节的学习，使学生对算法的思想有一个初步的认识,体会算法的基本思想——程序化思想，在归纳概括中培养学生的逻辑思维能力，从而进一步体会算法与现实世界的密切关系。

二、教学重点与难点：

重点：体会算法的思想，了解算法的含义；

难点：能够用语言来叙述算法。

三、学法与教学用具：

学法：学生通过对具体问题的感受，主动思考，互相交流，共同讨论，总结概括，从而更好地完成本节课的教学目标。

教学用具：某件物品、电脑、多媒体

四、教学设想：

1．创设情景

客串中央电视台的《幸运52》，让学生快速猜测出某件物品的价格。

2．探索研究

请同学们从老师和参与者的对话中感受参与者猜测的思路，试着叙述出参与者的思路。如果你是参与者，你会如何又快又准地猜出价格？用我们学过的一种思想，又将如何叙述？

实际上，我们可以把这种思想概括如下：（在给定区间为（a，b）的前提下）

1.报出首次价格T1；

2.根据老师的回答确定价格区间：

（1）若报价T1小于商品价格P，则商品的价格所在区间为（T1，b）；

（2）若报价T1大于商品价格P，则商品的价格所在区间为（a，T1）；

（3）若报价等于商品价格P，则游戏结束。

3.如果游戏没有结束，则报出上面确定的价格区间的中点T2，这个确定的价格区间就是新一轮报价的给定区间了。

按照这种方法，继续判断，直到游戏结束。

然而上述的这一系列的步骤就是解决实际问题的一个算法。

相信同学们对这个过程都有了一个初步的认识，但是还不够清晰，下面我们来看一个具体的实例。

3．例题分析

例题：在给定素数表的条件下，设计算法，将936分解成素因数的乘积。（4000以内的素数表见附录1）

让学生叙述解题的过程，了解一个初步的步骤，再根据这个解题的过程和学生共同完成这个算法的步骤,实质上就是用短除法将自然数分解成素因数。

解算法步骤如下：

1.判断936是否为素数：否。

2.确定936的最小素因数：2。936=2×468。短除法

3.判断468是否为素数：否。

4.确定468的最小素因数：2。936=2×2×234。

5.判断234是否为素数：否。

6.确定234的最小素因数：2。936=2×2×2×117。

7.判断117是否为素数：否。

8.确定117的最小素因数：3。936=2×2×2×3×39。

9.判断39是否为素数：否。

10.确定39的最小素因数：3。936=2×2×2×3×3×13。

11.判断13是否为素数：13是素数，所以分解结束。

分解结果是：

篇7：教案算法与程序设计思想

1.教学目标

1.知识与能力：我国近代科技、思想文化的特征和主要成就。京张铁路、侯氏制碱法、《海国图志》、《天演论》中译本等知识点。

2.过程与方法：根据课文和插图中有关的资料，讲解、分析魏源的典型事迹，指导学生“照方抓药”，主动学习有关其他三人的史实；魏源、严复、詹天佑、侯德榜取得成就的原因是共同的（精神、意识、品质、文化素养等），但具体表现又有所区别（学科领域、时代）；联系原始遗存的知识举例说明“物竞天择、适者生存”道理。

3.情感、态度与价值观：魏源、严复、詹天佑、侯德榜等人救亡图存、振兴中华，努力学赶超世界先进文化，热血报国的赤子之心，永远值得我们学习；只有先进文化才能代表社会发展的方向，只要谁先进，就要向谁学。

2.教学重点/难点

1.教学重点：教师如何引导学生，通过分析中国近代史这四位文化名人的典型事迹，概括出本课的主题，从而在情感态度和价值观上，对学生产生潜移默化的影响。2.教学难点：教师如何采用不同的方式，引导学生分析典型事迹，概括主题思想，并激发学生的爱国热情。

3.教学用具

电子白板

4.标签

八上历史21课,科学技术与思想文化

教学过程【课前检测】

1、近代交通：19世纪初，西方发明

、，后来传入中国，使人们出行的速度大大加快。

2、近代通讯：19世纪70年代以后，中国开始架设有线电报。

3、文化生活的变迁：①近代以来

和

传入中国，丰富了人们的精神生活。②鸦片战争后，外国人在上海创办

，后来，中文报纸出现，最著名的是1872年在上海创办的，报纸成为人们获取信息、了解社会的主要

。③1897年在上海创办的，是近代中国历史最长、规模最大的文化出版机构。【自学引导】

一、开眼看世界的思想家

1、中国近代向西方学习思想是在什么情况下产生的？代表人物有谁？

2、鸦片战争时期开眼看世界的思想家是谁？他的思想主张是什么？有何著作？其内容和目的是什么？

3、戊戌变法时期的启蒙思想家是谁？他的思想主张是什么？有何著作？书中有哪些进步观点？有何历史作用？

二、近代科学技术的发展

阅读132～133页课文，回答下列问题。

1、近代杰出的铁路工程师是谁？请概述他的贡献？

2、近代著名化学家是谁？他的主要成就是什么？

三、完成下列表格

近代科学技术与思想文化成就简表

课堂小结

近代中国是个多灾多难的国家，是个备受列强凌辱和蹂躏的国家，为了振兴中华民族，抵制外来的侵略，在近代史上，许多爱国知识分子不甘失败，积极展开挽救民族危亡的活动。他们在思想上、科技上学习西方先进文化，勇敢地进行赶超和创新，做出了杰出的贡献。

课后习题

一、单项选择题

1.中国人自行设计和施工的第一条铁路干线是（）A．滇越铁路

B．唐胥铁路 C．京张铁路

D．凇沪铁路 2.20世纪上半期，在制碱工业方面做出突出贡献的科学家是 A．詹天佑

B．李四光

C．侯德榜

D．茅以升 3.提出“师夷长技以制夷”的思想家是（）A．林则徐

B．魏源

C．严复

D．康有为 4.严复翻译的著作是（）

A．《海国图志》 B．《盛世危言》 C．《四洲志》 D。《天演论》 5.魏源和严复的主张的共同点是（）

A．师夷长技以制夷

B．学习西方的长处，改变中国的现状 C．物竞天择，适者生存

D．效法西方，推行维新改革 6.中国历史上第一部较详系细介绍西方的著作是：（）A.《海国图志》 B.《四库全书》 C.《天演论》 D.《四洲志》二.材料分析题

材料一：“师夷长技以制夷”。材料二：要救国，只有效法西方，推行维新改革。请回答：

1.材料一是谁的主张？他写的著作及主要内容是什么？

2.材料二是谁的主张？他的译著是什么？同他观点相同的派别是什么？

三、简答题

列举我国近代著名的科学家及其主要成就。

篇8：教案算法与程序设计思想

关键词：模型设计,电梯控制,自动生成代码,HDLcoder

随着嵌入式系统的普及,人们对产品的安全性、实时性、可操作性、特定功能等要求越来越高,这大大增加了嵌入式系统的复杂性和开发难度。在传统的解决办法中,整个项目开发周期可分为4个阶段:需求分析和技术规范、设计、实现及测试与验证。在这种传统的开发流程中,缺少一个必要的工具把4个阶段有机联系起来,从而导致了开发过程中的问题,例如基于文本的需求分析和规范定义,导致不同人产生不同的理解,使得最后开发出的产品可能不符合客户的需求;其次,在设计阶段可能需要昂贵的物理原型来验证算法是否满足要求;而在实现阶段,通常利用手工方法完成编码,不但费时费力,而且不可避免地引入人为失误。以上问题若等到最后的测试验证阶段才得到修正,不仅会增加开发成本,严重的会延误开发周期,增加开发风险。基于模型的设计提供了一种通用的开发和测试平台,使得4个阶段有机地结合在一起,无论在哪个阶段发现问题,都能及时、方便地进行定位、查错,这样既可以保证设计和需求的一致性,又可以避免手工编码的冗长过程,保证项目的开发周期[1]。

基于模型的设计对应传统的项目开发方法同样分为4个阶段,分别是:可执行的技术规范,定点生成,代码自动生成,连续的测试和验证。

1 可执行的技术规范

基于模型的设计始于可执行技术规范的建立。MathWorks公司的Matlab/Simulink及专用的模块,为嵌入式算法的高层描述提供了一个图形化环境。电梯控制算法的可执行规范如图1所示[2]。

如图1所示,该嵌入式系统分为3个部分:中间是该系统的子系统,左边是输入信号,右边是输出信号。子系统是该嵌入式系统的核心,负责输入信号的接收、处理以及给执行机构发出相应的指令;输入信号分为楼层面的输入命令和电梯箱内的输入命令;输出信号又分为升降电机控制信号和电梯门的控制信号。

算法实现在 Stateflow 有限状态机中建模完成,如图2所示[3]。

共分为3个状态:“Elevator_Manager”、“Elevator_A”、“Elevator_B”。“Elevator_Manager”负责电梯资源的调度:当有命令输入时,首先判断是不是有效命令,如果是则根据命令来判断是启用电梯A还是电梯B;“Elevator_A”和“Elevator_B”处理各自收到的服务指令:上升或者下降,到了指定位置打开门,并延时一段时间后关闭,也包括在紧急情况下,停在最近的楼层并打开电梯门。

建模完成后即可仿真。在Matlab/Simulink 环境中直接运行模型,测试、验证该算法的可行性、实时性、稳定性及功能的完整性。在此期间,设计团队的每个成员都应参与,理解并完善该模型[4]。

2 生成定点模型

在设计可执行的技术规范时,重点在于设计符合系统级要求的算法,而忽略了实现细节。比如本嵌入式系统最终要用一款普通的FPGA模块实现,就要考虑资源的有限性以及FPGA本身的特点。

(1)参数变量定点化。

因为本设计最终的实现目标是FPGA,所以必须将输入变量、中间变量、输出变量以及常量都要从双精度浮点型转化为定点型。在Simulink环境很容易实现这一点。定点数整数部分和小数部分的位数应以实际需要的精确要求决定,也可以参考Simulink系统推荐的方案。

(2)算法重新设计。

在算法的实现中调用了两个Matlab提供的库函数:一个是取绝对值;另一个是取整。如果最终要在FPGA实现该算法,则必须重新编写两个函数。设计采用添加两个Embedded Matlab函数实现,如图4所示。

在下一步代码自动生成之前,还必须重新编写该算法中有类似C语言中“for”循环结构的函数。这样的函数不止一个,下面以请求服务为例说明重新设计的思路与方法。

Stateflow可用图形化的流程图定义函数,也能使用类似于C语言中“for”循环结构体,如图4所示的enqueue()服务请求队列函数。

当某一楼层服务请求按钮第一次被按下时,如果请求队列第一个请求服务已经是该楼层则不用处理,否则进入循环体。只要符合条件就停留在第二个节点,直到找到该服务队列的末尾,结束循环;此时如果已经大于等于最好请求服务数则返回,否则把该楼层号插入到服务队列的末尾。现采用从头到尾逐个判断是否为空的方法来查找请求队列最近的空位并把该楼层号插入其中。

在定点化过程中,每一次改变必须进行验证和仿真以确保转换的正确性,而且自始至终都要验证技术规范。

3 自动生成代码

MathWorks公司提供的HDL Coder功能模块,可以将Simulink/Stateflow中的模型自动转换成可综合的HDL或者VHDL语言。在生成代码之前,必须做模型的一致性检查。如果检查没有错误,则可以自动生成代码。但第一次检查往往会有错误,必须根据错误提示改正。

4 连续的测试和验证

基于模型的设计从建立可执行的技术规范时,就可以不断地进行测试和验证,检测设计变更对系统的影响,并快速跟踪变更的来源。在代码自动生成之后,既可以通过MathWorks公司的ModelSim链接,在Simulink环境中使用 Modelsim对 HDL设计进行仿真,也可以通过其他途径进一步仿真。文中采用Altera公司的Quartus软件进行综合、仿真,结果如图6所示。

通过设置恰当的输入测试向量,验证了代码有效性与功能的完整性:在固定的时钟节拍下,电梯A和电梯B各自响应本电梯的请求服务,并在到达请求楼层后延时一定的打开电梯门,再延时一段时间后关闭;当楼层面有请求服务时,按就近原则决定是电梯A还是电梯B去响应;当按下火警按钮时,电梯A和电梯B如果已经停止,则立即打开电梯门,如果还在升降中,则在下一次到达某楼层面时及时打开电梯门;再次按下火警按钮时,关闭电梯门,如有未执行完请求任务则继续执行。

5 结束语

基于模型的设计提供了一个可行的设计方法,使用该方法,可以在嵌入式系统的开发过程中进行不断地测试和验证,利用HDL coder代码自动生成工具可以快速、有效地生成优化的、可综合的目标代码,缩短了开发周期,降低了开发成本。

参考文献

[1]刘杰.基于模型的设计及其嵌入式实现[M].北京:北京航空航天大学出版社,2010.

[2]MURPHY B.使用基于模型的设计进行虚拟测试[J].电子设计应用,2010(z1):46-48.

[3]LIDRBAUCH D.基于模型的设计加速验证功能[J].电子设计应用,2009(7):53-55.

篇9：教案算法与程序设计思想

关键词：将军令；动态密码；原理；算法

中图分类号：TN32

文献标识码：A

文章编号：1000-8136(2009)29-0125-02

“将军令”是广州网易互动娱乐有限公司自主研发的、具有完全知识产权的高科技身份认证产品，专门用来保护网易通行证(游戏账号)、直销商账号的密码。“将军令”是每隔1min(60s)产生一个全新的、不能重复使用的密码(6位)，俗称“动态密码”。采用“将军令”后，网易以“账号+密码+动态密码”的形式对游戏ID进行保护，大大提高了账号的安全性。对于将军令的工作原理，很多人提出自己的设想，笔者也就自己的研究，进行如下阐述。

“将军令”的实际工作流程很简单：即用户端(“将军令”本身)产生一个动态密码，然后将这个动态密码和服务器端进行匹配。由于用户端在出厂之后，同服务器端就再没有物理上直接的联系，因而，如何与服务器端保持逻辑上的同步是最大的问题，即如何保证用户端产生的动态密码与服务器端验证的动态密码是一个密码。

1第一种设想

在“将军令”内置微型芯片，里面保存大量“以6位数字为一组”的预定数组(6位数字动态码)，每60s自动读取下一组新数组，数组的排列顺序无规律并无一相同，但全部已经预先存放好，利用循环模式，当读完最后一组数后便从头再开始读取第一组数组。主机服务器端也同样预先存放好同样的数组列，启用“将军令”时以序列号来识别该取用哪一条数组列。这种方法是一种最易实现的方法，但这也是一种最易被破解的方法，安全性较低。

2第二种设想

这种设想是利用算法来实现动态密码的产生。

算法思想1：用户端在出厂时就植入一个算法，这个算法同样会被保存在服务器端。这个算法不一定要很复杂，比如f(x)=aX+b，X最好是一些独特的，各个“将军令”都不重复的数字，比如“将军令”的序列号等。a可以是一个固定的数字，而b可以是一个动态变化的数字，如第1次产生动态密码，b就为“1”；第2次产生动态密码，b就为“2”……

算法思想2：用户端产生的动态密码是一个与时间有关的动态密码，即密码M与时间T之间存在着关系：M=rand(TX)，rand()为随机函数，TX为随机函数的种子，x为另一因素，比如“将军令”的序列号等。

这里，x是一个服务器端已知的变量，出厂时就已经设定了，最大的可能是“将军令”的序列号所对应的一个因子，在生产“将军令”写入初始数据的时候，同时被植入用户端和服务器端，由于每个“将军令”的序列号是唯一的，因而，拿不到“将军令”就无法知道x，也就无法知道动态密码M。

显然，只有因子X是不够的，M=rand(x)是可以产生一个密码M，但这个密码M显然无法动态变化，也就失去了意义，因而时间因子T也同样不可缺少。但是，引入时间因子T之后，又将产生一个问题：就是用户端和服务器端时间同步的问题。

时间同步的同题，笔者认为可以这样解决：服务器端固定T₀，引入因子△t，服务器端植入△t，△t为用户端时钟同服务器端时钟之差，即△t=T₃-T₁这样，用户端的密码M=rand(T₃X)，服务器端密码M=rand((T₁+△t)X)。对于成千上万的用户端在服务器端只要记录了△t就可以了。这个△t，可以在“将军令”生产的时候植入服务器端予以记录。开通“将军令”后，在提交序列号和动态密码的时候，服务器端动态的调整△t，服务器端计算M=rand[(T₂+△t)X]，并且在△t的基础上，计算出……，△t-5*60，△t-4*60，△t-3*60，△t-2*60，△t-1*60，△t，△t+1*60，△t+2*60，△t+3*60，△t+4*60，△t+5*60，……这个数列。具体数列长度根据需要来定，由于是产生随机6位数的函数，在这个数列中是不会出现重复的M的。这样，就可以计算出△t附近前后相差n分钟所产生的密码M，只需要比对提交的动态密码与数列中的哪个值对应，就可以动态的调整△t。假设，动态密码与△t-2*60对应的密码相同，就可以调整△t=△t-2*60。这样，解决了用户端从出厂到开通使用所产生的时间误差。这个n，根据实际需要制定。

在使用“将军令”的时候，采用同样的方法可以同步。在确定了At后，服务器端在每次验证的时候，只要算出M1=rand[(TI+△t-y)x]，M=rand[(TI+At)X]，M2=rand[(T)+△t+y)x]，就可以算出At附近y秒的时间的密码M，就是允许“将军令”有y秒的时间误差。利用上面的算法来实现动态密码的产生显然要比第一种方法的安全性要高很多。

3第三种设想

这种设想利用一个相对复杂的映射来实现动态密码的产生。

它可能是根据：年，月，日，时，分，秒。这样的话，可以把“将军令”看成是一个计算器，计算出用户所需要的数字，然后与服务器通过同样方法对计算出来的数字进行比对。

假设：“将军令”出现的6位数字，我们分别设为a，b，c，d，e，f，将军令的序列号为x。

a=年*x

b=月*2X

c=日*3X

d=时*4X

e=分*5X

f=秒*6X

但是，如果通过这个映射来计算出动态密码的话，同样也会有时间同步的问题需要解决，这就可以参照上面的算法思想进行处理。

4结束语

篇10：《加减法的简便算法》教案设计

教学内容：

教科书第55页的例1、例2，练习十二的第7―12题。

教学目的：

1.使学生理解并掌握从一个数里连续减去两个数，改为从这个数里减去这两个减数的和的简便算法。

2.通过求加、减法算式中的未知数，使学生进一步理解加、减法各部分间的关系，为学习简易方程和列方程解应用题做较好的准备。

教学重点：求加、减法算式中的未知数

教学难点：理解加、减法各部分间的关系

教具准备：小黑板

教学过程：

一、教学例1

出示例1：育名小学图书室新买来130本图书。其中故事书46本，科技书34本，其余提连环画。买来连环画多少本?

指名学生读题，并说一说，这道题可以用几种方法解答，再让学生用两种方法解答出来。解答完后，指几名学生说说是怎样解答的，教师板书出两种解法：

130―46―34 130―(46+34)

=84―34 =130―80

=50(本) =50(本)

引导学对比这两种解法：

“这两种解法有什么区别?”(第一种解法是先从总本数中减去故事书的本数，再从减得的差中减去科技书的本数，求出连环画的本数;第二种解法是先算出故事书与科技书的和，再从总本数中减去求出的和，求出连环画的本数。)

“它们的结果怎样?”(两种算法的结果相同。)

“这道题用哪种方法计算比较简单?”

使学生初步理解：从一个数里连续减去两个数等于从这个数里减去这两个减数的.和，在这道题中用后一种解法计算比较简便。

二、教学例2

1.出示例2：计算295―128―72。

先出示学生观察题里的数目有什么特点，想一想：能不能用学过的知识使计算简便。然后引导学生联系例1思考：因为128与72的和正好是整百数，从295中依次减去128和72，等于从295中减去128与72的和。所以，先算(128+72)，再算295―200，计算起来比较简便，教师边分析边板书出计算步聚：

295―126―72

=295―200

说明虚框中的计算步聚初学时可以写出来，以后可以省略不写。

2.做第55页的“做一做”。

让学生独立完成，订正时，说一说简算的依据是什么。

三、巩固练习

做练习十二的第7―12题。

1.第7题，学生做完后，教师还可以再增加几道百数减去两位数的题，如：300―53，400―67等，让学生口算。

2.第8题，让学生自己填数，并说一说是怎样想的。

3.第9题，先让学生自己做，订正时，说一说口算方法的依据。

4.第10题，计算时，告诉学生，可以根据自己的情况确定写不写简算过程。

篇11：教案算法与程序设计思想

教学目标

1、使学生理解、掌握加法结合律.

2、能够应用加法的交换律和结合律进行简便计算.

教学重点

对加法结合律的理解、掌握和应用.

教学难点

加法结合律的运用.

教学步骤

一、铺垫孕伏.

1、什么叫加法交换律?用字母如何表示?

2、根据运算定律在下面的()里填上适当的数.

43+67=()+()35+()=65+()

()+18=19+a+100=()+()

3、下面各等式哪些符合加法交换律?

270+380=390+260 20+50+80=20+80+50

a+400=400+a140+60=60+140

谈话引入：以上，我们运用了加法的意义及交换律解决了一些问题，那么关于加法还有没有其他的规律性知识?这些知识又有什么用途呢?这节课我们继续学习这方面的知识--加法结合律和简便运算.(板书课题)

二、探究新知.

(一)教学例3、观察下面每组的两个算式，它们有什么样的关系?

(12+13)+14○12+(13+14)

(320+150)+230○320+(150+230)

1、教师提问：(1)上面等式两边算式有什么相同点?有什么不同点?

相同点：都有三个加数，左右两边的三个数相同;

不同点：加的顺序不同.

(2)每组两个算式的结果怎样?用什么符号连接?每组算式说明什么?

2、归纳加法的结合律.

3、用字母表示加法结合律.

如果用字母a、b、c分别表示3个加数，怎样用字母表示加法结合律呢?

教师板书：(a+b)+c=a+(b+c)

等号左边(a+b)+c表示先把前两个数相加，再同第三个数相加.

等号右边a+(b+c)表示先把后两个数相加再用第一个数相加.

a、b、c表示的数是什么范围的数?

4、练习：根据运算定律在下面的□里填上适当的数.

(25+68)+32=25+(□+□)

130+(70+4)=(130+□)+□

(二)教学简便算法.

应用加法结合律我们可以改变一些数的运算顺序，但应用加法交换律更主要的一点是可以使一些计算简便.

1、例4计算480+325+75

教师提问：同学们想要计算480+325+75，怎样计算比较简便?为什么?应用了什么运算定律?(学生试算)

教师板书：

480+325+75

=480+(325+75)

=480+400

=880

2、例5计算325+480+75

教师提问：这道题怎样算比较简便?为什么?应用了什么运算定律?(集体订正)

325+480+75

=325+75+480

=(325+75)+480

=400+480

=880

教师提示：哪一步可以省略?

325+480+75

=325+75+480

=400+480

=880

3、比较例4、例5在应用运算定律方面的不同.

例4没有调换加数的位置，直接应用了加法结合律进行了简算;

例5要使325与75相加，则必须先应用加法交换律将75交换到480的前面，再应用加法结合律简算.

4、反馈练习：137+31+63，怎样计算比较简便?用了什么定律?

5、想一想，过去哪些计算应用了加法的结合律?

(在做口算加法时应用了加法结合律)

如：36+48

36+48=36+(40+8)=(36+40)+8=76+8=84

教师说明：根据加法结合律不仅可以做口算加法，还使一些计算简便.简算时要注意数字特点.

三、巩固发展.

1、根据运算定律在下面的□填上适当的数.

369+258+147=369+(□+147)

(23+47)+56=23+(□+□)

654+(97+a)=(654+□)+□

2、下面哪些等式符合加法结合律?

a+(20+9)=(a+20)+9

篇12：算法与程序设计笔试题

1、extern “C”{}是什么含义?用来解决什么问题，(10分)

2、至少说出两种经典设计模式，并举例说明使用场景，有伪代码更加.(10分)

篇13：教案算法与程序设计思想

1 PageRank链接分析算法

Page Rank算法建立在随机冲浪模型上，将整个WWW看作一个有向链接图：G=(V,E)，其中V是节点网页集，E是边集(从页面i到j的链接)。基本思想是：如果一个页面被其他页面引用，则该页面可能是重要页面;一个页面尽管没有被多次引用，但被一个重要页面引用，那么该页面也可能是重要页面;一个页面的重要性被平摊到它所引用的所有页面[1]。

Page Rank算法基于整个WWW的的链接结构来计算各网页的重要性，初始计算方法如下公式(1)所示：

其中PRn+1(P)表示第n+1次迭代运算中网页P的PageRank值，Ti表示链入P的网页，C(Ti)表示Ti链出的网页总数，N为网页的总数量，d为阻尼系数，Google通常取值为0.85。

有向链接图中每条边的权重值是链接分摊出去的Page Rank值，如果定义n维列向量P来表示各网页的Page Rank值，则P=(P(1),P(2)，…，P(n))T。定义A为图的邻接矩阵，矩阵元素的值就是网页间的链接权重，则求n个公式(1)的方程可以转换成矩阵：ATP=P，计算Page Rank值就转化成了计算邻接矩阵A的特征向量。预先给定一个初值，经过迭代计算后，最终可得到网页的Page Rank排名值[2]。

2 网页分块思想

网页具有典型的语义分块特征，网页分块是按照该特征来理解和分析网页内容的新技术，在网页文档分类、信息提取、搜索引擎优化等方面具有重要作用，主要有基于DOM树分析、页面信息分析、页面布局关系分析及视觉特征分析等方法[3]。

VIPS是DengCai等人提出的一种基于视觉特征分析的网页分块算法，它将页面整体视为一个视觉块，并根据预设内聚度(PDo C)进行迭代分割而得到划分结果[4]。该算法将网页看作三元组：Ω=(Ο，Φ，δ)，其中Ο=(Ω1，Ω2，…，Ωk)，表示给定页面上的所有的不重叠的语义块集合，而每一个语义块Ωi又可被定义为三元组Ωi=(Οi，Φi，δi)，如此迭代循环。Φ=(φ1，φ2，…，φT)，表示当前页面上的所有水平和垂直分隔条(不真正存在，但具有一定的宽度和高度)的集合。δ=(ζ1，ζ2，…，ζm)，描述Ω集合中两个语义块间的关系，可用δ=Ο×Ο→Φ∪{NULL}描述。其中每个ζ都是一个(Ωi，Ωj)二元组，表示块Ωi和Ωj之间存在一个分割。

VIPS算法将整个分页过程分成页面块提取、分隔条提取、语义块重构三个步骤，并组成一次语义块检测的完整过程(图1)。当全部的语义块被提取出来以后，整个网页基于视觉的内容结构就构建完成。

3 基于网页分块思想的Page Rank算法

传统Page Rank算法将链接关系定位在页面之上，无法辨识是否与主题内容相关，搜索结果中容易出现无关网页，产生“主题漂移”、偏重“旧网页”等问题[5]。网页分块操作将一个页面分割为多个语义块，不仅过滤了与页面语义无关的导航、广告、友情等链接信息，而且有助于提取主题信息。基于网页分块的Page Rank算法，需要重构网页与块、块与块之间的关系[6]。

3.1 网页与网页块关系定义

网页关系图定义为Gp(Vp,Ep,Wp)，其中顶点Vp为网页集合，边Ep为链接关系集合，Wp为权重矩阵，如果网页i有链接指向网页j，则Wp(i,j)简单设为1，否则为0。网页块到网页间的关系矩阵Z可定义成如下公式(2):

其中Si为块i所链接的网页总数，Zij为用户从块i浏览网页j的概率。网页与网页块间的关系矩阵X可定义成如下公式(3):

其中fp给网页i中的每个块赋予权重值，其定义如下公式(4)所示，其中α为归一化因子，使得对每个网页fp(b)的总和为1。

根据公式(2)和(3),Wp权重矩阵可重新定义成如下公式(5)，即Wp=XZ,Wp(α，β)可以理解为从页面α开始，通过其中块b跳转到页面β的概率，其中α，β属于P。

3.2 网页块与网页块关系定义

网页块关系图定义为GB(VB,EB,WB)，其中顶点VB为块集合，边EB为块链接关系集合，WB为块集合关系权重矩阵。GB构建了网页块之间的链接关系，如果浏览者从网页α中的块a链接到网页β中的块b，则块a和b之间的关系可表示成如下公式(6):

WB是个概率转换矩阵，其中权重值表示网页块a通过链接跳转到另一网页β中的块b的概率。

3.3 块级Page Rank排名值的计算

块级Page Rank算法将链接关系定位在语义块之间，处理对象由网页变成了块。与页级Page Rank算法的处理过程类似，首先定义块级矩阵A，然后对建立的块图GB的权重矩阵WB归一化行向量，构建一个概率转移矩阵A，以表示网页之间通过块的转移概率。

假设用户随机浏览网页时，第一种是通过输入URL或随意点击链接等方式访问另一页;第二种是通过某一块内的链接访问另一主题相关的网页。定义第一种方式概率为k，第二种方式概率为1-k。对于第一种方式重新定义矩阵B，其值可简单的定义为1/n,n为当前网页中的有效链接总数。因此，可类似地定义列向量P为各网页块的Page Rank值，根据矩阵(kB+(1-k)A)TP=P迭代计算邻接矩阵kB+(1-k)A的特征向量，即可得到块级PageRank值。该值反映了网页中的语义结构，与主题不相关的网页块将被弱化或过滤。

4 块级PageRank算法的改进与优化

块级Page Rank算法建立在网页分块的基础上，分块效果直接影响Page Rank排名值的好坏。由于网页格式及视觉特征的复杂性，VIPS算法分块过程复杂，程序实现困难，而且效率不高。针对这些缺陷，本文提出通过快速构造

或

标签树，引入预设结构树深度(PTDoc)阈值和叶子节点数(PLDoc)阈值来控制分块过细或过粗的问题，具体方法如下图2所示：

1)快速构造

标签树。利用HTML Tidy对网页进行预处理，构造一棵兄弟-孩子结点树，每个结点都是

标签(如果

标签多于

标签，则构建

树)，结点保留字体大小、粗细、颜色、背景等信息。

2)提取网页可视块。从根结点下面的

标签开始提取，每一个循环提取标签树中的一层

节点，不判断当前的结点是否可分。

3)检测和提取分隔条。根据页面块中的视觉信息检测块中的分割条，与VIPS算法相同。

4)重构语义块。根据检测出的分隔条，页面的布局层次被重新构建，一些页面块将被合并形成新的语义块。

5)判断是否达到要求处理的粒度。如果本层次的语义块中存在Do C值小于PdoC的语义块则转向(2)中继续新一次循环。

6)如果

标签树的最大深度比PTDoc高，切分过细，则调低内聚度PdoC阈值;如果

标签树的叶子节点数比PLDoc低，切分过粗，则调高内聚度PdoC阈值;重新转向(2)中继续新一次循环。

块级Page Rank算法结合了网页分块的语义特征，但该算法毕竟与网页内容无关，过度依赖分块来提高排序准确度的效果仍然有限。因此，本文提出在块级Page Rank算法中引入主题内容相似度，并提出如下公式(7)所示的改进算法：

其中ContSim为基于VSM(向量空间模型)[7]的网页或网页块的内容相似度，p为权重系数，用来调节Page Rank值和内容相似度的计算比重，取值范围在0到1之间。对于不同的网页内容对象而言，可以利用不同的特征作为该对象的向量，比如网页文本，可以使用TF*IDF(词频*文档频率)来建立网页的向量空间，对于网页图像，可以使用颜色、形状、纹理等低层特征来建立向量空间，从而针对这些特征计算出网页内容相似度。

5 块级PageRank算法的应用与展望

通过分析网页、语义块、超链接之间的关系，块级Page Rank算法构建出了基于分块的网页链接关系图模型。根据待查询内容的不同特征构建相应的VSM向量空间，改进后的块级Page Rank算法可以广泛地应用于Web文本、图像、视频、音频等搜索引擎系统。

根据上述算法，本文设计和实现了一个Web图像搜索原型系统，其总体工作流程如下图3所示。首先对抓取到的网页进行分块，过滤掉无用的噪音信息;接下来对网页块中的内容进行分析，提取出块内与图像相关的文本信息和链接结构，过滤掉修饰及广告等无关图像，提取出有效图像。最后分别计算出每个网页块的Page Rank值以及与查询相关的内容相似度(本文简单采用了TF*IDF频率)，将它们进行融合计算，即可得到块级Page Rank排名值。经过对比实验，融合后的Page Rank算法能够获得更好的结果排序效果。

搜索引擎排序算法是目前因特网技术应用和研究的一个热点，当前仍有许多关键技术急待解决。本文提出的基于网页分块思想的Page Rank算法只是一些尝试性的初级研究，对于如何进一步完善分块算法、计算内容相似度、融合计算等细节问题，还有待于今后深入研究。

参考文献

[1]S Brin,L Page.The anatomy of a large-scale hypertextualWeb search engine[J].Computer networks and ISDN systems,1998-Elsevier.

[2]Oren Zamir,Oren Etzioni.Grouper:A Dynamic ClusteringInterface to Web Search Results[J].Computer Networks,1999(31):58-63.

[3]郭坤银.基于Web标准的页面分块算法研究[J].微处理机,2009(12).

[4]Cai D,Yu S,Wen JR,et al.VIPS:a vision based pagesegmentation algorithm.Microsoft Technical Report,MSR-TR-2003-79,2003:10.

[5]县小平.搜索引擎PageRank算法研究[D].西安:西北大学,2010:19-21.

[6]Deng Cai,Xiaofei He,Ji-Rong Wen,Wei-Ying Ma.Block-level Link Analysis,In Proceeding of the ACM-SIGIR,2004.