算法和程序设计实例和表示
2 posters
算法和程序设计实例和表示
由 maomao112 周四 五月 08, 2014 12:50 pm
第1章 算法和算法的表示
科学技术的进步，社会生产力的发展，都是由于相关问题不断地得到解决的结果。在当今的信息社会中，许多问题的解决都使用了电子计算机(以下简称计算机)。
使用计算机解题，首先要正确理解题意，接着是寻找或设计解题方法，并对解题方法的正确性进行论证。按照正确的解题方法，可以设计正确的算法，即，规定每一个解题步骤中要求计算机执行的处理，以及各个解题步骤的执行次序。有了正确的解题算法，可以使用合适的程序设计语言，将算法表达成计算机程序，计算机将能按照设计好的程序，高速、自动地进行计算，帮助我们获得问题的解。
1.1 确定解决问题的方法
[ 问题1 ]
使用一根长度为L厘米的铁丝，制作一个面积为S平方厘米的矩形框，要求计算该矩形框应有的高h和宽w。这里，铁丝的长度L和面积S可根据需要指定，如图1.1.1所示，具体解法如下。
L
图1.1.1 用铁丝制作一个矩形框
[ 方法1 ]
设矩形框的高为h厘米，宽为w厘米，则
，
整理后得到下面的一元二次方程
，
对于这个一元二次方程可以使用公式
，
计算方程的根。设d= ，则
当d>0时，方程的一个根是矩形框的宽w = ，
另一个根就是矩形框的高h = ；
当d=0时，方程有两个相同的根，矩形框的高和宽相等，是一个正方形；
当d<0时，方程无实数根，这种情况下我们不能制作出符合要求的矩形框。
想一想
什么是算法？算法和普通数学公式的主要区别是什么？
1.2 把解决问题的方法步骤化
为使计算机能按照上面确定的方法1进行计算，光有数学公式是不够的，我们必须把解决问题的方法步骤化，即：需要以某种方式告诉计算机，第一步做什么，下一步做什么，一般地，第i步做什么，第i+1步做什么。
对于上面确定的方法1而言，在进行计算之前，计算机必须要知道铁丝的长度L和矩形框的面积S，即，要把计算所需的原始数据L和S输入到计算机中，然后才能按确定的公式一步一步地进行计算，并输出最终的计算结果。
事实上，计算机是一种按照设计好的程序，快速、自动地进行计算的电子设备。计算机开始计算之前，必须把解决某个问题的程序存贮在计算机的内存中，通常，一个程序由如下两部分组成：
1.指令部分：由一系列的指令构成，每条指令都是要求计算机执行的一个动作。由适当的指令构成的一个序列，描述了解决这个问题的计算过程。
2.数据部分：用来存贮计算所需的原始数据、计算的中间结果或最终结果。
下面是装在计算机内存中的示意性的程序P1，这个程序用来计算矩形框的高度和宽度。
图中的一个方框代表内存中的一个存贮单元，每个这样的存贮单元可以存贮一条指令或一个数据。内存中的每个存贮单元都有惟一确定的编号，这样的编号称为内存单元的地址，标在每个方框的左边。
读这个示意性的程序P1时应注意：
1.程序中的指令，是从第一条开始，一条一条顺序地执行的；
2.执行地址为6的内存单元中的指令：若d=0 转到 12时，如果变量d中的数据是0，则改变指令执行的次序，使地址为12的内存单元中的指令，成为下一条将要被执行的指令；如果变量d中的数据不等于0，则继续往下执行地址为7的内存单元中的指令。
3.任何时候，只要执行了一条“停止”指令，整个程序就终止执行。
[ 程序P1 ]
1
指令区
输出文字“请输入长度：”
2
接收输入数据(铁丝的长度)送到变量L
3
输出文字“请输入面积：”
4
接收输入数据(方框的面积)送到变量S
5
计算 ，结果送变量d
6
若d=0 转到 12
7
若d<0 转到 15
8
输出文字“两条不同的边长”
9
输出: (L+ )/4
10
输出: (L- )/4
11
停止
12
输出文字“两条相同的边长”
13
输出 :L/4
14
停止
15
输出文字“无解”
16
停止
17
数据区
变量L
18
变量S
19
变量d
对于计算机而言，程序是非常重要的，计算机的工作完全依赖于程序，有什么样的程序，计算机就作什么样的工作。计算机能进行图文并茂的文稿的编辑处理，是因为计算机的内存中装载并运行了一个文字处理程序，例如WORD；计算机能在因特网上进行浏览，是因为计算机的内存中装载并运行了一个浏览程序，例如Explorer。如果在计算机的内存中装载并运行解决问题1的程序P1，则计算机就能作为解决问题1的工具。
为了解决不同的问题，人们必须设计不同的程序。设计一个程序时，需要考虑：
1.数据的存贮。计算所需要的原始数据(例如铁丝的长度和矩形框的面积)、计算产生的中间结果(例如计算 )需要存贮在不同的变量中(例如变量L、S、d)。
2.计算的过程。首先必须确定解决问题的方法，然后必须把该方法步骤化，即，用计算机能执行的动作(指令)，来描述问题的计算过程。这意味着程序的计算过程，不仅必须指出动作(例如，计算从哪些变量中取出的数据，经求和后，所得的结果存贮到哪个变量中)，也必须指出动作的次序(例如，当前这个动作执行完成后，下一个将被执行的动作是什么)。
计算机指令的种类是有限的，典型的有：
输入：通过输入设备(例如键盘)，程序接收从外界输入的数据，将数据存贮到指定的变量中。
输出：把文字、变量中存贮的数据或计算产生的结果，通过输出设备(例如显示器或打印机)显示或打印出来。
数学运算：进行加、减、乘、除、平方、开方等数学运算，通常，计算所需的数据从变量中获得，计算的结果可以存贮到指定的变量中。
逻辑判断：可以对指定的两个数据进行大小或相等性比较，比较的结果称为逻辑值(真或假)，也可以使用逻辑运算(例如与、或、非)，把若干个较简单的判断连接起来，形成一个复杂的判断。
1.3 算法的概念和表示方法
1.3.1 算法的概念
计算机是一种按照程序，高速、自动地进行计算的机器。用计算机解题时，任何答案的获得都是按指定顺序执行一系列指令的结果。因此，用计算机解题前，需要将解题方法转换成一系列具体的、在计算机上可执行的步骤，这些步骤能清楚地反映解题方法一步步“怎样做”的过程，这个过程就是通常所说的算法。
“算法”(algorithm)一词是从9世纪阿拉伯数学家花拉兹米(al-Khowwarizmi)的名字派生的。他一生发现了许多求解算术问题的方法，并写了一本叫作《合并与回代》(aljabr w’almuguabalah)的书。合并与回代这两个词是指解方程时所用的两个主要过程。这本书后来翻译成了拉丁文，书名被简化成现在人们所熟悉的“代数学”(algebra)。
从上面解决问题1的程序P1中，我们可以看到一个算法应该具有如下的特征：
1.有穷性。一个算法必须保证在有限个操作步骤执行后终止，即，操作步骤不能是无限的。例如，在解问题1的过程中，不论方程有0个、一个或两个根，最多只需要执行11个操作步骤，算法的执行便能终止。算法中可以有重复执行的步骤，只要这些步骤的执行能终止。广义地说，“有穷性”一般指操作步骤或完成操作的时间在合理的范围内。有些算法，虽然是有穷的，但它所花费的时间如果超出合理的限度，例如，需要一台或一组现代高速计算机运行几十甚至几百年，才能得到结果，那么这种算法，也不能算是有效的算法。
2.确定性。算法中的每个步骤必须有确切的含义，而不应当是含糊的、模棱两可的。例如，步骤
输出： L/正整数，
是无法执行的，因为没有指定L除以哪一个正整数，所以，这个步骤是不确定的。
3.能行性。算法中的每一个步骤都要足够简单，是实际能做的，而且能在有限的时间内完成。例如，程序P1中内存地址为9的指令
输出: (L+ )/4，
是在d≥0的情况下才被执行的，求正数的平方根、求和以及计算两个正数的商，所有这些计算都能在非常短的时间内实际完成。但如果没有d≥0这个前提，我们就不能完成这些计算。
4.有0个或多个输入。所谓输入是指算法在执行时需要从外界取得信息，其目的是为算法的某些阶段建立初始状态。如果建立初始状态所需的信息已经包含在算法中了，那就不再需要输入。例如，解问题1的算法需要两个输入(铁丝的长度L和矩形框的面积S)。
5.有一个或多个输出。算法的目的是用来求解问题，问题解决的结果应以一定的方式输出。例如，求解问题1的结果为：
两条不同的边长 宽度 高度 (三个输出)；
两条相同的边长 边长 (两个输出)；
无解 (一个输出)。
“无解”告诉我们在一定的情况下(d<0)该问题没有解，这也是结果，也是输出的信息。没有输出的算法是毫无意义的。
算法：是在有限步骤内求解某一问题所使用的具有精确定义的一系列操作规则。每条规则都必须是确定的(即有确切定义的)、能行的(例如，像除数为0这样的操作步骤是不行的)、不能有二义性的(不能想象某个变量的值既是3同时又是5这样的事发生)。算法要有一个清晰的起始步，且每一个步骤只能有一个确定的后继步骤，从而组成一个步骤的有限序列。步骤的终止表示问题得到解答或指出这一算法不能求得问题的解答。因为算法总是对数据进行加工处理，所以算法的执行过程中通常需要有数据输入和数据输出这样的步骤。
事实上，在日常生活中经常要用算法解决问题，只是在那里一般不叫算法罢了，例如，乐谱是乐队指挥和演奏的算法；菜谱是厨师做菜的算法等等。在漫长的岁月中，人们发现了很多算法。例如欧几里得(Euclid)发明的求两个自然数的最大公约数算法，早期希腊学者埃拉多塞尼(Eratosthenes)发明的寻找素数的筛法等都是著名的算法例子。电子计算机的出现，开创了算法研究的新时代。人们可以将算法编写成程序提交给计算机执行，从而迅速获得解题结果。著名计算机科学家克努特(D.E.Knuth)认为：计算机科学是算法的学习。
1.3.2 算法的表示
可以用多种不同的方法来描述一个算法，流程图(flowchart)是一种比较直观易用的、用图形来描述算法的方法。图1.3.1是用流程图描述的算法1。
被普遍使用的《信息处理用流程图符号标准》是由美国国家标准化学会(ANSI)制定的，这套标准中最基本、最常用的成分有：
①处理框(矩形框)：框中指出要处理的内容，该框有一个入口和一个出口。
②判断框(菱形框)：用来表示分支情况，菱形框的四个顶点中，通常用上面的顶点表示入口，视需要用其余两个顶点来表示出口。
③连接框(圆形框)：用于连接因画不下而断开的流程线。
④流程线(有向线段)：指出流程控制方向，即，动作的次序。
⑤开始、结束符(椭圆框)：用来表示算法的开始和结束。一个算法只能有一个开始处，但可以有多个结束处。
一般常用的还有平行四边形表示输入、输出框，这里都用矩形框替代了。
图1.3.1是按照问题1的解决方法1，用流程图表示的算法1：
算法1从“开始”处执行，依次执行了前四个处理框内的动作后，使用者已把计算所需的原始数据(铁丝的长度和矩形框的面积)输入，并分别存贮到程序的变量L和S中。第五框内的动作
d ←
表示计算 的值，计算的结果送到变量d中存贮。
接着执行的是由判断框表示的选择动作(即，分支情况)：取出变量d中的数据，若这个数据的值为0，则沿着标有Y（Yes）的有向线段，执行该有向线段所指向的动作(输出文字“两条相同的边长”)；若变量d中取出的数据不为0，则沿着标有N(No)的有向线段，执行该有向线段所指向的动作(判断d<0是否为真)。
开始
输出文字“请输入长度：”
接收输入数据(长度)送变量L
输出文字“请输入面积：”
接收输入数据(面积)送变量S
d ←
d=0?
输出文字“两个相同的边长”
输出：L/4
结束
输出文字“无解”
d<0?
输出文字“两个不同的边长”
输出： 、
结束
结束
N
Y
Y
N
图1.3.1 计算问题1的算法1
我们也可以使用自然语言，例如汉语，加上一些必要的数学符号，来描述解决问题的算法。下面是用自然语言描述的解决问题1的算法1：
1.(输入原始数据)输入：铁丝的长度送变量L，
矩形框的面积送变量S；
2.(计算d)计算 ，结果送变量d。
3.(判断是否仅有一个根)如果d = 0则转到7。
4.(判断是否无根)如果d < 0则转到9。
5.(方程有两个根)输出：文字“两条不同的边长”。
数值 (L+ )/4 (宽度)
(L- )/4 (高度)
6.(算法终止)停止。
7.(方程有一个根)输出：文字 “两条相同的边长”
数值 L/4 (边长)
8.(算法终止)停止。
9.(方程无实数根)输出：文字 “无解”
10.(算法终止)停止。
自然语言的主要缺点是有时会存在二义性，例如，“打死老虎”，既可以表示“打的是一只死老虎”，也可以表示“打死了一只老虎”，这将引起某些计算步骤的不确定性。
此外，我们还可以用“伪代码”(pseudo code)来描述算法。伪代码使用某些程序设计语言中的控制结构，来描述算法中各步骤的执行次序和模式，使用自然语言、数学符号或其他符号，来表示计算步骤要完成的处理或需要涉及的数据。使用伪代码可以免去许多绘图的麻烦，但前提是必须熟悉某种程序设计语言。下面是用伪代码描述的解决问题1的算法1：
read (L ← 铁丝的长度 ， S ← 矩形框的面积 )
d ←
if ( d=0 ) write ( “两条相同的边长” ， L/4 )
else if ( d<0 ) write ( “无解” )
else write ( “两条不同的边长” ，(L+ )/4 ，(L- )/4 )
1.3.3 变量和变量的用途
程序中的变量和数学公式中的变量是有区别的。程序中的变量是计算过程中要用到的数据的存贮单元，通过输入指令的执行，程序将外界输入的数据存贮到指定的变量中，程序计算的结果也可以存贮到指定的变量中。一旦把数据存贮到某个变量，例如变量v中，只要我们不把新的数据送到变量v，那么，变量v将永久地保存着这个数据。如果在计算过程中需要使用v中的数据，我们从变量v中可以取出这个数据，注意，此时变量v中仍然存贮着这个数据不变。实际上，只要我们不把新数据存贮到变量v中，可以从变量v中任意多次地读取该数据，原先存贮着的数据是不会发生任何变化的。
在一个问题的计算过程中，可能需要使用多个变量，来保存计算过程中的多个数据，我们应该为每个变量指定一个适当的名称。
[ 例1 ]
设计一个算法，计算一批数据的算术平均值。这批数据由使用者从键盘输入，使用者预先不指定数据的个数。并约定：输入0时表示本次计算所需的全部数据已输入完毕(即，所有有效的数据，其值均不为0，这是为了对问题的叙述方便起见，而作的假定，实际情况并非完全如此)。
计算数据的算术平均值，是用途广泛的一种计算，例如，统计某个学校某年级的体育成绩，统计某公司一个季度的经营业绩等等。
首先考虑该问题中涉及的数据，设计适当的变量来保存这些数据：
d: 用来存贮从键盘输入的一个数据，或存贮表示输入结束的数字记号0。
c: 用来记录已经输入的数据个数。
sum:用来计算数据之和。
下面考虑计算的过程。为了计算一组数据的平均值，必须知道这批数据的个数c，以及所有这些数据之和sum。显然，我们需要的计算结果是sum/c。因此，我们首先应该通过输入指令，把使用者输入的数据(也可能是表示结束的0)送到变量d中。如果变量d中接收到的是一个非零的数据，这个数据应该被累加到变量sum中，同时，使变量c的值增加1，表示接收到了一个新数据。
图1.3.2是计算数据算术平均值的算法。
图1.3.2 计算数据算术平均值的算法
请注意变量sum和变量c的用法。
变量c用来作为计数器，即，记录某个规定的事件已发生的次数，例如，已经输入到计算机中的有效数据的个数。当我们发现送入到变量d中的数据是一个有效数据时，计数器c的计数动作为：
c ← c+1，
这个动作的效果是，计算箭头右边的数学公式，把计算所得的结果存贮到变量c中。当我们计算c+1时，首先是从变量c中取出数据(最初，该变量的值是0，在算法的执行过程中，该变量中记录的是到目前为止已经接收到的有效数据的个数)，接着将它加上1，然后将结果送回到变量c中。因此，这个计数动作的效果是，使变量c在原值的基础上增加了1，即，记录了最新的有效数据的个数。
变量sum用来作为累加器，使用累加器来计算数据之和。累加器sum的初值是0，当第一个有效数据送到变量d中时，累加的动作为：
sum ← sum + d，
即，计算变量sum(置初值为0)与变量d(存贮着刚输入的第一个有效数据)之和，结果送到累加器sum中。当变量d中接收到一个新的有效数据时，仍然执行累加动作sum ← sum + d，即，计算变量sum(第一个有效数据)与变量d(第二个有效数据)之和，结果仍送到变量sum中。因此，当我们执行了n次这样的累加动作后，已经输入的n个有效数据之和将出现在累加器sum中。
显然，在算法的执行过程中，接收到一个有效数据时需要进行计数，并进行累加处理。这样的动作将不断地执行，直到接收到表示输入结束的0时，输出计算结果。随即，算法终止执行。
计数器(counter)
算法执行过程中，用来记录某种事件发生次数的变量。假定变量c作为计数器。
计数器的典型用法：
1.在算法执行的准备阶段中，应预置初值0。向计数器c预置初值0的动作为： c ← 0。
2.算法执行过程中，每当指定的事件发生时，对计数器c计数， 即，把事件已经发生的次数(在计数器c中)加1后，结果仍然送回到计数器c中。 计数器c的计数动作为: c ← c+1。
累加器(accumulator)
算法执行过程中，用来形成并存贮数据之和的变量。假定变量sum作为累加器，变量d中存贮了符合要求的一个数据。
累加器的典型用法：
1.在求和开始前的准备阶段中，应预置初值0。向累加器sum预置初值0的动作为：sum ← 0。
2.算法执行过程中，每遇到一个符合要求的数据时，把这个数据累加到累加器中，即，计算累加器与该数据之和，并把结果重新存贮到累加器中。数据d累加到sum的动作为：sum ← sum + d。
1.3.4 算法的执行流程
算法的执行流程，是指算法中各个处理步骤的执行次序和模式。通常需要如下三种不同的执行流程：
1.顺序模式：执行完一个处理步骤step1后，接着执行下一个处理步骤step2。
图1.3.3 顺序模式
例如，上面右图中顺序执行的两个计算步骤，计算并输出一个整数的平方。
2.选择模式：对某个情况e进行判断，当结果为真时，执行处理步骤step1，否则执行处理步骤step2。选择模式使算法能根据情况的不同，在准备好的两个处理步骤中，选择执行一个适当的处理步骤。
图1.3.4 选择模式
上面的右图中，顺序执行的三个计算步骤，第二个计算步骤(用虚线框围住的部分)是一个按选择模式进行的处理过程，其效果是判别变量a和b内数据的大小，把较大的数据送到变量d。这样，顺序执行的三个计算步骤完成后，我们将看到计算的结果：两个输入数据的最大值。
图中“a>b?”表示的是判断变量a的值是否大于变量b的值。
3.重复模式：对某个情况e进行判断，当结果为真时，执行处理步骤step，然后再次判断这个情况e，当结果为真时，再次执行处理步骤step，并继续判断情况e。总是重复上述过程，直到情况判断的结果为假。
图1.3.5 重复模式
上面的右图中，顺序执行的四个计算步骤，第一个步骤是接收原始数据n，第二个步骤是为重复处理做必要的准备，这包括：累加器s置初值0，变量k置初值1。第三个计算步骤(用虚线框围住的部分)是一个按重复模式进行的处理过程，其效果是计算 的和，结果将在变量s中逐步地形成，第四个步骤用来输出变量s中的最终计算结果。
这三种不同的流程模式通常会被组合起来使用，以表示各种较为的复杂问题的算法。例如，在重复模式的处理步骤step中，使用选择模式描述的处理动作，或在选择模式的处理步骤step1或step2中，使用重复模式描述该步的处理过程等等。
[ 例2 ]
设计一个算法，计算并输出一批数据中正数和负数的个数。这批数据由使用者从键盘输入，使用者预先不指定数据的个数，输入0时表示输入结束(即，所有有效的数据，其值均不为0)。
首先考虑该问题中涉及的数据，设计适当的变量来保存这些数据：
d: 用来存贮从键盘输入的一个数据，或表示输入结束的0。
c1: 计数器，用来计数正数数据的个数。
c2: 计数器，用来计数负数数据的个数。
下面考虑计算的过程。首先应该通过输入指令，把使用者输入的数据(也可能是表示结束的0)送到变量d中。如果变量d中接收到的是一个有效的数据，进行适当的处理后，继续接收下一个数据进行处理，即，本算法的主要处理过程，应该用重复模式加以描述。对于一个有效数据d的处理为：若d是正数，则使c1计数，否则使c2计数，显然，我们将使用选择模式来描述对一个有效数据的处理过程。此外，在算法的开始阶段，我们应设置计数器的初值，而在算法的结束阶段，则应输出计算的结果。
图1.3.6是本算法的流程图。
图1.3.6 计算正数个数和负数个数的算法
本章练习
一、思考题
1.一个正确的算法应该包含哪些基本特征？
2.变量的作用是什么？简述计数器和累加器的作用和用法。
二、练一练
1.使用流程图表示如下问题的算法：输入三条线段的长度a、b、c，判断这三条线段能否构成一个三角形，若能，输出“Y”，否则输出“N”。
2.使用流程图表示如下问题的算法：使用者从键盘输入一批数据，使用者预先并不指定数据的个数，输入0时即表示输入结束(即，所有有效的数据，其值均不为0)。计算并输出所有正数的算术平均值和所有负数的算术平均值。
科学技术的进步，社会生产力的发展，都是由于相关问题不断地得到解决的结果。在当今的信息社会中，许多问题的解决都使用了电子计算机(以下简称计算机)。
使用计算机解题，首先要正确理解题意，接着是寻找或设计解题方法，并对解题方法的正确性进行论证。按照正确的解题方法，可以设计正确的算法，即，规定每一个解题步骤中要求计算机执行的处理，以及各个解题步骤的执行次序。有了正确的解题算法，可以使用合适的程序设计语言，将算法表达成计算机程序，计算机将能按照设计好的程序，高速、自动地进行计算，帮助我们获得问题的解。
1.1 确定解决问题的方法
[ 问题1 ]
使用一根长度为L厘米的铁丝，制作一个面积为S平方厘米的矩形框，要求计算该矩形框应有的高h和宽w。这里，铁丝的长度L和面积S可根据需要指定，如图1.1.1所示，具体解法如下。
L
图1.1.1 用铁丝制作一个矩形框
[ 方法1 ]
设矩形框的高为h厘米，宽为w厘米，则
，
整理后得到下面的一元二次方程
，
对于这个一元二次方程可以使用公式
，
计算方程的根。设d= ，则
当d>0时，方程的一个根是矩形框的宽w = ，
另一个根就是矩形框的高h = ；
当d=0时，方程有两个相同的根，矩形框的高和宽相等，是一个正方形；
当d<0时，方程无实数根，这种情况下我们不能制作出符合要求的矩形框。
想一想
什么是算法？算法和普通数学公式的主要区别是什么？
1.2 把解决问题的方法步骤化
为使计算机能按照上面确定的方法1进行计算，光有数学公式是不够的，我们必须把解决问题的方法步骤化，即：需要以某种方式告诉计算机，第一步做什么，下一步做什么，一般地，第i步做什么，第i+1步做什么。
对于上面确定的方法1而言，在进行计算之前，计算机必须要知道铁丝的长度L和矩形框的面积S，即，要把计算所需的原始数据L和S输入到计算机中，然后才能按确定的公式一步一步地进行计算，并输出最终的计算结果。
事实上，计算机是一种按照设计好的程序，快速、自动地进行计算的电子设备。计算机开始计算之前，必须把解决某个问题的程序存贮在计算机的内存中，通常，一个程序由如下两部分组成：
1.指令部分：由一系列的指令构成，每条指令都是要求计算机执行的一个动作。由适当的指令构成的一个序列，描述了解决这个问题的计算过程。
2.数据部分：用来存贮计算所需的原始数据、计算的中间结果或最终结果。
下面是装在计算机内存中的示意性的程序P1，这个程序用来计算矩形框的高度和宽度。
图中的一个方框代表内存中的一个存贮单元，每个这样的存贮单元可以存贮一条指令或一个数据。内存中的每个存贮单元都有惟一确定的编号，这样的编号称为内存单元的地址，标在每个方框的左边。
读这个示意性的程序P1时应注意：
1.程序中的指令，是从第一条开始，一条一条顺序地执行的；
2.执行地址为6的内存单元中的指令：若d=0 转到 12时，如果变量d中的数据是0，则改变指令执行的次序，使地址为12的内存单元中的指令，成为下一条将要被执行的指令；如果变量d中的数据不等于0，则继续往下执行地址为7的内存单元中的指令。
3.任何时候，只要执行了一条“停止”指令，整个程序就终止执行。
[ 程序P1 ]
1
指令区
输出文字“请输入长度：”
2
接收输入数据(铁丝的长度)送到变量L
3
输出文字“请输入面积：”
4
接收输入数据(方框的面积)送到变量S
5
计算 ，结果送变量d
6
若d=0 转到 12
7
若d<0 转到 15
8
输出文字“两条不同的边长”
9
输出: (L+ )/4
10
输出: (L- )/4
11
停止
12
输出文字“两条相同的边长”
13
输出 :L/4
14
停止
15
输出文字“无解”
16
停止
17
数据区
变量L
18
变量S
19
变量d
对于计算机而言，程序是非常重要的，计算机的工作完全依赖于程序，有什么样的程序，计算机就作什么样的工作。计算机能进行图文并茂的文稿的编辑处理，是因为计算机的内存中装载并运行了一个文字处理程序，例如WORD；计算机能在因特网上进行浏览，是因为计算机的内存中装载并运行了一个浏览程序，例如Explorer。如果在计算机的内存中装载并运行解决问题1的程序P1，则计算机就能作为解决问题1的工具。
为了解决不同的问题，人们必须设计不同的程序。设计一个程序时，需要考虑：
1.数据的存贮。计算所需要的原始数据(例如铁丝的长度和矩形框的面积)、计算产生的中间结果(例如计算 )需要存贮在不同的变量中(例如变量L、S、d)。
2.计算的过程。首先必须确定解决问题的方法，然后必须把该方法步骤化，即，用计算机能执行的动作(指令)，来描述问题的计算过程。这意味着程序的计算过程，不仅必须指出动作(例如，计算从哪些变量中取出的数据，经求和后，所得的结果存贮到哪个变量中)，也必须指出动作的次序(例如，当前这个动作执行完成后，下一个将被执行的动作是什么)。
计算机指令的种类是有限的，典型的有：
输入：通过输入设备(例如键盘)，程序接收从外界输入的数据，将数据存贮到指定的变量中。
输出：把文字、变量中存贮的数据或计算产生的结果，通过输出设备(例如显示器或打印机)显示或打印出来。
数学运算：进行加、减、乘、除、平方、开方等数学运算，通常，计算所需的数据从变量中获得，计算的结果可以存贮到指定的变量中。
逻辑判断：可以对指定的两个数据进行大小或相等性比较，比较的结果称为逻辑值(真或假)，也可以使用逻辑运算(例如与、或、非)，把若干个较简单的判断连接起来，形成一个复杂的判断。
1.3 算法的概念和表示方法
1.3.1 算法的概念
计算机是一种按照程序，高速、自动地进行计算的机器。用计算机解题时，任何答案的获得都是按指定顺序执行一系列指令的结果。因此，用计算机解题前，需要将解题方法转换成一系列具体的、在计算机上可执行的步骤，这些步骤能清楚地反映解题方法一步步“怎样做”的过程，这个过程就是通常所说的算法。
“算法”(algorithm)一词是从9世纪阿拉伯数学家花拉兹米(al-Khowwarizmi)的名字派生的。他一生发现了许多求解算术问题的方法，并写了一本叫作《合并与回代》(aljabr w’almuguabalah)的书。合并与回代这两个词是指解方程时所用的两个主要过程。这本书后来翻译成了拉丁文，书名被简化成现在人们所熟悉的“代数学”(algebra)。
从上面解决问题1的程序P1中，我们可以看到一个算法应该具有如下的特征：
1.有穷性。一个算法必须保证在有限个操作步骤执行后终止，即，操作步骤不能是无限的。例如，在解问题1的过程中，不论方程有0个、一个或两个根，最多只需要执行11个操作步骤，算法的执行便能终止。算法中可以有重复执行的步骤，只要这些步骤的执行能终止。广义地说，“有穷性”一般指操作步骤或完成操作的时间在合理的范围内。有些算法，虽然是有穷的，但它所花费的时间如果超出合理的限度，例如，需要一台或一组现代高速计算机运行几十甚至几百年，才能得到结果，那么这种算法，也不能算是有效的算法。
2.确定性。算法中的每个步骤必须有确切的含义，而不应当是含糊的、模棱两可的。例如，步骤
输出： L/正整数，
是无法执行的，因为没有指定L除以哪一个正整数，所以，这个步骤是不确定的。
3.能行性。算法中的每一个步骤都要足够简单，是实际能做的，而且能在有限的时间内完成。例如，程序P1中内存地址为9的指令
输出: (L+ )/4，
是在d≥0的情况下才被执行的，求正数的平方根、求和以及计算两个正数的商，所有这些计算都能在非常短的时间内实际完成。但如果没有d≥0这个前提，我们就不能完成这些计算。
4.有0个或多个输入。所谓输入是指算法在执行时需要从外界取得信息，其目的是为算法的某些阶段建立初始状态。如果建立初始状态所需的信息已经包含在算法中了，那就不再需要输入。例如，解问题1的算法需要两个输入(铁丝的长度L和矩形框的面积S)。
5.有一个或多个输出。算法的目的是用来求解问题，问题解决的结果应以一定的方式输出。例如，求解问题1的结果为：
两条不同的边长 宽度 高度 (三个输出)；
两条相同的边长 边长 (两个输出)；
无解 (一个输出)。
“无解”告诉我们在一定的情况下(d<0)该问题没有解，这也是结果，也是输出的信息。没有输出的算法是毫无意义的。
算法：是在有限步骤内求解某一问题所使用的具有精确定义的一系列操作规则。每条规则都必须是确定的(即有确切定义的)、能行的(例如，像除数为0这样的操作步骤是不行的)、不能有二义性的(不能想象某个变量的值既是3同时又是5这样的事发生)。算法要有一个清晰的起始步，且每一个步骤只能有一个确定的后继步骤，从而组成一个步骤的有限序列。步骤的终止表示问题得到解答或指出这一算法不能求得问题的解答。因为算法总是对数据进行加工处理，所以算法的执行过程中通常需要有数据输入和数据输出这样的步骤。
事实上，在日常生活中经常要用算法解决问题，只是在那里一般不叫算法罢了，例如，乐谱是乐队指挥和演奏的算法；菜谱是厨师做菜的算法等等。在漫长的岁月中，人们发现了很多算法。例如欧几里得(Euclid)发明的求两个自然数的最大公约数算法，早期希腊学者埃拉多塞尼(Eratosthenes)发明的寻找素数的筛法等都是著名的算法例子。电子计算机的出现，开创了算法研究的新时代。人们可以将算法编写成程序提交给计算机执行，从而迅速获得解题结果。著名计算机科学家克努特(D.E.Knuth)认为：计算机科学是算法的学习。
1.3.2 算法的表示
可以用多种不同的方法来描述一个算法，流程图(flowchart)是一种比较直观易用的、用图形来描述算法的方法。图1.3.1是用流程图描述的算法1。
被普遍使用的《信息处理用流程图符号标准》是由美国国家标准化学会(ANSI)制定的，这套标准中最基本、最常用的成分有：
①处理框(矩形框)：框中指出要处理的内容，该框有一个入口和一个出口。
②判断框(菱形框)：用来表示分支情况，菱形框的四个顶点中，通常用上面的顶点表示入口，视需要用其余两个顶点来表示出口。
③连接框(圆形框)：用于连接因画不下而断开的流程线。
④流程线(有向线段)：指出流程控制方向，即，动作的次序。
⑤开始、结束符(椭圆框)：用来表示算法的开始和结束。一个算法只能有一个开始处，但可以有多个结束处。
一般常用的还有平行四边形表示输入、输出框，这里都用矩形框替代了。
图1.3.1是按照问题1的解决方法1，用流程图表示的算法1：
算法1从“开始”处执行，依次执行了前四个处理框内的动作后，使用者已把计算所需的原始数据(铁丝的长度和矩形框的面积)输入，并分别存贮到程序的变量L和S中。第五框内的动作
d ←
表示计算 的值，计算的结果送到变量d中存贮。
接着执行的是由判断框表示的选择动作(即，分支情况)：取出变量d中的数据，若这个数据的值为0，则沿着标有Y（Yes）的有向线段，执行该有向线段所指向的动作(输出文字“两条相同的边长”)；若变量d中取出的数据不为0，则沿着标有N(No)的有向线段，执行该有向线段所指向的动作(判断d<0是否为真)。
开始
输出文字“请输入长度：”
接收输入数据(长度)送变量L
输出文字“请输入面积：”
接收输入数据(面积)送变量S
d ←
d=0?
输出文字“两个相同的边长”
输出：L/4
结束
输出文字“无解”
d<0?
输出文字“两个不同的边长”
输出： 、
结束
结束
N
Y
Y
N
图1.3.1 计算问题1的算法1
我们也可以使用自然语言，例如汉语，加上一些必要的数学符号，来描述解决问题的算法。下面是用自然语言描述的解决问题1的算法1：
1.(输入原始数据)输入：铁丝的长度送变量L，
矩形框的面积送变量S；
2.(计算d)计算 ，结果送变量d。
3.(判断是否仅有一个根)如果d = 0则转到7。
4.(判断是否无根)如果d < 0则转到9。
5.(方程有两个根)输出：文字“两条不同的边长”。
数值 (L+ )/4 (宽度)
(L- )/4 (高度)
6.(算法终止)停止。
7.(方程有一个根)输出：文字 “两条相同的边长”
数值 L/4 (边长)
8.(算法终止)停止。
9.(方程无实数根)输出：文字 “无解”
10.(算法终止)停止。
自然语言的主要缺点是有时会存在二义性，例如，“打死老虎”，既可以表示“打的是一只死老虎”，也可以表示“打死了一只老虎”，这将引起某些计算步骤的不确定性。
此外，我们还可以用“伪代码”(pseudo code)来描述算法。伪代码使用某些程序设计语言中的控制结构，来描述算法中各步骤的执行次序和模式，使用自然语言、数学符号或其他符号，来表示计算步骤要完成的处理或需要涉及的数据。使用伪代码可以免去许多绘图的麻烦，但前提是必须熟悉某种程序设计语言。下面是用伪代码描述的解决问题1的算法1：
read (L ← 铁丝的长度 ， S ← 矩形框的面积 )
d ←
if ( d=0 ) write ( “两条相同的边长” ， L/4 )
else if ( d<0 ) write ( “无解” )
else write ( “两条不同的边长” ，(L+ )/4 ，(L- )/4 )
1.3.3 变量和变量的用途
程序中的变量和数学公式中的变量是有区别的。程序中的变量是计算过程中要用到的数据的存贮单元，通过输入指令的执行，程序将外界输入的数据存贮到指定的变量中，程序计算的结果也可以存贮到指定的变量中。一旦把数据存贮到某个变量，例如变量v中，只要我们不把新的数据送到变量v，那么，变量v将永久地保存着这个数据。如果在计算过程中需要使用v中的数据，我们从变量v中可以取出这个数据，注意，此时变量v中仍然存贮着这个数据不变。实际上，只要我们不把新数据存贮到变量v中，可以从变量v中任意多次地读取该数据，原先存贮着的数据是不会发生任何变化的。
在一个问题的计算过程中，可能需要使用多个变量，来保存计算过程中的多个数据，我们应该为每个变量指定一个适当的名称。
[ 例1 ]
设计一个算法，计算一批数据的算术平均值。这批数据由使用者从键盘输入，使用者预先不指定数据的个数。并约定：输入0时表示本次计算所需的全部数据已输入完毕(即，所有有效的数据，其值均不为0，这是为了对问题的叙述方便起见，而作的假定，实际情况并非完全如此)。
计算数据的算术平均值，是用途广泛的一种计算，例如，统计某个学校某年级的体育成绩，统计某公司一个季度的经营业绩等等。
首先考虑该问题中涉及的数据，设计适当的变量来保存这些数据：
d: 用来存贮从键盘输入的一个数据，或存贮表示输入结束的数字记号0。
c: 用来记录已经输入的数据个数。
sum:用来计算数据之和。
下面考虑计算的过程。为了计算一组数据的平均值，必须知道这批数据的个数c，以及所有这些数据之和sum。显然，我们需要的计算结果是sum/c。因此，我们首先应该通过输入指令，把使用者输入的数据(也可能是表示结束的0)送到变量d中。如果变量d中接收到的是一个非零的数据，这个数据应该被累加到变量sum中，同时，使变量c的值增加1，表示接收到了一个新数据。
图1.3.2是计算数据算术平均值的算法。
图1.3.2 计算数据算术平均值的算法
请注意变量sum和变量c的用法。
变量c用来作为计数器，即，记录某个规定的事件已发生的次数，例如，已经输入到计算机中的有效数据的个数。当我们发现送入到变量d中的数据是一个有效数据时，计数器c的计数动作为：
c ← c+1，
这个动作的效果是，计算箭头右边的数学公式，把计算所得的结果存贮到变量c中。当我们计算c+1时，首先是从变量c中取出数据(最初，该变量的值是0，在算法的执行过程中，该变量中记录的是到目前为止已经接收到的有效数据的个数)，接着将它加上1，然后将结果送回到变量c中。因此，这个计数动作的效果是，使变量c在原值的基础上增加了1，即，记录了最新的有效数据的个数。
变量sum用来作为累加器，使用累加器来计算数据之和。累加器sum的初值是0，当第一个有效数据送到变量d中时，累加的动作为：
sum ← sum + d，
即，计算变量sum(置初值为0)与变量d(存贮着刚输入的第一个有效数据)之和，结果送到累加器sum中。当变量d中接收到一个新的有效数据时，仍然执行累加动作sum ← sum + d，即，计算变量sum(第一个有效数据)与变量d(第二个有效数据)之和，结果仍送到变量sum中。因此，当我们执行了n次这样的累加动作后，已经输入的n个有效数据之和将出现在累加器sum中。
显然，在算法的执行过程中，接收到一个有效数据时需要进行计数，并进行累加处理。这样的动作将不断地执行，直到接收到表示输入结束的0时，输出计算结果。随即，算法终止执行。
计数器(counter)
算法执行过程中，用来记录某种事件发生次数的变量。假定变量c作为计数器。
计数器的典型用法：
1.在算法执行的准备阶段中，应预置初值0。向计数器c预置初值0的动作为： c ← 0。
2.算法执行过程中，每当指定的事件发生时，对计数器c计数， 即，把事件已经发生的次数(在计数器c中)加1后，结果仍然送回到计数器c中。 计数器c的计数动作为: c ← c+1。
累加器(accumulator)
算法执行过程中，用来形成并存贮数据之和的变量。假定变量sum作为累加器，变量d中存贮了符合要求的一个数据。
累加器的典型用法：
1.在求和开始前的准备阶段中，应预置初值0。向累加器sum预置初值0的动作为：sum ← 0。
2.算法执行过程中，每遇到一个符合要求的数据时，把这个数据累加到累加器中，即，计算累加器与该数据之和，并把结果重新存贮到累加器中。数据d累加到sum的动作为：sum ← sum + d。
1.3.4 算法的执行流程
算法的执行流程，是指算法中各个处理步骤的执行次序和模式。通常需要如下三种不同的执行流程：
1.顺序模式：执行完一个处理步骤step1后，接着执行下一个处理步骤step2。
图1.3.3 顺序模式
例如，上面右图中顺序执行的两个计算步骤，计算并输出一个整数的平方。
2.选择模式：对某个情况e进行判断，当结果为真时，执行处理步骤step1，否则执行处理步骤step2。选择模式使算法能根据情况的不同，在准备好的两个处理步骤中，选择执行一个适当的处理步骤。
图1.3.4 选择模式
上面的右图中，顺序执行的三个计算步骤，第二个计算步骤(用虚线框围住的部分)是一个按选择模式进行的处理过程，其效果是判别变量a和b内数据的大小，把较大的数据送到变量d。这样，顺序执行的三个计算步骤完成后，我们将看到计算的结果：两个输入数据的最大值。
图中“a>b?”表示的是判断变量a的值是否大于变量b的值。
3.重复模式：对某个情况e进行判断，当结果为真时，执行处理步骤step，然后再次判断这个情况e，当结果为真时，再次执行处理步骤step，并继续判断情况e。总是重复上述过程，直到情况判断的结果为假。
图1.3.5 重复模式
上面的右图中，顺序执行的四个计算步骤，第一个步骤是接收原始数据n，第二个步骤是为重复处理做必要的准备，这包括：累加器s置初值0，变量k置初值1。第三个计算步骤(用虚线框围住的部分)是一个按重复模式进行的处理过程，其效果是计算 的和，结果将在变量s中逐步地形成，第四个步骤用来输出变量s中的最终计算结果。
这三种不同的流程模式通常会被组合起来使用，以表示各种较为的复杂问题的算法。例如，在重复模式的处理步骤step中，使用选择模式描述的处理动作，或在选择模式的处理步骤step1或step2中，使用重复模式描述该步的处理过程等等。
[ 例2 ]
设计一个算法，计算并输出一批数据中正数和负数的个数。这批数据由使用者从键盘输入，使用者预先不指定数据的个数，输入0时表示输入结束(即，所有有效的数据，其值均不为0)。
首先考虑该问题中涉及的数据，设计适当的变量来保存这些数据：
d: 用来存贮从键盘输入的一个数据，或表示输入结束的0。
c1: 计数器，用来计数正数数据的个数。
c2: 计数器，用来计数负数数据的个数。
下面考虑计算的过程。首先应该通过输入指令，把使用者输入的数据(也可能是表示结束的0)送到变量d中。如果变量d中接收到的是一个有效的数据，进行适当的处理后，继续接收下一个数据进行处理，即，本算法的主要处理过程，应该用重复模式加以描述。对于一个有效数据d的处理为：若d是正数，则使c1计数，否则使c2计数，显然，我们将使用选择模式来描述对一个有效数据的处理过程。此外，在算法的开始阶段，我们应设置计数器的初值，而在算法的结束阶段，则应输出计算的结果。
图1.3.6是本算法的流程图。
图1.3.6 计算正数个数和负数个数的算法
本章练习
一、思考题
1.一个正确的算法应该包含哪些基本特征？
2.变量的作用是什么？简述计数器和累加器的作用和用法。
二、练一练
1.使用流程图表示如下问题的算法：输入三条线段的长度a、b、c，判断这三条线段能否构成一个三角形，若能，输出“Y”，否则输出“N”。
2.使用流程图表示如下问题的算法：使用者从键盘输入一批数据，使用者预先并不指定数据的个数，输入0时即表示输入结束(即，所有有效的数据，其值均不为0)。计算并输出所有正数的算术平均值和所有负数的算术平均值。
maomao112- 帖子数 : 50
注册日期 : 14-05-08
回复： 算法和程序设计实例和表示
由 Lydiaz 周六 五月 10, 2014 7:41 am
计算机辅助教学则只是把信息技术作为辅助的媒体和工具，主要是教师使用信息技术来辅助教学，没有改变教学方式，还是以讲授型为主，只是借助计算机多媒体把不形象的形象化，让不生动的生动起来，使教学过程更加具体化、细致化，并没有突破教师讲、学生听的传授式教学，只是传统教育的一种补充、完善和发展。
计算机辅助教学和信息技术与课程整合相比较，从计算机扩展为信息技术，从教学扩展到课程，从辅助扩展到整合。
计算机辅助教学和信息技术与课程整合相比较，从计算机扩展为信息技术，从教学扩展到课程，从辅助扩展到整合。
Lydiaz- 帖子数 : 30
注册日期 : 14-05-08
您在这个论坛的权限：
您不能在这个论坛回复主题