可见,作为程序设计人员,必须认真考虑和设计数据结构和操作步骤(即算法)。著名计算机科学家沃思(Nikiklaus Wirth)提出一个公式:
数据结构+算法=程序
综上所述,对于人来说,算法是为解决一个问题而采取的方法;而对于计算机来说,算法是具体的实实在在的操作序列或语句序列。C程序就是根据C语言的语法规则而编写的语句序列,语句的先后序列就体现了C程序的算法。
2.算法的特性
一个算法应该具有以下特性:
(1)有穷性
一个算法包含有限的操作步骤,而不能是无限的,否则意味着执行程序时永远不会 停止。
(2)确定性
算法中的每一步骤操作应当是确定的,而不应当是含糊的、模棱两可的。如果算法中具有不确定的操作描述,则算法无法通过编译,也就无法得到目标程序。例如,在实例1-3的“a=1219; b=23; money=a*b;”中,如果去掉前面的“a=1219; b=23;”,则操作“money=a*b;”就是不确定的。
(3)有零个或多个输入
如果运算所依赖的对象在程序设计时无法确定,则需要在程序执行时指定。这就意味着在执行程序时需要输入数据。一个算法可以没有输入,也可以有多个输入。例如在实例
C语言与程序的算法
例如在实例1-4中函数max()
z的值)返回给调用它的main()函数。
(5)有效性
有效性是指算法中的每一个操作步骤都应当有效地执行,并得到确定的结果。例如,若设x=1,a=0,则x/a是不能有效执行的。
1.3.2 算法描述方法
算法的描述方法有用自然语言表示算法、流程图表示算法、N-S盒图表示算法、伪代码表示算法、计算机语言表示算法等。下面重点介绍如何用自然语言、流程图和计算机语言描述算法。对于N-S盒图和伪代码表示算法的问题,请参考相关书籍。
1.用自然语言表示算法
自然语言就是人们日常使用的语言,可以是汉语、英语或其他语言。用自然语言表示算法,则算法通俗易懂,但文字冗长,容易出现歧义。自然语言所描述的内容往往不太严格,要根据上下文才能判断其正确含义。在算法分析的初始阶段使用自然语言描述算法是恰当的,尤其对于初学者来说,这是学习程序设计时迈出的第一步。
【实例1-5】 用自然语言描述1+2+3+ +1000的算法。
【分析】 对于此问题,人工计算时有两种方法:第一种方法是先进行1+2,再加3,再加4,一直加到1000,这种方法称为逐个相加法;第二种方法是进行(1+1000)+(2+999)+ (3+998)+ +(500+501)=500*1001=500500。逐个相加法虽然在人工计算时比较慢,但更具有规律性,因此适合计算机进行。在使用逐个相加法进行计算时,如果引入两个变量,一个变量代表要逐个相加的数,另一个变量代表每一次相加的结果。刚开始设前者的值为1,后者的值为0。在第一次将两个变量的值相加时,实际进行0和1相加,得1。然后,将结果1存入到后一个变量中,再将前一个变量的值增加1,进行第二次相加。在第二次将两个变量的值相加时,实际上进行1和2相加,得3。然后将结果3存入到后一个变量中,再将前一个变量的值增加1,再进行第三次相加 依此类推,直到前一个变量的值大于1000时,停止操作。最后,将后一个变量的值输出,所输出的结果就是希望得到的结果。而当计算停止的时候,我们一共重复了1000次相同的操作。
【算法】 现在设前一个变量为i,后一个变量s,在进行每一次重复操作之后增加逻辑判断,判断i的值是否大于1000,如果大于1000,则停止计算,否则重复相同操作。相应算法描述如下:
S1:把1存入变量i中;
S2:把0存入变量s中;
S3:把i的值和s的值相加,相加结果再次存入变量s中;
S4:把变量i的值增加1,相加结果再次存入变量i中;
S5:如果变量i的值不大于1000,则返回到S3,从第S3步起重复进行操作;否则继
C语言与程序的算法
续下面操作;
S6:将s的值输出,结束。
如果用“=”表示把左边的数据或计算结果存入右边的变量中,则上面的算法可简写成如下形式:
S1:i=1;
S2:s=0;
S3:s=s+i;
S4:i=i+1;
S5:如果i≤1000,则返回S3,重复操作,否则继续;
S6:输出s,结束。
2.用流程图表示算法
流程图使用一些图形符号来表示算法中的各种操作。用图形表示算法,直观、形象、易于理解。在流程图中常用的符号如图1-8所示。
图1-8 流程图常用的图形符号
在图1-8中菱形框的作用是对一个给定的条件进行逻辑判断,根据给定的条件是否成立来决定如何执行其后的操作。连接点(小圆圈)用于将画在不同地方的流程线连接起来。使用连接点,可以避免流程线交叉或者过长,使流程图更加清晰。注释框不是流程图的必要部分,不反映流程和操作,只是为了对流程图中某些框的操作做必要的补充说明,以帮助人们阅读和理解流程图。
【实例1-6】 使用流程图描述实例1-5中的算法。
该算法的流程图如图1-9所示。
3.用计算机语言表示算法
自然语言体现了我们分析问题的过程,流程图直观形象地表示了算法。实际上,无论是自然语言描述的算法,还是流程图描述的算法,它们都是从人的角度出发并为人写的,计算机是无法识别的。我们的任务是用计算机完成问题的求解,因此最终还是要考虑如何
C语言与程序的算法
图1-9 流程图
【实例1-7】 使用C语言描述实例1-5的算法。
#include "stdio.h"
main()
{
int i,s;
i=1;s=0;
while(i<=1000)
{
s=s+i; i=i+1;
}
printf("%d\n",s);
在这里,不打算详细介绍上述程序的细节,读者只需大体看懂它即可。在后续各章中会详细介绍C语言有关的使用规则。 }
本 章 小 结
在我国,C语言已经成为大多数学生学习程序设计时的入门课。作为C语言教材来说,其第一章也就是学习程序设计时的第一道门槛。本章从初学者的角度出发,重点回答了C程序是什么、它有什么特点、如何上机操作及其算法如何描述等问题。
C语言与程序的算法
习 题 一
一、选择题
1.下面是有关C程序的叙述,不正确的是( )。
A)一个C源程序可由一个或多个函数组成