第2章程序的灵魂算法备课笔记Word格式文档下载.docx
《第2章程序的灵魂算法备课笔记Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《第2章程序的灵魂算法备课笔记Word格式文档下载.docx（15页珍藏版）》请在冰点文库上搜索。
算法的分析与设计，即解决问题的操作步骤，是最为关键的一步，称之为程序灵魂。
比如说，从徐州到上海，可以坐飞机，坐动车，坐火车等等，这些不同的方法或者步骤，在计算机的求解问题中，就是选用不同的算法。
下面就具体介绍第二章程序的灵魂——算法。
第2章程序的灵魂——算法
2.1算法的概念
★几个基本概念
v数据：
是计算机程序处理的对象，可以是整数、实数、字符，也可以是图像、声音等的编码表示。
v数据结构：
程序中指定数据的类型与数据的组织形式
●在程序设计语言中，与数据结构密切相关的便是数据的类型和数据的存放。
v软件=程序+文档。
v程序：
用程序设计语言表达问题的求解过程。
●程序=数据结构+算法。
v算法：
用某种工具（文字、数学公式、框图、计算机伪代码等）解决问题的步骤。
程序设计
1.对于较小的简单问题，一般采用下列步骤进行程序设计：
●确定数据结构,如：
变量、数组
●确定算法
●编写程序代码
●上机调试
●整理并写出文档资料
2.对于较大的复杂问题采用的是“模块化、自顶向下、逐步细化”的程序设计方法。
2.2算法的基本表达方法
（1）什么是算法？
简单地理解，算法是为解决一个特定问题而采取的确定的、有限的方法和步骤。
（2）算法的特性（P19）
正确的算法应该满足5个特性：
•有穷性：
一个算法应包含有限的操作步骤，而不是无限的。
•确定性：
算法中的每个步骤都应该是确定的，不应含糊不清。
（不应产生歧义）
•有效性：
每个步骤都应有效执行，得到确定结果。
如果b=0，则执行a/b就不能有效执行。
•有零个或多个输入：
从外界取得必要的信息。
•有一个或多个输出：
算法的目的就是求解，“解”就是输出，没有输出的算法是没有意义的。
（3）算法的表达方法
v自然语言
v专用工具：
如流程图——
传统流程图
N-S流程图
v伪代码
v计算机语言
传统流程图
流程图是用一些图框表示各种操作。
用图形表示算法，直观形象，易于理解。
美国国
家标准化协会ANSI（AmericanNationalStandardInstitute）规定了一些常用的流程图符号。
★传统流程图的符号
★传统流程图表达算法实例
传统流程图的弊端
传统流程图用流程线指出各框的执行顺序，对流程线的使用没有严格限制，使用者可以不受限制地使流程随意地转来转去，使流程图变得毫无规律。
如图。
§
这种算法难以阅读，也难以修改，从而使其可靠性和可维护性难以保证。
如果写出的算法能限制流程的无规律任意转向，阅读起来就很方便。
但是，算法上难免会包含一些分支和循环，而不可能全部由一个一个框顺序组成。
1966年，Bohra和Jacopini提出了以下三种基本结构，作为表示一个良好算法的基本单元。
1、顺序结构
2、选择结构，或选取结构，或分支结构，如图。
PS：
无论条件P是否成立，只能执行A框或B框之一。
无论走哪一条路径，在执行完A或B之后，都经过b点，然后脱离本选择结构。
A或B两个框中可以有一个是空的，即不执行任何操作，如右图。
（3）循环结构，又称重复结构。
有两类循环结构：
①当型（While型）循环结构
功能：
当条件p1成立时，执行操作A，执行完A后，再判断p1是否成立，如果仍然成立，再执行A，如此反复执行A框，直到p1不成立为止，此时脱离循环结构。
②直到型（Until型）循环
功能：
先执行操作A，然后判断条件P2是否成立，如果P2条件不成立，则执行A，然后再对P2条件作判断，如果P2仍然不成立，又执行A……如此反复，直到P2条件成立为止，此时不再执行A，脱离本循环结构。
以上三种基本结构，有以下共同特点：
（1）只有一个入口。
（示图）
（2）只有一个出口。
请注意，不要将菱形框的出口和选择结构的出口混淆。
（3）结构内的每一部分都有机会被执行到。
对每一个框来说，都应有一条从入口到出口的路径通过它。
（4）结构内不存在“死循环”（无终止的循环）。
由基本结构所构成的算法属于“结构化”的算法。
基本结构不一定只限于上面三种，只要具有上述4个特点的都可以作为基本结构，如图。
N-S流程图
1973年由美国学者I.Nassi和B.Shneiderman提出，故取两位学者的姓首字母命名之。
N-S图：
去掉了流程图中带箭头的流程线，把整个算法描述在一个矩形框中。
伪代码
用传统流程图和N-S图表示算法，直观易懂，但画起来比较费事。
因此，为了设计算法时方便，常用一种称为伪代码（pseudocode）的工具。
伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。
伪代码表达算法实例
“打印x的绝对值”的算法可以用伪代码表示如下：
IFxispositiveTHEN
printx
ELSE
print–x
或者
若x为正
打印x
否则
打印–x
总之，用伪代码写算法并无固定的、严格的语法规则，只要把意思表达清楚，并且书写的格式要写成清晰易读的形式。
计算机语言
用计算机语言表示算法必须严格遵循所用语言的语法规则，这是和伪代码不同的。
练习：
求5!
N-S流程图
伪代码
BEGIN（算法开始）
1=>
t
2=>
i
whilei<
=5
{t×
i=>
i+1=>
i}
printt
END（算法结束）
计算机语言（C）
voidmain（）
{
inti，t;
t=1;
i=2;
while（i<
=5）
{
t=t*i;
i=i+1;
}
printf（"
%d"
，t）;
}
作业
2.4（3）：
有3个数a、b、c，要求按大小顺序把它们输出。
2.4（7）：
求两个数m和n的最大公约数。
①用传统流程图表示求解算法。
②用N-S图表示求解算法。
2.4（3）
2.4（7）
小结
1、算法是为解决一个特定问题而采取的确定的、有限的方法和步骤。
2、传统流程图的画法
3、N-S流程图的画法
升级会员 