资源简介

(共15张PPT)
分治算法
赣科学技术版五年级下册
第4课
分治算法
理解分治算法的基本思想，
掌握分治算法的求解过程，
能运用分治算法解决实际学习与生活中的问题。
任务卡
现有一个棋盘，它由4×4的方格组成，其中，恰好有一个方格和其他方格不同，如图所示，图中红色小方格被称为特殊方格， 而这个棋盘被称为特殊棋盘。同时，还有四种不同形态的L 型骨牌，如图所示。 游戏规则是，将L型骨牌覆盖于棋盘的方格之上，但不可以覆盖特殊方格，且两个L 型骨牌之间不能重叠覆盖。
一
说一说
拼图游戏里的特殊棋盘
拼图游戏里的 L型骨牌
怎么样才能用骨牌把所有的格子都覆盖满呢 试着完成这个游戏。
比一比：你的结果和小蓝的操作一样吗
一
说一说
小蓝的拼图结果
一
说一说
按照循环结构的思想，小红将找钥匙的过程，简化成了一个循环模型，如图。
小红的循环示意图画的和你的一样吗
二
想一想
你还记得刚刚是怎么样将拼图完成的吗 如果将特殊方格的位置更改，你还能够将 拼图完成吗 和同学们一起试试看。
二
想一想
除了使用一张张骨牌对拼图进行尝试，我们还可以用另一种想法，来尝试完成这个拼图游戏。我们可以将4×4的棋盘，分割开来，看作是由4个相同的2×2的“小棋盘”组成的“大棋盘”,如图所示。
此时，特殊方格必然只存在于4个“小棋盘”当中的1个“小棋盘”,而其余3个“小棋 盘”中则没有特殊方格，4个“小棋盘”不完全相同了。
如果我们将一个L 型骨牌覆盖在3个“小棋盘”的会合之处，则可以将4个“小棋 盘”再次变成相同的棋盘，然后尝试使用L 型骨牌来分别填满4个“小棋盘”,如图所示。
二
想一想
我们只需要将 L 型骨牌，放进每个“小棋盘”的空白方格处，就可以将整个棋盘填满了
分治算法就是将一个规模较大的问题分解为几个小问题，这些小 问题之间相互独立、但又与原问题性质相同，再对小问题进行分别求解，就可以最终得到 大问题的答案了。
因此，分治算法的求解过程就是
(1)分解：将原问题分解或几个规模较小的问题，此时要注意小问题中的条件、性质 需与原问题保持一致。
(2)求解：对于每个小问题进行求解，得到小问题的答案。
(3)合并：将所有小问题合并起来，作为原问题的答案。
什么是分治算法
三
想一想
结合先前所学过的递归算法，你认为分治算法和递归算法之间有什么关联性吗 你 可以尝试为棋盘游戏画出程序结构图吗
如果将棋盘游戏之中的棋盘大小变为8×8,其他条件不改 变，你是否能够用L 型骨牌将棋盘填满呢 如果棋盘的大小是16×16呢 快来做一下，看看谁做得又快又正确。
练一练
谢谢聆听！
谢谢
21世纪教育网（www.21cnjy.com)
中小学教育资源网站
兼职招聘：
https://www.21cnjy.com/recruitment/home/admin

展开更多......

收起↑