第一章 算法初步.doc

《第一章 算法初步.doc》由会员分享，可在线阅读，更多相关《第一章 算法初步.doc（51页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一章 算法初步1.1.1 算法的概念1.通过实例体会算法思想，了解算法的含义与主要特点；2.能按步骤用自然语言写出简单问题的算法过程；3.培养学生逻辑思维能力与表达能力.将问题的解决过程用自然语言表示为算法过程用自然语言描述算法算法不仅是数学及其应用的重要组成部分，也是计算机理论和技术的核心在以前的学习中，虽然没有出现算法这个名词，但实际上在数学教学中已经渗透了大量的算法思想，如四则运算的过程、求解方程的步骤等等，完成这些工作都需要一系列程序化的步骤，这就是算法的思想一、情景设置：1.把大象放冰箱总共分几步？2.两个大人和两个小孩一起渡河，渡口只有一条小船，每次只能渡1个大人或2个小孩，他们

2、四人都会划船，但都不会游泳。试问他们怎样渡过河去？请写出一个渡河方案。 二、探究新知（一）：算法的含义问题1：常有这样一种娱乐节目：就是猜数，让参加者从01000中猜出某商品的价格，猜测了以后，主持人说是高了，还是低了，然后再猜，直到猜中为止.而在这游戏中，较好的方法就是二分法：第一步 报出500第二步 如果是说高了，就再报250；如果低了，就报750；第三步 在前一个数与再前一个数之间，取它们的中间值；直到猜中为止.问题2：给出求1+2+3+4+5的一个算法解： 算法1 按照逐一相加的程序进行第一步：计算1+2，得到3；第二步：将第一步中的运算结果3与3相加，得到6；第三步：将第二步中的运算

3、结果6与4相加，得到10；第四步：将第三步中的运算结果10与5相加，得到15算法2 运用公式直接计算第一步：取=5；第二步：计算；第三步：输出运算结果【小结】算法(algorithm)的含义:对一类问题的机械的、统一的求解方法. 本章所研究的算法特指用计算机解决数学问题的方法.【体会】算法具有不唯一性二、探究新知（二）：算法的重要特征问题1：给出求解方程组的一个算法问题2：已知直角坐标系中的两点A（-1，0），B（3，2），写出求直线AB的方程的一个算法.【解】算法如下:第一步 计算斜率；第二步 用点斜式写出直线方程.问题3：设计一个算法,找出三个数a,b,c中的最大数.【解】算法如下:第一步

4、 比较a,b大小，若a小，则转第二步；若a大，则转第三步；第二步 比较b,c大小，若b小，则c是最大数，若b大，则b是最大数，结束任务； 第三步 比较a,c大小，若a小，则c是最大数，若a大，则a是最大数，结束任务。【小结】算法从初始步骤开始，每一个步骤只能有一个确定的后继步骤，从而组成一个步骤序列，序列的终止表示问题得到解答或指出问题没有解答. 算法具有如下两个性质:有限性：一个算法在执行有限个步骤后必须结束. 确定性：算法的每一个步骤和次序都应该是确定的、明确无误的,不应产生歧义三、典例分析例1 设计一个算法，判断7是否为质数.算法分析： 根据质数的定义，可以这样判断：依次用26除7，如果

5、它们中有一个能整除7，则7不是质数，否则7是质数。根据以上分析，可写出如下算法1：第一步：用2除7，得到余数1，因为余数不为0，所以2不能整除7第二步：用3除7，得到余数1，因为余数不为0，所以3不能整除7第三步：用4除7，得到余数3，因为余数不为0，所以4不能整除7第四步：用5除7，得到余数2，因为余数不为0，所以5不能整除7第五步：用6除7，得到余数1，因为余数不为0，所以6不能整除7,所以7是质数。算法2：第一步：第二步：余数为r ，若余数为0，则7不是质数，否则执行第三步；第三步：第四步：重复第二、第三步直到时结束算法。例1延伸： 设计一个算法，判断整数 是否为质数？算法：见课本例2：

6、用二分法求方程 的近似正根，精确度0.051下列有关“算法”的说法不正确的是（ D ）A.算法是解决问题的方法和步骤 B.算法的每一个步骤和次序应当是确定的C.算法在执行有限个步骤后必须结束 D.算法是能够在计算机上运行的程序语言2看下面的四段话，其中不是解决问题的算法的是（ C ）A.从济南到北京旅游，先坐火车，再坐飞机抵达B.解一元一次方程的步骤是去分母、去括号、移项、合并同类项、系数化为1C.方程x2-1=0有两个实根D.求1+2+3+4+5的值，先计算1+2=,再求3+3=6，6+4=10，10+5=15，最终结果为153.买一只杯子需2元，现要写出计算买n只杯子所需要的钱数的一个算法

7、，则这个算法中必须要用到的一个表达式为 2n .4.设计一个算法，计算输入实数的绝对值.【解】算法如下:第一步 输入x第二步 判断x的符号,如果为正或为零,则输出x;如果为负,则输出-x.5.完成课本第五页练习第1.2两题1.下列关于算法的说法中，正确的有（ ）求解某一类问题的算法是唯一的；算法必须在有限步操作之后停止；算法的每一步操作必须是明确的，不能有歧义或模糊；算法执行后一定产生确定的结果。A、1个 B、2个 C、3个 D、4个2.在数学中，现代意义上的算法是指（ ）A用阿拉伯数字进行运算的过程B解决某一类问题的程序或步骤C计算机在有限步骤之内完成，用来解决某一类问题的明确有效的程序或步

8、骤D用计算机进行数学运算的方法3.写出求过两点M(-3,-1)、N(2,5)的直线与坐标轴围成面积的一个算法。4.（1）写出解不等式x2-2x-30（a0）的一个算法。【解】（1）算法如下:第一步 解出方程x2-2x-3=0的两根是x1=3，x2= -1；第二步 由x2-2x-30可知不等式的解集为x | -1x0，解出方程ax2+bx+c=0的两根（设x1x2），则不等式解集为x | xx1或xx2；第三步 若= 0，则不等式解集为x | xR且x；第四步 若0）的根,画出相应的流程图 开始输入a1，a2将a1与a2的和记作b输出b将记作结束3、如图1所示的是一个算法的流程图,已知a1=3,

9、输出的b=7, 则a2的值是( )A.11 B.17 C.0.5 D.12输出yyy12-1x2y1x2-14、如图2所示的流程图最终输出的结果是_.图1图21.下面的结论正确的是 （）A、一个程序的算法步骤是可逆的B、一个算法可以无止境地运算下去的C、完成一件事情的算法有且只有一种 D、设计算法要本着简单方便的原则2、对顺序结构，下列说法：是最基本、最简单的算法结构；框与框之间是依次进行处理；除输入、输出框之外，中间过程都是处理框；可以从一个框图跳到另一个框图执行；其中正确的有 （ ）A、4个 B、3个 C、2个 D、1个3、画出解方程组的一个算法的流程图。4、 画出求两个正整数a与b相除所

10、得商q及余数r的一个算法的流程图。开始5、 x1 y2 yx+yxy+1yx +1tx xy yt 输出xy结束上述流程图结束时xy的值分别是多少？6.一个人带三只老虎和三头牛过河，只有一条船，可以容一个和各两只动物。如果老虎的数量不少于牛的数量，就会吃掉牛，设计安全渡河的算法。1.1.3 条件结构1. 进一步理解流程图的概念，了解条件结构的概念，能运用流程图表达条件结构；2.能识别简单的流程图所描述的算法；3.发展学生有条理的思考与表达能力，培养学生的逻辑思维能力.重点：运用流程图表示条件结构的算法难点：规范流程图的表示以及条件结构算法的流程图一、情景设置： 某铁路客运部门规定甲、乙两地之间

11、旅客托运行李的费用为： 其中（单位：）为行李的重量问题：试给出计算费用（单位：元）的一个算法，并画出流程图学生活动 学生讨论， 解： _； _，_； _。上述算法可以用框图直观地描述出来： （流程图二、知识探究问题1：条件结构的含义问题2：条件结构的程序框图由上面例子可以得出条件结构的两种形式； 满足条件？步骤A步骤B满足条件？步骤A是否三、典例分析例1设计求解一元二次方程的一个算法，并画出流程图例2设计一个求任意数的绝对值的算法，并画出流程图1下边的程序框图，能判断任意输入的数x的奇偶性，其中判断框内的条件是 （ ）开始输入xmx除以2的余数NY输出x是偶数输出x是偶数结束Am=0 Bx=0

12、 Cx=1 Dm=12.下面是一个算法的流程图，回答下面的问题：当输入的值为3时,输出的结果为 3.有以下问题：输入一个数x，输出它的算术平方根求函数的函数值求x的绝对值求三个数a,b,c中的最大数其中需要用条件语句来描述其算法的有（ ）A1个 B2个 C3个 D4个4.设计算法，求的解，并画出程序框图。解析：对于方程来讲，应该分情况讨论方程的解我们要对一次项系数a和常数项b的取值情况进行分类，分类如下：（1）当a0时，方程有唯一的实数解是；（2）当a=0，b=0时，全体实数都是方程的解；（3）当a=0，b0时，方程无解让学生按照刚讲解的条件结构的嵌套自己画程序框图。5.课本第20页练习第3题

13、1.如果考生的成绩大于或等于60分，则输出“及格”，否则输出“不及格”，用流程图表示这一算法的过程。NYNYab且ac输入a,b, cbc输出a输出c输出b开始结束2.右面的流程图表示了一个什么样的算法？3.写出解方程ax+b=0(a,b为常数)的算法，并画出流程图。4.右边的程序框图（如图所示），能判断任意输入的数x的奇偶性，其中判断框内的条件是（ ）A.m=0 B.x=0 C.x=1 D.m=15.选择结构不同于顺序结构的特征是含有（ ）A处理框 B判断框 C输入、输出框 D起、止框6.设计计算13+33+53+993的算法程序，并画出相应的流程图。1.1.4 循环结构1.了解循环结构的概

14、念，能运用流程图表示循环结构；2.能识别简单的流程图所描述的算法；3.发展学生有条理的思考与表达能力，培养学生的逻辑思维能力.重点：运用流程图表示循环结构的算法难点：规范流程图的表示以及循环结构算法的流程图一、情景设置： 北京获得了2008年第29届奥运会的主办权。你知道在申奥的最后阶段，国际奥委会是如何通过投票决定主办权归属的吗？2问题： 怎样用算法结构表述上面的操作过程？ 学生讨论， 解： _； _； _。 pNYA上述算法可以用框图直观地描述出来： （流程图）北京取得2008奥运会主办权。国际奥委会对遴选出的五个城市进行投票表决的操作程序：首先进行第一轮投票，如果有一个城市得票超过一半，

15、那么这个城市取得主办权；如果没有一个城市得票超过一半，那么将其中得票最少的城市淘汰；然后重复上述过程，直到选出一个城市为止。探究知识1循环结构的概念：_称为循环结构如图：虚线框内是一个循环结构，先执行框，再判断给定的条件是否为假；若为假，则再执行，再判断给定的条件是否为假，如此反复，直到为真，该循环过程结束。2说明：（1）循环结构主要用在反复做某项工作的问题中； （2）循环结构是通过选择结构来实现。 （直到型）3循环结构的三要素：_,_4.循环结构图AP成立不成立 成立AP不成立Until（直到型）循环 两种循环结构有什么差别？当型：先判断 后执行先判断指定的条件是否为真，若条件为真，执行循环

16、条件，条件为假时退出循环。直到型;先执行 后判断先执行循环体，然后再检查条件是否成立，如果不成立就重复执行循环体，直到条件成立退出循环。二、典例分析2：课本中例六、例七的讲解；其中例七的讲解给同学尝试并写出两种循环结构形式。3：用二分法求解方程求关于x的方程的根，精确到0.005课本19页练习练习题课本第20页练习B组第2题1、根据以下叙述内容，选择相应序号归类填写。当条件成立时不再执行循环当条件不成立时不再执行循环循环的特点是先判断，后执行，可能一次也不执行循环循环的特点是先执行后判断，循环至少执行一次上述属于当型循环的是 ；属于直到型循环的是 ；2下图给出的是计算的值的一个程序框图，其中判

17、断框内应填入的条件是开始S0，n2，i1ii+1nn+2ss+1/nNY输出s结束Ai10 Bi20 Di203.写出求（共有6个2）的值的一个算法，并画出流程图。4、画出计算10！的一个算法的流程图。5. 设计一个流程图，求满足10x2m then mbA5 B10 C5和10 D以上都不是4、下列程序段运行后，变量a，b的值为 a3b4if ab then taabbtend ifA3，4 B4，3 C3，3 D4，45、 下列算法中，最后输出的a，b，c各是多少？a3b-5c6abbcPrint a,b,c6、下列流程图表示的数学解析式是什么？是是否输出开始输入结束否7、用算法语句给出用

18、公式法求方程 的两个根的算法。8、编写一个程序，要求输入一个圆的半径，便能输出该圆的周长和面积。（ 取3.14）分析：设圆的半径为R，则圆的周长为，面积为，可以利用顺序结构中的INPUT语句，PRINT语句和赋值语句设计程序。程序： 9、 某班有50名学生，现将某科的成绩分为3个等级：不低于80分为A，低于60分为C，其余为B，试用条件语句表示输出每个学生相应的成绩等级的算法。1.2.2 基本算法语句（2）1.正确理解条件语句的步骤、结构及功能，并掌握其结构；2.能正确地使用条件语句表示选择结构；3.体会算法对逻辑思维能力的锻炼。重点：正确理解条件语句的步骤、结构及功能难点：使用条件语句表示选

19、择结构1问题1：某居民区的物业管理部门每月按以下方法收取卫生费：3人和3人以下的住户，每户收取5元；超过3人的住户，每超出1人加收1.2元试设计算法，根据输入的人数计算应收取的卫生费？【探究新知】（一）条件语句算法中的条件结构是由条件语句来表达的，是处理条件分支逻辑结构的算法语句。它的一般格式是：（IF-THEN-ELSE格式）满足条件？语句1语句2是否IF 条件 THEN语句1ELSE语句2END IF当计算机执行上述语句时，首先对IF后的条件进行判断，如果条件符合，就执行THEN后的语句1，否则执行ELSE后的语句2。其对应的程序框图为：（如上右图）在某些情况下，也可以只使用IF-THEN

20、语句：（即IF-THEN格式）满足条件？语句是否IF 条件 THEN语句END IF计算机执行这种形式的条件语句时，也是首先对IF后的条件进行判断，如果条件符合，就执行THEN后的语句，如果条件不符合，则直接结束该条件语句，转而执行其他语句。其对应的程序框图为：（如上右图）条件语句的作用：在程序执行过程中，根据判断是否满足约定的条件而决定是否需要转换到何处去。需要计算机按条件进行分析、比较、判断，并按判断后的不同情况进行不同的处理。【例题精析】例1：编写一个程序，求实数的绝对值。:例2：编写程序，输入一元二次方程的系数，输出它的实数根。分析：先把解决问题的思路用程序框图表示出来，然后再根据程序

21、框图给出的算法步骤，逐步把算法用对应的程序语句表达出来。算法分析：我们知道，若判别式，原方程有两个不相等的实数根、；若，原方程有两个相等的实数根； 若，原方程没有实数根。也就是说，在求解方程之前，需要首先判断判别式的符号。因此，这个过程可以用算法中的条件结构来实现。又因为方程的两个根有相同的部分，为了避免重复计算，可以在计算和之前，先计算，。程序框图：（参照课本）注：SQR（）和ABS（）是两个函数，分别用来求某个数的平方根和绝对值。即 ，例3：编写程序，使得任意输入的3个整数按从大到小的顺序输出。算法分析：用a，b，c表示输入的3个整数；为了节约变量，把它们重新排列后，仍用a，b，c表示，并

22、使abc.具体操作步骤如下。第一步：输入3个整数a，b，c.第二步：将a与b比较，并把小者赋给b，大者赋给a.第三步：将a与c比较. 并把小者赋给c，大者赋给a，此时a已是三者中最大的。第四步：将b与c比较，并把小者赋给c，大者赋给b，此时a，b，c已按从大到小的顺序排列好。第五步：按顺序输出a，b，c.程序框图： 程序设计： 1 练习14（题略）2铁路部门托运行李的收费方法如下：y是收费额（单位：元），x是行李重量（单位：kg）,当0x20时，按0.35元/kg收费，当x20kg时，20kg的部分按0.35元/kg,超出20kg的部分，则按0.65元/kg收费，请根据上述收费方法编写程序。分

23、析：首先由题意得：该函数是个分段函数。需要对行李重量作出判断，因此，这个过程可以用算法中的条件结构来实现。条件语句的条件表达式需用连接符如下：运算符功能举例数学表达式关系运算符小于a ba b小于或等于a bab大于a ba b 大于或等于a ba b等于a ba b不等于a bab逻辑运算符AND且x 5 AND x 11x5OR或 x 0 OR x 3x0或x3NOT非NOT x ax a1.P33，A组 1，2 B组1，3 P20 习题1.1 A组 3 设计出程序补充：1已知，写出求直线AB斜率的一个算法，画出程序框图，设计出程序2任意给定3个正实数，设计一个算法，判断分别以这3个数为三

24、边边长的三角形是否存在，画出这个算法的程序框图，并设计出程序。1.2.3 基本算法语句（3）一、教学目标1正确理解循环语句的概念，循环语句的应用环境，并掌握其结构。循环语句的两种形式：当型（WHILE型）和直到型（UNTIL型）两种语句结构。2会应用循环语句编写程序。 重点：正确理解循环语句的概念，并掌握其结构；会应用循环语句编写程序;并能进行简单的综合应用。难点：理解循环语句的表示方法、结构和用法；会编写程序中的循环语句.通过案例具体的案例，引导学生体会两种循环语句的形式、结构，结合计算机语言来完成程序编写。利用计算机来上机来感受循环语句的结构和形式，来加以修正和优化自己的算法程序。【创设情

25、境】试求自然数1+2+3+99+100的和。显然大家都能准确地口算出它的答案：5050。而能不能将这项计算工作交给计算机来完成呢？而要编程，以我们前面所学的输入、输出语句和赋值语句还不能满足“我们日益增长的物质需要”，因此，还需要进一步学习基本算法语句中的循环语句【循环语句】满足条件？循环体是否算法中的循环结构是由循环语句来实现的。对应于程序框图中的两种循环结构，一般程序设计语言中也有当型（WHILE型）和直到型（UNTIL型）两种语句结构。即WHILE语句和UNTIL语句。（1）WHILE语句的一般格式是：WHILE 条件循环体WEND其中循环体是由计算机反复执行的一组语句构成的。WHLIE

26、后面的“条件”是用于控制计算机执行循环体或跳出循环体的。当计算机遇到WHILE语句时，先判断条件的真假，如果条件符合，就执行WHILE与WEND之间的循环体；然后再检查上述条件，如果条件仍符合，再次执行循环体，这个过程反复进行，直到某一次条件不符合为止。这时，计算机将不执行循环体，直接跳到WEND语句后，接着执行WEND之后的语句。因此，当型循环有时也称为“前测试型”循环。其对应的程序结构框图为：（如上右图）满足条件？循环体是否（2）UNTIL语句的一般格式是：DO循环体LOOP UNTIL 条件其对应的程序结构框图为：（如上右图）问题1：直到型循环又称为“后测试型”循环，参照其直到型循环结构

27、对应的程序框图，说说计算机是按怎样的顺序执行UNTIL语句的？（让学生模仿执行WHILE语句的表述） 从UNTIL型循环结构分析，计算机执行该语句时，先执行一次循环体，然后进行条件的判断，如果条件不满足，继续返回执行循环体，然后再进行条件的判断，这个过程反复进行，直到某一次条件满足时，不再执行循环体，跳到LOOP UNTIL语句后执行其他语句，是先执行循环体后进行条件判断的循环语句。问题：通过对照，大家觉得WHILE型语句与UNTIL型语句之间有什么区别呢？ 区别：在WHILE语句中，是当条件满足时执行循环体，而在UNTIL语句中，是当条件不满足时执行循环体。【例题精析】例1：编写程序，计算自然数1+2+3+99+100的和。分析：这是一个累加问题。我们可以用WHILE型语句，也可以用UNTIL型语句。由此看来，解决问题的方法不是惟一的，当然程序的设计也是有多种的，只是程序简单与复杂的问题。程序： WHILE型： UNTIL型： 例2：根据1.1.2中的图1.1-2,将程序框图转化为程序语句。分析：仔细观察，该程序框图中既有条件结构，又有循环结构。程序：