算法初步教学实践讲义

1、算法初步教学实践讲义东莞群英学校 梁斌玉说明：新课标理念先进，内容新颖，尤其是算法与编程的引入，适应了时代的发展，对我国的软件事业的发展将产生重大的影响。但是算法和编程对学生来说是很陌生的事物，而但是现行教材，讲解比较抽象，学生难懂。为此我根据自己的教学实践对算法初步进行了改编。力求做到了如下几点：1.例子丰富翔实贴切；2.循序渐进，由浅入深，将较难得问题分解为几个小块，逐步深入。3.符合学生的认知规律，在编排顺序上改变较大。由于水平有限经验不足，会存在不少缺点，还存在令人不满意的地方，在此抛砖引玉，望不吝赐教。本文共一万两千余字，打印共37页。求高手告知那里可以发表这类文章，谢谢。1.1算法

2、与程序框图本节课用大量的例子来强化“算法”的概念。这些例子由浅入深，由现实生活出发，逐步向数学和计算机中的算法靠近，使算法概念得以深化。例1是现实生活中的例子，意在使学生形成“步骤”的概念。例2人鬼过河（网上有相应的flash动画），是一个经典的智力题，可以激发学生的兴趣，学生当堂不一定能完成，可以让学生思考以后，用flash按步演示，目的是加深对“步骤”的认识。例3例4由现实生活中的例子过渡到数学中的例子，并和计算机结合，使算法的概念得到升华。例5，用筛选法求质数，对刚刚接触算法的学生来说，比较难懂，对此，采取了由特殊到一般，由浅入深的策略，使学生突破难点。 计算机的问世可谓20世纪最伟大的

3、发明，它把人类社会带进了信息技术的时代，而算法是计算机科学的重要基础，就像使用算盘一样，人们要给计算机编制“口诀”算法，才能让它工作。要想了解计算机的工作原理，算法的学习是一个开始。做任何事情都有一定的步骤。例如，你想考大学首先要填报名志愿表，拿到准考证，参加考试，得到录取通知书，到大学报名注册等。这些步骤都是按一定顺序进行的，缺一不可。现实生活中，我们很多事情都是这样一步一步的完成的。 可见算法并不是一个全新的概念，它融入在我们的现实生活中。在我国古代，“算法”取得了辉煌的成就。例1.烧水泡茶请看一下烧水泡茶的过程解：烧水泡茶可分下面4步完成。Step1：洗好开水壶；Step2：灌上凉水，放

4、在火上，等待水开；Step3：洗茶杯，茶杯里放好茶叶；Step4：水开后再冲水泡茶。 例2.人鬼过河 现在河的岸边有三个人和三个鬼，河上只有一条小船，船上最多能坐两个“人”，在河的任何一边，当鬼的个数比人多时，鬼就会吃掉人。请问如何才能使人和鬼都平安的到达对岸。解： 要想使人鬼都安全过河，需要下面11步。 Step1：Step2：Step3：Step4：Step5：Step6：Step7：Step8：Step9：Step10：Step11：例3.已知，求解： 要求需要下面4步。Step1：Step2：Step3：Step4：从事各种工作和活动，都必须事先想好工作的步骤，然后按部就班的进行，才能

5、避免产生错误。定义：我们把用来解决问题的一系列步骤叫做算法（algorithm）。算法一词源于算术(algorism)，即算术方法，是指一个由已知推求未知的运算过程。随着计算机的出现，人们常把这些“步骤”编写为“程序”由计算机来解决。算法必须符合以下条件：1.算法的每一步要做什么必须是明确的，不能含糊不清，模棱两可；例如，要把全班同学分成两队，“高个子的同学站出来”这个步骤就是不确定的，含糊的，哪些同学算高，哪些同学算矮？个子中等的同学就会不知所措。2.算法的每一步都应当能有效的执行，并得到确定的结果。例如若是无效的，不能执行的。3.算法必须在有限步内完成，如果需要无限步完成，就失去了实际意义

6、。算法的有限性往往指“在合理的范围之内”。如果让计算机执行一个历时1000年才结束的算法，虽然是有限的，但超过了合理的限度，人们也不把它视作有效算法。究竟什么算“合理限度”并无严格标准，由人们的常识和需要而定。例4给计算机编写一个算法，输入一个自变量的值，求分段函数的函数值.解：Step1：输入x的值；Step2：进行判断，如果，则， 否则。Step3： 输出结果。说明：1.输入x的值就是把自变量x的值由键盘输入计算机，例如要计算x=2时的函数值，就输入2。 2.根据相应的x的值计算相应的函数值，比如输入3，则 ；如果输入-4，则。 3.输出结果就是把计算结果显示在计算机屏幕上。以上算法可以通

7、过输给计算机一系列“命令”来实现，这些命令叫做计算机语言。例5.筛选法求质数质数亦叫作素数，是大于1的自然数，并且除了该数本身和1以外没有其它的数能整除它，如2，3，5，7，11，13，质数有无穷多个。 （1）判断143是否为质数。解：Step1：1432不为整数；Step2：1433不为整数；Step3：1434不为整数；Step4：1435不为整数；Step5：1436不为整数；Step6：1437不为整数；Step7：1438不为整数；Step8：1439不为整数；Step9：14310不为整数；Step10：14311=13，143能被11整除；Step11：结论：143不是质数。（2

8、）判断17是否为质数。解：Step1：172不为整数；Step2：173不为整数；Step3：174不为整数；Step4：175不为整数；Step5：176不为整数；Step6：177不为整数；Step7：178不为整数；Step8：179不为整数；Step9：1710不为整数；Step10：1711不为整数；Step11：1712不为整数；Step12：1713不为整数；Step13：1714不为整数；Step14：1715不为整数；Step15：1716不为整数；Step16：结论：17是质数。 （3）判断216091是不是质数该题的计算量非常大，我们可以把算法编为程序，由计算机帮我们计算

9、。（4）设计一个算法，输入大于2的整数n，由计算机判断它是不是质数。解Step1：输入整数n；Step2：依次检验2(n-1)是不是n的因数，若有这样的数，则n不是质数，否则，n为质数。Step3：输出结果。说明：其中第3步在计算机中可以通过一个循环来实现，今后会学到。2001年12月5日拿大大学生迈克卡梅伦发现又发现一个最大质数，它被记作2134669171，而它的完整表示式中含有4053946个数字。他是GreatInternetMersennePrimeSearch(Gimps)计划的参加者，该计划在致力于解决这一问题时同时动用了全球13万台个人计算机。有意思的是，为了完整地写出这个最大

10、质数，迈克卡梅伦花去了整整三周时间。为了发现这个最大质数，他利用自己的800兆赫计算机工作了45天。 研究结果可以在数论中找到应用，也可以帮助研究更可靠安全的译码方法。目前，Gimps计划正在抓紧寻找由几千万个数字组成的质数，如谁的计算机能寻找到这隐藏的更大质数，则可以获得10万美元奖金。 思考 你能举出跟多算法的例子吗？于一般的解决问题的过程比较，你认为算法最重要的特征是什么？ 练习：1.任意给定一个正数，设计一个算法，求以这个数为半径的圆的面积。2.设计一个算法，求的值。3.牛虎过河。一个人带三只老虎和三头牛过河。只有一条船，可以容一个人和两只动物。没有人在的时候，如果老虎的数量不少于牛的

11、数量就会吃掉牛。设计安全渡河的算法。4.任意给定一个大于1 的正整数n，设计一个算法，求出n的所有因数。算法对学生来说是陌生的内容，根据“建构主义理论”应由最简单的开始，逐步构建出“程序框图”的知识。课本上先给出了一个包含三种基本结构的复杂框图，然后把它进行分解来认识它，违背了认知规律，学生不易理解，且易使学生产生畏惧心理。这种方法适合于学生比较熟悉的事物。据此，本节通过浅显的例子（这些例子多数是第一节中研究过的），依次引出顺序结构，选择结构和循环结构，并及时归纳总结，是学生在不知不觉中加深对三种结构的理解。算法可以用自然语言来表示，但为了使算法的步骤表达得更为直观，我们更经常地用图形方式来表

12、达，这就是 程 序框图。 程序有三种基本逻辑结构，顺序结构、选择结构和循环结构。复杂的程序都是由这三种结构组成。一、顺序结构例1烧水泡茶 请叙述一下烧水泡茶的过程解：该算法用自然语言表述为Step1：洗好开水壶；Step2：灌上凉水，放在火上，等待水开；Step3：洗茶杯，茶杯里放好茶叶；Step4：水开后再冲水泡茶。 可以用程序框图表示为： 开始洗水壶烧水泡茶洗茶杯，放茶叶结束 例2. 给计算机编写一个算法，输入一个自变量的值，求的函数值.解：该算法用自然语言表述为Step1：输入x的值Step2：Step3：Step4：Step5：Step6：输出y。可以用程序框图表示为：开始输入x输出y

13、结束 程序框图符号和它们所表示的功能：图形符号名称功能 起止框（终端框）表示一个算法的起始和结束输入输出框表示一个算法输入和输出的信息处理框（执行框）赋值、计算流程线连接程序框 顺序结构由若干个依次执行的处理步骤组成。这是任何一个算法都离不开的基本结构。二、选择结构例3给计算机编写一个算法，输入一个自变量的值，求分段函数的函数值.解：该算法用自然语言表述为Step1：输入x的值；Step2：进行判断，如果，则， 否则。Step3： 输出结果。可以用程序框图表示为：开始输入x输出y结束其中被虚线框起来的是选择结构，它的一般形式为：步骤2步骤1 选择结构由一个判断框和两个分支组成。当条件框内的条件

14、成立时，程序沿着分支1进行；否则程序沿分支2进行。图形符号名称功能判断框判断某一条件是否成立，它有两个出口：“是”或“否”。条件成立时，程序沿着“是”这个分支走下去；当条件不成立时，程序沿着“否”这个分支进行。 流程线连接程序框连接点当一个程序框图很大，一页写不下时，连接程序框图的两部分。一般在连接处标上相同的数字序号。例4.判断一元二次函数是否有根。分析：，当时，方程有根；当时，方程无根。解：程序框图表示为开始输入a,b,c结束输出：方程有实根输出：方程无实根一般情况下，选择结构有两个分支，分别说明条件“成立”时怎样做，件“不成立”时怎样做。但也有特殊情况，当条件不成立时什么也不做（或者条件

15、成立时什么也不做），这时只有一个分支。例5.电视上有很多智力竞赛的题目，主持人提问，选手回答，若回答正确，加10分，如果错误，不加分。试用程序框图来描述这一情况。解：回答正确？开始结束选手回答主持人提问加10分 一个分支的条件结构的一般形式为：步骤 选择结构的嵌套例6.函数，编写一个算法，输入x的值，输出y的值解：该算法的程序框图为开始输入x输出y结束（1） 虚线框起来的部分为嵌套选择结构；（2） 当x0时程序沿着“Yes”分支进行；（3） 当时程序沿着“No”分支进行（4） “No”分支中又包含了一个条件结构。三、循环结构例5.上例中，智力竞赛的真实过程要复杂很多，主持人提问，选手回答，若回

16、答正确，加10分，如果错误，不加分，然后主持人继续提问，选手继续回答，如此循环下去，直到提问结束。（当然这也只是简化过程。）用程序框图来描述这一情况。解：由于过程中出现了循环，需要用循环结构果来表示。 开始结束分数=0选手回答主持人提问回答正确？分数=分数+ 10分还要提问？（1） 程序按箭头所指方向进行；（2） 虚线框起来的部分称为循环结构；（3） 每次进入循环前都要判断是否“还要提问”，若还要提问，则进入循环（继续提问），若提问结束，则不再进入循环，算法结束。（4） 其中“主持人提问”、“选手回答”、“判断是否加分”等步骤是每次循环所重复的内容，叫做循环体。（5） “分数=分数+ 10分”

17、是一个赋值语句，其含义是：“后来的分数=原分数+10分”循环结构的一般形式为：循环体满足条件？ 例5 写出求1+2+3+4+5+6的一个算法。解： Step1：计算1+2得到3；Step2：将第一步中的运算结果3与3相加得到6；Step3：将第二步中的运算结果6与4相加得到10；Step4：将第三步中的运算结果10与5相加得到15；Step5：将第四步中的运算结果15与6相加得到21。例6设计一个计算的算法解：如果按例5的方法，计算量很大。我们可以设想有一个空储物箱，第1次放入1个球，第2次放入2个球第100次放入100个球。这样重复100次后，储物箱里的总球数就是个。每放一次球我们可以看作一

18、次循环，总共循环了100次。 为了求从1 到100 的和，我们可以设一个变量S，它就像一个储物箱，一开始S=0，相当于储物箱是空的。另设一个变量i，用它来记录循环（即累加）的次数，i的初始值为1，每循环一次，i增加1，当i=100时，刚好循环了100次，当i=101时，i100,就退出循环。开始结束 输出S （1）程序按箭头所指方向进行， 在判断框处 ，如果，则按yes所指方向进行循环，否则按No所指方向进行。（2）i叫做计数变量，用于记录循环次数，同时它的取值还可以用来判断循环是否中止。循环第一圈时i的值为1，第二圈时i的值为2第100圈时，i的值为100。这种变化是通过语句i=i+1来实现

19、的。其含义是“后来的i值=原i值+1”每循环一圈，i=i+1被执行一遍，的值就增加了。（3）S叫做累加变量，用于记录累加结果。循环第1圈在S上加1；循环第2圈在S上加2；循环第3圈在S上加3；循环第i圈在S上加i；循环第100圈在S上加100；“循环第i圈在S上加i”用语句S=S+i表示，把这时i的值加到S上。当循环到100圈时，S的值就是的和。例7下面是一个计算的算法，请补充完整。分析：先考虑清楚下面两个问题。1. 从2到100的偶数共有多少个？_2. 两个相邻偶数的间隔是多少？_解：开始结束 输出S为了理解该程序，填写下表圈数i100s直到型循环结构绝大多数情况下可以有当行循环结构代替，对

20、开发学生智力并无多大帮助，反而会使学生产生迷惑，何必增加这些内容呢？练习1. 设计一个求任意数的绝对值得算法，并划出程序框图。2. 任意给定3个正实数，设计一个算法，判断分别以这3个数为边长的三角形是否存在。画出这个算法的程序框图。3. 某居民区的物业部门每月向居民收取卫生费，计费方法是：3人和三人以下的住户，每人收取5元；超过3人的住户，每超出一人，加收1.2元。写出一人数x为自变量，以卫生费y为函数值的分段函数。设计一个算法，根据输入的人数，计算应收取的卫生费，画出程序框图。4. 设计一个求解一元二次方程的算法，画出程序框图。5. 设计一个计算的算法，画出程序框图。6. 设计一个算法，求的

21、值.，画出程序框图。1.2基本算法语句计算机完成任何一项任务都需要算法。但是，我们用自然语言或程序框图描述的算法，计算机是无法“理解”的。因此还需要把算法翻译成计算机能理解的“计算机程序设计语言”（Progamming Language），编制成计算机程序。我们前面学过，算法有三种基本结构：顺序结构、条件结构和循环结构。为了实现算法中三种基本的逻辑结构，各种程序设计语言都包括下列算法语句：输入语句、输出语句、赋值语句、条件语句和循环语句。程序设计语言有很多种，如BASIC，Foxbase，C语言，C+，J+，VB等。它们的基本原理是相同的。本章中，我们学习的程序设计语言是“QuickBASIC

22、”语言，它是一种类BASIC语言。BASIC是Beginner Allpurpose Symbolic Instruction Code(初学者通用符号指令代码)的英文缩写，与1964年由美国的两位教授设计，具有简单、易学的特点。 输入语句、输出语句、和赋值语句基本上对应于算法中的顺序结构。计算机从上而下按照语句排列的顺序执行这些语句。一、输入语句例1.编制一个程序，在电脑屏幕上显示“Hello，evryone！”。解：运行QuickBASIC软件，在编辑窗口内输入下面程序。PRINT “Hello,everyone!”ENDHello,everyone! 编辑程序 运行结果 其中的PRINT

23、是一个命令，它的作用是输出它后面引号中的内容。运行该程序，会在电脑屏幕上显示：Hello,everyone!例2 设变量x=123，编制一个程序，在屏幕上显示出x的值。解：“运行QuickBASIC软件，在编辑窗口内输入下面程序。x=123PRINT xEND123 编辑程序 运行结果思考 PRINT语句后的输出内容中，加引号和不加引号的区别？ _上面几个例子中“PRINT”语句就是输出语句，对应于程序框图中的输出语句。其一般格式为：PRINT “提示内容”；变量想一想下面语句会输出什么结果？X=123+321PRINT “x=” ; xENDx=444 编辑程序 运行结果例3.当x=234时

24、求函数的值。解：“运行QuickBASIC软件，在编辑窗口内输入下面程序。X=123y=x3+3*x2-24*x+30PRINT “y=” ; yENDx=19033323 编辑程序 运行结果程序中的运算符，和我们平常用的有所不同，具体如下：数学运算加减乘除程序符号+-*/xnsqr(a)abs(a)二、输出语句例4.编写一个程序，输入x的值求函数的值。解：“运行QuickBASIC软件，在编辑窗口内输入下面程序。INPUT “x=” : xy=x3+3*x2-24*x+30PRINT “y=” ; yEND编辑程序这个程序中，第一行的INPUT语句就是输出语句，其后的x是一个变量。该语句的作

25、用是从键盘输入x的值。例如要计算x=100时的函数值，就输入100。输出语句对应于程序框图中的输出框，其一般格式为：INPUT “提示内容”；变量 输出语句可以在计算机屏幕上输出常量、变量和提示信息。运行程序后会出现如下提示窗口：x=？运行后程序提示输入x的值x=？111x=111y=1401960输入x的值111后程序自动计算出y=1401960三、赋值语句赋值语句前面已经见过，请再在看一下例3 ：x=123y=x3+3*x2-24*x+30PRINT “y=” ; yEND.第一行和第二行叫做赋值语句，顾名思义，赋值语句就是将表达式所带表的值赋给变量。赋值语句中的“=”叫做赋值号，它和数学

26、中的等号不完全一样。计算机执行赋值语句时，先计算“=”右边的表达式式的值，然后把这个值赋给左边的变量。例如第一行中，就把左边的123赋给右边的变量x（即让x等于123）；第二行，先计算出左边的表达式的值为1401960，然后把1401960赋给变量y。赋值语句的一般格式为：变量 = 表达式可以把变量看作一个存放数据的盒子，而且最多只能存放一个数据的盒子。当一个新数据放进去时，原来的数就被“挤”了出去。请说出下面程序输出的结果a=10a=a+20PRINT “a=”;aEND第一行：把等号右边的数值10赋给左边的变量a；10 a第二行：先计算等号右边的值a+20=10+20=30，然后把数据30

27、存入变量a，a中原来的10被冲掉。 30 a 输出结果：a =20 例5.编写程序，计算一个学生数学、语文、英语三门课的平均成绩。解：程序为：INPUT “Maths=”;a INPUT “ Chines=”;b INPUT “ English=”;c x=(a+b+c)/3 PRINT “ The average is”;x END思考请把下面的程序框图翻译为程序，并说出那些框图对应输出语句，那些框图对应输入语句，那些框图对应赋值语句。开始输入x输出y结束例6.已知，交换的值。分析：请看下面的程序 a=2b=5a=bb=aPRINT a,bEND 输出结果为：5 5.请思考为什么？第一行：a

28、的值为2；第四行：b的值为5； 第三行: 把b的值赋给a，这时b的值为5，所以a=5;(注意：这时a中原来存储的数值2 已经被冲掉了。) 第四行：把a的值赋给b，而这时a的值为5，所以b的值还是5； 第五行：因为a，b的值均为5，所以输出结果为5 5。 没有达到交换的目的。 为了加深理解，请大家请分析一下每行中a、b的值，并填表。 a b 第1行：第2行：第3行： 第4行：第5行：解：（空桶法）交换装满水的两个水桶里的水需要再找一个空桶，交换两个变量正确的方法是设置一个中间变量t。 a=2b=5t=aa=bb=tPRINT a,bEND 第三行t=a的作用：把a的值2保存在变量x中，这样当执行

29、a=b时，a中的值仍可以在t中找到。 请分析一下每行中a、b、t的值，并填表。 a b t 第1行：第2行：第3行： 第4行：第5行：第6行： 练习1. 已知华氏温度和摄氏温度的转化公式为： 编写一个程序，输入一个华氏温度，输出其相应的摄氏温度。2. 编写一个程序，输入两个非零实数，输出他们加、减、乘、除的结果。3. 已知一个三角形的三边长分别是，它的面积可用海伦秦九韶公式计算。 ，其中 设计一个算法，输入三角形的三条边长，输出三角形的面积S。写出程序框图和相应的程序。4. 春节到了，糖果店的售货员忙极了。已知水果糖每千克10.4元，奶糖每千克15.6元，果仁巧克力每千克25.2元，那么依次购

30、买这三种果糖千克，应收取多少钱？请你设计一个程序，帮售货员算账。5. 编写一个程序，输入梯形的上底、下底和高的值，计算并输出其面积。6. 编写一个程序，交换两个变量a 、b的值，并输出交换前后的值。算法中的条件结构由条件语句来表达。一、基本条件语句（1）两个分支的条件结构IF 条件 THEN语句体1ELSE语句体2ENF IF步骤2步骤1 条件结构框图 条件语句当计算机执行上述语句时，首先对IF后的条件进行判断，如果条件成立，就执行THEN之后的语句体，否则执行ELSE之后的语句体。例1. 给计算机编写一个程序，输入一个自变量的值，输出分段函数的函数值.解： 用程序框图表示为：开始输入x输出y

31、结束用QuickBASIC 语言可写为INPUT “x=”;x IF x=0 THEN y = x + 2 ELSE y = x2 END IF PRINT “y =” ; y END数学运算等于不等于大于小于大于等于小于等于程序符号=0 THEN外层IF语句 y = 1内层IF语句 ELSE IF x=0 THEN y = 0 ELSE y = -1 END IF END IF PRINT “ y=”; y END该程序中有两个IF语句，大IF语句中嵌套了一个小IF语句。思考 请将程序框图和相应的语句对应起来。例3 编写一个程序，求一元二次方程的根.分析：，当时方程有两个不相等的实根；当时，

32、方程有两个相等的实根；当时，方程没有实根。解：程序框图为 开始输入a,b,c结束输出:没有实根 输出x输出:没有实根将程序框图改写为QuickBASIC 程序INPUT a,b,cD=b2-4*a*cIF D=0 THEN IF D0 THEN x1=(-b+sqr(D)/2*a x1=(-b-sqr(D)/2*a PRINT “x1=”;x1,”x2=”;x2 ELSE x=-b/2*a PRINT “x=”;x END IFELSE PRINT “No root.”END IFEND例4 排序编写一个程序，使得任意输入的3个整数按从大到小的顺序输出。算法分析：我们用a,b,c表示输入的三个

33、整数，比较三个整数，把最大的整数存入变量a中，次大的整数存入b中，最小的整数存入c中。Step1：输入三个整数a,b,c；Step2：将a与b比较，如果ab,交换它们的值；Step3：将a与c比较，如果ac,交换它们的值； (第2步和第3步后，a中存储的已经是最大的整数)Step4：将b与c比较，如果ba THEN t=a a=b b=t END IF IF ca THEN t=a a=c c=t END IFIF cb THEN t=b b=c c=t END IF PRINT a,b,c END练习1.读程序，说出该程序的功能。 INPUT “Please input an inter:”;x IF 9x AND x100 THEN a=x10 b=x MOD 10 PRINT a,b END IFEND数学运算且或的商的余数程序符号ANDORa MOD b注：1.在程序中用“AND”表示“且”，用“OR”表示“或”。 2.用“a/b”