(共34张PPT)
高效的策略
川教版
八年级上
新知导入
A
C
B
D
10km
16km
18km
13km
15km
9km
大家还记得上节课我们学习的“快递员派送”的6种策略中，我们得出方案走ABCDA是距离最短的，称它是最有效的策略
复
习
旧
知
引入新知
欢欢的学校开运动会，运动会结束了，需要给前三名的同学发奖，但是乐乐不知道怎样来发这些奖品，想让乐乐帮助他分析一下奖品该怎样发合适，乐乐非常乐意帮助欢欢来发奖品，下面我们就来看看他们是怎样发奖品的？
分“奖品”问题
学校开运动会需要给获得前三名的同学颁奖，奖品总数是17个，第一名应得总数的1/2，第二名得总数的1/3，第三名得总数的1/9。请问：这17个奖品应该如何分给第一、二、三名的同学？请同学们帮老师分一下奖品。
新知讲解
分“奖品”问题
欢欢的分法:
第一名的奖品数量=17×1/2
=
8.5个
第二名的奖品数量=17×1/3
=
5.66……个
第三名的奖品数量=17×1/9
=
1.88……个
这种分法会将奖品拆分为小数个，显然不够合理。
新知讲解
乐乐的分法：
第一、二、三名的奖品数比例为:
1/2:
1/3:
1/9，将比例换算为整数，则比例为9:6:2，奖品总数恰好17个，所以第一名应得9个，第二名应得6个，第三名应得2个。
分“奖品”问题
新知讲解
分“奖品”问题
结论
欢欢和乐乐的两种策略计算方法不同，所以导致了得出不同的结果。从整体来看，第二种方法更加合理。如果策略可以完成分配，则为有效策略，如果不能完成任务，则需要更换策略。
新知讲解
1.整理出乐乐策略的伪代码。
2.还有其他分配策略吗?
（比如：从外面借一个奖品来，将奖品总数变成18个，再分。分完后会剩一个，再还回去)
任
务
一
合作探究
如果第一名得总奖品数的1/2，第二名得总奖品数的1/3，第三名得总奖品数的1/5，奖品总数为31个时，请问前三名每人应该分到多少个奖品?
拓
展
延
伸
新知讲解
1/2:1/3:1/5
=
15:10:6
奖品一共31个，
恰好第一名15个奖品，
第二名10个奖品，
第三名6个奖品
拓
展
延
伸
计算结果
新知讲解
最有效的策略
通常定义为不牺牲任何总目标和各分目标的条件下，技术上能够达到的最好的解。在选择策略时，通常人们会选择“最优解”，能用简单的办法合理分配的策略即为“最优解”。乐乐的策略够合理分配奖品，也即为“最优解”
新知讲解
最有效的策略
报数游戏
游戏规则：轮流报数，从1开始报，每次可报1到3个数，不能不报数，先报出20的玩家获胜。
欢欢和乐乐为了熟悉规则，尝试了一次游戏。
1，2，3
4，5
6，7，8
（8是4的2倍）
9
10，11，12
（12是4的3倍）
13，14，15
16
（16是4的4倍）
17，18，19
20
（20是4的5倍）
新知讲解
最有效的策略
乐乐发现如果能报到16，则一定能获胜。
20÷（1+3）=5，整除没有余数，不管先报的人报什么数，后报的人只要报的数和先报的数加起来等于4或4的倍数即可，这样报完4轮后所报数的和累积起来一定为16。
之后无论先报的人报什么，都是后报的人先报出20，后报的人一定能获胜。
策略可以简化为：只要第一个抢到4，并在每一轮抢到4的倍数的人，就能必胜。
乐乐也想要取得游戏的胜利，他仔细分析了策略:
新知讲解
最有效的策略
Begin(算法开始)
定义乐乐第i轮报数Ai
for
i
in
range(4):
if
Ai%4=0:
则乐乐获胜
break
else:
则欢欢获胜
End(算法结束)
乐
乐
整
理
出
策
略
的
伪
代码
新知讲解
两人轮流报数，每次可报1到4个数，不能不报数，先报出41的人获胜。仔细思考是否存在必胜策略，并写出策略的伪代码。
任
务
二
分析：(41-1)÷(1+4)
=8，先报数的人第一次只报一个数，后续不管后报数的人报几个数，先报数的人只要保证自己报的最后一个数是“5的倍数加1”即可获胜。
合作探究
打破常规的思维
解决现实生活中的问题，如果要求使用“最优解”，则往往需要我们打破常规的思维方式，去思考“最优”的方法。
实例：有7袋玻璃球（每个袋中玻璃球的数量若干），其中6袋中，每粒玻璃球重1克，有1袋中玻璃球是每粒重2克。所有玻璃球外观与大小完全一样，天平至少要称几次，才能保证找出是哪袋玻璃球（异常袋）与其他6袋不一样?
新知讲解
从7袋中每袋分别取出1粒，然后放到天平上去称，天平另一端放1克重的砝码，如此，最多称6次，就能找出“异常袋”。
打破常规的思维
欢欢的分法：
新知讲解
在天平左右两边各放1粒，如果重量相等，则另换两粒称。如此，最多只需称3次，就能找出“异常袋”。
打破常规的思维
乐乐的分法：
新知讲解
欢欢改进了乐乐的方法：同时在天平左右两边各放3粒，如果相等，则剩下的那粒来自“异常袋”；若不相等，则将重的那3粒中，任取2粒放在天平左右两边称。如此，只需称2次，就能找出“异常袋”。
打破常规的思维
欢欢的改进方法：
新知讲解
打破常规的思维
最优解
步骤一：给袋子编号
先对7个袋子进行编号，如右图所示。
步骤二：从袋子中取出玻璃球
根据袋子的编号，是几号，就取出几粒玻璃球，如右图所示。
步骤三：用天平称玻璃球总重量
如果取出来的28粒玻璃球都是1克重，那总重量就应该是28克。显然，称出来的重量肯定是大于28克的。只称1次，称出总重量，就能知道哪个袋子是“异常袋
新知讲解
任
务
二
请大家整理最优解思路，填写下表
如果
那么
克
编号1的袋子异常
总重量将是：
29
编号2的袋子异常
编号3的袋子异常
编号4的袋子异常
编号5的袋子异常
编号6的袋子异常
编号7的袋子异常
合作探究
简化问题归纳出“最优解”
“取玻璃球”的游戏
游戏的规则如下：
有A、B、C共3袋玻璃球。A袋中有1粒玻璃球，B袋2粒，C袋3粒。找两位同学轮流从3个袋子中取出玻璃球。每人每次只能选出其中1袋，从这袋中取任意粒（比如C袋中可取1、2或3粒）玻璃球，谁取出所有袋中最后那粒，或谁取最后一次，谁就获胜。
简化问题归纳出“最优解”
①如果A、B、C这3袋只剩1袋存在玻璃球，则谁先取，他就会一次将这袋全取光，所以：谁先取，谁必胜;
欢欢对这个游戏的分析:
②如果有任意2袋存在玻璃球，并且2袋中都只剩1粒球，结果：谁先取，谁必输;
③如果有2袋，其中1袋剩1粒，另1袋剩2粒，则先取的人必胜。因为他只需要取走2粒中的1粒，剩下就是上面编号2的情况，轮到对方先，对方输;
④如果有2袋，其中1袋剩1粒，另1袋剩3粒，则先取的人必胜。因为他只需要取走3粒中的2粒，剩下就是上面编号2的情况，轮到对方先，对方输;
⑤如果有2袋，每袋都是2粒，则先取的人必输。他若取走1粒，剩下的就是上面编号3的情况，对方先取，对方胜：他若取走某袋中的2粒，则对方取光剩下那袋，也是对方胜;
新知讲解
简化问题归纳出“最优解”
⑥如果有2袋，1袋是2粒，另1袋3粒，则先取的人必胜。先取的人只需从3粒中取走1粒，剩下的就是上面编号5的情况，轮到对方先，对方输;
⑦如果有3袋，且3袋中都剩1粒，则谁先取，谁必胜;
⑧如果有3袋，3袋中有2袋剩1粒，另1袋剩2粒，则谁先取，只需直接取光2粒那袋，剩下就是上面编号2的情况，轮到对方先，对方输;
⑨如果有3袋，3袋中有1袋剩1粒，另2袋均剩2粒，则谁先取，只需直接取走1粒那袋，剩下就是上面编号5的情况，轮到对方先，对方输;
⑩如果有3袋，3袋中有2袋剩1粒，另1袋剩3粒，则谁先取，只需直接取光3粒那袋，剩下就是上面编号2的情况，轮到对方先，对方输。
新知讲解
简化问题归纳出“最优解”
现在我们可以回到最初的游戏，A袋中有1粒玻璃球，B袋2粒，C袋3粒，则谁先取谁必输。先取的策略只有以下几种:
若从C袋中取走1粒，就成了上面编号9的情况；
若从C袋中取走2粒，就成了上面编号8的情况；
若将C袋全取走，则是上面编号3的情况；
若从B袋中取走1粒，就成了上面编号10的情况；
若将B袋2粒全取走，就成了上面编号4的情况；
若将A袋取光，就成了上面编号6的情况。
综合所有情况，后取的人只要不出错，则后取必胜。也就是说，后取的人有“必胜策略”，“必胜策略”就是后取的“最优解”。
新知讲解
还是“取玻璃球”的游戏，若有A、B、C、D
4袋玻璃球，D袋中有4个玻璃球，其他袋与之前相同。
请问：该问题的最优解，先取者是输还是赢?
拓
展
练
习
温馨提示：直接将D袋取光，剩下的就还原为上面的游戏，且轮到对方先取。
新知讲解
拓
展
阅
读
是一类模拟自然生物进化或者群体社会行为的随机搜索方法的统称。由于这些算法求解时不依赖于梯度信息，故其应用范围较广,特别适用于传统方法难以解决的大规模复杂优化问题。
主要算法有：遗传算法、人工神经网络、蚁群算法、蛙跳算法、粒子群优化算法等。这些算法均是模仿生物进化、神经网络系统、蚂蚁寻路、鸟群觅食等生物行为。
仿生算法
新知讲解
较强的并行性、搜索较优解能力强
拓
展
阅
读
蚁群系统
1996年
Gambardella和Dorigo
提出时间
特
点
提出者
新知讲解
蚂蚁在前进的过程中，对所经过的路径留下了一种挥发性分泌物一信息素。这种物质的存在及其强度能够在蚂蚁在觅食过程中被感知，并指导蚂蚁下一步运动方向。即在待选择路径上，蚂蚁选择移动的方向总是朝着高浓度的信息素所对应的路径，即路径上的信息素强度越高，就会有越多的蚂蚁去选择它，而这样会使得该路径上留下的信息素变得更为强大，从而吸引更多的蚂蚁，这是信息素的一种正反馈形式。通过信息素的正反馈，蚂蚁最终可以寻找到最佳行动路径。
蚁群系统
新知讲解
“取玻璃球”的游戏，若有A、B、C、D
、E
5袋玻璃球，E袋中有5个玻璃球，其他袋与之前相同。
请问：该问题的最优解，先取者是输还是赢?
课堂练习
课堂总结
总结本节课内容
板书设计
高效的策略
“分奖品”的问题
最有效的策略
简化问题归纳出“最优解”
打破常规的思维
https://www.21cnjy.com/help/help_extract.php中小学教育资源及组卷应用平台
川教版信息技术八年级上册《高效的策略》教学设计
课题
高效的策略
单元
第三单元
学科
信息技术
年级
八年级
学习目标
了解策略的效率理解“最优解”的概念
重点
理解“最优解”的概念
难点
理解“最优解”的概念
教学过程
教学环节
教师活动
学生活动
设计意图
导入新课
复习上节所讲的“快递员派送”策略，找出最短送货路线，这就是最有效的策略。这节课欢欢有遇到了一个问题：学校运动会需要给前三名的同学发奖，想让乐乐帮助他分析一下奖品该怎样发合适。这就是我们这节课要学习的“高效的策略”
复习旧知，以学生回答问题为主
温故知新，尝试运用多种方法解决实际生活中的问题
讲授新课
一
“分奖品”的问题学校开运动会需要给获得前三名的同学颁奖，奖品总数是17个，第一名应得总数的1/2，第二名得总数的1/3，第三名得总数的1/9。请问：这17个奖品应该如何分给第一、二、三名的同学？请同学们帮老师分一下奖品。欢欢的分法:第一名的奖品数量=17×1/2
=
8.5个第二名的奖品数量=17×1/3
=
5.66……个第三名的奖品数量=17×1/9
=
1.88……个这种分法会将奖品拆分为小数个，显然不够合理。乐乐经过思考，明白了问题所在，他提出了另外一种分奖品策略。乐乐的分法：二、三名的奖品数比例为:
1/2:
1/3:
1/9，将比例换算为整数，则比例为9:6:2，奖品总数恰好17个，所以第一名应得9个，第二名应得6个，第三名应得2个。两种策略计算方法不同，导致了不同的结果。从整体来看，第二种方法更加合理。如果策略可以完成分配，则为有效策略，如果不能完成任务，则需要更换策略。任务一1.整理出策略二的伪代码。2.还有其他分配策略吗?（比如：从外面借一个奖品来，将奖品总数变成18个，再分。分完后会剩一个，再还回去)拓展:如果第一名得总奖品数的1/2，第二名得总奖品数的1/3，第三名得总奖品数的1/5，奖品总数为31个时，请问前三名每人应该分到多少个奖品?1/2:1/3:1/5
=
15:10:6奖品一共31个，恰好第一名15个奖品，第二名10个奖品，第三名6个奖品二
最有效的策略在选择策略时，通常人们会选择“最优解”，能用简单的办法合理分配的策略即为“最优解”。上文中的策略二能够合理分配奖品，也即为“最优解”欢欢和乐乐解决两人了“分奖品”问题后，又玩起了“报数游戏”。游戏规则：轮流报数，从1开始报，每次可报1到3个数，不能不报数，先报出20的玩家获胜。欢欢和乐乐为了熟悉规则，尝试了一次游戏。游戏过程如下:欢欢先报1，2，3乐乐报4，5欢欢报6，7，8
（8是4的2倍）乐乐报9欢欢报10，11，12
（12是4的3倍）乐乐报
13，14，15欢欢报
16
（16是4的4倍）乐乐报
17，18，19欢欢报
20
（20是4的5倍）欢欢取得了胜利乐乐想要取得游戏的胜利，仔细分析了策略:乐乐发现如果能报到16，则一定能获胜。20÷（1+3）=5，整除没有余数，不管先报的人报什么数，后报的人只要报的数和先报的数加起来等于4或4的倍数即可，这样报完4轮后所报数的和累积起来一定为16。之后无论先报的人报什么，都是后报的人先报出20，后报的人一定能获胜。策略可以简化为：只要第一个抢到4，并在每一轮抢到4的倍数的人，就能必胜。乐乐整理出策略的伪代码:Begin(算法开始)定义乐乐第i轮报数Aifor
i
in
range(4):
if
Ai%4=0:
则乐乐获胜
break
else:
则欢欢获胜End(算法结束)任务二两人轮流报数，每次可报1到4个数，不能不报数，先报出41的人获胜。仔细思考是否存在必胜策略，并写出策略的伪代码。总结：(41-1)÷(1+4)
=8，先报数的人第一次只报一个数，后续不管后报数的人报几个数，先报数的人只要保证自己报的最后一个数是“5的倍数加1”即可获胜。两次报数游戏均有必胜策略，这种必胜策略实际上就是“最优解”。其实很多游戏都存有必胜策略。三、打破常规的思维解决现实生活中的问题，如果要求使用“最优解”，则往往需要我们打破常规的思维方式，去思考“最优”的方法。比如下面这个问题:有7袋玻璃球（每个袋中玻璃球的数量若干），其中6袋中，每粒玻璃球重1克，有1袋中玻璃球是每粒重2克。所有玻璃球外观与大小完全一样，天平至少要称几次，才能保证找出是哪袋玻璃球（异常袋）与其他6袋不一样?欢欢说：这个问题，我先从“最笨”的方法开始。从7袋中每袋分别取出1粒，然后放到天平上去称，天平另一端放1克重的砝码，如此，最多称6次，就能找出“异常袋”。乐乐说：欢欢同学，我觉得没有必要逐个称量，可以在天平左右两边各放1粒，如果重量相等，则另换两粒称。如此，最多只需称3次，就能找出“异常袋”。欢欢说：乐乐同学，我在你这个方法的基础上，再改进一下：同时在天平左右两边各放3粒，如果相等，则剩下的那粒来自“异常袋”；若不相等，则将重的那3粒中，任取2粒放在天平左右两边称。如此，只需称2次，就能找出“异常袋”。以上思路，都是常规思路，如果要求只称1次就找出“异常袋”，那我们就必须找到“最优解”。师说：两位同学，你们上面提到的策略都能解决这个问题，所以你们的策略都是“有效策略”。你们这些策略中的“最优解”需要称2次才能找出“异常袋”。如果我们换一种思路的话，只称1次就可找出“异常袋”。方法如下:步骤一：给袋子编号先对7个袋子进行编号，如下图所示。步骤二：从袋子中取出玻璃球根据袋子的编号，是几号，就取出几粒玻璃球，如下图所示。步骤三：用天平称玻璃球总重量如果取出来的28粒玻璃球都是1克重，那总重量就应该是28克。显然，称出来的重量肯定是大于28克的。只称1次，称出总重量，就能知道哪个袋子是“异常袋”。任务三请大家整理最优解思路，填写下表。如果那么克编号1的袋子异常总重量将是29编号2的袋子异常编号3的袋子异常编号4的袋子异常编号5的袋子异常编号6的袋子异常编号7的袋子异常欢欢说：只称1次就能找出“异常袋”，这个策略真妙啊！我感受到“策略”的力量啦！看来只有提升我们的思维能力，才能在遇到问题时，找到真正的“最优解”。四、简化问题归纳出“最优解”有时候我们会遇到一些复杂的问题，为了解决这样的问题，我们可以对问题进行“简化”，然后根据简化后的结果，逐渐找出原问题的“最优解”。下面我们来玩一个“取玻璃球”的游戏吧。游戏的规则如下：有A、B、C共3袋玻璃球。A袋中有1粒玻璃球，B袋2粒，C袋3粒。找两位同学轮流从3个袋子中取出玻璃球。每人每次只能选出其中1袋，从这袋中取任意粒（比如C袋中可取1、2或3粒）玻璃球，谁取出所有袋中最后那粒，或谁取最后一次，谁就获胜。乐乐说：这个游戏会有“最优解”吗？看起来好难啊！老师说：我们要学会对困难的问题进行简化。欢欢说：老师，我来试试简化这个游戏。以下是欢欢对这个游戏的简化:①如果A、B、C这3袋只剩1袋存在玻璃球，则谁先取，他就会一次将这袋全取光，所以：谁先取，谁必胜;②如果有任意2袋存在玻璃球，并且2袋中都只剩1粒球，结果：谁先取，谁必输;③如果有2袋，其中1袋剩1粒，另1袋剩2粒，则先取的人必胜。因为他只需要取走2粒中的1粒，剩下就是上面编号2的情况，轮到对方先，对方输;④如果有2袋，其中1袋剩1粒，另1袋剩3粒，则先取的人必胜。因为他只需要取走3粒中的2粒，剩下就是上面编号2的情况，轮到对方先，对方输;⑤如果有2袋，每袋都是2粒，则先取的人必输。他若取走1粒，剩下的就是上面编号3的情况，对方先取，对方胜：他若取走某袋中的2粒，则对方取光剩下那袋，也是对方胜;⑥如果有2袋，1袋是2粒，另1袋3粒，则先取的人必胜。先取的人只需从3粒中取走1粒，剩下的就是上面编号5的情况，轮到对方先，对方输;⑦如果有3袋，且3袋中都剩1粒，则谁先取，谁必胜;⑧如果有3袋，3袋中有2袋剩1粒，另1袋剩2粒，则谁先取，只需直接取光2粒那袋，剩下就是上面编号2的情况，轮到对方先，对方输;⑨如果有3袋，3袋中有1袋剩1粒，另2袋均剩2粒，则谁先取，只需直接取走1粒那袋，剩下就是上面编号5的情况，轮到对方先，对方输;⑩如果有3袋，3袋中有2袋剩1粒，另1袋剩3粒，则谁先取，只需直接取光3粒那袋，剩下就是上面编号2的情况，轮到对方先，对方输。现在我们可以回到最初的游戏，A袋中有1粒玻璃球，B袋2粒，C袋3粒，则谁先取谁必输。先取的策略只有以下几种:若从C袋中取走1粒，就成了上面编号9的情况；若从C袋中取走2粒，就成了上面编号8的情况；若将C袋全取走，则是上面编号3的情况；若从B袋中取走1粒，就成了上面编号10的情况；若将B袋2粒全取走，就成了上面编号4的情况；若将A袋取光，就成了上面编号6的情况。欢欢说：综合所有情况，后取的人只要不出错，则后取必胜。也就是说，后取的人有“必胜策略”，“必胜策略”就是后取的“最优解”。老师说：对。类似像这样的问题，看起来很复杂，但我们可以将其简化，然后逐步推导其结果，从而最终找到这种复杂问题的“最优解”。乐乐说：这个游戏真有意思！用“简化问题”的方法来解决问题，也就是一种解决问题的“策略”。谢谢老师，我学会啦。拓展练习:还是“取玻璃球”的游戏，若有A、B、C、D4袋玻璃球，D袋中有4个玻璃球，其他袋与之前相同。请问：该问题的最优解，先取者是输还是赢?答案很简单：直接将D袋取光，剩下的就还原为上面的游戏，且轮到对方先取。拓展阅读：仿生算法：是一类模拟自然生物进化或者群体社会行为的随机搜索方法的统称.由于这些算法求解时不依赖于梯度信息,故其应用范围较广,特别适用于传统方法难以解决的大规模复杂优化问题.主要有：遗传算法、人工神经网络、蚁群算法、蛙跳算法、粒子群优化算法等.这些算法均是模仿生物进化、神经网络系统、蚂蚁寻路、鸟群觅食等生物行为.故叫仿生算法.蚁群系统提出时间：1996年提出者：Gambardella和Dorigo特????点：较强的并行性、搜索较优解能力强概述：蚂蚁在前进的过程中，对所经过的路径留下了一种挥发性分泌物一信息素。这种物质的存在及其强度能够在蚂蚁在觅食过程中被感知，并指导蚂蚁下一步运动方向。即在待选择路径上，蚂蚁选择移动的方向总是朝着高浓度的信息素所对应的路径，即路径上的信息素强度越高，就会有越多的蚂蚁去选择它，而这样会使得该路径上留下的信息素变得更为强大，从而吸引更多的蚂蚁，这是信息素的一种正反馈形式。通过信息素的正反馈，蚂蚁最终可以寻找到最佳行动路径。课堂练习“取玻璃球”的游戏，若有A、B、C、D
、E
5袋玻璃球，E袋中有5个玻璃球，其他袋与之前相同。请问：该问题的最优解，先取者是输还是赢?
仔细读题，认真分析
利用上节课所学知识写伪代码和欢欢、乐乐一起玩“报数游戏”小组合作，共同完成和欢欢、乐乐一起玩“找异常袋”游戏小组合作完成和欢欢、乐乐一起玩“去玻璃球”游戏增加一个袋子完成练习
动脑筋思考问题类比找出最优解实践应用，多想方法在游戏中掌握知识增加团队合作精神通过游戏知道“最优解”，开动脑筋，拓展思路集思广益，共同完成，时间短效果好简化问题找出“最优解”巩固所学，拓展思维，找出“最优解”
课堂小结
总结本节课所讲内容
以学生复述为主，老师补充
梳理本节课的知识点，完成学习目标，培养学生总结概况能力，拓展思维能力
板书
“分奖品”的问题
最有效的策略
高效的策略
打破常规的思维
简化问题归纳出“最优解”
21世纪教育网
www.21cnjy.com
精品试卷·第
2
页
（共
2
页）
HYPERLINK
"http://www.21cnjy.com/"
21世纪教育网(www.21cnjy.com)
