2009年高一数学基础知识讲义(8)算法初步

第八讲算法初步知识要点算法与程序框图⑴算法的概念①算法的含义：通常是指可以用计算机来解决的某一类问题的程序或步骤，这些程序和步骤必须是明确有效的，而且能够在有限步之内完成。换句话说，算法其实就是计算机的解题的过程。②算法的特点：I.概括性；II.逻辑性；III有限性；IV.不唯一性；V.普遍性。③高斯消去法解一般的二元一次方程组：描述如下'1111221'211222212axaxbaxaxb因为是二元一次方程组，所以方程组中1121,aa不能同时为0。第一步：假定110a，''212112211222211111112,aaaabaxbaaa即方程组化为'1111221'11222112211221134axaxbaaaaxabab第二步：如果112212210aaaa解方程'4得到'1122112112221125ababxaaaa第三步：将'5代入'3整理得到：'2211221112221126ababxaaaa第四步：输出12,xx。如果112212210aaaa，则从'4可以看出，方程组无解或有无穷多组解。以后，我们在描述算法时，用英文12,xx,…,来表示第一步，第二步，…，④解二元一次方程组的公式法：1S计算11221221Daaaa2S如果0D，则原方程无解或有无穷多解；否则0D，12221221112112,;babababaxxDD3S输出计算的结果12,xx或无法求解的信息。⑤算法的描述：在这里我们主要向大家介绍程序框图I.符号表示II.画图规则：ii）框图一般从上到下，从左到右的方向画。iii）除判断框外，其它框图符号，只有一个进入点和一个退出点。iv）判断框分二择一形式的判断和多分支判断。v）图形符号内语言要简练清楚。III.三种基本逻辑结构框图：顺序结构；条件分支结构；、循环结构。⑤设计算法的要求：I.必须能够解决一类问题，并且能够重复使用。II.要使算法尽量简单，步骤尽量少，每一个步骤只能有一个后续步骤，从而组成一个步骤序列，序列的终止表示问题得到解答或没有得到解答。III.算法过程要一步一步执行，每一步执行的操作，必须确切，不能含糊不清，而且一定在有限步后算出结果。⑥算法的应用：数值性问题算法表述；非数值性算法描述。基本算法语句⑴赋值语句①定义：在表达一个算法时，经常要引入变量，并赋给变量一个值。用来表示赋给某一个变量一个具体的确定值的语句叫赋值语句。②格式：变量名=表达式③作用：赋值语句中的“=”叫赋值号。赋值语句的作用是先计算出赋值号右边表达式的值，然后把该值赋给赋值号左边的变量，使该变量的值等于表达式的值。④注意：I.赋值号的左边只能使变量名字，而不是表达式。II.赋值号左右不能对换。III.不能利用赋值语句进行代数式的演算。IV.赋值号与数学中的等号的意义不同。⑤几种常用形式：I.赋予变量常数值。II.赋予变量其它变量或表达式值。III.将含有变量自身的表达式赋予变量。⑵输入输出语句⑶条件语句①定义：处理条件分支逻辑结构的算法语句，叫做条件语句。②一般格式：if表达式语句序列1；else语句序列2；end或③功能：主要是用来实现算法中的条件分支结构，我们在运算中经常需要计算机按条件进行分析、比较、判断，并按判断后的不同情况进行不同处理。⑷循环语句①定义：在程序处理中，经常需要对一条或一组语句重复执行多次，以最终完成某项任务，这就是循环的概念。在Scilab程序语言中提供了两种循环语句，for循环和while循环。②一般格式：while循环格式for循环格式for循环变量=初值：步长：终值循环体end步长为1时可以省略不写，但为其它值必须写。③循环语句的作用：循环语句主要用来处理算法中的循环结构，来处理一些有规律重复的计算问题。如累加求和、累乘求积。用for循环编写时要注意设定好循环变量的初值、步长和终值，避免出现多一次循环或少一次循环的情况；用while循环编写程序时，一定要注意表达式的写法，当表达式为真时执行循环体，表达式为假时结束循环体，以防出现表达正好相反的错误。中国古代数学中算法的案例⑴更相减损之术（经常用来求最大公约数）⑵割圆术⑶秦九韶算法考试要求：体会算法思想，了解算法的含义，理解框图的三种基本逻辑结构，理解几种算法语句能初步应用这些算法语句编写Scilab程序，知道几个中国古代数学中的算法案例。命题趋向：在算法的含义及思想会有些基本题目，重点还是三种基本逻辑结构：顺序、条件、循环和几种基本的算法语句结合程序框图编写程序会有些综合题目，同学们要引起注意。例题讲解夯实基础if表达式语句序列1；endwhile条件循环体end1.算法的有穷性是指（C）.A算法的最后包含输出.B算法中的每个步骤都是可执行的.C算法的步骤必须有限.D以上说法都不对2.写出解二元一次方程组32142xyxy，的两种算法。解析：32142xyxy（1）（2）12341214113333214520(3)334(4)SxyySy算法：（1）（-）+（2），得到（）y=-2-即方程组化为解方程（3）可得S将（4）代入（2），可得x-4=-2,x=2；S输出2，-412355算法2：计算SD=31-1(-2)=5141-(-2)(-2)(-2)3-141Sx=y=S输出2，-4.3）①写出一个求解任意二次函数20yaxbxca的最值算法。②设计一个算法，对任意3个数,,abc，求其中的最小值。解：①算法步骤用自然语言叙述如下：1S计算244acbma；2S若0a，则函数的最小值为m；否则执行3S；3S函数的最大值为m。②算法步骤如下：1Smina2S如果minb，则minb；3S如果minc，则minc；4Smin就是,,abc中的最小值。4）一位商人有9枚银元，其中有一枚略轻的是假银元，你能用天平（不用砝码）将假银元找出来吗？设计一个算法，解决这一问题。解析：算法1：算法步骤如下：1S任取2枚银元分别放在天平的两端，如果天平左右不平衡，则轻的一侧是假银元；如果平衡则执行2S2S取下右边的银元，放在一边，然后把剩余的7枚银元依次放在右边进行称量，直到天平不平衡，偏轻的那一枚就是假银元。算法2：1S把银元分成三组，每组3枚；2S先把两组分别放在天平的两边，如果天平不平衡，那么假银元就在偏轻的那一组；如果天平左右平衡，则假银元就在未称的第三组里；3S取出含假银元的一组，从中任取两枚银元放在天平的两端，如果左右不平衡，则轻的一边是假银元；如果天平平衡，则未称的那一枚为假银元。上述两种算法中，算法1最少称量1次，最多称量7次，而算法2只需2次称量，可见算法2是对算法1的改进，比算法1优越。5）任意给定3个正实数，设计一个算法，判断分别以这3个数为三边边长的三角形是否存在，画出这个算法的程序框图。算法分析：判断分别以这3个数为三边边长的三角形是否存在，只需验证这3个数当中任意两个数的和是否大于第三个数。程序框图：6）观察下面框图表示了怎样的算法。解析：第一步：输入,,abc第二步：判断abac与，与的大小，如果abc同时大于和，则输他出a，否则执行第三步；第三步：判断bc与的大小，因为a已小于bc或，所以只需比较,bc的大小就能看出,,abc中谁是最大的，如果bc，则输出b，否则输出c。这样，该框图标示的含义就很清楚了。7）已知函数223yxx，编写一个程序，使每输入一个x的值，都得到相应的y值。解析：程序：();xinputx^22*3;yxxint%2,;prioxint%2,;prioyend8）为了节约用水，学校改革澡堂收费制度，实行计时收费，30分钟以内，每分钟收费0.1元，30分钟以上每分钟0.2元，请设计算法，使用基本语句完成澡堂计费工作，要求输入时间，输出费用。解析：设时间为t，则费用y为0.1,030,3300.2,30.ttytt程序框图如图所示：这里应用的是选择结构，应该用条件语句来表述。输入用水时间t；jf30t，then0.1;ytelse3300.2;yt输出用水费用y。300.1;3300.2;jftthenytelseyt能力提升1）画出计算111135999值的一个程序框图。从题目可以看出相加数的分子是不变的，而分母是有规律的递增，因此我们也可以引入累加变量1,2SiSSiii和计数变量，则，这个式子时反复执行的。2）阅读给出的程序框图，若输入的n是100，则输出的变量,ST的值依次是（）.2550,2500A.2550,2550B.2500,2500C.2500,2550D解析：设第k次计算后的S值为kS，所得T值为kT，则15049494821100,2,4,,98,SSSSSSS相加得501502469850492450,2550.SSS1504949482199,1,3,,97,TTTTTTT相加得250150135797492401,2500.TTTA3）（07宁夏、海南高考题）如图所示程序框图，那么输出的S（）.2450AB.2500C.2550D.2652解析：由信息图知12,1,2,3,,50kkSSkk取相加得≤1021325049S-S=2S-S=4S-S=6...,S-S=100500050242502550,0,2550,SSSSC选