《算法初步介绍(修订版).doc》由会员分享，可在线阅读，更多相关《算法初步介绍(修订版).doc（6页珍藏版）》请在金锄头文库上搜索。
1、“算法初步P.P.T”的文字说明Page 3 章头图的设计意图本章章头图意在体现中国古代数学与现代计算机科学的联系，它们的基础都是“算法”中国古代数学注重实际问题的解决，以算法为中心，寓理于算，其中蕴涵了丰富的算法思想章头图的背景是元代朱世杰所著的四元玉鉴，前景的后部是盛行一时的计算工具算筹和算盘算筹是中国古代的计算工具，在春秋时期已经很普遍；明代算盘开始在中国盛行，直至计算机普及的现在，许多人仍然在使用算盘 计算机科学的基础也是算法就像使用算盘一样，人们需要给计算机编制“口诀”算法，才能让它工作事实上，计算机是只做一件事情的设备：通过执行算法来处理信息章头图前景的前部是一台计算机章头图正是想
2、说明：从古到今，“算法”都在扮演着重要的时代角色Page 4 教学目标我认为，本章要教给学生的算法初步知识包括：算法的概念、算法的三种基本逻辑结构、算法的三种描述方式和一些具体的算法案例。Page 89 算法思想算法是什么在构建一个算法之前，我们首先需要弄明白的问题是“算法是什么”从形式上看，算法就是一个步骤（或指令）集合。按照其中的步骤（或指令）逐条操作，可以使问题得到解决，而且总能得到正确的结果。这就要求算法中的每一个步骤是明确的、无二义性的，而且步骤的全体是有限的。在计算科学中，对算法提出了更高的要求：通用性（适用性） 算法应适用于某一类问题中的所有个体，而不是只用来解决一个具体问题。如
3、辗转相除法可以用来求任意两个整数的最大公约数。但并不存在通用的算法，也就是说，一个算法只能解决一类问题；而且不是所有的问题都存在算法（例如，希尔伯特第十问题：是否存在一个算法可以判定任意丢番图方程有无整数解，已经证明这样的算法是不存在的）。能行性 算法应有明确的步骤一步一步地引导计算的进行，即每一步对于利用算法解决问题的人或计算机来说都是可读的、可执行的，并且能够得到最终结果。明确性 算法下一步应执行的步骤必须明确或者由规则直接确定，或者由规则和上一步的结果确定，而不需要计算者临时动脑筋。有限性 算法应由有限步组成；至少对某些输入数据，算法应在有限多步内结束，并给出计算结果。离散性 算法的输入
4、数据和输出数据都应该是离散的符号（或称字母，其中也包括数字）。例如不能输入一条曲线。如果能设计满足上述要求的算法，那么这个算法在任何时刻都能精确地告诉我们，应该对某一类问题做什么。如果给定了某类问题的一个算法和属于这个问题类的一个问题，那么解决问题并不依赖执行者的聪明才智，只要严格地“照章办事”就行了。Page 10 结构设置算法的三种描述方式包括自然语言、程序框图和算法语句教科书对其的介绍是分散进行的：在介绍算法的概念时，用自然语言描述算法；在介绍算法的三种基本逻辑结构时，分别介绍三种基本逻辑结构对应的程序框图；单列一节介绍算法语句本章的核心内容是算法的三种基本逻辑结构。因为学生需要用三种基
5、本逻辑结构构建算法，我们也希望通过学习，学生构建的算法具有三种基本逻辑结构的清晰结构。因此，教科书在设置上分别通过程序框图和Page 916 编写意图与教学建议算法的概念（P.9）这部分内容（1.1.1节）的教学目标是引入算法的概念，让学生通过实例初步感受算法的思想教科书的编排顺序是：从具体的二元一次方程组求解步骤出发，推广到求解步骤一般的二元一次方程组的算法，旨在传达这样一个思想：算法是用来解决某一类问题的，从而引出算法的描述性定义和算法的主要特征，然后用“质数的判定”和“二分法求方程近似解”两个例题进一步展现算法的特征由于构建算法的概念非常关键，这部分可做较详细地介绍，主要包括下面几个方面
6、：1. （P.910）通过两次使用加减消元法解一个具体的二元一次方程组，然后直接把这些步骤改写为解一般的二元一次方程组的步骤，就得到了解一般的二元一次方程组的一个算法。这里的编写意图在于让学生体会将二分法的算理转化为算法步骤的过程，即将实现算理需要做的事情分解成若干明确的步骤，然后用自然语言有条理地一步一步地表达出来。2. 算法概念的教学处理好几个关系： 算法与行动方案在算法的教学实践中，一些教师认为，既然算法是“按照一定规则解决某一类问题的明确和有限的步骤（人教A版对算法的描述）”，那么烹制一道菜肴的食谱、组装一个办公座椅的说明或者称量硬币以找出假币的方案等行动方案，都可以称为算法但是，算法
7、首先应该是用于解决数学问题的在实际应用中，无论待解决的问题来自生产、生活和科学实践的哪个领域，最终都归结为数学模型，而解决问题的关键就是寻求计算该数学模型的算法而且可选用的解决数学问题的简单算法不胜枚举，因此完全没有必要把“烧一壶水”等行动方案归入算法的行列其次，算法的“能行性”“明确性”的要求主要是针对算法的执行者而言的一般来说，我们创建的算法将被计算机执行，而计算机只能做加、减、乘、除、整除、取模等算术运算、逻辑运算和初等的函数运算，因此算法步骤必须可以明确地分解为有限多个这样的运算而行动方案中涉及对物质所做的物理操作，这种操作的“能行性”“明确性”无从判断因此尽管行动方案表面看来具有算法
8、特征，实际上却不利于学生对算法本质特征的理解 算法与解题方法在学习算法之前，学生已经学过许多解题方法，从加、减、乘、除到解方程、尺规作图等这些解题方法实际上就是算法例如，在小学时我们就会把两个数相加、减、乘、除，这并不是说对于任意两个数，我们都可以得到它们的和、差、积、商，而是说我们掌握了统一的作加法、减法、乘法和除法的算法如我们会从右到左取出被乘数的每一位，与乘数相乘，并将中间结果的末位与取出的被乘数对齐，然后把所有的中间结果加起来（图1）；而英国的学生可能从左到右地进行运算（图2） 图1 图2又如，用公式x1=， x2=求方程ax2+bx+c=0(a0)的解就是求解一般的一元二次方程的一种
9、算法而求一个非负整数n的阶乘，可以按照阶乘的定义来算：当n0时，n！=1；若已经算出了(n1)！，则n！=n(n1)！这里的定义就提供了计算阶乘的一种算法上述解题方法可以看成推理形成的算法，而我们寻求的是操作所需的算法因此在探求解决问题的一般性方法的基础上，还需将解决问题的步骤离散化、具体化、程序化换句话说，算法本质上是由基本运算和规定的运算顺序所构成的解题步骤，但它所具有的鲜明的“算法”特征又使它不同于一般的解题方法 算法与程序Page 1732 编写意图与教学建议程序框图1. （P. 1718）通常，人们在用计算机解决问题时，先在头脑中构思一个算法（这类似于用自然语言描述算法），接着画出程
10、序框图形象直观地把算法表达出来，然后再根据这个框图来编写程序与自然语言描述算法不同的是，程序框图更加清楚简练、形象直观、流向清楚，既可以避免自然语言出现二义性的情况，又可以清楚地看出三种基本的逻辑结构，很容易改编成计算机程序1.1.2节的教学目标是设计程序框图表达算法，并在具体问题的解决过程中，理解算法的三种基本逻辑结构教科书的编排顺序是：先介绍程序框图的基础知识，接着以一个完整的程序框图描述1.1.1中“质数的判定”的算法，然后从“质数的判定”的程序框图中分解出算法的三种基本逻辑结构，并分别用简单的例子加以说明2.（P. 1926）算法的三种基本逻辑结构：尽管算法的种类不计其数，但人们在长期
11、实践中不断地总结经验，将算法归纳为三种基本逻辑结构的组合，即顺序结构、条件结构和循环结构由这三种基本结构组成的算法，不仅结构清楚，而且已经证明可以解决任何复杂的问题同时，这三种基本逻辑结构也是程序框图的构成要素因此，教科书将这三种基本逻辑结构的教学与程序框图的教学结合起来，这不仅降低了这三种基本逻辑结构的学习难度，也为学习程序框图的画法提供了前提条件所以，三种基本逻辑结构与程序框图也就成了算法内容的教学重点算法的三种基本逻辑结构是本章的重点内容 顺序结构顾名思义，顺序结构就是按照算法步骤排列的顺序，逐条执行算法在计算机中表现为计算机按照语句出现的先后次序执行一串语句 条件结构条件结构是根据“条
12、件”在不同情况下的取值选择不同的处理方法，可以在两种情况下选择一种，也可以在多种情况下选择一种计算机区别于其他机械的能力就来自于算法做判定和按判定行动的能力 循环结构循环结构用于在某个条件成立的情况下重复执行某个动作，例如做累加或累乘运算循环结构不能是永无终止的“死循环”，一定要在某个条件下终止循环，这就需要条件结构来做出判断，因此，循环结构中一定包含条件结构计算机运算速度快，最善于进行重复性的工作教科书介绍了两种基本的循环结构当型循环和直到型循环当型循环先对一些条件进行判断，根据判断的结果决定是否执行循环体；直到型循环则是先执行一次循环体，再对一些条件进行判断，然后根据判断的结果决定是否继续
13、执行循环体也就是说直到型循环语句至少执行一次循环体，而当型循环语句则可能一次也不执行循环体（P.2426）由于循环结构可能是教学的难点，教科书用一个“累加器”的例子具体说明了用循环结构构建算法的过程：例 设计一个计算1+2+100的值的算法，并画出程序框图算法分析：通常，我们按照下列过程计算1+2+100的值第.1步：0+1=1第2步：1+2=3第3步：3+3=6第4步：6+4=10第100步：4 950+100=5 050显然，这个过程中包含重复操作的步骤，可以用循环结构表示分析上述计算过程，可以发现每一步都可以表示为 第（i1）步的结果i第i步的结果这里的“”是赋值号，表示把S1的值仍赋给
14、S.为了方便、有效地表示上述过程，我们用一个累加变量S来表示每一步的计算结果，即把Si的结果仍记为S，从而把第i步表示为SSi，其中S的初始值为0，i依次取1,2，100由于i同时记录了循环的次数，所以也称为计数变量解决这一问题的算法是：第一步，令i1，S0第二步，若i100成立，则执行第三步；否则，输出S，结束计算。第三步，计算SSi第四步，计算ii1，返回第二步程序框图： 图1.114上述程序框图用的是当型循环结构，教科书还给出了直到型循环结构的程序框图。3. （P.2732）为了帮助教学中突破程序框图的画法这一算法教学难点，教科书结合“用二分法求方程的近似解”这一算法，详细介绍了程序框图
15、的画法，并总结了画程序框图的步骤：第一步，用自然语言将算法步骤表达出来第二步，将每一个算法步骤所包含的逻辑结构找出来并用框图表示，得到该步骤的程序框图第三步，将所有步骤的程序框图用流程线连接起来并加上终端框，得到表示算法的程序框图Page 3338 编写意图与教学建议基本算法语句1. （P.3337）用自然语言或程序框图描述的算法，计算机是无法“理解”的，因此我们还需要将算法用计算机能够理解的语言表达出来，这就是通常所说的程序与程序设计，所用的语言称为程序设计语言（programming language）程序设计语言是由一些有特定含义的程序语句构成，与程序框图中介绍的算法三种基本逻辑结构相对应注：这部分内容尽力让学生在简单的程序设计环境中学习算法的基本知识，而把设计、实现、调试和测试程序的任务留给信息技术等其他课程因此
