第一章算法初步

算法一.算法的基本概念1什么是算法算法（algorithm）一词源于算术(algorism),算术方法的原义是一个由已知推求未知的运算过程。后来，人们把它推广到一般,指算法是在有限步骤内求解某一问题所使用的一组定义明确的规则,甚至把把进行某一工作的方法和步骤也称为算法。

例如，人们在计算过程中，先乘除，后加减，从内到外去括号等规则，都是按部就班必须遵守的算法。人类最早关于算法的记录存在于在两河流域发现的公元前两三千年的泥板书上，其中的一个典型例子就是计算利息何时能够够等于本金。算法早期发展中值得一提的另一个成果应归功于古希腊的欧几里得，他提出的计算最大公约数的辗转相除法（又称欧几里得算法）至今仍在使用。欧几里得是古代最有名望的学者之一，古希腊数学家，几何学的鼻祖。公元前300年左右，他所著《几何原本》13卷，是世界上最早公理化的数学著作。在《几何原本》中他充分总结了前人的生产经验和研究成果，从公理和公设出发，运用演绎法，经过逻辑推理和数学运算，创立了著名的欧几里得（简称欧氏几何）。在《几何原本》中，欧几里得还阐述了关于求两个整数的最大公约数的过程，这就是著名的欧几里得算法——辗转相除法，其具体过程如下：设给定的两个正整数为m和n，求它们的最大公约数的步骤为：（1）以m除以n，令所得的余数为r（r必小于n）；（2）若r＝0，则输出结果n，算法结束；否则，继续步骤（3)（3）令m=n，n=r,并返回步骤（1）继续进行。中国古代数学研究中也有许多有关算法的成果。用我国传统的开方术求高次方程的近似根，是算法上的一大成就。此外,在社会上得到广泛使用的珠算口诀就可以看做是典型的算法,它把复杂的计算(例如除法)描述为一系列按口诀执行的简单的算珠拨动操作。中国古代数学以算法为主要特征，其中最具代表性的就是《九章算术》。《九章算术》是战国、秦、汉时期数学发展的总结，就其数学成就来说，堪称是世界数学名著。其内容按类分章，以数学问题的形式出现，包括分数四则运算、开平方与开立方（包括二次方程数值解法）、盈不足术、各种面积和体积公式、线性方程组解法、正负数运算的加减法则、勾股形解法（特别是勾股定理和求勾股数的方法）等。其中方程组解法和正负数加减法则在世界数学发展上是遥遥领先的。就其特点来说，它形成了一个以筹算为中心，与古希腊数学完全不同的独立体系。

在11~14世纪约300年期间著名的数学家的著作中，如贾宪的《黄帝九章算法细草》，刘益的《议古根源》，秦九昭的《数书九章》，李治的《测圆海镜》和《益古演段》，杨辉的《详解九章算法》、《日用算法》和《杨辉算法》中，算法的特点得到了进一步的强化和发展（其中包括发展了一套求高次方程近似根的方法。2。算法的一般特征

算法实际上是一种抽象的解题方法，它具有动态性。因此，算法的行为非常重要。作为一个算法，应具有以下四个特征。1）能行性(effectiveness）算法的能行性包括两个方面：一是算法中的每一个步骤必须是能实现的。例如，在算法中，不允许出现分母为零的情况；在实数范围内不能求一个负数的平方根等。二是算法执行的结果要能达到预期的目的。通常，针对实际问题设计的算法，人们总是希望能够得到满意的结果。

（2）确定性(definiteness）算法的确定性，是指算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。这一特征也反映了算法与数学公式的明显差异。在解决实际问题时，可能会出现这样的情况：针对某种特特殊问题，数学公式是正确的，但按此数学公式设计的计算过程可能会使计算机系统无所适从，这是因为，根据数学公式设计的计算过程只考虑了正常使用的情况，而当出现异常情况时，该计算过程就不能适应了。例如，某计算工具规定：大于100的数认为是比1大很多，而小于10的数不能认为是比1大很多；且在正常情况下出现的数或是大于100,或是小于10.但指令“输入一个X，若x比1大很多，则输出数字1，否则输出数字0”是不确定的。这是因为，在正常的输入情况下，这一指令的执行可以得到正确的结果，但在异常情况下（输入的x在10与100之间），这一指令执行的结果就不确定了．例如，某计算工具具有七位有效数字（如FORTRAN中的单精度运算）,在计算下列三个量A＝，B＝1，C＝的和时，如果采用不同的运算顺序，就会得到不同的结果，即A＋B＋C=＋1＋=0A＋C十B=＋＋1=1而在数学上，A+B+C与A+C+B是完全等价的。这可知，算法和计算公式是有差别的。3）有穷性(finiteness）算法的有穷性是指算法必须能在有限的时间内执行完，即算法必须能在执行有限个步骤之后终止。数学中的无穷级数，在实际计算时只能取有限项，即计算无穷级数的过程只能是有穷的。因此，一个数的无穷级数的表示只是一种计算公式，而根据精度要求确定的计算过程才是有穷的算法。算法的有穷性还应包括合理的执行时间的含义。如果一个算法的执行时间是有穷的，但却需要执行千万年．显然这就失去了算法的实用价值。例如，克莱姆(Cramer)规则是求解线性代数方程组的一种数学方法，但不能以此为算法，这是因为，虽然总可以根据克莱姆规则设计出一个计算过程用于计算所有可能出现的行列式，但这样的计算过程所需的时间实际上是不能容忍的。还例如，从理论上讲，总可以写出一个正确的弈棋程序，而且这也并不是一件很困难的工作。由于在一个棋盘上安排棋子的方式总是有限的，而且，根据一定的规则．在有限次移动棋子之后比赛一定结束。因此．弈棋程序可以考虑计算机每一次可能的移动，它的对手每一次可能的应答，以及计算机对这些移动的可能应答等等，直到每个可能的移动停止下来为止。此外，由于计算机可以知道每次移动的结果，因此总可以选择一种最好的移动方式。但即使如此，这种弈棋程序还是不可能执行，因为所有这些可能移动的次数太多，所要花费的时间不能容忍。由上述两个例子可以看出，虽然许多计算过程是有限的．但仍有可能无实用价值。（4）算法必须拥有足够的情报一个算法是否有效，还取决于为算法的执行所提供的情报是否足够。例如，对于指令“如果小明是学生，则输出字母Y，否则输出N”。当算法执行过程中提供了小明一定不是学生的某种信息时，执行的结果将输出字母N；当提供的只是部分学生的名单，且小明恰在此名单之中，则执行的结果将输出字母Y。但如果在提供的部分学生的名单中找不到小明的名字．则在执行该指令时无法确定小明是否是学生。通常，算法中的各种运算总是要施加到各个运算对象上，而这些运算对象又可能具有某种初始状态．这是算法执行的起点或是依据。因此，一个算法执行的结果总是与输入的初始数据有关，不同的输入将会有不同的结果输出。如果输入不够或输入错误，则算法本身也就无法执行或执行有错。一般来说，只有当算法拥有足够的情报时，该算法才是有效的；而如果提供的情报不够，则算法并不是有效的。综上所述，所谓算法，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的且是明确的，此顺序将在有限的次数下终止1.1.2程序框图狭义而言,算法是专指用计算机解决某一问题的方法和步骤.著名计算机科学家D.E.Knuth在其《计算机程序设计技巧》一书中为算法所下的定义是：“一个算法,就是一个有穷规则的集合,其中之规则规定了一个解决某一特定类型问题的运算系列”.1.算法的概念复习回顾

是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的且是明确的，此顺序将在有限的次数下终止。用自然语言表达问题容易理解，但往往不严格，易出现“歧义性”，即对于同一段文字，不同的人可能会有不同的理解。例如请同学们理解“这个人连老张也不认识。”这句话的含义。算法的描述：自然语言新课引入为了使算法的程序或步骤表达得更为直观,且不容易出现歧异，我们更经常地用图形方式来表达它.例如上一节“例1.任意给定一个大于1的整数n,试设计一个程序或步骤对n是否为质数做出判定”的算法可以用以下形式来表达.开始输入ni=2i=i+1i≥n或r=0?n不是质数结束r=0?1否是求n除以i的余数1n是质数是否这样的图我们称为程序框图i=i+1i≥n或r=0?否是求n除以i的余数输入ni=2n不是质数r=0?n是质数是否尽管不同的算法千差万别,但它们都是由三种基本的逻辑结构构成的,这三种逻辑结构就是顺序结构、选择结构、循环结构.下面分别介绍这三种结构．三种不同的逻辑结构.程序框图又称流程图,是一种用规定的图形、指向线及文字说明来准确、直观地表示算法的图形.讲授新课1.程序框图的概念2.常见的程序框图流程线连接循环框连结点连接循环框图的两部分一、程序框图终端框(起止框)输入、输出框处理框(执行框)判断框表示一个算法的起始和结束表示一个算法输入和输出的信息赋值、计算判断某一条件是否成立,成立时在出口处标明“是”或“Y”,不成立时标明“否”或“N”.(1)起止框:框内填写开始、结束,任何程序框图中，起止框是必不可少的；(2)输入、输出框:框内填写输入、输出的字母、符号等;(3)处理框(执行框):算法中需要的算式、公式、对变量进行赋值等要用执行框表示.(4)判断框:当算法要求在不同的情况下执行不同的运算时，需要判断框.框内填写判断条件.3.四种基本的框图及其功能用法:为了使大家彼此之间能够读懂各自画出的框图,必须遵守一些共同的规则,下面对一些常用的规则作一简单的介绍.(1)使用标准的框图符号.(2)框图一般按从上到下、从左到右的方向画.(3)除判断框外，大多数程序框图符号只有一个进入点和一个退出点，判断框是具有超过一个退出点的唯一符号.(4)一类判断框是“是”与“否”两分支的判断,而且有且仅有两个结果;另一类是多分支判断,有几种不同的结果.4.画流程图的规则(5)在图形符号内描述的语言要非常简练清楚.(7)一个程序框图包括以下几部分:表示相应操作的程序框;带箭头的流程线;程序框外必要的文字说明．(6)起始框只允许一条流出线,终止框只允许一条流入线,输入框、输出框、处理框只有一条流入线和一条流出线,判断框有一条流入线和两条流出线,但任何时候只有一条流出线起作用.二、顺序结构及框图表示1.顺序结构:按照步骤依次执行的一个算法,称为具有“顺序结构”的算法,或者称为算法的顺序结构.语句A语句B2.顺序结构的流程图

顺序结构是最简单的算法结构,语句与语句之间,框与框之间是按从上到下的顺序进行的.它是由若干个处理步骤组成的,这是任何一个算法都离不开的基本结构.3.画顺序结构程序框图时注意事项左图中,语句Ａ和语句Ｂ是依次执行的,只有在执行完语句Ａ指定的操作后,才能接着执行语句Ｂ所指定的操作．(1)在程序框图中,开始框和结束框不可少；(2)在算法过程中，第一步输入语句是必不可少的;(3)顺序结构在程序框图中的体现就是用流程线将程序框自上而下地连接起来,按顺序执行算法步骤．【例1】已知一个三角形的三边边长分别为2,3,4,利用海伦—秦九韶公式设计一个算法,求出它的面积,画出算法的程序框图.开始输出S结束开始框处理框输出框结束框【1】求两个实数a,b的算术平均值aver.S1:输入两个实数a,b；S2：计算c=a+b；S3:计算aver=c/2；S4:输出aver.输出c开始输入a,baver=c/2结束解：用自然语言【2】“鸡兔同笼”是我国隋朝时期的数学著作《孙子算经》中的一个有趣而具有深远影响的题目:“今有雉兔同笼,上有三十五头,下有九十四足,问雉兔各几何.”请你设计一个这类问题的通用算法.并画出算法的程序框图.设有X只鸡,Y只兔.则解:鸡兔同笼,设鸡兔总头数为H,总脚数为F,求鸡兔各有多少只.算法分析如下：

解方程组,得第一步:输入总头数H,总脚数F；第二步:计算鸡的个数x=(4H-F)/2；第三步:计算兔的个数y=(F-2H)/2；第四步:输出x,y开始输出X,Y结束X=(4H-F)/2Y=(F-2H)/2输入H和F解：用自然语言程序框图第四步:计算;【3】试描述求点(x0,y0)到直线Ax+By+C=0的距离的算法,并画出算法的程序框图.第一步:输入x0,y0,A,B,C;第二步:计算Z1=Ax0+By0+C;第三步:计算Z2=A2+B2;第五步:输出d.解：用自然语言开始输入x0,y0,A,B,CZ1=Ax0+By0+CZ2=A2+B2输出d结束程序框图课堂小结2.三种基本结构：顺序条件循环结构现以证明,无论多么复杂的问题，其算法都可表示为这三种基本结构的组合.其结构清晰、易于理解、易于验证其正确性，也易于查错和排错.1.算法的描述：(1)自然语言(2)程序框图:由于图形的描述方法既形象,又直观,设计者的思路表达得清楚易懂，便于检查修改,所以得到广泛的应用.1.2基本算法语句1.2.1输入语句输出语句赋值语句温故而知新1.什么是程序框图？2.算法的基本逻辑结构有哪些？

程序框图是一中用规定的图形、指向线及文字说明来准确、直观的表示算法的图形。

算法的基本结构有三种：顺序结构、条件结构、循环结构，其中循环结构又分为当型结构和直到型结构两种。1.计算机能够"理解"的语言与人的语言有什么区别？

计算机不同于人：人有大脑，可以思考问题，而计算机则不能.用自然语言和程序框图描述的算法，计算机无法识别，必须转化为其能理解的语言，即程序语言。2、基本的算法语句有哪些？各自对应怎样的算法结构？

基本的算法语句有：输入语句、输出语句、赋值语句、条件语句、循环语句；输入语句、输出语句、赋值语句基本上是对应顺序结构，条件语句对应条件结构、循环语句对应循环结构。例１用描点法作函数y=x3+3x2-24x+30的图象是时，需要求出自变量和函数的一组对应值。编写程序，分别计算当x=-5,-4,-3,-2,-1,0,1,2,3,4,5时的函数值。程序：INPUT“x=“;xy=x^3+3*x^2-24*x+30PRINTxPRINTyEND算法：开始输入x输出x、y结束i=1i=i+1i>11否是1、输入语句的一般格式是：举例：输入语、数、英三门课成绩或INPUT”Maths,Chinese,English”;a,b,cINPUT“maths”;aINPUT“Chinese”;bINPUT“English”;cINPUT“提示内容”；变量INPUT“提示内容1，提示内容2，提示内容3，…”；变量1，变量2，变量3，…2、输入语句的作用是：实现算法的输入信息功能（即对程序中的变量赋值）3、“提示内容”提示用户输入什么样的信息

变量是指程序在运行时其值是可以变化的量；

（一）输入语句：INPUT“n=”;nINPUT“a,b,c”;a,b,c输入框：INPUT“请输入需判断的整数n=”；n注：①“提示内容”与变量之间必须用分号“；”隔开。②各“提示内容”之间以及各变量之间必须用逗号“，”隔开。但最后的变量的后面不需要。③提示内容和它后面的“；”可省略

④由键盘输入的数据必须是常量，不能是函数、变量或表达式,输入多个时用“，”分隔，个数与变量个数要相同思考：能用输入语句表达１．１．２中程序框图中的输入框的内容吗？输出语句的一般格式PRINT“提示内容”；表达式输出语句的作用是实现算法的输出结果功能；“提示内容”提示用户输入什么样的信息，表达式是指程序要输出的数据；

输出语句可以输出常量、变量或表达式的值以及字符。

（二）输出语句TheFibonacciProgressionis：11235813213455…输出框：PRINTn；“是质数。”输出框：PRINTn；“不是质数。”PRINT

“TheFibonacciProgressionis：”；11235813213455“…”此时屏幕上显示为：〖思考〗：在1.1.2中程序框图中的输出框的内容怎样用输出语句来表达？例2：编写程序，计算一个学生数学、语文、英语三门课的平均成绩。程序算法开始输入a,b,c结束输出yINPUT“数学=”;aINPUT“语文=”;bINPUT“英语=”;cPRINT

“Theaverage=”;(a+b+c)/3

END（三）赋值语句：用来表明赋给某一个变量一个具体的确定值的语句。

变量=表达式赋值语句也可以给变量提供初值。它的一般格式是：其中“=”叫做赋值号。

赋值语句的作用：先计算出赋值号右边表达式的值，然后把这个值赋给赋值号左边的变量，使该变量的值等于表达式的值。注：①赋值号左边只能是变量名字，而不能是表达式;右边表达式可以是一个数据、常量或算式.如：2=X是错误的②赋值号左右不能对换。如“A=B”“B=A”的含义运行结果是不同的。③不能利用赋值语句进行代数式的演算。（如化简、因式分解、解方程等）④赋值号“=”与数学中的等号意义不同。（5）对于一个变量可以多次赋值。〖例3〗：给一个变量重复赋值。A=10A=A+10PRINT

AEND程序：在此程序的基础上，设计一个程序，求A的输出值是

多少？A=10A=A+15PRINT

AA=A+5PRINT

AEND〖例4〗：交换两个变量A和B的值，并输出交换前后的值。分析：引入一个中间变量X,将A的值赋予X,又将B的值赋予A，再将X的值赋予B，从而达到交换A，B的值。（比如交换装满水的两个水桶里的水需要再找一个空桶）INPUT

AINPUT

BPRINT

A，BX=AA=BB=XPRINT

A，BEND程序：

例1编写程序，计算一个学生语文、数学、英语三门课程的总成绩和平均成绩，并输出。开始输入数学a输入语文b输入英语c总分s=a+b+c平均p=s/3输出总分s输出平均分p结束程序：INPUT“Maths=”;aINPUT“Chinese=”;bINPUT“Enghlish=”;cs=a+b+cp=s/3PRINT“sum=”;sPRINT“Theaverage=”;pEND程序框图：INPUT“Maths,Chinese,Eng