算法设计与分析书中概念总结

第一篇：算法设计与分析书中概念总结

6递推步骤

7算法描述（盒图 PAD图之类的老师说看看但我不懂怎么考）

1.算法的基本性质

（1）目的性：算法有明确的目的，算法能够完成赋予它的功能。

（2）分步性：算法为完成其复杂的功能，由一系列计算机可执行的步骤组成。

（3）有序性：算法的步骤是有序的，不可能随意改变算法步骤的执行顺序。

（4）有限性：算法是有限的指令顺序，算法所包含的步骤是有限的。

（5）操作性：有意义的算法总是对某些对象进行操作，使其改变状态完成其功能。

2.算法的考量

对于算法的分析和评估，一般考虑正确性、可维护性、可读性、运算量、占用存储空间等方面考虑。三条主要标准：

（1）算法实现所耗费的时间。

（2）算法实现所耗费的空间，其中主要考虑辅助存储空间。

（3）算法易于理解、易于编码、易于调试。

3.什么是迭代

迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。

4.分治法求解的过程

分治法求解问题的过程是，将整个问题分解成若干个小问题后分而治之。如果分解得到的子问题相对来说还太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生方便求解的子问题，必要时逐步合并这些子问题的解，从而得到问题的解。

（1）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问

题。

（2）解决：若子问题规模较小而容易被解决则直接解决，否则继续分解为更小的子

问题，直至容易解决。

（3）合并：将已求解的各个子问题的解，逐步合并为原问题的解。

5.动态规划策略

基本思想：把求解问题分成许多阶段或多个子问题，然后按顺序求解各个子问题。基本步骤：

（1）划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意，着

若干个阶段一定要是有序的或者可排序的。

（2）选择状态：将问题发展到各个阶段时所出现的各个客观情况用不同的状态表

示出来。当然，状态的选择要满足无后效性。

（3）确定决策并写出状态转移方程：状态转移就是根据上一阶段的状态和决策来

导出本阶段的状态。这就像是“递推”，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。

6.递推

第二篇：算法分析与设计知识点总结

第一章 概述

算法的概念：算法是指解决问题的一种方法或过程，是由若干条指令组成的有穷序列。算法的特征：

可终止性：算法必须在有限时间内终止；

正确性：算法必须正确描述问题的求解过程；

可行性：算法必须是可实施的；

算法可以有0个或0个以上的输入；

算法必须有1个或1个以上的输出。

算法与程序的关系：

区别：程序可以不一定满足可终止性。但算法必须在有限时间内结束；

程序可以没有输出,而算法则必须有输出；

算法是面向问题求解的过程描述，程序则是算法的实现。

联系：程序是算法用某种程序设计语言的具体实现；

程序可以不满足算法的有限性性质。

算法描述方式：自然语言，流程图，伪代码，高级语言。

算法复杂性分析：

算法复杂性的高低体现运行该算法所需计算机资源（时间，空间）的多少。

算法复杂性度量：

期望反映算法本身性能，与环境无关。

理论上不能用算法在机器上真正的运行开销作为标准（硬件性能、代码质量影响）。

一般是针对问题选择基本运算和基本存储单位，用算法针对基本运算与基本存储单位的开销作为标准。

算法复杂性C依赖于问题规模N、算法输入I和算法本身A。即C=F(N, I, A)。

第二章递归与分治

分治法的基本思想：

求解问题算法的复杂性一般都与问题规模相关，问题规模越小越容易处理。

分治法的基本思想是，将一个难以直接解决的大问题，分解为规模较小的相同子问题，直至这些子问题容易直接求解，并且可以利用这些子问题的解求出原问题的解。各个击破，分而治之。

分治法产生的子问题一般是原问题的较小模式，这就为使用递归技术提供了方便。递归是分治法中最常用的技术。

使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。

分治法所能解决的问题一般具有以下几个特征：

该问题的规模缩小到一定的程度就可以容易地解决；

该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；利用该问题分解出的子问题的解可以合并为该问题的解；

该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。（这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。）

递归的概念：

直接或间接地调用自身的算法称为递归算法，用函数自身给出定义的函数称为递归函数。

反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。

边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。

第三章动态规划

动态规划的基本思想：

动态规划算法与分治法类似，其思想把求解的问题分成许多阶段或多个子问题，然后按顺序求解各子问题。最后一个阶段或子问题的解就是初始问题的解。

分治法求解时，子问题数目太多，从而导致解决原问题需要耗费指数级时间。与分治法不同的是，动态规划中分解得到的子问题往往不是互相独立的。

但不同子问题的数目常常只有多项式级。用分治法求解时，有些子问题被重复计算了许多次。

动态规划的适用条件：

动态规划法解所能解决的问题一般具有以下两个基本因素：

一、最优子结构性质

当问题的最优解包含着其子问题的最优解时，称该问题具有最优子结构性质。

二、重叠子问题性质

递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。

其它同分治法。

动态规划问题的特征：

求解的问题是组合优化问题；

求解过程需要多步判断，从小到大依次求解；

子问题目标函数最优解之间存在依赖关系；

动态规划算法设计的基本步骤和要素：

基本步骤：

（1）找出最优解的性质，并刻画其结构特征。（考察是否适合采用动态规划法。）

（2）递归地定义最优值。(建立递归式或动态规划方程)

（3）以自底向上的方式（或以自顶向下的备忘录方法）计算出最优值。

（4）根据计算最优值时得到的信息，构造最优解。

要素：

最优子结构

重叠子问题

备忘录（表格）

应用实例分析：

1、矩阵连乘问题：

（1）分析最优解结构：

计算A[i:j]的最优次序所包含的计算矩阵子链 A[i:k]和A[k+1:j]的次序也是最优的。矩阵连乘计算次序问题的最优解包含着其子问题的最优解，满足最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。

（2）建立递归关系；

（3）计算最优值—递归求解（递归求解最优值复杂度较高的原因是：子问题重复度高)；计算最优值—迭代查表求解

计算最优值—备忘录求解

（4）构造最优解

第四章贪心法

贪心算法的基本思想：

当一个问题具有最优子结构性质时，可用动态规划方法求解，但有时会有更简单有效的方法。

顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。

贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。贪心算法中，较大子问题的解恰好包含了较小子问题的解作为子集，这与动态规划算法设计中的优化原则本质上是一致的。

动态规划算法在某一步决定优化函数的最大或最小值时，需要考虑到它的所有子问题的优化函数值，然后从中选出最优的结果；贪心算法的每步判断时，不考虑子问题的计算结果，而是根据当时情况采取“只顾眼前”的贪心策略决定取舍。

贪心算法的设计要素：

可以用贪心算法求解的问题一般具有2个重要的性质：

1、最优子结构性质：

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征

2、贪心选择性质：

贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法与动态规划算法的主要区别。

动态规划算法通常以自底向上的方式求解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。

对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。

应用实例：

1、活动安排问题：

第五章回溯法

回溯法的基本思想：

回溯法的使用条件：

回溯法适用于搜索问题和优化问题。

回溯法的设计要素：

针对问题定义解空间：

问题解向量

解向量分量取值集合构造解空间树

两类典型的解空间树：

子集树：当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。子集树通常有2n个叶结点

排列树：当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。排列树通常有n!个叶结点。

判断问题是否满足多米诺性质。

搜索解空间树，确定剪枝函数。

确定存储搜索路径的数据结构。

第六章分支限界法

分支限界法的基本思想：

分支界限法类似与回溯法，也是在问题解空间中搜索问题解的一种算法。

分支界限法与回溯法思想对比：

求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。

搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。

在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。

此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。

常见的两种分支界限法：

队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。

优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。

最大堆：最大效益优先

最小堆：最小耗费优先

第三篇：数据结构算法设计与分析

数据结构算法设计与分析、计算机网络、计算机组成原理、操作系统原理、编译原理、数据库原理及应用、软件工程、软件测试等计算机基础理论课程；

网页制作、程序设计Java、JSP程序设计、Oracle、XML程序设计、计算机网络、SSH（Struts+Spring+Hibernate）框架、Java EE程序设计、Ajax程序设计、Linux+PHP+MySQL程序设计、Android手机开发、UML系统分析与设计、性能测试、自动化软件测试、软件质量保证、毕业设计及项目综合实训等。

数据结构、计算机网络、计算机组成原理、操作系统原理、编译原理、数据库原理及应用、金融学概论、西方经济学等基础理论课程；

网页制作、程序设计Java、JSP程序设计、J2EE程序设计、SQL Server数据库、Oracle数据库、Linux操作系统、UML系统分析与设计、软件工程、XML程序设计、SSH框架、金融市场学、ERP财务管理、管理信息系统、投资银行学、商业银行学、国际金融管理、毕业设计及项目综合实训等专业课程。

数据结构、计算机网络、计算机组成原理、操作系统原理、数据库原理及应用、软件工程、软件测试等计算机基础理论课程；

网页制作、程序设计Java、JSP程序设计、J2EE程序设计、XML程序设计、Ajax程序设计、SSH框架、Android手机开发、Linux+PHP+MySQL程序设计、SQL Server数据库、Linux操作系统、UML系统分析与设计、软件项目管理、行业标准与规范、IT服务管理、IT职业英语、毕业设计及项目综合实训等专业课程

第四篇：算法设计与分析学习心得

算法设计与分析学习心得

班级：物联网1201 姓名：刘潇 学号：1030612129

一、实验内容：

这学期的算法与设计课，老师布置了这四个问题，分别是货郎担问题，动态生成二维数组，对话框下拉列表，排序问题。

二、学习掌握：

基本程序描述：

（1）货郎担问题：货郎担问题属于易于描述但难于解决的著名难题之一，至今世界上还有不少人在研究它。货郎担问题要从图g的所有周游路线中求取具有最小成本的周游路线，而由始点出发的周游路线一共有（n一1）！条，即等于除始结点外的n一1个结点的排列数，因此货郎担问题是一个排列问题。货郎担的程序实现了利用穷举法解决货郎担问题，可以在城市个数和各地费用给定的情况下利用穷举法逐一计算出每一条路线的费用，并从中选出费用最小的路线。从而求出问题的解

（2）费用矩阵：费用矩阵的主要内容是动态生成二维数组。首先由键盘输入自然数，费用矩阵的元素由随机数产生，并取整，把生成的矩阵存放在二维数组中，最后把矩阵内容输出到文件和屏幕上。它采用分支界限法，分支限界法的基本思想是对包含具有约束条件的最优化问题的所有可行解的解（数目有限）空间进行搜索。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集，并为每个子集内的解计算一个下界或上界。动态生成二维n*n的数组程序利用指针表示数组的行和列，并逐一分配空间，在输入n的数值后，系统自动分配空间，生成n*n的数组，并产生随机数填充数组，最后将结果输入到指定文件中。

（3）Mfc：在下拉列表框中添加内容程序，在下拉列表对应的函数中利用addstring添加需要的内容。首先定义下拉列表框为ccombox型，并定义其属性名，利用addstring函数可以任意添加需要的内容。a排序问题:快速排序的运行时间与划分是否对称有关，其最坏情况发生在划分过程中产生的两个区域分别包含n-1个元素和1个元素的时候。其算法的时间复杂度为O(n 2),在最好的情况下每次划分的基准恰好为中值，可得其算法时间复杂度为O(n㏒n)。算法的实现和理解和代码实现完全是两回事，想要完全掌握一种算法，需要动手实践，用代码实现，才能理解透彻，真正掌握。b对话框下拉列表：这个项目简单易懂，轻松实现。三.疑问与总结：

货郎担的问题，我认为穷举法相对比而言是比较初级的方法，费时耗力，适合在练习时选用，但是在实际问题中不建议采用。克鲁斯卡尔或者普里姆算法求取最小生成树的方法来解决货郎担的问题是更适合现实解决问题的。我认为程序可以用switch函数来将函数分成几个部分更人性化，比如分为解决问题的的选项，输出结果选项，退出程序选项等。再有就是费用矩阵的值可以从文件中读取，而结果也可以直接放在指定文件中，这样在实际应用中比较广泛。

动态生成二维数组的程序我认为如果按照规范性，我的方法是中规中矩的，毕竟再向下延伸，生成三维的数组，需要三层的指针来实现。但是就程序的简化程度和计算机处理时间来说，我认为这样双层指针的算法有些太占用内存，毕竟要给行和列各分配n个空间。我通过与同学的交流，我发现可以用1位数组来实现二维的n*n的数组。首先分配n*n的空间，然后通过循环在一行的数据达到n时自动换行。这样程序得到了一定的简化，并且减少了一定的内存使用。我认为这种方法是比较贴合实际的。

四.心得体会

在计算机软件专业中，算法分析与设计是一门非常重要的课程，很多人为它如痴如醉。很多问题的解决，程序的编写都要依赖它，在软件还是面向过程的阶段，就有程序=算法+数据结构这个公式。算法的学习对于培养一个人的逻辑思维能力是有极大帮助的，它可以培养我们养成思考分析问题，解决问题的能力。

如果一个算法有缺陷，或不适合某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂性和时间复杂度来衡量。算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。计算机系统中的操作系统、语言编译系统、数据库管理系统以及各种各样的计算机应用系统中的软件，都必须使用具体的算法来实现。算法设计与分析是计算机科学与技术的一个核心问题。因此，学习算法无疑会增强自己的竞争力，提高自己的修为，为自己增彩。

第五篇：算法的概念 教学设计

算法的概念教学设计 杭州二中分校陈海玲执笔 一．内容和内容解析

本节课是算法的起始课，主要内容有：算法的概念、用自然语言描述算法。

算法是一种解决问题的方法，是数学及其应用的重要组成部分，也是计算机科学的重要基础。算法的思想有着广泛的应用性。

在数学中，算法通常是指按照一定规则解决某一类问题的明确和有限的步骤。现在，算法通常可以编成计算机程序，让计算机执行并解决问题．

在算法概念的表述中，有范围限定词“在数学中”，因此学习的内容均为数学中的问题。有一个有前缀限制的基本特征词“步骤”，前缀中，“按照一定规则”指的是解决具体问题时的依据和表达方式，关注的是算法的基本逻辑结构（顺序、条件和循环），也表示算法具有有序性。“解决某一类问题”，强调的是算法适用对象的常态，突出算法的研究价值以及它的普遍适用性，也表明特殊问题的解题与一般问题的算法，存在联系又有区别。“明确和有限”，表示算法的每一步都是明确的、可执行的，总的步骤是有限的。

算法有多种表示方法，其中自然语言描述与人的表达方式最接近，是学习其它描述方法的基础。

中国古代数学是以算法为主要特征，并蕴涵着丰富的算法思想。现代信息技术的发展使算法唤发出新的生机和活力，并使之成为当代社会必备的基本知识。算法进入高中必修内容正是反应了时代的需要。

算法具有的基本逻辑结构与形式逻辑结构存在对应关系，有着丰富的逻辑思维材料。算法思想贯穿于整个中学数学内容之中，有着丰富的层次递进的素材。因此，算法的学习对整个高中数学的学习有着“源”与“流”的关系。又由于算法的具体实现上可以和信息技术相结合。因此，算法的学习十分有利于提高学生的逻辑思维能力，培养学生的理性精神和实践能力，发展他们有条理的思考与表达的能力，同时可以让他们知道如何利用现代技术解决问题。

二．目标和目标解析

本节课的教学目标是：

1．在解特殊的二次一次方程组到得出一般二元一次方程组的解法的过程中，让学生对算法的概念有一个初步认识，并了解算法是如何表示的。

2．在判定7，35、1949和整数n(n>1)是否为质数的过程中，进一步理解算法的概念，学习算法的自然语言表示，认识算法的特征、作用和优势。

3．在得出用二分法求方程一个近似解的算法的过程中，初步运用算法概念，体会算法自然语言描述形成的过程，会初步用自然语言描述算法。

在实现上述目标的过程中，需要适时、恰当地借题发挥，使学生体会算法的思想，了解算法的基本逻辑结构，培养观察、表达能力和逻辑思维能力。

因此，本节课教学重点是，通过一些具体问题，引导学生变过去关注解决问题为关注解决问题过程的逻辑结构，通过解法与算法的比较，体会算法思想，形成算法概念，并会用自然语言描述一些具体问题的算法。

三．教学问题诊断

算法对学生来说并不遥远。比如列方程解应用题，证明函数的单调性，求曲线的方程，等，都是学生碰到过的算法的问题，但是，在此之前并没有明确提出“算法”的概念，学生原有的经历为算法学习提供了良好的条件。由于算法至今没有公认的定义，算法概念的建立需要与认识它的特征相联系，这拉大了算法概念与学生原有体验之间的距离，从而可能会造成学生概念理解上的偏差。因此，算法概念的形成需要搭建台阶，使学生运用已知建立新知，与此同时还要特别注意防止算法概念的泛化。

算法的实质是将人的思维过程处理成计算机能够一步一步执行的步骤，进而转化为一步一步执行的程序.这决定了算法概念的形成与学生的观察能力，表达能力和逻辑思维能力有着直接联系。在以班级为单位的教学中，面临能力发展不平衡，产生部分学生算法学习有困难，因此，需要在教学中把握好适应面较广、符合学生认知基础的切入点。

通常，特殊问题的解的过程只是解法而不是算法，算法是解决一般（一类）问题（要与数学有关）的，即不进入到一般问题的层面就得不到算法，而一般问题往往远离学生原有的基础，需要通过搭建解决特殊问题这一台阶，帮助学生进入一般问题。在这样的情境中，学生的关注点需要由特殊转到一般，这对许多学生来讲是有困难的，需要教师设计问题或情境帮助学生加以克服，因此，这是本节课的教学难点之一。解决这一难点需要在教学中设计好问题，并给学生提供思维的时间，并在问题引导下，实现关注点的转移。

算法是一种解决问题的方法，特别擅长处理具有条件、循环结构的问题，有其特有的作用和价值，这是学生原来没有体会过的，若教学中对此忽视，学生算法学习时的关注会缺少思维量，只停留在低层次上。因此，需要教师结合问题创设学生活动情境，促成学生关注算法中存在的逻辑结构，并予以揭示。

算法的自然语言描述与高中学生具备的表达方式虽有不同但也有联系，相比算法的其它描述方法，自然语言描述最接近学生现有的表达方式。因此，对只有顺序结构的算法描述时，学生是容易写出这类问题算法的。教师在小结时，只需指出：写算法要按顺序，每步要明确（可执行），总体是有限步即可。对涉及条件、循环结构的算法时，由于需要表示算法中存在的结构，而学生原来没有接触过这种表达，因此，这也是本节课的一个教学难点。解决这一难点，需要在教学中给学生提供尝试的机会，在他们发生困惑，产生问题后给予指导，帮助他们学会用递归语言描述算法。

四．教学支持条件分析

为了有效实现教学目标，条件许可，可以借助计算机或者计算器来参与运算或表达算法.通过计算机演示帮助学生体会算法学习的作用和价值.五．教学过程设计

（一）课题引入

教师介绍：图中的前景有算筹、算盘、计算机,介绍计算机领域的重大贡献，引出计算机的工作原理——算法。后景取自宋朝数学家朱世杰的数学作品《四元玉鉴》，借此介绍我国古代数学在算法方面的伟大成就。纵观章头图，从古到今，算法始终扮演着重要的时代角色。

提问：什么是算法？引出课题。

设计意图：要充分挖掘章头图教学价值，它至少可以体现：1）算法概念的由来；2）我们将要学习的算法与计算机有关；3）展示中国古代数学的成就；4）激发学生学习算法兴趣。5）借问题自然引出课题。

（二）问题情境，引出算法概念

问题1：你能写出求解二元一次方程组：的步骤吗？

设计意图：从学生具备的认识水平出发，归纳解二元一次方程组的求解步骤。从而让学生经历算法分析的基本过程，并在此过程中引导学生关注更具一般性解法，形成解法向算法过渡的准备，为建立算法概念打下基础。

师生活动：让学生解方程组。收集学生的不同解答，再与教科书上的解答作比较。

问题2 你们所写的解答和教科书有什么不同？教科书提供的解答有什么特点？

设计意图：旨在引导学生关注书上表达方式的明显地步骤性特征，关注解的过程的逻辑结构，让学生明白解法和算法的差异

师生活动：教师引导学生从表达方式上、解的方法上进行对比，让学生对比后回答1。同学们写的是解法，关注的是解，书上写的是解题步骤具有明显的步骤性特征2。同学们用的是加减代入消元法解方程组，书上两次用的读是加减消元法等。

教师：投影用加减消元法求解的步骤，问：参照本题解法，你能完成下面问题吗？请一试。

问题3：写出求方程组的解的步骤.设计意图：在复习解特殊二元一次方程组基本步骤的基础上．进一步复习回顾解一般的二元一次方程组的步骤，目的是让学生明白算法是用来解决某一类问题的，从而提高学生对算法的普遍适用性的认识，为建立算法的概念做好铺垫.师生活动：让学生写出求解步骤后，教师：投影显示解题步骤：

第一步，得.第二步，解，得.第三步,得.第四步,解,得.第五步,得到方程组的解为:.教师：

1．引导学生分析上述解题过程的结构。

2．提出以上步骤就是求一般的二元一次方程组的解的算法.3．说明：把它编成程序就可以用计算机来解二元一组方程组了。用事先编好的程序，让学生输入数据，计算机直接给出方程组的解.（三）分析归纳，得到算法概念

问题4。到底什么是算法？如何表达算法的含义？

设计意图：有了上面所举实例，学生对算法的概念开始有了一些认识，但对概念的比较全面的描述还有一定的困难.教师在此处设问后，再通过帮助学生回顾上面关于算法的实例，引导学生进行归纳总结.让学生切实参与到概念的形成过程中来.师生活动：教师在提出问题后，一定要给学生思考时间，让学生先用自己的语言表达对算法概念的理解，在学生思考、交流、回答的基础上，教师引导学生看书，让同学们看看自己所归纳的算法的概念和课本中概念的差异，帮助学生初步认识算法的概念.算法的概念:在数学中，算法通常是指按照一定规则解决某一类问题的明确和有限的步骤．现在，算法通常可以编成计算机程序，让计算机执行并解决问题．

教师：结合问题3你能说说这里面关键词的含义吗？

(四)解决问题，促进理解算法概念，学习算法自然语言描述

过渡语：联系时事、地域与质数有关的问题，激发学生的好奇心和求知欲。

问题5，写出判断7是否为质数的步骤.设计意图：由学生已有的认识水平出发，创设学生可以完成的体验情境，认学生认识求解结构中存在“重复”。为导出一般问题的算法创造条件，也为学习算法的自然语言表示提供时机。.师生活动：

教师提问：

1.什么是质数？（引导学生回忆质数概念）

2.如何判断一个数是不是质数？如何把判断过程的基本步骤有条理的写出来？

让学生写算法的步骤，交流并点评学生写的算法步骤.体会如何从算法的角度思考质数的判定，体会算法的特征，知道下列表述的步骤是不明确的，所以都不是算法：

（1）因为2至6的整数都不能整除7，所以7是质数.（2）第一步，用2除7，得到余数不为0，所以2不能整除7.第二步，同理，3至6的整数都不能整除7，所以7是质数.纠正学生所写基本步骤后，教师接着提出问题：

问题6 你能写出判定35是否为质数的算法吗？

设计意图：35是偶数的代表，为判断任意给定一个大于2的整数是否为质数奠定基础。

师生活动：让学生试着写一写，可能会出现不同情况.教师有针对性地进行相应讲解.第一步，用2除35，得到余数为1.因为余数不为0，所以2不能整除35.第二步，用3除35，得到余数为2.因为余数不为0，所以3不能整除35.第三步，用4除35，得到余数为3.因为余数不为0，所以4不能整除35.第四步，用5除35，得到余数为0.因为余数为0，所以5能整除35.所以35不是质数

学生完成后；教师提问：

两个解法有何相同之处？有何不同之处？

教师在学生回答后小结：对7是在试完1到6后才知道是质数，对35在试到5时，也就是在试的过程中，就得出不是质数，故没试完；不管哪个数，判断过程都是按一定规则有序进行的，都存在着“重复”这样的结构。

问题7 你能写出判断1949是否是质数的算法吗？

设计意图：1949是一个具体的数字，而且是一个比较大，无法用几个顺序结构的步骤就能表达清楚的算法问题，设计1949过渡，让学生从具体数的质数判断过程中认识循环结构，为一般的质数判断问题做准备。

师生活动：数字太大，像判定7是否为质数那样去判定1949是否为质数是一件很困难的事情.因此，学生可能会写出下列步骤：

第一步，用2除1949，得到余数为1.因为余数不为0，所以2不能整除1949.第二步，用3除1949，得到余数为2.因为余数不为0，所以3不能整除1949.第三步，用4除1949，得到余数为1.因为余数不为0，所以4不能整除1949

„„

第一千九百四十七步，用1948除1949，得到余数为1.因为余数不为0，所以1948不能整除1949因此，1949是质数.但是，上述表述的过程不是算法.事实上，“„„”你知我知，对计算机来说就是不明确的。

从问题7知道，一个算法步骤中不能出现类似“„„”的步骤，但对于像1949这样大的数，要像判定7是质数那样的写出判定其是质数的所有步骤是不现实的.那么，在不改变“规则”的前提下怎样表达这个算法呢？

引导学生分析并认识到，在问题5中，判定7是否为质数的每一个步骤，除了除数不同外其余的内容是一致的.如果用i表示除数，那么所有步骤都包含以下内容：

“用i除7，得到余数为r.因为r不为0，所以i不能整除7.”

在问题6中，只要把被判定的数7改为1949，则每一步均包含以下内容：

“用i除1949，得到余数为r.因为r不为0，所以i不能整除1949.”

因此，我们可以把判定1949是否为质数的算法写为：

第一步，令i=2.第二步，用i除1949，得到余数为r.第三步，判断r是否为0.若是，则1949不是质数；否则把i的值增加1仍记为i.第四步，判断“i>1948”是否成立.若是，则1949是质数；若否，返回第二步..问题8 任意给定一个大于2的整数n，能否设计一个算法对n是否为质数做出判断？

设计意图：在问题7学生活动的基础上，通过学生活动，得出该问题的算法，从而促进学生对算法概念的进一步理解，感受算法的作用和优势，学习算法的自然语言描述，同时，引入学生关注算法中存在的结构。

师生活动：让学生将1949改为任意大于2的整数，改写算法，得出“判定整数n（n>2）是否为质数”的算法.得出问题8算法（见教材例1算法）后，教师提问

此时，你是如何理解算法的？

教师小结：扣住下面问题。

1．用四步就可以解决问题6的算法，虽然没有使我们直接看到结果，但可以由计算机去解决了。（理解定义中：算法通常可以编成计算机程序，让计算机执行并解决问题）

即学习了算法，我们又增加了一种解决问题的方法（当然要借助计算机，说明算法的作用与优势）

2．算法可以用自然语言描述，描述算法的步骤一定是有限的，这是算法有限性特征；描述的算法具有“按部就班”的特点，这是算法“有序性”的特征；算法的第一步的表达要求“明确”，以便于编程让计算机执行，这是算法明确性的特征；

3．在解决问题过程中，对于反复进行的步骤,可以用递归语言进行描述.此时，通常分三个步骤:首先要给一个初始值,接着表达重复做的事情,最后要进行终止判断.这类问题的背后含有算法的基本逻辑结构。问题9.写出用“二分法”求方程x2-2=0（x>0）的近似解的算法.设计意图：二分法是算法中的经典问题，具有明显的顺序和可操作的特点．通过此例可以让学生进一步了解算法的逻辑结构，领会算法的思想，体会算法的的特征。同时也可以达到巩固用自然语言描述的算法，提高用自然语言描述算法的表达水平.师生活动：教师引导学生分析在二分法求方程近似解过程中所包含的基本逻辑结构，尤其关注其中的循环结构和条件结构。然后展示其算法。（主要考虑时间比较紧）

在设计算法的时候可以先不考虑精确度，在学生活动后，教师提出，在现有条件下，可以得到方程根存在的区间会越来越小，但我们的操作则永远不能停止。

因此，需要引入能够控制，使算法具备有“有限”的量，这就是精确度。

教师与学生共同得出本题算法：

第一步，令.给定精确度.第二步, 给定区间,满足.第三步,取中间点.第四步,若则含零点的区间为;否则含零点的区间为.将新得到的含零点的仍然记为.第五步, 判断的长度是否小于或者是否等于０.若是，则是方程的近似解;否则，返回第三步．

在完成上述算法表达的基础上，教师指出：

1．如果没有精确度要求，该算法将无法终止。（通过精确度强调算法的“有限性”）。

2．引导学生分析该算法的逻辑结构。（了解算法中存在的顺序、条件和循环结构）

3．给出精确度，指导领学生看教材,结合必修3第4页上有关内容.说明按以上步骤，我们将依次得到表1-1和图1.1-1.于是，开区间（1.4140625，1.41796875）中的实数都是满足假设条件的原方程的近似解.4．改变输入的函数表达式，给定精确度后，上面算法可以求所有方程的近似解，因此，它是算法。通过“二分法”求方程的近似解的算法与解法的比较，发现算法一般都是没有具体结果的，而解法结果都是确定的，从而强调算法通常是针对解决一类问题而言的。

（五）归纳小结 将本节的主要内容以问题的形式呈现，让学生通过思考和回答问题，达到回顾和总结的目的．

问题1：你能举出更多算法的例子吗？

设计意图：以举例的形式使学生体会算法的思想，以此评价他们对算法的概念以及特征的领会情况.师生活动：学生举例，师生共同评价.问题2：与一般解决问题的过程相比，你认为算法最重要的特征是什么？

设计意图：通过让学生思考回答来评价他们对算法的特征中顺序、明确、有限的步骤的领会情况．同时提高学生的总结、归纳、表达能力.师生活动：在学生回答的基础上，引导他们归纳：与一般解决问题的步骤相比,算法具有有序性、明确性、有限性等特点.六．目标检测设计

1．课堂检测

第1题．课本第6页练习1。

第2题．有人对歌德巴赫猜想“任何大于4的偶数都能写成两个奇质数之和”设计了如下操作步骤：

第一步：检验6=3+3

第二步：检验8=3+5

第三步：检验10=5+5

„„

利用计算机无穷地进行下去！请问，利用这种程序能够证明猜想的正确性吗？这是一个算法吗？

设计意图：促进学生进一步了解算法的概念及特征的，体会算法的思想。

活动方式：学生独立思考，在学生回答的基础上，教师予以评点。

答：这不是算法问题，不符合算法概念中提到的“有限性”。

2．课后检测

第1题.写出求一元二次方程根的一个算法.设计意图：巩固学生已领会的算法的思想，促进学生用自然语言正确表达算法。

第一步，计算。

第二步，如果,则原方程无实数解；

第三步:输出或无实数解的信息.第2题.任意给定一个大于1的正整数n，设计一个算法求出n的所有因数.设计意图：检查学生是否会用自然语言正确表达算法，训练学生的应变能力.第一步，给定一个大于1的整数n.第二步,令i=1.第三步,用i除n，得到余数为t，若t=0，则i是n的一个因数输出i；否则，不输出i.第四步，给i增加1仍然用i表示.第五步,判断是否成立,若是,则算法结束；否则,返回第三步.本文是“‘中学数学核心概念、思想方法结构体系及其教学设计研究’课题成果”