算法basic语言教程

第1章程序设计基础知识随着科学技术的迅猛发展,计算机技术日新月异,计算机程序设计语言也层出不穷.
那么,什么是程序语言什么是程序设计应该学哪一种程序语言如何进行程序设计这些都是程序设计初学者首先遇到的问题,也是程序设计的基本问题、共性问题.

不论是什么样的计算机语言,其程序设计的基本方法是相同的.
本书作为程序设计的入门教材,将以C语言程序设计为主线,介绍程序设计的基本概念和基本方法,讲述C语言的语法规则和实用的C程序设计技术.
作为全书的开篇,本章就程序设计的基本知识作概括性讨论,首先介绍计算机的工作原理,然后重点介绍算法的概念及特征、设计算法的方法和策略、流程图的表示和结构化程序设计方法等内容.
需要说明的是,有些概念和方法要随着后续各章的深入学习才会有深刻的理解.

1.
1计算机的工作原理1.
1.
1计算机的指令系统大家知道,计算机中的存储器是由千千万万个的电子线路单元组成,每个单元有两个稳定的工作状态(例如二极管或三极管的截止和导通,磁性元件的消磁和充磁等),分别以0和1表示,因此计算机存储的信息是以二进制形式存储的.
人们要计算机处理信息,就要给计算机规定一些最基本的操作,并用0和1表示这些操作,这就构成一条一条的指令.
在设计的时候,就给它规定了一套指令,称之为指令系统(instructionset).
不同型号的计算机,指令系统也不相同.
一条指令由操作码(opcode)和操作数(oprand)两部分构成,例如在Z80中有这样一条指令:1100011000000110操作码操作数操作码11000110表示加法操作,操作数是00000110.
这条指令的功能是把操作数00000110与计算机累加器中的数相加,相加的和仍放在累加器中,例如先在累加器中放一个数00000101,执行这条指令的过程如图1.
1所示.
这条指令用十六进制表示为:C606.
1.
1.
2计算机的解题过程计算机解题要由人事先告诉它解题的方法和步骤,一步一步地去执行.
如果人们设计的步骤是正确的,计算机就能计算出正确的结果,如果设计的步骤不正确,计算机就不能计算出正确的结果,甚至没有结果.

图1.
1执行过程以极简单的5+6为例,它的解题步骤如下:(1)把数字5和6送到计算机的内存中存放起来,存储单元都要有一个编号,称为地址.
例如,43号地址存放数5,写为(43)←5,同样,44号地址存放数6,写为(44)←6.
(2)把数5取出来,送到累加器.
(3)把数6取出来,与累加器中的数相加,结果放在累加器中.
(4)把累加器结果送回到内存的45号地址存放起来,即(45)←11.
(5)把结果输出到打印机或显示器上.
(6)结束.
这些解题步骤的集合,称之为程序,第(1)步是数据的输入,第(5)步是数据的输出,第(2)~(4)步是计算机内部的处理,用某种机器指令写出第(2)~(4)步这一过程,有如下形式:存储地址机器指令0001000000111011000100010000000000010010000010110001001100100001000101000000000000010101000011000001011010000110000101110011001000011000000000000001100100101101001010110000010100101100000001100010110100001011这些由机器指令构成的有序集合,就称为机器语言程序.
计算机的工作就是按规定顺序执行程序.
人们使用计算机就要为它编制程序,称为程序设计.
用机器语言编写程序很不直观,初学者看到这个程序就不知其所以然了(初学者看不懂没关系,不必着急,首先对机器语言有点感性认识就可以了),但对于计算机来说,只有这样的机器语言,才能执行.

1.
1.
3存储程序原理有了指令和程序的概念,就可以进一步了解计算机的工作原理,计算机是基于存储程序的原理工作的.

首先,把程序和数据通过输入设备送入内存.
一般的内存都是划分为很多存储单元,每个存储单元都有地址编号,这样按一定顺序把程序和数据存起来,而且还把内存分为若干区域,比如有专门存放程序的程序区和专门存放数据的数据区.

其次,执行程序,必须从第一条指令开始,以后一条一条地执行.
一般情况下按存放地址号的顺序,由小到大依次执行,当遇到条件转移指令时,才改变执行的顺序.
每执行一条指令,都要经过三个步骤:第一步,把指令从内存中送往译码器,称为取指;第二步,译码器把指令分解成操作码和操作数,产生相应的各种控制信号送往各电器部件;第三步,执行相应的操作.
这一过程是由电子线路来控制的,从而实现自动连续的工作.

这一原理是计算机结构设计的基础,它是美籍匈牙利数学家冯·诺依曼(VonNeumann)1946年提出并论证的,因此常把这一类型的计算机称为冯·诺依曼计算机,迄今为止,各种计算机仍是基于存储程序的原理工作的.

1.
2程序语言与程序设计1.
2.
1计算机程序与程序语言1.
计算机语言什么是计算机语言为什么要使用计算机语言过去,一提到语言这个词,人们自然想到的是像汉语、英语这样的自然语言,因为它是人和人相互交流信息不可缺少的工具.
而今天,计算机遍布于我们生活的每一个角落,除了人和人之间的相互交流之外,我们还必须和计算机交流.
用什么样的方式和计算机做最直接的交流呢人们自然想到的是最古老也最方便的方式——语言.
人和人交流用的是双方都能听懂和读懂的自然语言,同样,人和计算机交流也要用人和计算机都容易接受和理解的语言,这就是计算机语言.
人用自然语言讲述和书写,目的是给另外的人传播信息.
同样,人使用计算机语言把人的意图表达给计算机,目的是使用计算机.

计算机语言是根据计算机的特点而编制的,它没有自然语言那么丰富多样,而只是有限规则的集合,所以它简单易学.
但是,也正因为它是根据机器的特点编制的,所以交流中无法意会和言传,而更多地表现了说一不二,表现了"规则"的严谨.
例如该是","的地方不能写成":",该写"a"的地方不能写成"A",这使得人和计算机的交流在一开始会有些不习惯.
不过,只要认识到计算机语言的特点,注意学习方法,把必需的严谨和恰当的灵活相结合,一切都会得心应手.

2.
程序语言程序是计算机指令的序列集合,编制程序的工作就是为计算机安排指令序列.

指令是二进制编码,用它编制程序既难记忆,又难掌握,所以,计算机工作者就研制出了各种计算机能够懂得、人们又方便使用的计算机语言,程序就是用计算机语言来编写的.
因此,计算机语言通常被称为"程序语言",一个计算机程序总是用某种程序语言书写的.
程序语言的产生和发展,直接推动了计算机的普及和应用.
自第一个高级语言问世以来,人们已发明了上千种程序语言,常用的也有上百种.
这些语言之间有什么区别我们应该学习哪一种计算机语言按使用方式和功能可分为低级语言和高级语言.
低级语言包括机器语言和汇编语言.
机器语言就是计算机指令的集合,它与计算机同时诞生,称为第一代计算机语言;汇编语言用符号来表示计算机指令,称为第二代计算机语言.
机器语言和汇编语言都是围绕特定的计算机或计算机族而设计的,是面向计算机的语言,要使用这种语言必须了解计算机的内部结构,而且难学、难写、难记忆,所以把这种语言称为低级语言.
因为低级语言是难以普及应用的,为此便产生了第三代计算机语言——高级语言,它是用更接近人的自然语言和数学表达式的一种语言,由表达不同意义的"关键字"和"表达式",按照一定的语法语义规则组成,完全不依赖机器的指令系统.
这样的高级语言为人们提供了很大的方便,编制出来的程序易读易记,也便于修改、调试,大大提高了编制程序的效率,也大大提高了程序的通用性,便于推广交流,从而极大地推动了计算机的普及应用.

例如,使用高级语言BASIC编程,要想得到3*8*sin((/2)的结果,只需要写出print3*8*sin(3.
14159/2)即可,计算机将计算并输出结果.
高级语言离人们的理解愈加接近了,但离计算机的理解就愈远了.
计算机是不能直接理解那些英语单词、数学表达式的.
所以,为了填补人机之间的鸿沟,还是得求助于翻译.
这种"翻译"通常有两种做法,即编译方式和解释方式.

编译方式是:事先编好一个称为编译程序的机器指令程序,并放在计算机中,把用高级语言编写的源程序输入计算机,编译程序便把源程序整个地翻译成用机器指令表示的目标程序.
然后执行该目标程序,得到计算结果.

解释方式是:事先编好一个称为解释程序的机器指令程序,并放在计算机中,把用高级语言编写的源程序输入计算机,它并不是像编译方式那样把源程序整个地翻译成用机器指令表示的目标程序,而是逐句翻译,译出一句立即执行一句,即边解释边执行.
这种方式比编译方式多费机器时间,但可少占计算机的内存.

可以看到高级语言只是要求人们向计算机描述问题的求解过程,而不关心计算机的内部结构,所以把高级语言称为"面向过程语言",它易于被人们理解和接受.
典型的面向过程语言有BASIC、FORTRAN、COBOL、C和Pascal等.

随着计算机技术的迅猛发展,自从20世纪80年代以来,众多的第四代非过程化计算机语言、第五代智能化计算机语言也竞相推出.
如果说第三代语言要求人们告诉计算机怎么做,那么第四代语言只要求人们告诉计算机做什么.
因此,人们称第四代语言是"面向对象语言".
面向对象概念的提出是相对于"面向过程"的一次革命,面向对象技术在系统程序设计、多媒体应用、数据库等诸多领域得到广泛应用.
但是,"面向过程"是程序设计的基础,尤其对于程序设计的初学者.
所以,下面将以面向过程的C程序设计语言为背景,主要介绍程序设计的基本概念和方法.

1.
2.
2程序设计什么是程序设计呢在日常生活中可以看到,同一台计算机,有时可以画图,有时可以制表,有时可以玩游戏,诸如此类,计算机可以做许多事情,尽管计算机本身只是一种现代化方式批量生产出来的通用机器,但是,使用不同的程序,计算机就可以处理不同的问题.
今天,计算机之所以能够产生如此大的影响,其原因不仅在于人们发明了机器本身,更重要的是人们为计算机开发出了不计其数的能够指挥计算机完成各种各样工作的程序.
正是这些功能丰富的程序给了计算机无尽的生命力,它们正是程序设计工作的结晶.
而程序设计就是用某种程序语言编写这些程序的过程.

更确切地说,所谓程序,就是用计算机语言对所要解决的问题中的数据以及处理问题的方法和步骤所做的完整而准确的描述,这个描述的过程就称为程序设计.
对数据的描述就是指明数据结构形式;对处理方法和步骤的描述也就是1.
3节要讨论的算法问题.
因而,数据结构与算法是程序设计过程中密切相关的两个方面.
曾经发明Pascal语言的著名计算机科学家沃思(NikiklausWirth)教授关于程序提出了著名公式:程序=数据结构+算法.
这个公式说明了程序设计的主要任务.
但在本书中,并没有以数据结构和算法为主展开讨论,因为本书的主题是介绍用C语言进行编程.
关于数据结构有许多专门的教材.

对于程序设计的初学者来说,首先要学会设计一个正确的程序.
一个正确的程序,通常包括两个含义:一是书写正确,二是结果正确.
书写正确是指程序在语法上正确,符合程序语言的规则;而结果正确通常是指对应于正确的输入,程序能产生所期望的输出,符合使用者对程序功能的要求.
程序设计的基本目标是编制出正确的程序,但这仅仅是程序设计的最低要求.
一个优秀的程序员,除了程序的正确性以外,更要注重程序的高质量.
所谓高质量是指程序具有结构化程度高、可读性好、可靠性高、便于调试维护等一系列特点.
毫无疑问,无论是一个正确的程序,还是一个高质量的程序,都需要设计才能使之达到预期的目标.

那么,如何进行程序设计呢一个简单的程序设计一般包含以下4个步骤:(1)分析问题,建立数学模型.
使用计算机解决具体问题时,首先要对问题进行充分的分析,确定问题是什么,解决问题的步骤又是什么.
针对所要解决的问题,找出已知的数据和条件,确定所需的输入、处理及输出对象.
将解题过程归纳为一系列的数学表达式,建立各种量之间的关系,即建立起解决问题的数学模型.
需要注意的是,有许多问题的数学模型是显然的或简单的,以至于我们没有感觉到需要模型.
但是有更多的问题需要靠分析问题来构造计算模型,模型的好与坏、对与错,在很大程度上决定了程序的正确性和复杂程度.

(2)确定数据结构和算法.
根据建立的数学模型,对指定的输入数据和预期的输出结果,确定存放数据的数据结构.
针对所建立的数学模型和确定的数据结构,选择合适的算法加以实现.
注意,这里所说的"算法"泛指解决某一问题的方法和步骤,而不仅是指"计算".
(3)编制程序.
根据确定的数据结构和算法,用自己所使用的程序语言把这个解决方案严格地描述出来,也就是编写出程序代码.

(4)调试程序.
在计算机上用实际的输入数据对编好的程序进行调试,分析所得到的运行结果,进行程序的测试和调整,直至获得预期的结果.

由此可见,一个完整的程序要涉及4个方面的问题:数据结构、算法、编程语言和程序设计方法.
这4个方面的知识都是程序设计人员所必须具备的.

1.
3算法和算法的表示我们知道计算机所做的工作就是按指定的步骤执行一系列的操作,以完成某一特定的任务.
因此,要计算机为我们做事,就必须事先为它设计出这一系列的操作步骤,并用计算机语言写成程序,这就是程序设计.
解决问题的方法和步骤,称之为算法,它是程序设计的关键,因此,在学习用C语言进行程序设计之前,首先了解一点算法的知识,它是后续章节学习的基础.

1.
3.
1什么是算法计算一个算术式,要先乘除后加减,这个规则就是算法.
使用算盘,珠算口诀就是算法.
在日常生活中做任何一件事情,都是按照一定规则,一步一步进行,比如乐队演奏、厨师炒菜,都有各自的操作步骤,这就是算法.
在工厂中生产一部机器,先把零件按一道道工序进行加工,然后,又把各种零件按一定规则组装成一部完整机器,它们的工艺流程就是算法.
在农村种庄稼有耕地、播种、育苗、施肥、中耕、收割等各个环节,这些栽培技术也是算法.
总之,把任何这些数值计算或非数值计算过程中的方法和步骤,都称之为算法.

计算机用于解决数值计算,如科学计算中的数值积分、解线性方程等的计算方法,就是数值计算的算法;用于解决非数值计算,如用于管理、文字处理、图像图形等的排序、分类、查找,就是非数值计算的算法.

下面举几个简单例子,以说明计算机算法.
【例1.
1】将两个变量X和Y的值互换.
设X=5,Y=10.
问题分析:两人交换座位,只要各自去坐对方的座位就行了,这是直接交换.
一瓶酒和一瓶醋互换,就不能直接从一个瓶子往另一个瓶子倒.
必须借助于一个空瓶子,先把酒倒入空瓶,再把醋倒入已倒空的酒瓶,最后把酒倒入已倒空的醋瓶,这样才能实现酒和醋的交换,这是间接交换.

计算机中交换两个变量的值不能用两个变量直接交换的方法,而必须采用间接交换的方法.
因此,设一中间变量为Z.

算法表示如下:S1将Y值存入中间变量Z:Y→Z.
S2将X值存入变量Y中:X→Y.
S3将中间变量Z的值存入X中:Z→X.
这里S1、S2、……,即是Step1、Step2、……的简写,用以标识执行的步骤,以后的例子中均用这些符号,不再说明.

用一个示意图说明此算法,如图1.
2所示.
【例1.
2】求5个自然数的和(即S=1+2+3+4+5).
问题分析:该题有如下两个特点.
(1)重复执行加法,每加一个数,总和的值都在变;(2)加数是一个有规则的等差数列,第1项是1,以后每加一次,加数就增加1.

因此,可以用以下算法实现.
算法1:S1设一存放累加和的变量S,初值置0,即0→S;设一计数变量N,初值置0,即0→N.

S2计算和S+N→S,并把计数变量增值N+1→N.
S3判断:当N(5时,返回第2步S2,再次求和;当N>5时,顺序执行下一步S4.
S4输出结果,S为所求之和.
算法2:S10→S,1→N(同算法1).
S2判断:当N(5时,顺序执行下一步S3;当N>5时,跳过第3步和第4步S3、S4,执行第5步S5.

S3S+N→S,N+1→N(同算法1).
S4返回第2步S2.
S5输出结果,S为所求之和.
在这个算法里,出现了重复求和的操作,称为循环,这种循环必须用条件加以限制,让它进行有限次就停止,否则成为死循环.
上述算法1的S3是条件判断,求和的操作是先执行,后判断;算法2的S2是条件判断,求和的操作是先判断,后执行.

【例1.
3】计算函数M(x)的值.
函数M(x)为:M(x)=问题分析:该题是一个数值运算问题.
其中M代表要计算的函数值,有两个不同的表达式,根据x的取值决定采用哪一个算式.
因此,可用以下算法实现.

S1将a、b、c和x的值输入到计算机.
S2判断是否x(a,若条件成立,执行第3步S3,否则,执行第4步S4.
S3按表达式bx2+a计算出M(x),然后执行S5.
S4按表达式a(c–x)+c2计算出M(x),然后执行S5.
S5输出结果M(x)的值.
【例1.
4】求两个自然数M和N的最大公约数.
问题分析:最大公约数就是能同时整除M和N的最大正整数,这是一个古老的算术问题,这里介绍两种算法.

算法1:欧几里得(Euclid)算法.
S1输入两个自然数M和N.
S2求M除以N的余数R(0N,则N→R,否则M→R.
S3若M除以R的余数等于0并且N除以R的余数也等于0,则执行S5,否则顺序执行下一步.

S4R–1→R,转S3.
S5输出R,R为所求最大公约数.
综合以上算法示例看出,算法是解题方法的精确描述.
算法并不给出问题的精确解,只是说明怎样才能得到解.
每一个算法都是由一系列的操作组成的.
这些操作包括加、减、乘、除、判断、置数等,按顺序、分支、循环等结构组成.
所以研究算法的目的就是研究怎样把各种类型问题的求解过程分解成一些基本的操作.

算法写好之后,要检查其正确性和完整性,再根据它编写出用某种高级语言表示的程序.
程序设计的关键就在于设计出一个好的算法.
所以,算法是程序设计的核心.

1.
3.
2算法的基本特征从上面的例子中,可以概括出算法具有以下基本特征:(1)算法中执行的步骤总是有限次数的,不能无休止地执行下去,这称之为有穷性.
例如,计算圆周率π的值可用如下公式:这个多项式的项数是无穷的,因此,它是一个计算方法,不是算法.
我们要计算π的值,只能取有限个项数.
例如,取精确到小数点后第5位,那么,这个计算就是有限次的,因而才能称得上算法.

(2)算法中的每一步操作的内容和顺序必须含义确切,这称之为确切性.
不能有二义性.
(3)算法中的每一步操作都应该能有效地执行,这称之为有效性.
一个不可执行的操作是无效的.
例如,一个数被零除的操作是无效的,应当避免这种操作.

(4)要有数据输入.
算法中操作的对象是数据,因此,应在操作前提供数据.

(5)要有结果输出.
算法的目的是用来解决一个给定的问题,因此,它应向人们提供产生的结果,否则,就没有意义了.

了解算法的这些特性,对我们在程序设计中构造一个好的算法,是有重要指导意义的.

1.
4用流程图表示算法描述算法有多种不同的工具,采取不同描述算法的工具对算法的质量有很大的影响.
如例1.
1至例1.
4是用自然语言——汉语描述的算法.
使用自然语言描述算法的最大优点在于人们比较习惯,容易接受,但也确实存在着很多缺点:一是容易产生二义性,例如,中文"走火"二字,既可表达子弹从枪膛射出,又可表示电线上漏电,也可表示说话漏了嘴;二是比较冗长;三是在算法中如果有分支或转移时,用文字表示就显得不够直观;四是计算机不便于处理.
所以自然语言不适合描述算法.
在计算机中常用流程图、结构化流程图、计算机程序设计语言等描述工具来描述算法.

流程图,亦称框图,它是用一些几何框图、流程线和文字说明表示各种类型的操作.
直观形象,易于理解.
ANSI规定了一些常用的流程图符号,如图1.
3所示.

图1.
3流程图中的符号处理框亦称矩形框,有一个入口,一个出口.
判断框亦称菱形框,有一个入口,两个出口.
在框内写上简明的文字或符号表示具体的操作,用带箭头的流程线表示操作的先后顺序.
流程图是人们交流算法设计的一种工具,不是输入给计算机的.
只要逻辑正确,能看得懂就可以了,一般是由上而下地按执行顺序画下来.
图1.
4~图1.
7给出了用流程图表示例1.
1~例1.
4的算法.

流程图的优点是形象直观,清晰明了,所以它很早就被广泛采用在各种高级语言的程序设计中,常常称之为传统的流程图.

但是它也有不足之处,对于较复杂的问题,占面积大,而且由于使用流程线,使流程任意转移,容易使人弄不清流程的思路.