资源描述
算法的概念算法的概念在小品在小品“钟点工钟点工”片段中片段中问：要把大象装冰箱，总共分几步？问：要把大象装冰箱，总共分几步？答：分三步：答：分三步：第一步：把冰箱门打开第一步：把冰箱门打开第二步：把大象装冰箱第二步：把大象装冰箱第三步：把冰箱门关上第三步：把冰箱门关上算法的概念算法的概念 算法通常指可以用来解决的某一类问题算法通常指可以用来解决的某一类问题的步骤或程序，这些步骤或程序必须是的步骤或程序，这些步骤或程序必须是明确的和有效的，而且能够在有限步之明确的和有效的，而且能够在有限步之内完成的。内完成的。一般来说，一般来说，“用算法解决问题用算法解决问题” 可以利用可以利用计算机帮助完成。计算机帮助完成。例例1 “鸡兔同笼鸡兔同笼”是我国隋朝时期的数学著作是我国隋朝时期的数学著作孙孙子算经子算经中的一个有趣而具有深远影响的题目：中的一个有趣而具有深远影响的题目： “今有鸡兔同笼，上有十七头，下有四十八足，问：今有鸡兔同笼，上有十七头，下有四十八足，问：鸡兔各几只？鸡兔各几只？” 解：算术方法：如果没有小兔，那么小鸡解：算术方法：如果没有小兔，那么小鸡应为应为17只，总的腿数应为只，总的腿数应为217=34条，条，但现在有但现在有48条腿，造成腿的数目不够是由条腿，造成腿的数目不够是由于小兔的数目为于小兔的数目为0，每有一只小兔便会增，每有一只小兔便会增加两条腿，故应有加两条腿，故应有(48172) 2=7只小只小兔。相应的，小鸡有兔。相应的，小鸡有10只。只。代数方法：设有代数方法：设有x只小鸡，只小鸡，y只小兔只小兔. 则则172448xyxy将第一个方程的两边同乘以将第一个方程的两边同乘以2加到第二加到第二个方程中去，得到个方程中去，得到17(42)48 17 2xyy解第二个方程得解第二个方程得y=7.把把y代入到第一个方程得代入到第一个方程得x=10.思考思考1 教材中例教材中例1是著名的是著名的“鸡兔同笼鸡兔同笼”问题，其中第一种解法是算术方法，教问题，其中第一种解法是算术方法，教材中对它的评价是材中对它的评价是“简单直观，却包含简单直观，却包含着深刻的算法思想着深刻的算法思想”，那么它是如何体，那么它是如何体现算法的思想呢？现算法的思想呢？S1 假设没有小兔，则小鸡应为假设没有小兔，则小鸡应为n只；只；S2 计算总腿数为计算总腿数为2n只；只； S3 计算实际总腿数与假设总腿数的差值计算实际总腿数与假设总腿数的差值为为m2n；S4 计算小兔只数为计算小兔只数为 ; 22mnS5 小鸡的只数为小鸡的只数为n . 22mn思考思考2 教材中例教材中例1的第二种解法是列方程的第二种解法是列方程组的方法，它是否也是一种算法呢？组的方法，它是否也是一种算法呢？探究：是的，其算法步骤为：探究：是的，其算法步骤为： S1 设未知数；设未知数；S2 根据题意列方程组；根据题意列方程组；S3 解方程组；解方程组；S4 还原实际问题，得到实际问题的答案。还原实际问题，得到实际问题的答案。 在实际中，很多问题可以归结为求解在实际中，很多问题可以归结为求解二元一次方程组，下面我们用消元法来二元一次方程组，下面我们用消元法来解一般的二元一次方程组解一般的二元一次方程组11 1122121 12222 a xa xba xa xbS1 假定假定a110，a11a21得得 11 11221112221 12211 221 1 ()a xa xba aa axa ba bS2 如果如果a11a22a12a210，则执行下步；，则执行下步； 否则执行否则执行S6S3 两边同除以两边同除以a11a22a12a210得得 11 1122111 221 12112221 12 a xa xba ba bxa aa aS4 代入代入.得得 22 11221112221 1211 221 12112221 12 a ba bxa aa aa ba bxa aa aS5 输出结果输出结果x1，x2， S6 若若a11b2a21b10. 则执行下一步；否则执行下一步；否则执行则执行S8S7 输出输出“方程组无解方程组无解”.S8 输出输出“方程组有无穷多个解方程组有无穷多个解” 以上解二元一次方程组的方法，叫做以上解二元一次方程组的方法，叫做高斯消去法高斯消去法1.可执行性可执行性 2.确定性确定性 3.有限性有限性 4.可以解决一类问题可以解决一类问题 5.有输出结果的说明有输出结果的说明6、不唯一性、不唯一性算法的要求算法的要求 算法的表示算法的表示 描述算法可以有不同的方式描述算法可以有不同的方式, ,常用的有自然常用的有自然语言、程序框图、程序设计语言语言、程序框图、程序设计语言. . 自然语言就是人们日常使用的语言自然语言就是人们日常使用的语言, ,可以是可以是汉语、英语或数学语言等汉语、英语或数学语言等. .用自然语言描述算法用自然语言描述算法的优点是通俗易懂的优点是通俗易懂, ,当算法中的操作步骤都是顺当算法中的操作步骤都是顺序执行时比较容易理解序执行时比较容易理解. .缺点是如果算法中包含缺点是如果算法中包含判断和转向判断和转向, ,并且操作步骤较多时并且操作步骤较多时, ,就不那么直就不那么直观清晰了观清晰了. .(1)(1)自然语言自然语言(2)(2)程序框图程序框图(3)(3)程序设计语言程序设计语言1.1.21.1.2程序框图程序框图中讲解中讲解1.21.2基本算法语句基本算法语句中讲解中讲解算法的基本思想与特征算法的基本思想与特征:(1)解决某一类问题解决某一类问题(2)在在有限步有限步之内完成之内完成(3)每一步的明确性和有效性每一步的明确性和有效性(一般性一般性)(有穷性有穷性)(确定与可行性确定与可行性)判断下列关于算法的说法是否确：判断下列关于算法的说法是否确：1、求解某一类问题的算法是唯一的；、求解某一类问题的算法是唯一的；2、算法必须在有限步操作之后停止：、算法必须在有限步操作之后停止：3、算法的每一步必须是明确的，不能有歧、算法的每一步必须是明确的，不能有歧义或模糊：义或模糊：4、算法执行后一定产生确定的结果：、算法执行后一定产生确定的结果：S1 max=aS2 如果如果bmax, 则则max=b.S3 如果如果Cmax, 则则max=c.S4 max就是就是a, b, c中的最大值。中的最大值。 例例2 用数学语言，写出对任意用数学语言，写出对任意3个整数个整数a，b，c求出最大值的算法。求出最大值的算法。变式变式 写出一个求有限整数列中的最大值写出一个求有限整数列中的最大值的算法。的算法。解：算法如下：解：算法如下： S1 先假定序列中的第一个整数为先假定序列中的第一个整数为“最大值最大值”; S2 将序列中的下一个整数值与将序列中的下一个整数值与“最大值最大值”比比较，如果它大于此较，如果它大于此“最大值最大值”，这时你就假定，这时你就假定“最大值最大值”是这个整数；是这个整数； S3 如果序列中还有其他整数，重复如果序列中还有其他整数，重复S2; S4 在序列中一直到没有可比的数为止，这时在序列中一直到没有可比的数为止，这时假定的假定的“最大值最大值”就是这个序列中的最大值。就是这个序列中的最大值。例例3 写出求写出求1+2+3+4+5+6的一个算法。的一个算法。解：算法解：算法1：S1 计算计算1+2得到得到3；S2 将第一步中的运算结果将第一步中的运算结果3与与3相加得到相加得到6S3 将第二步中的运算结果将第二步中的运算结果6与与4相加得到相加得到10S4 将第三步中的运算结果将第三步中的运算结果10与与5相加得到相加得到15S5 将第四步中的运算结果将第四步中的运算结果15与与6相加得到相加得到21练习练习 求求1357911的值，写出的值，写出其算法。其算法。算法算法1；第一步，先求第一步，先求13，得到结果，得到结果3；第二步，将第一步所得结果第二步，将第一步所得结果3再乘以再乘以5，得，得到结果到结果15；第三步，再将第三步，再将15乘以乘以7，得到结果，得到结果105；第四步，再将第四步，再将105乘以乘以9，得到，得到945；第五步，再将第五步，再将945乘以乘以11，得到，得到10395，即，即是最后结果。是最后结果。算法算法S1 计算计算 的值的值S2 计算计算z0=|ax0+by0+c|的值的值.S3 计算计算 得所求的距离得所求的距离.22zab0zdz例例4. 设计算法解决下面的问题：已知点设计算法解决下面的问题：已知点P的坐标为的坐标为(x0，y0)，直线，直线l的方程为的方程为ax+by+c=0 (ab0)，求点，求点P到直线到直线l的距离的距离. 例例5 一位商人有一位商人有9枚银元，其中有枚银元，其中有1枚略轻枚略轻的是假银元，你能用天平（不用砝码）将的是假银元，你能用天平（不用砝码）将假银元找出来吗？假银元找出来吗？ 算法一：算法一：S1 任取任取2枚银元分别放在天平的两边，如枚银元分别放在天平的两边，如果天平左右不平衡，则轻的一边就是假银果天平左右不平衡，则轻的一边就是假银元；如果天平平衡，则进行元；如果天平平衡，则进行S2；S2 取下右边的银元放在一边，然后把剩余取下右边的银元放在一边，然后把剩余的的7枚银元依次在右边进行称量，直到天枚银元依次在右边进行称量，直到天平不平衡，偏轻的那一枚就是假银元。平不平衡，偏轻的那一枚就是假银元。算法二：算法二： S1 任取任取2枚银元分别放在天平的两边，如枚银元分别放在天平的两边，如果天平左右不平衡，则轻的一边就是假银果天平左右不平衡，则轻的一边就是假银元；如果天平平衡，则进行元；如果天平平衡，则进行S2；S2 从余下的从余下的7枚银元中再任取枚银元中再任取2枚分别放枚分别放在天平的两边，如果天平左右不平衡则轻在天平的两边，如果天平左右不平衡则轻的一边就是假银元；如果天平平衡，则进的一边就是假银元；如果天平平衡，则进行行S3；S3 从余下的从余下的5枚银元中再任取枚银元中再任取2枚分别放枚分别放在天平的两边，如果天平左右不平衡，则在天平的两边，如果天平左右不平衡，则轻的一边就是假银元；如果天平平衡，则轻的一边就是假银元；如果天平平衡，则进行进行S4；S4 从余下的从余下的3枚银元中再任取枚银元中再任取2枚分别放枚分别放在天平的两边，如果天平左右不平衡，则在天平的两边，如果天平左右不平衡，则轻的一边就是假银元；如果天平平衡，则轻的一边就是假银元；如果天平平衡，则最后剩下的还未称的最后剩下的还未称的1枚银元就是假银元。枚银元就是假银元。算法三：算法三：S1 任取任取4枚银元分别放在天平的两边，各枚银元分别放在天平的两边，各2枚，如果天平左右不平衡，则轻的一边中枚，如果天平左右不平衡，则轻的一边中含有假银元，并进行含有假银元，并进行S2；如果天平平衡，；如果天平平衡，则进行则进行S3；S2 将轻的一边的两枚银元分别放在天平将轻的一边的两枚银元分别放在天平的两边，则轻的一边的那枚银元就是假银的两边，则轻的一边的那枚银元就是假银元，称量结束；元，称量结束；S3 从余下的从余下的5枚银元中再任取枚银元中再任取4枚分别放枚分别放在天平的两边，各在天平的两边，各2枚，如果天平左右不枚，如果天平左右不平衡，则轻的一边就含有假银元，并转向平衡，则轻的一边就含有假银元，并转向S2；如果天平平衡，则最后剩下的还未称；如果天平平衡，则最后剩下的还未称的的1枚银元就是假银元，称量结束。枚银元就是假银元，称量结束。算法四：算法四：S1 把银元分成把银元分成3组，每组组，每组3枚；枚；S2 先将两组分别放在天平的两边，如果先将两组分别放在天平的两边，如果天平不平衡，那么假银元就在轻的那一组；天平不平衡，那么假银元就在轻的那一组；如果天平左右平衡，则假银元就在未称的如果天平左右平衡，则假银元就在未称的第第3组里；组里；S3 取出含假银元的那一组，从中任取两取出含假银元的那一组，从中任取两枚银元放在天平的两边，如果左右不平衡，枚银元放在天平的两边，如果左右不平衡，则轻的那一边就是假银元；如果天平两边则轻的那一边就是假银元；如果天平两边平衡，则未称的那一枚就是假银元平衡，则未称的那一枚就是假银元.1下面的四种叙述不能称为算法的是下面的四种叙述不能称为算法的是（ ）（A）广播的广播操图解）广播的广播操图解 （B）歌曲的歌谱）歌曲的歌谱 （C）做饭用米）做饭用米 （D）做米饭需要刷锅、淘米、添水、加）做米饭需要刷锅、淘米、添水、加热这些步骤热这些步骤反馈练习：反馈练习：C2下列关于算法的说法正确的是（下列关于算法的说法正确的是（ ）（A）某算法可以无止境地运算下去）某算法可以无止境地运算下去 （B）一个问题的算法步骤可以是可逆的）一个问题的算法步骤可以是可逆的 （C）完成一件事情的算法有且只有一种）完成一件事情的算法有且只有一种 （D）设计算法要本着简单、方便、可操）设计算法要本着简单、方便、可操作的原则作的原则 D3下列语句表达中是算法的有（下列语句表达中是算法的有（ ）. 从济南到巴黎可以先乘火车到北京再坐从济南到巴黎可以先乘火车到北京再坐飞机抵达；飞机抵达；利用公式利用公式 S = ah2 计算底为计算底为1高为高为2的的三角形的面积；三角形的面积； x2x +4；求求M(1，2)与与N(3，5)两点连线的方程可两点连线的方程可先求先求MN的斜率再利用点斜式方程求得的斜率再利用点斜式方程求得A. 1 个个 B. 2 个个 C. 3 个个 D. 4 个个21C4、已知一个学生的语文成绩为、已知一个学生的语文成绩为89，数学，数学成绩为成绩为96，外语成绩为，外语成绩为99，求他的总分和，求他的总分和平均成绩的一个算法为：平均成绩的一个算法为：第一步取第一步取A89，B96，C99;第二步第二步；第三步第三步；第四步输出第四步输出D，E.计算总分计算总分DA+B+C 计算平均成绩计算平均成绩E 3D5、写出交换两个大小相同的杯子中、写出交换两个大小相同的杯子中 的液体的液体 (A 水、水、 B 酒酒) 的一个算法的一个算法第一步第一步, ,找一个大小与找一个大小与A A相同的空杯子相同的空杯子C.C.第二步第二步, ,将将A A 中的水倒入中的水倒入C C中中. .第三步第三步, ,将将B B中的酒精倒入中的酒精倒入A A中中. .第四步第四步, ,将将C C中的水倒入中的水倒入B B中中, ,结束结束. .6、写出求一元二次方程、写出求一元二次方程 ax2+bx+c=0 的根的算法的根的算法.第一步第一步, ,计算计算=b b2 2-4-4acac. .第二步第二步, ,如果如果0,0,则原方程无实数解则原方程无实数解 ; ;否则否则(0)(0)时，时，,a2bx1 .a2bx2 第三步第三步: :输出输出x x1 1, , x x2 2或无实数解的信息或无实数解的信息. .第三步第三步, 若若f(a) f(m) 0,则含零点的区间为则含零点的区间为a,m；第一步第一步, 给定区间给定区间a,b,满足满足f(a) f(b)0第二步第二步, 取中间点取中间点2abm第四步第四步, 判断判断a,b的长度是否小于的长度是否小于d或者或者f(m)是否等于是否等于.若是，则若是，则m是方程的近似是方程的近似 解解;否则，返回第三步否则，返回第三步将新得到的含零点的仍然记为将新得到的含零点的仍然记为a,b .否则，含零点的区间为否则，含零点的区间为m, b.7 7、用二分法设计一个求方程、用二分法设计一个求方程220 x的近似根的算法的近似根的算法. .(0 )x 本节课主要讲了算法的概念，算法就是解本节课主要讲了算法的概念，算法就是解决问题的步骤，算法虽然没有一个明确的概念，决问题的步骤，算法虽然没有一个明确的概念，但其特点还是很鲜明的；平时不论我们做什么但其特点还是很鲜明的；平时不论我们做什么事都离不开算法，算法的描述可以用自然语言，事都离不开算法，算法的描述可以用自然语言，也可以用数学语言。也可以用数学语言。课堂作业课堂作业的算法。、写出975311求出最大值的算法。、个整数、写出对任意 32cba的算法。、写出解03432 xx
展开阅读全文