《算法的概念》设计 市赛一等奖

《算法的概念》教学设计教学目标：理解并掌握算法的概念与意义，会用“算法”的思想编制数学问题的算法。教学重点：算法的设计与算法意识的的培养教学难点：用算法步骤表示算法时怎样划分步骤．教学课时:1个课时教学过程：一、问题情景：请大家研究解决下面的一个问题1．两个大人和两个小孩一起渡河，渡口只有一条小船，每次只能渡1个大人或两个小孩，他们四人都会划船，但都不会游泳。试问他们怎样渡过河去？请写出一个渡河方案。（通过学生讨论得出渡河方案与步骤如下）S1两个小孩同船过河去；S2一个小孩划船回来；S3一个大人划船过河去；S4对岸的小孩划船回来；S5两个小孩同船渡过河去；S6一个小孩划船回来；S7余下的一个大人独自划船渡过河去；对岸的小孩划船回来；S8两个小孩再同时划船渡过河去。2．一群小兔一群鸡，两群合到一群里，要数腿共48，要数脑袋整17，多少小兔多少鸡？先列方程组解题，得鸡10只，兔7只；再归纳一般二元一次方程组的通用方法，即用高斯消去法解一般的二元一次方程组。令D，若D，方程组无解或有无数多解。若D，则，。由此可得解二元一次方程组的算法。计算；如果，则原方程组无解或有无穷多组解；否则（），，输出计算结果、或者无法求解的信息。二、数学构建：算法的概念：由基本运算及规定的运算顺序所构成的完整的解题步骤，或者是按照要求设计好的有限的计算序列，并且这样的步骤或序列能解决一类问题。算法的五个重要特征：（1）有穷性：一个算法必须保证执行有限步后结束；（2）确切性：算法的每一步必须有确切的定义；（3）可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次即可完成；（4）输入：一个算法有0个或多个输入，以刻划运算对象的初始条件。所谓0个输入是指算法本身定出了初始条件。（5）输出：一个算法有1个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。三、知识运用：例1．一个人带三只狼和三只羚羊过河，只有一条船，同船可以容纳一个人和两只动物。没有人在的时候，如果狼的数量不少于羚羊的数量，狼就会吃掉羚羊。（1）设计过河的算法；（2）思考每一步算法所遵循的相同之处原则是什么。解：算法或步骤如下：S1人带两只狼过河S2人自己返回S3人带一只羚羊过河S4人带两只狼返回S5人带两只羚羊过河S6人自己返回S7人带两只狼过河S8人自己返回带一只狼过河例2．写出一个求有限整数序列中的最大值的算法。解：为了便于理解，算法步骤用自然语言叙述：先将序列中的第一个整数设为最大值；将序列中的下一个整数值与“最大值”比较，如果它大于此“最大值”，这时就假定“最大值”就是这个整数；如果序列中还有其它整数，重复；在序列中一直进行到没有可比的数为止，这时假定的“最大值”就是这个序列中的最大值。试用数学语言写出对任意3个整数中最大值的求法max=a如果b>max，则max=b如果c>max，则max=c,max就是中的最大值。例3．(1)设计一个算法,判断7是否为质数.(2)设计一个算法,判断35是否为质数.(1)根据质数的定义，可以这样判断:用自然语言描述:依次用2～6除7,如果它们中有一个能整除7,则7不是质数,否则7是质数.算法如下:第一步,用2除7,得到余数1,因为余数不为0,所以2不能整除7.第二步,用3除7,得到余数1,因为余数不为0,所以3不能整除7.第三步,用4除7,得到余数3,因为余数不为0,所以4不能整除7.第四步,用5除2,得到余数1,因为余数不为0,所以5不能整除7.第五步,用6除7,得到余数1,因为余数不为0,所以6不能整除7.因此,7是质数.(2)类似地,可写出判断35是否为质数.一般情形：算法分析：对于任意给定一个大于2的整数n，若用i表示2～（n-1）中的任意整数，则“判断n是否为质数”的算法包含这样的思想：首先给定大于2的整数n.然后依次从2至（n-1）检验是不是n的因数，即整除n的数，若有这样的数，则n不是质数；若没有这样的数，则n是质数.具体算法如下：第一步,给定大于2的整数n.第二步,令i=2.第三步,用i除n,得到余数r,判断余数r是否为零,若是,则n不是质数,结束算法;否则,将i的值增加1,仍用i表示.第四步,判断i是否大于(n-1),若是,则n是质数,否则,返回第三步.这是判断一个大于1的整数n是否为质数的最基本算法。例4．用“二分法”设计一个求方程x2–2=0(x>0)的近似解的算法.算法分析：回顾二分法解方程的过程，并假设所求近似根与准确解的差的绝对值不超过，第一步,令f(x)=x2–2,给定精度.因为f(1)<0，f(2)>0，所以设x1=1，x2=2。第二步,令m=(x1+x2)/2，判断f(m)是否为0，若是，则m为所求；若否，则继续判断f(x1)·f(m)大于0还是小于0.第三步,若f(x1)·f(m)>0，则令x1=m；否则，令x2=m.第四步,判断|x1–x2|<是否成立？若是，则x1、x2之间的任意取值均为满足条件的近似根；若否，则返回第二步.根据二分法的思想,则设计出以下算法：第一步,令f(x)=x2–2,给定精度d.第二步,给定区间[a,b],满足f(a)f(b)<0.第三步,取区间中点.第四步,若f(a)f(m)<0,则含零点的区间是[a,m];否则,含零点的区间是[m,b].将新得到的含零点的区间仍记为[a,b].第五步,判断[a,b]的长度是否小于d或f(m)是否等于零.若是,则m是方程的近似解;否则,返回第三步.四、学力发展：1．给出求的一个算法。2．给出求点P关于直线的对称点的一个算法。五、课堂小结：算法的概念：由基本运算及规定的运算顺序所构成的完整的解题步骤，或者是按照要求设计好的有限的计算序列，并且这样的步骤或序列能解决一类问题。算法的五个重要特征：（1）有穷性：一个算法必须保证执行有限步后结束；（2）确切性：算法的每一步必须有确切的定义；（3）可行性：算法原则上