算法的基本思想课件（二） 北师大版必修3.ppt

复习回顾,1.算法的概念,在数学中,算法是解决某一类问题的一系列步骤或程序,只要按照这些步骤执行,都能使问题得到解决.,2.算法的特征,（1）确定性:算法的每一步应该是确定的,能有效地执行且得到确定的结果,而不应当模棱两可.,（2）顺序性与正确性:算法从初始步骤开始,分为若干明确的步骤,前一步是后一步的前提,只有执行完前一步,才能执行下一步,并且每一步都准确无误,才能解决问题.,（3）不唯一性:求解某一个问题的算法不一定是唯一的,对于一个问题可以有不同的解法.,（4）有限性:算法的步骤序列是有限的,一个算法必须能够在执行有限步之后结束,不能无限循环.,3.问题讨论,一个人带着三只狼和三只羊过河,只有一条船,同船可容纳一个人和两支动物,没有人在的时候,如果狼的数量不少于羊的数量狼就会吃羊.该人如何将动物转移过河?请你写出解决问题的步骤.,参考答案,算法步骤:,1.人带两只狼过河,并自己返回.,2.人带一只狼过河,自己返回.,3.人带两只羊过河,并带两只狼返回.,4.人带一只羊过河,自己返回.,5.人带两只狼过河.,1算法的基本思想(2),一、具体算法案例分析,韩信像,例1.“韩信点兵”问题,韩信是汉高祖刘邦手下的大将,他英勇善战,智谋超群,为建立汉朝立下汗马功劳.据说他在点兵的时候,为了保住军事机密,不让敌人知道自己部队的实力,采用下述点兵方法:先令士兵从13报数,结果最后一个士兵报2;再令士兵从15报数,结果最后一个士兵报3;又令士兵从17报数,结果最后一个士兵报4.这样,韩信很快就算出了自己部队士兵的总人数.请设计一个算法,求出士兵至少有多少人.,解,算法步骤如下:,先令士兵从13报数，结果最后一个士兵报2；再令士兵从15报数，结果最后一个士兵报3；又令士兵从17报数，结果最后一个士兵报4.请设计一个算法，求出士兵至少有多少人？,1.首先确定最小的满足除以3余2的正整数：2；,2.依次加3得到所有除以3余2的正整数：2,5,8,11,14,17,20,23,26,29,32,35,38,41,44,47,50,53,56,3.在上列数中确定最小的满足除以5余3的数：8；,4.然后依次加上15，得到：8,23,38,53,5.在第4步得到的一列数中找出满足除以7余4的最小数：53,这就是所求的数.,这5个步骤称为解决“韩信点兵”问题的一个算法.,解法二算法步骤如下：,1.首先确定最小的满足除以7余4的正整数：4；,2.依次加7就得到所有除以7余4的正整数：4,11,18,25,32,39,46,53,60,3.在第2步得到的一列数中确定最小的除以5余3的数：18；,4.然后依次加上35,得到：18,53,88,5.在第4步得到的一列数中找出最小的满足除以3余2的正整数：53.,概括：同一个问题，可能有多种算法.,先令士兵从13报数，结果最后一个士兵报2；再令士兵从15报数，结果最后一个士兵报3；又令士兵从17报数，结果最后一个士兵报4.请设计一个算法，求出士兵至少有多少人？,一位商人有9枚银元,其中有1枚略轻的是假银元,你能用天平（不用砝码）将假银元找出来吗？,解算法步骤如下：,1.任取2枚银元分分别放在天平的两边.如果天平左右不平衡,则轻的一边就是假银圆;如果天平平衡,则进行第2步.,2.取下右边的银圆,放在一边,然后把剩余的7枚银圆依次放在右边进行称量,直到天平不平衡,偏轻的那一枚就是假银圆.,例2.“真假银元”问题,思考:这种算法最少要称_次,最多要称_次.,1,7,一位商人有9枚银元,其中有1枚略轻的是假银元,你能用天平（不用砝码）将假银元找出来吗？,解算法步骤如下：,1.将银元分成3组，每组3枚；,2.先将两组分别放在天平的两边,如果天平不平衡,那么假银元就在轻的那一组;如果天平左右平衡,则假银元就在未称的那一组；,3.取出含假银元的那一组,从中任取两枚银元放在天平的两边,如果左右不平衡,则轻的那一边是假银元;如果天平两边平衡,则未称的那一枚是假银元.,概括:算法有优劣之分,在实际问题中,找出好的算法是一项重要的工作.,例2.“真假银元”问题,思考:这种算法只要称_次.,2,2.二分法求方程f(x)=0的近似解的基本思想是：将方程的有解区间平分为两个小区间,然后判断解在哪个小区间;继续把有解的区间平分并进行判断,直到求出满足精度要求的近似解.,二、最优策略-二分法,1.当且仅当_方程f(x)=0在区间a,b上有解x=x0,其算法步骤如下（要求近似解精确到10-n):,1.确定有解区间a,b(f(a)f(b)0).,2.取a,b的中点.,3.计算函数f(x)在中点处的函数值.,4.判断函数值是否为零：,（1）若为0,就是方程的解,问题就得到解决；,（2）若不为0,则分下列两种情形：,若,则确定新的有解区间为;,若,则确定新的有解区间为.,5.判断新的有解区间的长度是否大于精度：,（1）若新的有解区间长度大于精度,则在新的有解区间的基础上重复上述步骤;,（2）如果新的有解区间长度小于或等于精度,则这个有解区间中的任意一个数均为方程的满足精度的近似值.,例3.求方程在0,1上的近似解,精到0.1.,解算法步骤如下：,1.因为f(0)=-1,f(1)=1,f(0)f(1)0,则区间0,1为有解区间;,2.取0,1的区间中点0.5;,3.计算f(0.5)=-0.625;,4.由于f(0.5)f(1)0,可得新的有解区间0.5,1,5.取0.5,1的区间中点0.75;,6.计算f(0.75)=-0.015625;,7.因为f(0.75)f(1)0,可得新的有解区间0.75,1,8.取0.75,1的区间中点0.875;,9.计算f(0.875)=0.435546875;,10.因为f(0.75)f(0.875)0,可得新的有解区间0.75,0.875,11.取0.75,0.875的区间中点0.8125;,12.计算f(0.8125)=0.196533203125;,13.因为f(0.75)f(0.8125)0,可得新的有解区间0.75,0.8125,区间0.75,0.8125中的任一数值,都可以作为方程的近似解.,0.8125-0.75=0.06250.1,设,三、课堂练习,1.有一盒围棋子,5个5个地数,最后余下两个;7个7个地数,最后余下3个;9个9个地数,最后余下4个.请设计一种算法,求出这把棋子至少有多少个.,2.一个大油瓶装8kg油.还有两个空油瓶,一个能装5kg油,另一个能装3kg油.请设计一种算