《第3课 分治算法》课件.pptx

第3课分治算法五年级下册

理解分治算法的基本思想。掌握分治算法的求解过程。能运用分治算法解决实际学习与生活中的问题。学习目标

情境导入现有一个棋盘，它由4×4的方格组成，其中，恰好有一个方格和其他方格不同，如图所示，图中红色小方格被称为特殊方格，而这个棋盘被称为特殊棋盘。拼图游戏里的特殊棋盘

情境导入同时，还有四种不同形态的L型骨牌，如图所示。游戏规则是，将L型骨牌覆盖于棋盘的方格之上，但不可以覆盖特殊方格，且两个L型骨牌之间不能重叠覆盖。拼图游戏里的L型骨牌怎么样才能用骨牌把所有的格子都覆盖满呢？试着完成这个游戏。

情境导入比一比：你的结果和小蓝的操作一样吗？小蓝的拼图结果

01分治算法的设计实例

分治算法的设计实例你还记得刚刚是怎么样将拼图完成的吗？如果将特殊方格的位置更改，你还能够将拼图完成吗？和同学们一起试试看。你能想出一个拼图思路，适用于解决任意方格位置的情况吗？

分治算法的设计实例除了使用一张张骨牌对拼图进行尝试，我们还可以用另一种想法，来尝试完成这个拼图游戏。我们可以将4×4的棋盘，分割开来，看作是由4个相同的2×2的“小棋盘”组成的“大棋盘”，如图所示。此时，特殊方格必然只存在于4个“小棋盘”当中的1个“小棋盘”，而其余3个“小棋盘”中则没有特殊方格，4个“小棋盘”不完全相同了。

分治算法的设计实例如果我们将一个L型骨牌覆盖在3个“小棋盘”的会合之处，则可以将4个“小棋盘”再次变成相同的棋盘，然后尝试使用L型骨牌来分别填满4个“小棋盘”，如图所示。

分治算法的设计实例我们只需要将L型骨牌，放进每个“小棋盘”的空白方格处，就可以将整个棋盘填满了。

02分治算法的基本思想

分治算法的基本思想分治算法就是将一个规模较大的问题分解为几个小问题，这些小问题之间相互独立、但又与原问题性质相同，再对小问题进行分别求解，就可以最终得到大问题的答案了。因此，分治算法的求解过程就是：分解：将原问题分解或几个规模较小的问题，此时要注意小问题中的条件、性质需与原问题保持一致。求解：对于每个小问题进行求解，得到小问题的答案。合并：将所有小问题合并起来，作为原问题的答案。什么是分治算法

分治算法的基本思想结合先前所学过的递归算法，你认为分治算法和递归算法之间有什么关联性吗？你可以尝试为棋盘游戏画出程序结构图吗？

03分治算法的拓展

分治算法的概念与拓展练一练如果将棋盘游戏之中的棋盘大小变为8×8，其他条件不改变，你是否能够用L型骨牌将棋盘填满呢？

分治算法的概念与拓展练一练如果棋盘的大小是16×16呢？快来做一下，看看谁做得又快又正确。