粤教版高中信息算法和算法的描述课件.ppt

1、高中信息技术高中信息技术算法和算法的描述算法和算法的描述软件、程序、算法 软件是包含程序的有机集合体，程序是软件的必要元素。任何软件都有可运行的程序，至少一个。算法就是程序的灵魂，一个需要实现特定功能的程序，实现它的算法可以有很多种，所以算法的优劣决定着程序的好坏。软件、程序、算法之间的关系软件软件程序程序算法算法算法练习1：渡河问题：渡河问题：一个农夫带着一条狼、一只山羊和一篮一个农夫带着一条狼、一只山羊和一篮蔬菜过河，但只有一条小船，并且每次只蔬菜过河，但只有一条小船，并且每次只能让农夫带一样东西过河。农夫在场的情能让农夫带一样东西过河。农夫在场的情况下一切相安无事，一旦农夫不在，狼会况下

2、一切相安无事，一旦农夫不在，狼会吃羊，羊会吃蔬菜。吃羊，羊会吃蔬菜。问农夫如何解决过河问题。问农夫如何解决过河问题。河河1 1、算法、算法概念：概念：算法是在有限步骤内求解某一问题所使用的一组定义明算法是在有限步骤内求解某一问题所使用的一组定义明确的规则，即用计算机求解某一问题的方法，是能被机械地确的规则，即用计算机求解某一问题的方法，是能被机械地执行的动作或指令的有穷集合。执行的动作或指令的有穷集合。特征：特征：1 1）有零个或多个输入。解题算法中可以没有数据输入，也可以同时输入多）有零个或多个输入。解题算法中可以没有数据输入，也可以同时输入多 个需要算法输入的数据。个需要算法输入的数据。2

3、 2）确定性。解题方法中任何一个操作步骤都是清晰无误的，不会让人产生）确定性。解题方法中任何一个操作步骤都是清晰无误的，不会让人产生 歧义或误解。歧义或误解。3 3）有穷性。任何一种提出的解题方法都是在有限的操作步骤内可以完成）有穷性。任何一种提出的解题方法都是在有限的操作步骤内可以完成 的，的，哪怕是失败的解题方法。一个算法在执行有穷步之后必须结束。哪怕是失败的解题方法。一个算法在执行有穷步之后必须结束。4 4）有一个或多个输出。一个算法执行结束后必须有数据处理结果输出，哪）有一个或多个输出。一个算法执行结束后必须有数据处理结果输出，哪 怕是输出错误的输出结果，没有输出的算法是毫无意义的。怕

4、是输出错误的输出结果，没有输出的算法是毫无意义的。5 5）能行性。解题方法中任何一个操作步骤在现有计算机软硬件条件下和逻）能行性。解题方法中任何一个操作步骤在现有计算机软硬件条件下和逻 辑思维中都能够实施实现。辑思维中都能够实施实现。辗转相除法：辗转相除法：又名欧几里得算法，是求两个正整数之最大公约数的算法。它是已又名欧几里得算法，是求两个正整数之最大公约数的算法。它是已 知最古老的算法，其可追溯至前知最古老的算法，其可追溯至前300300年。它首次出现于欧几里得的年。它首次出现于欧几里得的几几 何原本何原本中，而在中国则可以追溯至东汉出现的中，而在中国则可以追溯至东汉出现的九章算术九章算术。

5、它并不。它并不 需要把二数作质因数分解。需要把二数作质因数分解。列列1：求求112和和64的最大公约数！的最大公约数！1 1、算法的渊源、算法的渊源列列2：求求8192和和3072的最大公约数！的最大公约数！问题问题1：什么是最大公约数？什么是最大公约数？问题问题2：什么是最小公倍数？什么是最小公倍数？辗转相除法：辗转相除法：又名欧几里得算法，是求两个正整数之最大公约数的算法。它是已又名欧几里得算法，是求两个正整数之最大公约数的算法。它是已 知最古老的算法，其可追溯至前知最古老的算法，其可追溯至前300300年。它首次出现于欧几里得的年。它首次出现于欧几里得的几几 何原本何原本中，而在中国则可

6、以追溯至东汉出现的中，而在中国则可以追溯至东汉出现的九章算术九章算术。它并不。它并不 需要把二数作质因数分解。需要把二数作质因数分解。具体操作：具体操作：1 1、m mn n ，令，令r r为所得余数（为所得余数（0rb0rb），若），若r=0r=0，n n即为最大公约数，输出即为最大公约数，输出n,n,算法结束算法结束;否则，继续步骤否则，继续步骤2 2。2 2、互换：置、互换：置m=nm=n，n=rn=r，并返回第一步。，并返回第一步。1 1）112112除以除以6464，余数为（，余数为（）；）；2 2）（）（）除以（）除以（）余数为（）余数为（）；）；3 3）（）（）除以（）除以（）余

7、数为（）余数为（）。）。答：答：112112和和6464的最大公约数为（的最大公约数为（）。）。48486464484816160 01616484816161 1、算法的渊源、算法的渊源例：例：求求112112和和6464的最大公约数，算法如下的最大公约数，算法如下：2 2、算法的描述、算法的描述 表示算法的语言有表示算法的语言有自然语言自然语言、流程图流程图、伪代码伪代码等。等。用自然语言描述辗转相除法：用自然语言描述辗转相除法：1 1）输入）输入m m和和n n的值；的值；2 2）令）令r r等于等于m m除以除以n n的余数；的余数；3 3）如果）如果r=0r=0，则输出，则输出n n

8、值；否则令值；否则令m=nm=n，n=rn=r返回第返回第2 2步；步；4 4）结束。）结束。自然语言：自然语言：是人们日常所用的语言，如汉语、英语、德语等，使用这是人们日常所用的语言，如汉语、英语、德语等，使用这些语言不用专门训练，所描述的算法也通俗易懂。些语言不用专门训练，所描述的算法也通俗易懂。流程图：流程图：使用流程图描述算法，让人感到算法的流程描述清晰简洁，容使用流程图描述算法，让人感到算法的流程描述清晰简洁，容易表达选择结构；它不依赖于任何具体的计算机和计算机程序易表达选择结构；它不依赖于任何具体的计算机和计算机程序设计语言，从而有利于不同环境的程序设计。设计语言，从而有利于不同环

9、境的程序设计。图图 形形名名 称称功功 能能开始开始/结束框结束框表示算法的开始或结束表示算法的开始或结束输入输入/输出框输出框表示算法中变量的输入或输出表示算法中变量的输入或输出处理框处理框表示算法中变量的计算与赋值表示算法中变量的计算与赋值判断框判断框表示算法中的条件判断表示算法中的条件判断流程线流程线表示算法中的流向表示算法中的流向连接点连接点表示算法中的连接表示算法中的连接2 2、算法的描述、算法的描述表表1 1 流程图的基本图形及其功能流程图的基本图形及其功能开开 始始输入正整数输入正整数m和和nr=m除以除以n的余数的余数r=0?输出输出n的值的值结束结束m=n，n=r是是否否图图

10、1 1 用流程图表示辗转相除法用流程图表示辗转相除法伪代码：伪代码：是用介于自然语言和计算机语言之间的文字和符号来描述是用介于自然语言和计算机语言之间的文字和符号来描述算法的工具。它不使用图形符号，因此，书写方便，格式算法的工具。它不使用图形符号，因此，书写方便，格式紧凑，易于理解，便于向计算机程序语言过渡。紧凑，易于理解，便于向计算机程序语言过渡。用伪代码描述辗转相除法：用伪代码描述辗转相除法：输入输入m m和和n n的值的值r r等于等于m mod nm mod ndo while r0do while r0m=nm=nn=rn=rr=m mod nr=m mod nLoopLoop输出输

11、出n n值值2 2、算法的描述、算法的描述表表2 2 三种算法描述方式的优劣三种算法描述方式的优劣算法描述方式算法描述方式优点优点缺点缺点自然语言自然语言不需要专门训练，通俗易懂不需要专门训练，通俗易懂歧义性、语句长、循歧义性、语句长、循环和分支较多时难以环和分支较多时难以清晰表示、不便翻译清晰表示、不便翻译成计算机程序设计语成计算机程序设计语言言流程图流程图描述清晰简洁，容易表达选描述清晰简洁，容易表达选择结构，利于不同环境的程择结构，利于不同环境的程序设计序设计无法被计算机直接接无法被计算机直接接受进行操作受进行操作伪代码伪代码书写方便，格式紧凑，易于书写方便，格式紧凑，易于理解，便于向计

12、算机程序设理解，便于向计算机程序设计语言过渡计语言过渡种类繁多，语句不容种类繁多，语句不容易规范易规范 在运用计算机程序解决问题的过程中，算法设计有着在运用计算机程序解决问题的过程中，算法设计有着举足轻重的地位和作用，算法是程序设计的核心，是程序举足轻重的地位和作用，算法是程序设计的核心，是程序设计的灵魂。算法的好坏，直接影响着程序的通用性和有设计的灵魂。算法的好坏，直接影响着程序的通用性和有效性，影响着问题解决的效率。程序的编制依赖于算法的效性，影响着问题解决的效率。程序的编制依赖于算法的设计，程序的效率主要取决于算法的效率。设计，程序的效率主要取决于算法的效率。3 3、算法的地位、算法的地

13、位算法练习2：鸡兔同笼问题鸡兔同笼问题 一个笼子里有鸡和兔，现在只知道里面一个笼子里有鸡和兔，现在只知道里面一共有一共有35个头，个头，94只脚，鸡和兔各有多少只脚，鸡和兔各有多少只？只？设计一个求解的算法，并用设计一个求解的算法，并用自然语言自然语言和和流流程图程图描述出来。描述出来。程序与程序设计语言程序与程序设计语言1 1、定义：、定义：程序是一组机器操作的指令或语句的序列，是算法的一种描述。程序是一组机器操作的指令或语句的序列，是算法的一种描述。2 2、特征：、特征：1 1）每一个算法的步骤对应着程序设计语言的一个或多个语句，每）每一个算法的步骤对应着程序设计语言的一个或多个语句，每

14、个语句对应着一个或多个操作，每个操作都要求有执行对象，个语句对应着一个或多个操作，每个操作都要求有执行对象，并且根据对象状态变化形成动态的效果，同时可变的对象用变并且根据对象状态变化形成动态的效果，同时可变的对象用变 量来表示，变量的值的变化则可通过基本操作赋值来完成。量来表示，变量的值的变化则可通过基本操作赋值来完成。2 2）除非特别声明，程序都从）除非特别声明，程序都从第一条第一条语句开始顺序执行。语句开始顺序执行。3 3）总是施行操作于某些对象，这些对象通常称为数据。）总是施行操作于某些对象，这些对象通常称为数据。4 4）数据一般应该有属性和取值范围，即类型说明。）数据一般应该有属性和取

15、值范围，即类型说明。5 5）有时语句要求执行者作出判定，即在某种条件成立的情况下执）有时语句要求执行者作出判定，即在某种条件成立的情况下执 行一条或一组语句，否则执行另一条或另一组语句。行一条或一组语句，否则执行另一条或另一组语句。6 6）一条或一组语句可能需要执行一次以上，当一条或一组语句要）一条或一组语句可能需要执行一次以上，当一条或一组语句要 重复时，必须指明重复次数或重复的条件。重复时，必须指明重复次数或重复的条件。7 7）程序本身是一个静态实体，而执行语句的进程是动态的。）程序本身是一个静态实体，而执行语句的进程是动态的。一、程序一、程序3 3、程序的基本结构：、程序的基本结构：顺序

16、结构：顺序结构：各语句依次按照顺序执行。各语句依次按照顺序执行。选择结构：选择结构：通过检验条件是否成立来决定做还是不做的控件结构。通过检验条件是否成立来决定做还是不做的控件结构。循环结构：循环结构：在一定条件下需要重复执行的控件结构。在一定条件下需要重复执行的控件结构。S1S2.SnS1CCS1S2任何复杂的算法都可以用任何复杂的算法都可以用顺序结构顺序结构、选择结构选择结构、循环结构循环结构三种基本结构组合而成的三种基本结构组合而成的程序表示。程序表示。程序设计即是程序设计即是编写程序的过程编写程序的过程。一个高质量的程序，应具备以下条件：一个高质量的程序，应具备以下条件：1 1）建立正确

17、的数学模型和确定有效的计算方法；）建立正确的数学模型和确定有效的计算方法；2 2）运行结果必须正确，且在精度和其他各方面均满足要求；）运行结果必须正确，且在精度和其他各方面均满足要求；3 3）程序本身具有良好的结构，逻辑清楚，易读易懂；）程序本身具有良好的结构，逻辑清楚，易读易懂；4 4）程序运行时间尽可能短，同时尽可能合理地使用内存；）程序运行时间尽可能短，同时尽可能合理地使用内存；5 5）便于检查、修正、移植和维护。）便于检查、修正、移植和维护。二、程序设计二、程序设计语言种类语言种类优势优势不足不足机器语言机器语言能被计算机直接接受和执行能被计算机直接接受和执行程序设计任务繁重，程序设计

18、任务繁重，效率低下，与自然语效率低下，与自然语言存在巨大鸿沟，程言存在巨大鸿沟，程序员不易培养。序员不易培养。汇编语言汇编语言比机器语言更易理解比机器语言更易理解必须有语言翻译器支必须有语言翻译器支持，效率低，汇编源持，效率低，汇编源程序较冗长、复杂，程序较冗长、复杂，容易出错。容易出错。高级语言高级语言更接近自然语言，移植性好更接近自然语言，移植性好要语言翻译器支持要语言翻译器支持表表3 3 三种语言的优缺点三种语言的优缺点源代码：源代码：以汇编语言或高级语言所编写的程序被称为以汇编语言或高级语言所编写的程序被称为“源代码源代码”，这，这些代码需要我们逐一地输入到计算机中，并把他们以文件的些

19、代码需要我们逐一地输入到计算机中，并把他们以文件的形式保存起来，这个过程称为程序的编辑。保存的文件称为形式保存起来，这个过程称为程序的编辑。保存的文件称为“源文件源文件”。大多数的源文件都是以最简单的文本形式进行。大多数的源文件都是以最简单的文本形式进行存储的，和我们常见的存储的，和我们常见的.txt.txt文件没有区别，只不过为了表明文件没有区别，只不过为了表明它是源文件，通常会起不同的扩展名。它是源文件，通常会起不同的扩展名。三、程序的编辑和翻译三、程序的编辑和翻译高级语言的翻译程序有两种类型：高级语言的翻译程序有两种类型：编译程序编译程序和和解释程序解释程序。编译程序：编译程序：主要功能是将高级语言编写的程序在执行前翻译主要功能是将高级语言编写的程序在执行前翻译 成等效的机器语言程序，以便在机器上直接执行。成等效的机器语言程序，以便在机器上直接执行。解释程序：解释程序：对源程序的每一可能的行为都用机器语言编写一对源程序的每一可能的行为都用机器语言编写一 个子程序，用来模拟这一行为。因此对高级语言个子程序，用来模拟这一行为。因此对高级语言 程序的解释，实际上是调用了一系列的子程序来程序的解释，实际上是调用了一系列的子程序来 完成的。完成的。三、程序的编辑和翻译三、程序的编辑和翻译