《算法的最优解》PPT课件.ppt

《《算法的最优解》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法的最优解算法是解决某一类问题的一系列步骤或程序。算法可执行性确定性有限性算法的特点算法的思想程序化思想例1：一位商人有9枚银元，其中有1枚略轻的是假银元。你能用天平（不用砝码）将假银元找出来吗？一、算法的优化问题1.任取2枚银元分别放在天平的两边，如果天平左右不平衡，则轻的一边就是假银元；如果天平平衡则进行第2步。2.取下右边的银元，放在一边，然后把剩余的7枚银元依次放在右边进行称量，直到天平不平衡，偏轻的那一枚就是假银元。（方法一）思考：这种算法需要称量几次？（方法二）2．先将两组分别放在天平的两边。如果天平不平衡，那么假银元就在轻的那一

2、组；如果天平左右平衡，则假银元就在未称的第3组里。3．取出含假银元的那一组，从中任取两枚放在天平的两边。如果左右不平衡，则轻的那一边就是假银元；如果天平两边平衡，则未称的那一枚就是假银元。1.把银元分成3组，每组3枚。思考：这种算法需要称量几次？最优算法一位商人有9枚银元，其中有1枚略轻的是假银元。你能用天平（不用砝码）将假银元找出来吗？变式训练:10三名学生分别写出烧水泡茶喝的算法,请说明谁写的算法更合理.练习一甲:先做好一切准备工作，洗开水壶,洗茶壶、洗茶杯、拿茶叶；一切就绪，灌水烧水；坐待水开了，泡茶喝。乙:洗开水壶,灌上凉水,放在火上；

3、坐待水开；水开了之后洗茶壶、洗茶杯、拿茶叶、泡茶喝。丙:洗开水壶,灌上凉水,放在火上；在等待水开的时候,洗茶壶、洗茶杯、拿茶叶；等水开了，泡茶喝。例2：我国《算经十书》之一《孙子算经》中有这样一个问题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩四，问物至少几何？二、剩余问题的算法三三数只剩二,五五数只剩三,七七数只剩四。1.确定最小的满足除以3余2的正整数：22.依次加3就得到所有除以3余2的正整数：2,5,8,11,14,17,20,23,26，……5.在上列数中找出满足除以7余4的最小正整数：53，这就是我们要求的数4.依次加

4、15就得到所有满足除以3余2和除以5余3的正整数：8,23,38,53，……3.在上列数中确定最小的满足除以5余3的正整数：8思考：颠倒3，5,7的顺序会出现什么样的算法？孙氏剩余定理/中国剩余定理“韩信点兵”练习二韩信点兵时，为了保住军事机密，不让敌人知道自己部队的实力，采用下述点兵方法：先令士兵从1~5报数，结果最后一名士兵报2；再令士兵从1~7报数，结果最后一名士兵报3；最后令士兵从1~9报数，结果最后一名士兵报4；这样韩信就很快算出自己部队士兵的总人数.请设计一个算法求出士兵至少有多少人.