資源簡介

(共15張PPT)
分治算法
贛科學(xué)技術(shù)版五年級下冊
第4課
分治算法
理解分治算法的基本思想，
掌握分治算法的求解過程，
能運用分治算法解決實際學(xué)習(xí)與生活中的問題。
任務(wù)卡
現(xiàn)有一個棋盤，它由4×4的方格組成，其中，恰好有一個方格和其他方格不同，如圖所示，圖中紅色小方格被稱為特殊方格， 而這個棋盤被稱為特殊棋盤。同時，還有四種不同形態(tài)的L 型骨牌，如圖所示。 游戲規(guī)則是，將L型骨牌覆蓋于棋盤的方格之上，但不可以覆蓋特殊方格，且兩個L 型骨牌之間不能重疊覆蓋。
一
說一說
拼圖游戲里的特殊棋盤
拼圖游戲里的 L型骨牌
怎么樣才能用骨牌把所有的格子都覆蓋滿呢 試著完成這個游戲。
比一比：你的結(jié)果和小藍(lán)的操作一樣嗎
一
說一說
小藍(lán)的拼圖結(jié)果
一
說一說
按照循環(huán)結(jié)構(gòu)的思想，小紅將找鑰匙的過程，簡化成了一個循環(huán)模型，如圖。
小紅的循環(huán)示意圖畫的和你的一樣嗎
二
想一想
你還記得剛剛是怎么樣將拼圖完成的嗎 如果將特殊方格的位置更改，你還能夠?qū)?拼圖完成嗎 和同學(xué)們一起試試看。
二
想一想
除了使用一張張骨牌對拼圖進(jìn)行嘗試，我們還可以用另一種想法，來嘗試完成這個拼圖游戲。我們可以將4×4的棋盤，分割開來，看作是由4個相同的2×2的“小棋盤”組成的“大棋盤”,如圖所示。
此時，特殊方格必然只存在于4個“小棋盤”當(dāng)中的1個“小棋盤”,而其余3個“小棋 盤”中則沒有特殊方格，4個“小棋盤”不完全相同了。
如果我們將一個L 型骨牌覆蓋在3個“小棋盤”的會合之處，則可以將4個“小棋 盤”再次變成相同的棋盤，然后嘗試使用L 型骨牌來分別填滿4個“小棋盤”,如圖所示。
二
想一想
我們只需要將 L 型骨牌，放進(jìn)每個“小棋盤”的空白方格處，就可以將整個棋盤填滿了
分治算法就是將一個規(guī)模較大的問題分解為幾個小問題，這些小 問題之間相互獨立、但又與原問題性質(zhì)相同，再對小問題進(jìn)行分別求解，就可以最終得到 大問題的答案了。
因此，分治算法的求解過程就是
(1)分解：將原問題分解或幾個規(guī)模較小的問題，此時要注意小問題中的條件、性質(zhì) 需與原問題保持一致。
(2)求解：對于每個小問題進(jìn)行求解，得到小問題的答案。
(3)合并：將所有小問題合并起來，作為原問題的答案。
什么是分治算法
三
想一想
結(jié)合先前所學(xué)過的遞歸算法，你認(rèn)為分治算法和遞歸算法之間有什么關(guān)聯(lián)性嗎 你 可以嘗試為棋盤游戲畫出程序結(jié)構(gòu)圖嗎
如果將棋盤游戲之中的棋盤大小變?yōu)?×8,其他條件不改 變，你是否能夠用L 型骨牌將棋盤填滿呢 如果棋盤的大小是16×16呢 快來做一下，看看誰做得又快又正確。
練一練
謝謝聆聽！
謝謝
21世紀(jì)教育網(wǎng)（www.21cnjy.com)
中小學(xué)教育資源網(wǎng)站
兼職招聘：
https://www.21cnjy.com/recruitment/home/admin

展開更多......

收起↑