程序设计基础内部讲义

郑州大学

2012级计算机科学与技术

程序设计基础内部讲义

讲授教师：王黎明

班级：________

姓名：

第一章解决问题的一般概念

要点

•日常生活问题的解决

•问题的类型

•计算机解决的问题

•解决问题的难点

一、日常生活问题的解决

1.明确问题：

2.理解问题：

理解问题提出方的知识背景；了解自己的知识背景；

关键是必须能与客户沟通并搞清楚解决问题涉及的细节。

3.寻找备选方案：

尽可能全面列出可行的备选方案。

4.从备选方案列表中找出最好的解决方案：

制定一个评定的标准，对所有的方案进行评价。

5.列出所选择的解决方案的指令：

这些有限的、分步的指令必须包含在第二步所确定的知识范围内。

6.评价解决方案：

检查它的结果是否正确，是否令用户满意，如果结果错误或者不能令人满意，必须重新

设计一个解决方案。

解决问题的这6个步骤可以适用于绝大多数情况。

大多数人可能不知道这6个步骤，但却一直在使用它们。

［例子］关于今晚做什么的问题

第一步：明确问题

如何度过一个漫长的夜晚。

第二步：理解问题。

大学生、住校、学校纪律、学习压力......

第三步：寻找备选

(1)看电视

(2)玩游戏

(3)去教室学习

(4)在寝室学习

第四步：从备选方案列表中找出最好的解决方窠。

去教室学习

第五步：准备一个步骤(指令)列表

(1)背书包(2)进教室(3)学习高数

(4)学习英语(5)学习线代(6)回寝室

第六步：评价这个方案。

有意义吗？快乐吗？

描述问题的格式

第一步：明确问题。

第二步：理解问题。

(1)在有助于问题理解的地方进行解释

(2)描述知识背景(包括解决问题所需要的各种知识)

第三步：寻找备选

方案优点缺点

(1)

(2)

(3)

第四步：从备选方案列表中找出最好的解决方案。

为什么选择这个方案？

第五步：列出所选择的解决方案的指令

(1)

(2)

(3)

第六步：评价这个方案。

这个方案有效吗？如果无效，如何进行改进？

［例子］两个整数的乘法

第一步：明确问题

整数乘法。

第二步：理解问题。

只能用笔和纸，知道乘法表，……

第三步：寻找备选

(1)传统算法

(2)英国算法

（3）alarusse（俄罗斯式）算法

（4）分治法

第四步：从备选方案列表中找出最好的解决方案。

传统算法。（什么标准？）

第五步：准备一个步骤（指令）列表

从右到左取出被乘数的每一位，与乘数相乘，把中间结果写在上一个中间结果的下面,

同时最低位往左偏移一位。把每」行全部加起来得到结果。

第六步：评价这个方案。

结果正确。

传统算法英国式算法

981981

12341234

3924981...

2943.1962..

1962..2943.

981...3924

12105541210554

alarusse（俄罗斯式）算法

98112341234把乘数和被乘数并排写在一起，每个操作数一

4902468列。

24549364936

12298721、将左边操作数整除2,在该操作数下面写下商;

2、将右边操作数乘以2,在该操作数卜面写下积。

611974419744

3、以上一次的商和积作为操作数重复以上规则,

3039488直到左边的操作数为1为止。

1578976789764、接着把左列中商为偶数的行全部删除，最后

7157952157952把右列中剩卜的数字加起来就得到结果。

3315904315904

不需要乘法表！！！

1631808631808

在计算机硬件中就用到了类似的算法进行乘法

1210554运算。

分治法

乘移位结果

1)09(u)12(x)4108....

2)09(u)34(y)2306..

3)81(v)12(x)2972..

4)81(v)34(y)02754

1210554

uvXxy=(102u+v)X(102x+y)

=104ux+102(uy+vx)+vy

二、问题的类型

•算法方案：

可以通过一系列的动作来解决问题的方案，叫做算法方案。

通过选定的步骤达到预期的目标，这些步骤叫做【算法】。

•启发式方案：

不能通过一些直观的步骤来解决的方案叫做启发式方案。

（这类问题除了必须有相应的知识和经验外,还需要经过不断的尝试和失败才能达到最

终目标。）

《韦氏大学词典（第九版）》中，算法的解释是“求解数学问题（如寻找最大公约数）的一个

过程，该过程步骤有限，通常还涉及重复的操作；广义地说，算法是按部就班解决一个问题

或为达到某个目标的过程。”

•问题解决者在算法方案和启发式方案中都可以采取6个步骤。

•在启发式方案中，第6步的正确性和恰当性标准不确定。

•在启发式方案中，问题解决者通常要反复执行这6个步骤，并在做出决定前仔细评价每

一种可能的方案。

同•种方案不一定在任何时候都适用，所以问题解决者在以后解决同样问题的时候必须

重新进行评价和分析。

•许多问题需要将这两种方案结合起来加以解决。

三、计算机解决的问题

•解决方案：

本课程中特指问题解决过程中的第5步所列出的指令序列。遵从这些指令才能得到满意

的结果。

•结果：

指成果或在计算机辅助下得到的完整答案。

•程序：

指用特定的计算机语言编写的一组用于解决问题的指令。

•计算机主要用来执行那些对于人来说非常困难或非常耗时的算法方案。

■计算复杂的微积分；

■将1,000,000个名字按字母排序,

•人类比计算机更善于使用启发式方案。

■下围棋

■说汉语

•处理启发式问题所涉及的计算机技术领域叫做人工智能。

人工智能可以让计算机建立自己的知识库并学会人类的语言等，通过人工的手段赋予计

算机智能。人工智能是处于发展中的计算机技术领域。

•启发式方案必须首先转化成算法形式才能供计算机使用。

四、解决问题的难点

•人类在解决问题时会遇到很多问题。

通常是不能很好地完成其中的一步或几步；

■可能错误地定义了问题；

■没有列出足够的备选方案；

■排除了好的方案，错误估计了利弊；

■可能搞错了步骤的顺序；

■过早专注细节、忽略了整体框架；

■没有对方案进行测试：

■错误或草率地评价解决方案；

在用计算机解决问题时，最难的事情之一就是编写指令。

“我不能解释我是如何知道的，但我就是知道“这种解释对计算机来说没有什么用处。计算机

是一种工具，它只能执行用户解释清楚的任务。

计算机有它自己特殊的通信系统，无论是程序员还是用户都必须了解它。它要求我们必须详

细阐明解决方案中的每个步骤而且顺序正确。

要知道，除非我们告诉它，否则计算机一无所知，然而虽然它很无知，但它对解决问题却很

有帮助。

五、小结

•问题解决过程中的6个步骤

•算法方案

•启发式方案

•计算机能够解决的问题

六、术语

•算法（algorithm）

•算法方案（algorithmicsolution）

•启发式方案（heuristicsolution）

•程序（program）

・结果（Result）

・解决方案（solution）

习题

一、简答

1、什么是问题的算法方案？

2、列举3个目前生活中遇到的可以用算法方案解决的问题。解释为什么这些问题在本质上

是属于算法的。

3、什么是问题的启发式方案？

4、列举3个目前生活中遇到的可以用启发式方案解决的问题。解释这些问题有什么启发性。

二、练习

1、针对下列每一项任务，写出一个有编号的、详细步骤的指令（方案），要尽量详细，使其

他人不问任何问题就可以独立完成工作。给出所需要的知识背景。

1）从教室走到学生宿舍、餐厅

2）图书馆借书

2、详述下列问题的知识背景

1）建房

2）计算一个学年的费用

3、写出从3个数中找出最大数的方案。详细列出每一步，使其他人可以使用该方案找到最

大的那个数。

4、关于机器人Otto的问题。Otto不是非常聪明。它的知识背景只有15条指令，它可以根

据设定的指令进行活动，只要这些指令在它知识背景的15条指令范围内。它按顺序执行指

令，也就是执行完一条指令后，紧接着执行下一条指令。它只按设定好的指令行事。下面列

出了Otto的指令集、假定、一个示例解决方案和问题。

Otto的知识背景包括如下指令：

身体指令

1）StandUp（起立）

2）Sitdown（坐下）

3）Takeastep（向前走一步----必须在站立时执行）

4）Turn（向右转90度--必须在站立时执行）

5）Raisearms（举起手臂，向前抬到与身体成直角）

6）Lowerarms（将手臂放到体侧）

算术指令

Otto的内存中有一个数，它可以将这个数加一或减-。指令开始执行时这个数是零。

7）Addone（将内存中的数加一）

8）Subtractone（将内存中的数减一）

9）Gotos（跳到s号指令，其中s是一个已知数，然后从s开始继续执行。s可能在当前位置

之前或之后）

条件指令

Otto可以进行3种不同类型的测试,根据测试结果的正确与否从两套指令中选取一套继续执

行。通过这种方式，Ott。可以决定下一步该怎么做。测试遵循下面的格式。

指令编号.Test：（测试内容）

yes：测试结果正确时执行的指令

no：测试结果错误时执行的指令

l）Test：你的手摸到什么东西了吗？yes：no：

2）Test：你的手摸到门了吗?yes：no：

3）Test：内存的数是零吗？yes：no：

循环指令

4）Repeadtxtimes[一组指令]（反复执行括号中的指令x次，其中x是己知数，而且是常

量。）

其他指令

5）Opendoor（开门，当Otto走过后，门自动关上）

6）Stop（停止指令的执行）

假定：

A.开始的时候，Otto是坐在椅子上的。

B.结束时，Otto要回到同一张椅子上坐下。

实例：

写一组指令让Otto向前走5步再向后走5步。

解决方案1：

1.StandUp

2.Repeat5times[Takeastep]

3.Repeat2times[turn]

4.Repeat5times[Takeastep]

5.Repeat2times[turn]

6.Sitedown

解决方案2：

1.StandUp

2.Repeat2times[a.Repeat5times[Takeastep]b.Repeat2times[turn]]

3.Sitedown

任务：

写一组指令让Otto逐步完成下列任务。

1）让Otto沿着每个边长为3步的正方形走，所有的弯都向右转，有多少种解决方案？

2）让Otto沿着每个边长为3步的正方形走，所有的弯都向左转。

3）让Otto向前走，一直走到墙，然后再走回来。当Otto抬起手的时候它可以摸到墙和椅子

的靠背。Otto和墙的距离可以任意步远。（提示：用到测试命令。）

4）让Otto向前走，•直走到墙，然后再走回来。当Otto抬起手的时候它可以摸到墙；但是

椅子太矮，Otto回来的时候摸不到椅子。

5）写一组指令使Otto可以走出迷宫。迷宫四面有墙、一个入口、一个出口。本题迷宫没有

死胡同，没有十字路口，出口和入口在同一个边上，入口在Otto出发点前面2步的位置，

当Otto面对入口时，出口在它右边3步的位置。注意要给出通用方案，不是针对某一个特

定的迷宫布局，满足条件的迷宫都有效。（提示：每走一步都要测试是否碰到墙或门）。图1

给出了3个迷宫样图。

图1任务5中迷宫的例子

1）修改上面的任务5中的解决方案使之适用于出口位置的变化。解决方案要允许出口在迷

宫的任何一边上。注意解决方案要确保让Otto从任意的出口走回到椅子处。图2给出了3

个迷宫样图。

图2任务6中迷宫的例子

附：

描述问题的格式

第一步：明确问题。

第二步：理解问题。

(1)在有助于问题理解的地方进行解释

(2)描述知识背景(包括解决问题所需要的各种知识)

第三步：寻找备选

方案优点缺点

(1)

(2)

(3)

第四步：从备选方案列表中找出最好的解决方案。

为什么选择这个方案？

第五步：列出所选择的解决方案的指令

(1)

(2)

(3)

第六步：评价、测试这个方案。

这个方案有效吗？如果无效，如何进行改进？

第二章通过计算机解决问题的方法

要点

•分析问题：问题的初步分析

•结构图：解决方案的总体布局和结构

•IPO图：给出模块的输入、处理过程和输出

•算法：解决方案的指令序列

•内部和外部文档：程序相关信息

•测试解决方案：

•编程：

•计算机能解决的问题是能通过一种算法来描述的问题。

•该问题可以通过一些简单的指令序列来描述。

•这些指令必须用计算机能够理解的方式书写，计算机以程序中指定的顺序执行它们。

•如果这些指令以适当的规则书写，严格地遵循计算机语言的语法，那么计算机就可以顺

利地解决问题。

•计算机只会简单的按顺序地执行输入的指令，它没有发现程序中算法错误的能力。

一、分析问题

为了很好地解决问题，程序员应该首先进行需求分析。

分析问题的一种有效方法是它分成4个部分：

1.已知数据

2.所需结果

3.所需处理

4.备选方案

问题分析图(PAC)

已知数据所需结果

第一部分：问题中给出的数据或用户提供的第二部分：问题要求解的目标。

数据。包括需要的信息和格式。

可以填写具体的数值或数据项的名称。

所需处理备选方案

第三部分：需要对数据进行的处理。包括公第四部分：备选方案。

式或其他形式的处理过程。求解思想等。

问题分析图的目的在于理清思路，它帮助程序员抓住问题中的主要数据和信息，忽略次要信

息，问题分析图是一种很有用的分析工具。

例：计算一个员工的总薪水

计算公式：总薪水=工作时间*单位时间薪水

已知数据所需结果

工作时间，单位时间薪水总薪水

所需处理备选方案

总薪水=1、工作时间和单位时间薪水定义为常量

工作时间*单位时间薪水2、工作时间和单位时间薪水定义为变量，

在运行时输入。

二、结构图(交互图)

问题求解的下一步是把个大而复杂的问题分解为若干个子问题，称为模块(module),并

把模块连在一起表示出模块间的相互关系。每个模块完成一项功能；

模块中有一个用于控制的模块，称为控制模块(controlmodule)或主模块(mainmodule)o

交互图的绘制方法

采用自上而下的方法。

自上而下是把一个问题分解为若干子问题，并按照从图的顶部执行到底部的顺序来说明和阐

述这些子问题。概括了整个解决方案的模块称为控制模块，它控制所有的数据处理。该模块

要完成的子任务列在其下方。

注意：

交互图描述了要解决的子问题，显示出了问题各个部分之间的相互关系，但没有给出解决

方法。

控制

0000

三、IPO图(Input-Processing-Output)

IPO图将问题分析图中描述的信息进一步细化。

它更详细地指出哪些数据项是输入数据，对这些数据要做什么处理，哪些信息作为最终结果

输出。

输入处理模块引用编号输出

所有的输入数据（问顺序列出处理过程（结构图中的模块引所有需要输出的数

题分析图第一栏）问题分析图第三、第用编号据项（问题分析图

四栏）第一、第二栏）

填写顺序：1、输出；2、输入；3、处理;

例：计算员工总薪水的IPO图

输入处理模块引用编号输出

工作时间1、输入工作小时数0000总薪水

单位时间薪水2、输入单位小时薪水1000

3、计算薪水2000

4、打印薪水3000

5、结束

四、写算法

写出结构图中每个模块的指令序列。

为了让计算机能够理解，指令必须遵循特定的规则书写，这些规则后面章讲解。

算法综合了结构图和IPO图的信息，给出了一个详细的解决方案。

算法有很多表示方法：

伪代码（pseudo-code流程图、NS图、PAD图等。

算法和流程图表格

算法流程图注解测试内部文档外部文档

填写算法和测试数据、

流程图的测试方法

注释、变量

、注意事项，

等。

五、内部和外部文档

•内部文档：阐述程序的相关信息。

内部文档可以使其他程序员在最短的时间内读懂程序(可读)。

包括：程序员、程序的概要说明、程序修改信息、开发该程序的注意事项等。

编程的同时撰写。

•外部文档：由帮助手册或帮助菜单组成。

是为用户编写的。

良好的外部文档可以帮助用户在最短的时间内知道如何使用该系统，并解答用户在使用

过程中可能遇到的问题。

包括：使用指南、输入定义、安装指南、命令解释。

书面文档或电子文档。

六、测试解决方案

•对于给定的解决方案，要通过测试确定它是否满足用户的需求，是否存在逻辑错误和计

算错误。

•测试数据的选择；

•不要预先假设解决方案是正确的；

•错误越早出现越好。

七、编程

•将解决方案编写成由计算机语言描述的程序。

•将在计算机语言课上详细介绍。

习题

1,可以在银行自动提款机(AutomaticTellerMachine,ATM)上使用银行信用卡，请针对

自动取款问题，绘制一张问题分析图、结构图，列出所有可能的模块。

第三章计算机解决问题的初级概念

要点：

•变量和常量

•数据类型

•操作符

•表达式和赋值

目标：

通过本章的学习，您应该能够做到：

•区分变量和常量

•了解类型的基本知识

•识别操作符、操作数和结果

•理解赋值

能使用计算机解决的问题可以分为3类：

1.计算型

指包括数学计算过程的问题；

2.逻辑型

指包含关系或逻辑处理的问题；

3.反复型

指需要反复执行一组数学计算型或逻辑型指令的问题

为了解决这些问题，本章介绍一些基本的概念

一、常量与变量

处理过程中有两种数据：常量和变量。

1.常量:

固定不变的数据，在整个指令执行过程中都不会改变。

例如：3.1415926是一个常量。

也可以给常量命名，起一个能表示其含义的名字。

例如:PI,圆周率

2.变量：

它的值在处理过程中可以改变。

程序员必须给使用的每一个变量命名，通过使用这个名字对变量进行操作（访问）。

假定名字为x的变量，它的值是512。

x512

如果变量x在程序执行的过程中改变，改变为1024。

则变量的值就会改变，但它的名字不会改变。

x1024

起一个能够表示其明确含义的名字，既容易理解也方便记忆。

假定Age为表示年龄的变量，它的值是18。

Age18

如果变量Age在程序执行的过程中改变，改变为19。

则变量的值就会改变，但它的名字不会改变。

Age19

二、数据类型

计算机能表示的数据是离散数据、是受限制的，不能表示所有可能的数据，只能表示部分

数据。

计算机及编程语言把能够表示的这部分数据分成几个集合。

1.数值型：

整数：1,0,-1,567,...

实数：3.1415926,0.000246,...

2.字符型：，a',，A',T,…

3.字符串型：“China”,"12345”,“2006-09-20”,...

4.逻辑型：TRUE,FALSE

三、操作符

•操作符(operator)：用于通知计算机对数据进行什么样的操作。数学操作符、关系操

作符、逻辑操作符及其它操作符。

・操作数(operand)：是操作符连接、处理的数据。

•结果值(resultant)：是操作完成后所得到的结果。

数学操作符(mathematicaloperactor)

操作符符号例子结果

加+3.0+5.28.2

减-7.5-5.02.5

乘*8.0*540.0

除/9/42.25

整除\(DIV)9\42

取模MOD9MOD54

关系操作符(relationaloperator)

操作符符号例子结果

等于=5=7FALSE

小于<5<7TRUE

大于>5>7FALSE

小于等于<=5<=7TRUE

大于等于>=5>=7FALSE

不等于<>5<>7TRUE

逻辑操作符(logicaloperator)

操作符符号例子结果

与ANDTRUEANDTRUETRUE

或ORTRUEANDTRUETRUE

非NOTNOTTRUEFALSE

逻辑运算的真值表

ABAANDBAORB

TrueTrueTrueTrue

TrueFalseFalseTrue

FalseTrueFalseTrue

FalseFalseFalseFalse

ANOTA

TrueFalse

FalseTrue

操作的优先级：

1.先括号里后括号外；

2.先计算优先级高的再计算优先级低的;

3.同级别的从左向右执行；

怎么计算?

32+C*9/5x+y<x*yx>1ANDX<3

yMOD4=0ANDyMOD100o0ORyMOD400=0

yearMOD4=0ANDyearMOD100o0ORyearMOD400=0

操作的级别操作数的数据类型结果值的数据类型

1：\,MOD,*,/数值型数值型

2：+,-数值型数值型

3：=，<9>9<=,

数值型、字符型逻辑型

>=,<>

4：NOT逻辑型逻辑型

5：AND逻辑型逻辑型

6：OR逻辑型逻辑型

四、表达式

表达式(expression)：使用操作符对数据和操作数进行处理。

例：

建立数学表达式：

4Y

X(3Y+4)---------------

X+6

对应的计算机表达式为：

X*(3*Y+4)-4*Y/(X+6)

1.将所有的括号、操作数和操作符写在同一行上。

2.将省略的操作符添上，不能使用任何数学中的省略操作符。

3.添加所有必须的括号

计算整型变量x的第1、2、3、4、5位

试评价？

Xmod10

Xmod10

(X\10)mod10

(X\10)mod10

((X\10)\10)mod10

(X\100)mod10

(((X\10)\10)\10)mod10

(X\1000)mod10

((((X\10)\10)\10)\10)mod10

(X\10000)mod10

赋值语句

•赋值语句(assignmentstatement)：通过<-将表达式的结果值送给变量，从此这个变

量就具有这个结果值。原来的值被替换成新值。

・Area<-length*width

r-10

Area-3.14159*r*rArea=?

r-20Area=?

Area-3.14159*r*rArea=?

计算整型变量X的第1、2、3、4、5位

Xxmod10

xmod10123455

x-x\101234

xmod104

x-x\10123

xmod103

x*-x\1012

xmod102

x-x\101

xmod101

术语:

常理、变量

数据、数据类型

操作符、表达式、等式、优先级、结合方式

习题

一、简答

1、什么是常量？什么是变量？

2、指出下列表达式或赋值中操作数的类型以及结果的类型。

操作数的类型结果的类型

A*B

OD

NOTE

FANDG

X<-B

3、计算F的值，其中A=12,B=3,C=6,D=2：

1)F<-A+B/C-D

2)F<-(A+B)/C-D

3)F<-A+B/(C-D)

4)F<-(A+B)MODC

5)F<-(A+B)\D

4、将下列式子写出计算机可识别的形式：

、Z+Y

1）X=Y+3Z-

2）XA=50Y1H--4-G-Z—+1）-Y

3）X=（X-Y）2

5、建立表达式计算下列问题（自行设置变量名）。

1）房间的面积。

2）房间的墙壁面积，不包括其中的一扇门和两扇窗。

3）求5个数的平均数。

6、计算结果，其中A=FALSE,B=TRUE,C=FALSE,D=TRUE

1)R<-AANDBORCANDD

2)R<-NOT(AANDB)ORNOT(DANDC)

3)R<-(AORB)AND(DORC)

4)R<-NOT(AANDBORC)AND(AORBANDD)

5)R<-CORNOT(AANDB)AND(AORB)ORNOT(AORC)

7、根据条件建立表达式。

Dxe[0,1000]

2）x是[0,1000]中的奇数

第四章程序的灵魂一一算法

1算法的概念

2简单算法举例

3算法的特性

4怎么表示一个算法

4.1用自然语言表示算法

4.2用流程图表示算法

4.3三种基本结构和改进的流程图

4.4用N-S流程图表示算法

5结构化程序设计方法

对数据的描述。

在程序中要指定数据的类型和数据的组织形式，即数据结构(DataStructure)

对操作的描述。

也就是算法(Algorithm)

数据是操作的对象，操作的目的是对数据进行加工处理。

著名计算机科学家NikilausWirth提出一个公式：

数据结构+算法=程序

程序设计人员应具备的知识

一个程序设计人员应具备4个方面的知识。

程序=算法+数据结构+程序设计方法+语言工具和环境

•算法是灵魂

•数据结构是加工对象

•语言是工具

•编程需要采用合适的方法。

一、算法的概念

•做任何事情都有一定的步骤。

•为解决一个问题而采取的方法和步骤，就称为“算法”

•对同一个问题，可以有不同的解决方法和步骤。

有不同的算法。

计算机算法的分类

1、数值运算算法

数值运算的目的是求数值解。

这类计算有现成的模型,可以运用数值分析方法,因此对数值运算方面的算法研究比较深入,

算法比较成熟。

2、非数值运算算法

非数值运算包括的面十分广泛，最常见的是用于事务管理领域。

【种类繁多，要求各异，难以规范化】

•图书检索

•人事管理

•行车调度

•控制

二、简单算法举例

【例1】求1*2*3*4*求

方法一

步骤-：先求1*2,得到结果2。

步骤二：将步骤一得到的结果再乘以3,得到新的结果6。

步骤三：将步骤二得到的结果再乘以4,得到新的结果24.

步骤四：将步骤三得到的结果再乘以5,得到最后结果120.

问题：1*2*...*1000结论：这样的算法太繁琐,

怎么办？表示方法不通用

方法二

设置两个变量：部分积p,乘数i,乘积结果计算出来以后作为新的部分积

S1：使P-1

S2：使i-2

S3：使p*i,乘积仍放在变量p中，既p=p*ip=2

S4：使i的值加1,既i-i+1i=3

S5：使p*i,乘积仍放在变量p中，既p=p*ip=6

S6：使i的值加1,既i-i+1i=4

S7：使p*i,乘积仍放在变量p中，既p-p*ip=24

S8：使i的值加1,既i-i+1i=5

S9：使p*i,乘积仍放在变量p中，既p-p*Ip=120

S10：使i的值加1,既i-i+1i=6

用循环算法表示：

SI：P-1

S2：i-2

S3：p—p*i1

S4：i*-i+1i重复部分

S5：如果i不大于5(i<=5),

则重新执行步骤S3以及其后的S4和S5；

否则算法结束。

最后得到的p的值就是5!的值。

如果题目改为求1*3*5*7*9*11

算法如下：

SI：p*-1

S2：i-3

S3：p—p*i1

S4：i-i+2J重复部分

S5：如果

则返回S3；

否则算法结束。

【例2】有50个学生，要求将他们之中成绩在80分以上者打印出来。

用n表示学生学号，nl代表第-个学生学号，ni代表第i个学生学号。用代表学生成

绩，gl代表第一个学生成绩，gi代表第i个学生成绩。

算法表示

SI：i-1

S2：如果gi>=80,则打印ni和gi,否则不打印

S3：i-i+1

S4：如果i<=50,返回S2,继续执行；否则，算法结束。

S1：循环的初始化

S2：处理<—1

S3：循环变量的更新

S4：循环控制条件一!

S5：循环结束

【例3］求1-1/2+1/3-1/4+...+1/99-1/100

100

£(-l)n+l/n

n=l

算法表示

S1：sign一-1

S2：sum-0

S3：dcno一1

S4：sign一(-1)*sign

S5：term一sign*(1/dcno)

S6：sum-sum+term

S7：deno—deno+1

S8：当denov=100时,转S4继续执行；否则，算法结束.

【例4】对一个大于或等于3的正整数，判断它是不是一个素数。

素数定义：

素数是指个除了1和该数本身之外，不能被其它任何整数整除的数。

方法：

将n作为被除数，将2到(n—1)之间各个整数轮流作为除数，如果都不能被整除，则

n为素数。

算法表示

S1：输入n的值

S2：i-2

S3：n被i除，得余数r

S4：如果r=0,表示n能被i整除，则打印n“不是素数”，算法结束；否则执行S5

S5：i-i+1

S6：如果i<=n-l,转S3继续执行；否则打印n“是素数”，然后算法结束。

改进算法

i<=n/2或i<=4n

S1：输入n的值

S2：i-2

S3：n被i除，得余数r

S4：如果r=0,表示n能被i整除，则打印n“不是素数”，算法结束；否则执行S5

S5：i*-i+1

S6：如果i<=4,转S3继续执行；否则打印n“是素数”，然后算法结束。

三、算法的特性

1、有穷性

••个算法应包含有限的操作步骤，不能是无限的。并且每•步都必须在有限时间内完

成。

•“有穷性”也必须是“在合理的范围之内”。

2、确定性

•算法中的每一个步骤都应当是确定的，不应当是含糊的、模棱两可的。

•算法的含义应当是唯一的，不应当产生“歧义性”。并且，在任何情况下，算法只有

唯一的一条执行路径。即相同的输入只能得到相同的输出。

3、有零个或多个输入

•执行算法时需要从外界获取信息

4,有一个或多个输出

•算法的目的是为了求解，“解”就是输出。没有输出的算法是没有意义的。

5、有效性

•算法中的每一个步骤都应当能有效地执行，并得到确定的结果。

•算法中描述的操作，都可以通过已实现的基本运算执行若干次组合来实现。

程序与算法不同

•程序是算法用某种程序设计语言的具体实现。

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

例如：

操作系统，它是在无限循环中执行的程序，因而不是算法。

然而可把操作系统的各种任务看成一些单独的问题，每一个问题由操作系统中的•个

子程序通过特定的算法实现。该子程序得到输出结果后便终止。

一个"好'’的算法不仅要满足具体问题的需求，而且还要有较高的时间效率和空间效率。即尽

可能运行时间短，占用存储空间少。

判断一个正整数N是否为素数。

算法一：

在2〜N-1范围内查找有没有N的因数，若有，则N不是素数；否则N是素数。

算法二：

在2〜4N范围内查找有没有N的因数，若有，则N不是素数，否则N是素数。

显然，算法二判断查找的范围少，因此时间效率高。

四、怎样表示一个算法

表示一个算法，用很多方法。

•自然语言

•传统流程图

•结构化流程图

•伪代码

•NS图

•计算机语言

四（1）用自然语言表示算法

自然语言就是人们日常使用的语言：

汉语、英语或其它语言。

1.通俗易懂

2.文字冗长

3.容易出现“歧义性”

含义不太严格，要根据"上下文''才能判断其正确含义。

4.用自然语言描述包含分支和循环的算法，不方便。

四（2）用流程图表示算法

流程图是用一些图框表示各种操作。

输入输出框判断框

I或

处理框流程线连接点

注释框

ANSI(AmericanNationalStatdardInstitude)规定的常用流程图符号

菱形框

菱形框的作用是对一个给定的条件进行判断，

根据给定的条件是否成立来决定如何执行其后

的操作。

一个入口，两个出口

连接点

连接点（小圆圈）是用于将面在不同地方的流程

图连接起来。

相同标号的连接点是互相连接在一起的。

实际上，它们是同一个点，只是画不下才分开

来画。

用连接点，可以避免流程线的交叉或过长，使

流程图清晰。

注释框

注释框不是流程图中必要的部分，不反映流程和操作，只是为了对流程图中某些框的操作做

必要的补充说明，以帮助阅读流程图的人更好地理解流程图的作用。

【例5】求5!的算法

增加的打

印处理

【例6】将50名学生中成绩在80分以上者的学号和成绩打印出来。

XlfWni,gi/

i-i+1

（结束）

增加学生学号和成绩的输入

【例7］将求1-1/2+1/3-1/4+...+1/99-1/100的算法用流程图表示

100

100]_

X(-l)n+l/nI(-1)

n=ln=1n

【例8】将判断素数的算法用流程图表示

一个流程图包括以下部分：

1.表示相应操作的框；

2.带箭头的流程线；箭头的方向表示流程执行的先后次序。

3.框内外必要的文字说明。

流程图特点：

1.形象直观，比较清楚地显示框之间的逻辑关系；

2.这种流程图占用篇幅比较多，尤其当算法比较复杂时，画流程图既费时又不方便。

四(3)三种基本结构和改进的流程图

1.传统的流程图的弊端

•传统的流程图用流程线指出各框的执行顺序，对流程线的使用没有严格限制。

BS型算法(abowlofspaghetti)。

•难以阅读，难以修改，从而使算法的可靠性和可维护行难以保证。

•为了提高算法质量，必须限制箭头的滥用，不允许无规律地使流程随意转向。

解决的方法

规定几种基本结构，然后由这些基本结构按一定规律组成算法结构，整个算法的结构是由上

而下地将各个基本结构顺序排列起来的。

2、三种基本结构

1966年，Bohra和Jacopini提出了以下三种基本结构。

(1)顺序结构

在执行完A框所指定的操作后，必然接着

执行B框所指定的操作。

(2)选择结构、分支结构

此结构中包含一个判断框，根据给定的条件p是否成立而选择执行A框或B框。

注意：无论p条件是否成立，只能执行A框或B框之不能既执行A框又执行B框。

(3)循环结构、重复结构

[11当型(While)循环结构

当给定的条件pl成立时，执行A框操作，执行完

A框后，再判断条件pl是否成立，如果仍然成立

,再执行A框，如此反复执行A框，直到某一次

pl条件不成立为止，此时不执行A框，而从b点

脱离循环结构。

一种变形

a

:G成U丁t一不成『

A

b

[2]直到型（Until型）循环结构

先执行A框，然后判断给定的条件p2

是否成立，如果不成立，则执行A框，

然后再对p2条件作判断，如果条件仍

然不成立，继续执行A框，如此反复执

行A框，直到某一次p2条件成立为止

,此时不执行A框，而从b点脱离循

环结构。

Until结构可以由While结构来实现。

两种循环结构的区别

•Until先执行循环体A,后判断条件。至少执行一次A框

•While先判断条件，后执行循环体Ao可能一次也不执行A框

例：打印1,2,3,4,5

三种结构的特点

•只有一个入口

•只有一个出口

•结构内的每一部分都有机会被执行到。

对每一个框来说，都存在•条从入口到出口的路径通过它。

•结构内不存在“死循环”（无终止的循环）

关于基本结构的一个结论

已经证明：由顺序结构、选择结构、循环结构顺序组成的算法结构，可以解决任何复杂的问

题。

由基本结构所构成的算法属于“结构化''的算法，它不存在无规律的转向，只在基本结

构内才允许分支和向前或向后的跳转。

派生结构

规则：只要具有基本结构的4个特点的结构都可以作为基本结构。

b

多分支结构

a

四(4)用N-S流程图表示算法

•N-S图是美国Nassi和Shneiderman于1973年提出的结构化流程图。

•Chapin在1974年又对其进一步扩展。因此，N-S图又称为Chapin图或盒状图。

N-S图的目标是开发一种不破坏结构化基本构成元素的过程设计表示。

(1)顺序结构:

P

(2)选择结构:立

当p成立

(3)循环结构:A

A

直到p成一立

While型Un忖型

【例9】求5!的算法用N-S图表示

【例10】打印50个学生中成绩高于80分者的学号和成绩。

【例111求