(
课件网) 分治算法 赣科学技术版五年级下册 第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 ... ...
