第一章算法初步规律方法与数学思想.docx
- 文档编号:9890915
- 上传时间:2023-05-21
- 格式:DOCX
- 页数:45
- 大小:359.56KB
第一章算法初步规律方法与数学思想.docx
《第一章算法初步规律方法与数学思想.docx》由会员分享,可在线阅读,更多相关《第一章算法初步规律方法与数学思想.docx(45页珍藏版)》请在冰点文库上搜索。
第一章算法初步规律方法与数学思想
第一章 算法初步
§1.1 算法与程序框图
【入门向导】
“孙子问题”最早出现在我国《算经十书》之一的《孙子算经》中.其原文是:
“今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二.问物几何?
答曰:
二十三”.意思是说:
今有一些事物,不知道它的数目,三个三个地数它们剩余二个,五个五个地数它们剩余三个,七个七个地数它们剩余二个,问这些事物的数目是多少?
“孙子问题”相当于求关于x,y,z的不定方程组
的正整数解.
《孙子算经》中给出了具体的解法,其步骤是:
选定5×7的一个倍数,被3除余1,即70;选定3×7的一个倍数,被5除余1,即21;选定3×5的一个倍数,被7除余1,即15.然后按下式计算:
m=70×2+21×3+15×2-105P.式中105为3,5,7的最小公倍数,P为适当的整数,使得0 你能想出一种算法,利用计算机来解决上述问题吗? 法概念解读 1.对算法含义的理解 (1)算法是机械的 算法的设计要“面面俱到”,不能省略任何一个小小的步骤,有时可能要进行大量重复计算,但只要按步骤一步一步地执行,总能得到结果.算法的这种机械化的特点,在设计出算法后,便于把具体过程交给计算机去完成. (2)算法是普遍存在的 实际上处理任何问题都需要算法,如国际象棋的棋谱、走法、胜负的评判标准,邮寄物品的相关手续,求一个二元一次方程组的解等等. (3)求解某个具体问题的算法一般是不唯一的 算法实际上是解决问题的步骤和方法,求解问题的出发点不同,就会得到不同的算法.如求二元一次方程组的解有代入消元法和加减消元法,但不同的算法可能会有“优劣”之分. 例1 早上从起床到出门需要洗脸刷牙(5min)、刷水壶(2min)、烧水(8min)、泡面(3min)、吃饭(10min)、听广播(8min)几个步骤.从下列选项中选出最好的一种流程( ) A.1.洗脸刷牙、2.刷水壶、3.烧水、4.泡面、5.吃饭、6.听广播 B.1.刷水壶、2.烧水同时洗脸刷牙、3.泡面、4.吃饭、5.听广播 C.1.刷水壶、2.烧水同时洗脸刷牙、3.泡面、4.吃饭同时听广播 D.1.吃饭同时听广播、2.泡面、3.烧水同时洗脸刷牙、4.刷水壶 分析 处理问题的算法要求能够一步一步地执行,好的算法还要花费时间少. 解析 A中洗脸刷牙可以在烧水的过程中进行,听广播可以和吃饭同时进行;D中吃饭要在刷水壶、烧水、泡面之后. 答案 C 2.算法与数学问题解法的区别与联系 (1)联系 算法与解法是一般与特殊的关系,也是抽象与具体的关系.如教材中由具体的二元一次方程组的求解过程(解法)出发,归纳出了二元一次方程组求解的步骤;同时指出,这样的求解步骤也适合有限制条件的二元一次方程组,这些步骤就构成了二元一次方程组的算法.算法的获得要借助一般意义上具体问题的求解方法,而任何一个具体问题都可利用这类问题的一般算法解决. (2)区别 算法是解决某一类问题所需要的程序和步骤的统称,也可理解为数学中的“通法通解”;而解法是解决某一个具体问题的过程和步骤,是具体的解题过程. 例2 写出解方程x2-2x-3=0的一个算法. 分析 本题是求一元二次方程解的问题,方法很多.要注意设计算法时算法的逻辑性和有穷性. 解 算法1: 利用配方法设计算法如下: 第一步,移项,得x2-2x=3.① 第二步,①两边同时加1,并配方,得(x-1)2=4.② 第三步,②式两边开方,得x-1=±2.③ 第四步,解③得x=3或x=-1. 算法2: 利用公式法设计算法如下: 第一步,计算方程的判别式,判断其符号Δ=22+4×3=16>0. 第二步,将a=1,b=-2,c=-3代入求根公式x= ,得x1=3,x2=-1. 3.程序框图 (1)与自然语言相比用程序框图表示算法的优越性 用自然语言表示算法的步骤有明确的顺序性,但在处理条件结构或循环结构这样的问题时比较困难,不够直观、准确.程序框图是表示算法的另一种形式,它的结构清晰,步骤准确,有时能解决自然语言不易表达的问题. (2)画程序框图的规则 画程序框图的规则应是大家共同遵守的一些规则,目的是为了使大家彼此之间能读懂各自画的框图. ①使用标准的框图符号; ②框图一般按从上到下,从左到右的方向来画; ③除判断框外,大多数框图符号只有一个进入点和一个退出点,判断框是唯一具有超过一个退出点的符号; ④在图形符号内描述语言要简练、清楚. 例3 已知圆的半径,设计一个算法求圆的周长和面积的近似值,并用程序框图表示. 分析 解答本题可由圆的周长公式和面积公式直接求解,其中圆的半径可由算法输入. 解 算法设计: 第一步,输入圆的半径R. 第二步,计算L=2πR. 第三步,计算S=πR2. 第四步,输出L和S. 程序框图: 错点剖析 1.算法的确定性理解不到位 例4 求2+4+6+8+…+100的算法. 错解 算法: 第一步,计算2+4+6+8+…+100; 第二步,输出第一步中的结果. 正解 算法: 第一步,计算2+4得到6; 第二步,将第一步的结果与6相加得到12; 第三步,将第二步的结果与8相加得到20; 第四步,如此继续下去,一直加到100; 第五步,输出运算结果. 2.程序框图中循环结构功能、条件出错 例5 如图所示是某一算法的程序框图,根据该框图指出这一算法的功能. 错解 求S= + + +…+ 的值. 正解 在该程序框图中,S与n为两个累加变量,k为计数变量,所以该算法的功能是求 + + +…+ 的值. 3.混淆循环结构的两种形式 例6 试设计一个求1×2×3×4×…×n的值的当型循环结构程序框图. 错解 程序框图如图所示. 正解 程序框图如图所示. 点评 这是一个累乘问题,重复进行了(n-1)次乘法,可以用循环结构描述,需引入累 乘变量t和计数变量i,这里t与i每循环一次,它们的值都在改变. 计算法的三种思路 1.按部就班法 此法是基本方法,要求按问题的解题步骤“按部就班”地做,每一步都有唯一的结果,且在有限步之后得出结果. 例1 写出作∠ABC的平分线的一个算法. 分析 解决这个问题,只需按作图方法“按部就班”地设计算法. 解 第一步,以B为圆心,以任意长为半径画弧,与边BA交于M点,与边BC交于N点. 第二步,以M为圆心,以大于 MN的长d为半径画弧. 第三步,以N为圆心,以大于 MN的长d为半径画弧. 第四步,取第二、三两步所得的弧的交点P. 第五步,过B,P作射线BP,射线BP即为∠ABC的平分线. 2.公式法 利用现有公式解决问题是设计算法的重要思路. 例2 计算上底为2,下底为4,高为5的梯形的面积. 分析 根据梯形的面积公式S= (a+b)h.其中a是上底,b是下底,h是高,只需令a=2,b=4,h=5,代入公式即可. 解 算法如下: 第一步,a=2,b=4,h=5; 第二步,S= (a+b)h; 第三步,输出S. 3.循环法 有些问题需要重复计算,而这正是计算机的强项,因此我们可以利用循环来实现. 例3 设计出一个求23+43+63+…+603的算法. 解 第一步,p=0,i=2. 第二步,p=p+i3. 第三步,i=i+2. 第四步,如果i>60,算法结束,否则,返回第二步. 第五步,输出p. 程序框图的“三抓” 1.抓特征 组成任何一个程序框图的三要素是“四框”、“一线”加“文字说明”.“四框”即起止框、输入(出)框、处理框、判断框.“一线”即流程线,任意两个程序框之间都存在流程线.“文字说明”即在框图内加以说明的文字、算式等,这是每个框图不可缺少的内容. 2.明规则 程序框图的画法规则是: (1)用标准,即使用标准的图形符号; (2)按顺序,即框图一般按照从上到下、从左到右的顺序画;(3)看出入,即大多数程序框只有一个入口和一个出口,判断框是唯一具有两个出口的图框,条件结构中要在出口处标明“是”或“否”;(4)明循环,即循环结构要注意变量的初始值及循环终止条件;(5)辨流向,即流程线的箭头表示执行的方向,不可缺少;(6)简说明,即在程序框内的描述语言要简练清晰. 3.依步骤 画程序框图的总体步骤是: 第一步,先设计算法,因为算法的设计是画程序框图的基础,所以在画程序框图前,首先应在稿纸上写出相应的算法步骤,并分析算法需要哪些基本逻辑结构;第二步,再把算法步骤转化为对应的程序框图,在这种转化过程中往往需要考虑很多细节,是一个将算法“细化”的过程. 例4 某商场进行优惠促销: 若购物金额x在500元以上(不包括500元),则全部货款打8折;若购物金额x在300元以上(不包括300元)500元以下(包括500元),则全部货款打9折;否则,不打折.画出程序框图,要求输入购物金额x元,能输出实际交款额. 分析 由题意,实际交款额y与购物金额x之间的函数关系是y= 判断,所以算法含有两个条件结构,写出算法步骤如下. 解 算法如下: 第一步,输入购物金额x. 第二步,判断x≤300是否成立.若是,则y=x,执行第四步;否则,进入第三步. 第三步,判断x≤500是否成立.若是,则y=0.9x;否则,y=0.8x. 第四步,输出y,算法结束. 点评 (1)画顺序结构图,即起止框及输入框,并且流程线连接(如图中①); (2)画条件结构图,即画判断框,里面填写“x≤300? ”(如图中②).对于“是”画处理框并填入“y=x”,对于“否”流向下一个判断框;(3)再画条件结构图,即画判断框,里面填写“x≤500? ”对于“是”画处理框并填入“y=0.9x”,对于“否”画处理框并填入“y=0.8x”(如图中③);(4)画一个总的输出框并输出y,以及起止框表示算法结束(如图中④).最后,合成整个算法程序框图. 题多解 例5 用程序框图表示求S=1+2+22+23+…+249的值的一个算法. 分析 解答本题可以采用循环结构型框图,引入i作为计数变量,S作为累加变量,设计程序框图时可采用直到型循环结构,也可采用当型循环结构. 解 方法一 (直到型循环结构) 方法二 (当型循环结构) 点评 (1)如果算法问题中涉及到的运算进行了多次重复,且参与运算的数前后有规律可循,就可以引入变量以参与循环结构. (2)在不同的循环结构中,应注意判断条件的差别,及计数变量和累加(乘)变量的初值与运算框先后关系的对应性.初始值也可令S=1,i=1,同样正确. 例6 已知函数y= 写出求该函数值的算法及程序框图. 分析 该函数是分段函数,当x取不同范围内的值时,函数的表达式不同,因此当给出一个自变量x的值时,必须先判断x的范围,然后确定利用哪一段的表达式求函数值,因为函数分了三段,所以判断框需要两个,即进行两次判断.两次判断的内容可以进行交换. 解 算法如下: 第一步,输入x; 第二步,如果x>0,那么使y=-1,如果x=0,那么使y=0,如果x<0,那么使y=1; 第三步,输出函数值y. 程序框图如图所示. 方法一 方法二 方法三 点评 判断框中的内容是没有顺序的,判断框中的内容交换时对应的下一框图中的内容或操作也必须相应地进行变化. 1.(天津高考)阅读下边的程序框图,运行相应的程序,则输出i的值为( ) A.3B.4C.5D.6 解析 i=1时,a=2;i=2时,a=5;i=3时,a=16;当i=4时,a=65>50.即条件a>50成立,所以输出的i的值为4. 答案 B 2.(湖南高考)若执行如图所示的程序框图,输入x1=1,x2=2,x3=3, =2,则输出的数等于________. 解析 由框图的算法功能可知,输出的数为: S= = . 答案 3.(山东高考)执行下面的程序框图,输出的T=____. 解析 按照程序框图依次执行为S=5,n=2,T=2;S=10,n=4,T=2+4=6; S=15,n=6,T=6+6=12; S=20,n=8,T=12+8=20; S=25,n=10,T=20+10=30>S, 输出T=30. 答案 30 3题 4题 4.(上海高考)某算法的程序框图如图所示,则输出量y与输入量x满足的关系式是__________. 解析 由题意知,程序框图表达的是一个分段函数 y= 答案 y= 5.(广东高考)某篮球队6名主力队员在最近三场比赛中投进的三分球个数如下表所示: 队员i 1 2 3 4 5 6 三分球个数 a1 a2 a3 a4 a5 a6 下图是统计该6名队员在最近三场比赛中投进的三分球总数的程序框图,则图中判断框应填________,输出的s=________. 解析 该程序框图是统计6名队员在最近三场比赛中投进的三分球总数,因此图中判断框应填i≤6,输出的s=a1+a2+…+a6. 答案 i≤6? a1+a2+a3+a4+a5+a6 §1.2 基本算法语句 【入门向导】 在超市买完东西付款时,收银员会用扫描仪读取物品上的条形码,而后计算机屏幕上会显示这个物品的信息,当所有物品被扫描完后,计算机屏幕上会显示总价格,付款后,打印机打印购物小票.这个简单的过程可以分成三个方面: 通过扫描仪输入物品信息,然后计算机分析,最后在屏幕上输出信息.计算机之所以能完成这一系列操作,是因为我们给它植入一套计算机能够“理解”的程序语言.本节我们共同研究程序设计语言中的一些基本算法语句. 法与程序设计语言 1.程序是算法的精确形式,是计算机可以理解的算法.通常情况下,解决某个具体问题的算法包含大量烦琐的计算、复杂的作图等操作,而计算机强大的数据处理功能是帮助我们轻松完成这些具有重复性、机械性操作步骤的有力工具.但是用算法步骤或程序框图表示的算法是计算机不能理解的算法形式,计算机能够执行的算法必须是用计算机能够理解的语言进行描述的,而程序设计语言基本上就是计算机能够理解的语言.因此,学习用程序表示算法的一个重要原因是为了借助计算机执行算法. 2.程序是由若干算法语句组成的有序集合.程序框图是由表示算法基本逻辑结构的图形组成的,类似地,程序是由表示算法基本逻辑结构的算法语句组成的.任何高级程序设计语言都包含输入语句、输出语句、赋值语句、条件语句和循环语句五种基本语句.这五种基本算法语句与算法的三种基本结构基本上是相互对应的. 3.算法语句有着严格的语法规则,由算法语句组成的程序是否正确,这需要利用计算机执行程序加以验证.因此,上机验证程序的正确性通常是编写程序的一个必不可少的环节.同时,用程序表示算法的一个重要目的,就是利用计算机实现算法. 例1 已知三角形的三边长分别为a、b、c,要求输入三边长,输出三角形的面积. 分析 解决该问题的算法包括输入边长信息、赋值计算公式和输出运算结果. 解 程序: 点评 套用公式求值问题是传统数学求值问题的一种,它是一种典型的顺序结构,也就是说只通过输入、输出和赋值语句就可以完成任务.解决这类问题的关键是先分析这种问题的解法,即构造计算的过程,再写出算法步骤和流程图,最后翻译成算法语句即可. 4.输入、输出语句和赋值语句的含义及功能 (1)输入语句,又称“键盘输入语句”,在程序运行到此处时,停机等候用户从键盘输入数据,而不必在编写程序时就指定,这样增加了程序的灵活性.输入语句的主要功能是对程序中的变量赋值,用户由键盘输入的数据必须是常量,不能是函数表达式或变量.输入多个数据时,用“,”分隔,且个数不少于变量个数. (2)输出语句,又称“打印语句”,它可以将表达式的值、变量的值和系统信息在屏幕上显示出来.其功能是输出表达式的值或计算结果. (3)赋值语句的功能是对程序中的变量赋值、计算.在其格式中的赋值号与数学中的“=”意义不同,数学中它表示“=”两边的式子的值相等,如数学式子i=i+1是错误的,但在赋值语句中它的作用是将i+1的值赋给i,即i的值加1后,再赋给i,这样i原来的值被冲掉. 例2 判断下列给出的输入语句、输出语句和赋值语句是否正确? 为什么? (1)输入语句INPUT a;b;c; (2)输出语句A=4; (3)赋值语句3=B; (4)赋值语句A=B=-2. 解 (1)错,变量之间应用“,”号隔开. (2)错,输出语句不能用赋值号“=”. (3)错,赋值语句中“=”左右不能互换. (4)错,一个赋值语句只能给一个变量赋值. 点评 输入语句、输出语句和赋值语句基本上对应于算法中的顺序结构.输入语句、输出语句和赋值语句都不包括“控制转移”,由它们组成的程序段必然是顺序结构. 序语言中的函数和算术运算符 1.几种常见的函数及其功能 函数名 功能 注意事项 LOG(x) lnx(自然对数) e≈2.71828 SQR(x) x的算术平方根 x≥0 ABS(x) x的绝对值 INT(x) 取整函数,求不大 于x的最大整数 INT(-6.3)=-7 INT(6.5)=6 SGN(x) 符号函数 SGN(x)= 2.几种常见的算术运算符 运算符 作用 ∧ 乘幂运算,(如ab=a∧b) *,/ 乘法,除法运算,(如a×b=a*b) MOD,\ 求余运算,取商运算 +,- 加法,减法运算 例3 编写一个程序,要求输入两个正数a和b的值,输出这两个数的几何平均数 和算术平均数 . 分析 解答本题可先利用INPUT语句输入两个正数,然后将 和 分别赋给两个变量,然后输出两个变量的值即可. 解 程序如下: 点评 程序设计时,一定要遵守语句的格式和程序语言中函数和表达式的书写要求,否则程序会出错. 件语句的结构 条件语句中必须有IF、THEN、ENDIF,根据需要ELSE及其后面的语句体有时可省略. 例4 编写程序并画出程序框图,输入一个正数x,求函数y=|lnx|(x>0)的值. 分析 本题可以先求出lnx的值,利用单支条件语句对lnx<0时的值输出其相反数即可. 解 程序框图如图: 程序如下: 点评 单支条件语句采用IF-THEN的形式,对IF后的条件进行判断,若条件成立,则执行THEN后的语句;若条件不成立,则结束条件语句,执行ENDIF后面的语句. 种形式的循环语句比较 (1)当型循环先判断条件后执行,循环体可能一次也不执行; (2)直到型循环先执行一次循环体再判断条件,循环体至少执行一次;(3)对同一个算法,当型循环语句与直到型循环语句中的条件是相反的. 例5 分别用UNTIL与WHILE语句编写一个程序,求2×4×6×…×20的值. 分析 循环语句中要引入计数变量i和累乘变量s,设置条件开始或终止循环. 解 (UNTIL语句) (WHILE语句) 点评 注意两种语句中的条件是相反的;设计程序中要使用规范的语句格式和运算符号. 错点剖析 例6 已知a=2,b=5,交换a、b的值. 错解 程序如下: 错解辨析 第一行: a的值为2; 第二行: b的值为5; 第三行: 把b的值赋给a,这时b的值为5,所以a=5(注意: 这时a中原来存储的数值2已经被冲掉了); 第四行: 把a的值赋给b,而这时a的值为5,所以b的值还是5; 第五行: 因为a,b的值均为5,所以输出结果为5 5. 没有达到交换的目的.交换装满水的两个水桶里的水需要再找一个空桶,交换两个变量 正确的方法是设置一个中间变量t. 正解 程序如下: 例7 设计一个程序,任意输入点A的坐标,判断点A与单位圆的位置关系. 错解 程序如下: 正解 程序如下: 例8 给出30个数: 1,2,4,7,…,其规律是: 第1个数是1,第2个数比第一个数大1,第3个数比第二个数大2,第4个数比第3个数大3,以此类推,要计算第30个数的大小.现在已给出了该问题算法的程序框图(如图所示). (1)请在图中判断框①处和执行框②处填上合适的语句,使之能完成该题算法功能. (2)根据程序框图写出程序. 错解 (1)①中应填写“i>30? ”②中应填写“P=i”. (2)程序如下: 错解辨析 本题给出的程序框图中的循环结构是先判断条件然后执行循环体,属于当型循环结构,当型循环应是满足条件执行循环体,不满足条件退出循环,故①应填“i≤30? ”,设计的程序中的循环语句应用当型(WHILE)语句. 正解 (1)①中应填“i≤30? ” ②中应填“P=i” (2)程序如下: 何实现程序框图和程序的互化 1.根据程序画程序框图 根据程序画程序框图要做到: (1)明确程序是由哪些关键语句构成(条件语句、循环语句)的; (2)明确各类语句定义符的含义;(3)明确各类语句对应的程序框图.可简记为“抓关键,补附件,按照规则画出来”. 例1 下面给出的是输出裴波那契数列的一段程序,请根据算法程序画出程序框图. 程序(如图1所示): 图2 分析 本程序的关键语句为一个当型循环语句,它对应的程序框图的一般形式如图2所示.a=1,b=1,i=2都是赋值语句(其中i是计数变量),要用矩形框来表示,PRINT c是输出语句,要用平行四边形框来表示,另外,别忘了“开始”和“结束”. 解 给出的算法程序对应的程序框图(图3)如下: 图3 2.根据程序框图设计程序 根据程序框图设计程序关键在于: (1)要明确程序框图的结构(顺序结构、条件结构、循环结构); (2)要明确各程序框的含义;(3)要明确各结构及程序框对应的程序语言.可简记为“一看结构,二看框,程序语言用恰当”. 例2 请写出下面的程序框图描述的算法的程序. 分析 通过观察我们发现这个程序框图描述的算法含有两个条件结构;通过进一步分析我们还会发现这是一个求分段函数y= 函数值的算法.输入、输出框分别对应输入、输出语句,判断框对应条件语句. 解 所求算法的程序如下图所示. 点评 ①在本程序中,IF-THEN语句中嵌入了另一个IF-THEN语句,在每一个语句结束时都要写ENDIF;②上述两个语句的先后层次关系,我们用缩进若干空格的办法来体现,从而使程序层次分明,便于阅读;③若程序中有幂,其底数和指数之间要用专用符号“∧”连接. 题多解 例3 编写程序求n! =1×2×3×…×n. 分析 本题中的n要由键盘输入,因此在程序开始要用一个输入语句,以后的程序相应改变. 解 程序如下: 方法一 方法二 方法三 点评 (1)累乘变量的初始值一般为1; (2)循环体中语句次序的调换可能影响程序的运行结果.可在设置条件时进行检验. 1.(广州四校联考)下列程序运行后输出的结果为________. 答案 22,-22 2.(济宁模拟)下面两个程序最后输出的结果分别为( ) A.都是17B.都是21 C.都是27D.27与21 答案 D 3.(威海模拟)下面是求S=1+3+5+…+101的两个程序,请补充完整. 程序一: 程序二: 答案 一: 0 1 <=101 2 二: 0 1 2 >101 §1.3 算法案例 【入门向导】 秦朝末年,楚汉相争.一次,韩信率1500名将士与楚王大将李锋交战.苦战一场,楚军不敌,败退回营,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第一章 算法 初步 规律 方法 数学 思想