c语言教程 (2).ppt

《c语言教程 (2).ppt》由会员分享，可在线阅读，更多相关《c语言教程 (2).ppt（22页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第二章第二章程序的灵魂程序的灵魂算法算法江苏大学计算机学院计算机科学系2教学要求、重点与难点教学要求、重点与难点要求、掌握算法的概念、了解算法特征、掌握用流程图、N-S结构流程图描述算法 3、了解结构化程序设计方法重点和难点、流程图设计、NS图设计23内内 容容 1 算法的概念 简单算法举例 算法的特性 怎样表示一个算法 5 结构化程序设计方法 本章小结 本章作业342.1算法的基本概念算法的基本概念一个程序包括两方面内容：一个程序包括两方面内容：1、对数据的描述数据结构（data structure）2、对操作的描述算法（algorithm）一、概念数据结构+算法程序计算一个算术式，要先乘除

2、后加减，这个规则就是算法。使用算盘，珠算口诀就是算法。工厂中生产一部机器，先把零件按一道道工序进行加工，然后，又把各种零件按一定法则组装成一部完整机器，它们的工艺流程就是算法；计算机解决问题的方法和步骤，就是计算机的算法。计算机解决问题的方法和步骤，就是计算机的算法。45例1：将两个变量X和Y的值互换。设X=5，Y=10。问题分析：两人交换座位，只要各自去坐对方的座位就行了，这是直接交换。问题分析：两人交换座位，只要各自去坐对方的座位就行了，这是直接交换。一瓶酒和一瓶醋互换，就不能直接从一个瓶子往另一个瓶子倒。必须借助于一个空瓶子，一瓶酒和一瓶醋互换，就不能直接从一个瓶子往另一个瓶子倒。必须借

3、助于一个空瓶子，先把酒倒入空瓶，再把醋倒入已倒空的酒瓶，最后把酒倒入已倒空的醋瓶，这样才能实现先把酒倒入空瓶，再把醋倒入已倒空的酒瓶，最后把酒倒入已倒空的醋瓶，这样才能实现酒和醋的交换，这是间接交换。酒和醋的交换，这是间接交换。计算机中交换两个变量的值不能用两个变量直接交换的方法，而必须采用间计算机中交换两个变量的值不能用两个变量直接交换的方法，而必须采用间接交换的方法。因此，设一中间变量为接交换的方法。因此，设一中间变量为Z。算法表示如下：算法表示如下：S1：将X值存入中间变量Z：XZS2：将Y值存入变量X中：YXS3：将中间变量Z的值存入Y中：ZYx510zy10552.2简单算法举例简单

4、算法举例56例2：计算计算N！（！（即求即求1*2*3*4*5*6*N）的值。的值。问题分析：该题有两个特点：问题分析：该题有两个特点：（1）重复执行乘法的操作，每乘一次，积都在变；）重复执行乘法的操作，每乘一次，积都在变；（2）乘数是一个有规则的等差级数，后项是前项加）乘数是一个有规则的等差级数，后项是前项加1。因此，可用以下算法实现。因此，可用以下算法实现。Sn=1*2*3*n S1*2 S2 S2*3 S3 S3*4 S4 Sn-1*n Sn 1 1*2 1*2*3 1*2*3*4 1*2*(n-1)*n 1 S1 初始初始 S=1；S=S*2；S=S*3；S*=4；S*=n；初始初始

5、i=1；S=1；i+;S=S*i；i+;S=S*i；i+;S*=i；i+;S*=i；67S1：指定一个具体的N值，如5N。S2：设一累乘变量M，初值置1；设一计数变量P，初值置1。S3：求积MPM，计数变量P增值P+1P。S4：判断：当PN时，返回第3步S3；否则，往下执行S5。S5：输出结果，M为所求之积。用自然语言描述如下：2.2简单算法举例简单算法举例78例 求两个自然数M和N的最大公约数。问题分析：最大公约数就是能同时整除M和N的最大正整数，这是一个古老的算术问题，这里介绍欧几里得（Euclid）算法。S1 输入两个自然数。S2 求余数：M/N，得到余数R（0RN?输出M结束输入NNY

6、（2 2）计算）计算 N N！1112（3 3）求两个自然数）求两个自然数M M和和N N的最大公约数。的最大公约数。N Y开始R=M%NM=N,N=R R=0?输出M结束输入M,N1213原因：1流程线没有限制 2、难于阅读和修改三、三种基本结构结构化程序（Structured Program）：1、它的基本思想是象玩积木游戏那样，只要有几种简单的结构，可以构成任意复杂的程序。2、程序设计规范化，便于用工程的方法来进行软件生产。3、基于这样的思想，1966年意大利的Bobra和Jacopini提出了三种基本结构A A块块B B块块 Y N条件条件?A A块块B B块块顺序结构顺序结构 选择结

7、构选择结构 1314 T F条件条件?A A块块 F T 条件条件?A A块块当型循环当型循环结构结构 直到型循环直到型循环结构结构 3 循环结构（亦称重复结构）循环结构（亦称重复结构）有限次重复执行某一块程序，再退出循环。循环结构有两种类型：(1)当型循环当型循环结构，先判断条件是否满足，若满足时就执行循环体，如条件不满足时就不执行循环体，并转到出口。(2)直到型循环直到型循环结构，它是先执行循环体，后判断。当条件不满足时继续执行循环体，条件满足时，停止执行，并转到出口。1415v三种基本结构具有以下特点：三种基本结构具有以下特点：1、只有一个入口和一个出口。、只有一个入口和一个出口。2、无

8、死语句。即没有永远都执行不到的语句。、无死语句。即没有永远都执行不到的语句。3、无死循环。即无永远执行不完的循环。、无死循环。即无永远执行不完的循环。四、用NS图表示算法美美国国学学者者I.Nassi和和B.Schneiderman于于1973年年提提出出了了一一种种新新的的绘绘制制流流程程图图的的方方法法。这这种种结结构构化化流流程程图图，完完全全去去掉掉了了在在描描述述中中引引起起混混乱乱的的带带箭箭头头的的流流程程线线，全全部部算算法法由由三三种种基基本结构的框表示。本结构的框表示。条件条件 T F A 块块 B 块块A块块B块块顺序结构顺序结构选择结构选择结构1516 A 块块直到条件

9、满足直到条件满足当条件满足时当条件满足时 A 块块当型循环结构当型循环结构直到型循环结构直到型循环结构例：例：开始开始输入输入X,YYZZX输出输出X,Y结束结束XY输入X,YYZXYZX输出X,Y1617开始M=1,P=1M=M*PP=P+1PN?输出M结束输入NNY输入输入NM=1,P=1 M=M*PP=P+1PN输出输出M1718N Y开始R=M%NM=N,N=R R=0?输出M结束输入M,N输入输入M，NR=M%NMNNRR0输出输出M18192.5结构化程序设计方法结构化程序设计方法结构化程序：用高级语言表示的结构化算法结构化程序设计，它的基本思想是象玩积木游戏那样，只要有几种简单类

10、型的结构化程序设计，它的基本思想是象玩积木游戏那样，只要有几种简单类型的结构，可以构成任意复杂的程序。这样可以是程序设计规范化，便于用工程的结构，可以构成任意复杂的程序。这样可以是程序设计规范化，便于用工程的方法来进行软件生产。方法来进行软件生产。I.自顶向下自顶向下II.逐步细化逐步细化III.模块化设计模块化设计IV.结构化编码结构化编码1920开始开始提出和分析问题提出和分析问题选择计算方法选择计算方法算法设计算法设计画框图画框图编写程序编写程序输入程序输入程序进行试算进行试算构造数学模型构造数学模型正式运行正式运行整理资料整理资料结束结束设计程序步骤设计程序步骤2021小小 结结、算法的特点、流程图、NS图、结构化程序设计步骤 2122作作 业业1.书面作业P37 2.4（3），（6），（8）22