1.1算法案例分析.ppt

1、算 法,计算方法,做蛋挞,例1：要把大象装冰箱，总共分几步？,问题情境,S1：打开冰箱门,S2：把大象放入冰箱,S3：关上冰箱门,把物体A放入冰箱,算法：把物体装冰箱,例2：猜商品价格：在电视台的某个娱乐节目中，要求参与者快速猜出物品价格。主持人出示某件物品，参与者每次估算出一个价格，主持人只能回答高了，低了或者正确。,在某次节目中，主持人出示了一台价值1000以内的随声听，并开始了竞猜。下面是主持人与参与者的一段对话：,参与者：800元！ 主持人：高了！ 参与者：400元！ 主持人：低了！,如果你是参与者，你接下来会怎么猜？,问题情境,560元,S1：报出首次价格：T1；,S2：根据主持人回

2、答确定价格区间： （1）若报价小于商品价格，则商品的价格区间为（T1，1000）； （2）若报价大于商品价格，则商品的价格区间为（0，T1）； （3）若报价等于商品价格，则游戏结束。,S3：如果游戏没有结束，则报出上面确定的价格区间的中点：T2。,算法：猜商品价格,一般地，对一个问题的算法就是解决该问题的程序步骤的概要说明，它有以下三个基本特征：,（1）确定性,（2）有效性,（3）有限性,各步骤的本质与次序被明确清楚的加以说明,按此程序步骤最后必然能得到这一问题正确的解,该程序在有限步以后停止,数学应用,例3：给出求1+2+3+4+5的一个算法。,算法1：累加法,S2：将第一步得到的结果3与3

3、相加得到6；,S3：将第二步得到的结果6与4相加得到10；,S4：将第三步得到的结果10与5相加得到15。,S1：计算1+2，得到3；,S1：取n=5；,S2：计算 ，得到15；,算法2：公式法,算法：自然数求和,数学应用,例4：设计一个算法，判断7是否为素数。,S1：用2除7，得到余数1，所以2不能整除7；,S2：用3除7，得到余数1，所以3不能整除7；,S3：用4除7，得到余数3，所以4不能整除7；,S4：用5除7，得到余数2，所以5不能整除7；,只能被1和自身整除的大于1的整数,S5：用6除7，得到余数1，所以6不能整除7。,设计一个算法，判断整数n(n2)是否为素数。,算法：判断某整数

4、是否为素数,素数表,S1：取正整数n；,S2：查表判断n是否为素数；,算法：判断某整数是否为素数,程序包,分析：从最小的素因数开始，依次分解，直至不能分解为止,(4000以内的素数表见附录1，详见课本P163),数学应用,例5：在给定素数表的前提下，设计算法，将936分解成素因数的乘积。,S1：查表判断936是否为素数： （1）如果936是素数，则分解结束； （2）如果936不是素数，则进行第二步。,S2：确定936的最小素因数：2，则936=2468。,S3：查表判断468是否为素数： （1）如果468是素数，则分解结束； （2）如果468不是素数，则重复上述步骤，确定 468的最小素因数。,算法：对自然数进行素因数分解,反思回顾,1、算法的含义：,2、算法的特点：,3、算法的思想：,解决某类问题的程序步骤；,确定性，有效性，有限性；,程序化思想。,课后作业,2、设计一个算法，求1356与2400的最小公倍数。,3、一个问题通常有许多种算法，在解决问题的同时，我们追求的是哪种算法更好，更有