《《算法的最优解》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《算法的最优解》PPT课件.ppt（10页珍藏版）》请在三一办公上搜索。
1、算法的最优解,算法是解决某一类问题的一系列步骤或程序。,算法,可执行性,确定性,有限性,算法的特点,算法的思想,程序化思想,例1：一位商人有9枚银元，其中有1枚略轻的是假银元。你能用天平（不用砝码）将假银元找出来吗？,一、算法的优化问题,1.任取2枚银元分别放在天平的两边，如果天平左右不平衡，则轻的一边就是假银元；如果天平平衡则进行第2步。,2.取下右边的银元，放在一边，然后把剩余的7枚银元依次放在右边进行称量，直到天平不平衡，偏轻的那一枚就是假银元。,（方法一）,思考：这种算法需要称量几次？,（方法二）,2先将两组分别放在天平的两边。如果天平不平衡，那么假银元就在轻的那一组；如果天平左右平衡
2、，则假银元就在未称的第3组里。,3取出含假银元的那一组，从中任取两枚放在天平的两边。如果左右不平衡，则轻的那一边就是假银元；如果天平两边平衡，则未称的那一枚就是假银元。,1.把银元分成3组，每组3枚。,思考：这种算法需要称量几次？,最优算法,一位商人有9枚银元，其中有1枚略轻的是假银元。你能用天平（不用砝码）将假银元找出来吗？,变式训练:,10,三名学生分别写出烧水泡茶喝的算法,请说明谁写的算法更合理.,练习一,甲:先做好一切准备工作，洗开水壶,洗茶壶、洗茶杯、拿茶叶；一切就绪，灌水烧水；坐待水开了，泡茶喝。,乙:洗开水壶,灌上凉水,放在火上；坐待水开；水开了之后洗茶壶、洗茶杯、拿茶叶、泡茶喝
3、。,丙:洗开水壶,灌上凉水,放在火上；在等待水开的时候,洗茶壶、洗茶杯、拿茶叶；等水开了，泡茶喝。,例2：我国算经十书之一孙子算经中有这样一个问题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩四，问物至少几何？,二、剩余问题的算法,三三数只剩二,五五数只剩三,七七数只剩四。,1.确定最小的满足除以3余2的正整数：2,2.依次加3就得到所有除以3余2的正整数：2,5,8,11,14,17,20,23,26，,5.在上列数中找出满足除以7余4的最小正整数：53，这就是我们要求的数,4.依次加15就得到所有满足除以3余2和除以 5余3的正整数：8,23,38,53，,3.在上列数中确定最小的满足除以5余3的 正整数：8,思考：颠倒3，5,7的顺序会出现什么样的算法？,孙氏剩余定理/中国剩余定理,“韩信点兵”,练习二,韩信点兵时，为了保住军事机密，不让敌人知道自己部队的实力，采用下述点兵方法：先令士兵从15报数，结果最后一名士兵报2；再令士兵从17报数，结果最后一名士兵报3；最后令士兵从19报数，结果最后一名士兵报4；这样韩信就很快算出自己部队士兵的总人数.请设计一个算法求出士兵至少有多少人.,
