分治策略朱全民ppt課件-展示頁
2025-05-15 08:34本頁面
【正文】 K2)+2]+2=22+2+22C(2K2) =22+2+2[2C(2K3)+2]=23+22+2+23C(2K3) …… = 2K1+2K2+…+2+2 K1C(2) =2K1+2K2+…+2+2 K1 =2K2+2K1 C(n)=3n/2 2 分治思想 ? 分治 (divideandconquer)就是“分而治之”的意思，其實(shí)質(zhì)就是將原問題分成 n個(gè)規(guī)模較小而結(jié)構(gòu)與原問題相似的子問題；然后遞歸地解這些子問題，最后合并其結(jié)果就得到原問題的解。 由 c(2)=1, 使用迭代方法可知 c(n) = 3n/2 2。 ?對(duì)于 N枚金塊，我們可以推出比較次數(shù)的公式： 假設(shè) n是 2的次冪， c(n)為所需要的比較次數(shù)。在第二步中，若 n＞ 2，則遞歸地應(yīng)用分而治之方法。設(shè) A中最重和最輕的金塊分別為 HA 與 LA，以此類推， B中最重和最輕的金塊分別為 HB 和 LB。 ? n＞ 2，第一步，把這袋金塊平分成兩個(gè)小袋 A和 B。 for i:=2 to n1 do {n2次比較，從剩下的元素中找最小的 } if a[i]max then min:=a[i]。 for i:=j+1 to n do a[i1]:=a[i]。 for i:=2 to n do {n1次比較，從 n個(gè)元素中找到最大的 } if a[i]max then begin max:=a[i]。 end 。 for i:=2 to n do {2n2次比較 } begin if a[i]max then max:=a[i]。 ?算法如下： max:=a[1]。找到最重的金塊后，可以從余下的 n1個(gè)金塊中用類似的方法通過 n2次比較找出最輕的金塊。 方法 1 ?假設(shè)袋中有 n 個(gè)金塊。如果有新的金塊周期性的加入袋中，則每個(gè)月都必須找出最輕和最重的金塊。按規(guī)矩，排名第一的雇員將得到袋中最重的金塊，排名第二的雇員將得到袋中最輕的金塊。 問題 2： 金塊問題 ?有一個(gè)老板有一袋金塊。最多可能有 8次比較。最多可能有 15次比較。利用這臺(tái)儀器，可以知道兩組硬幣的重量是否相同。你的任務(wù)是找出這枚偽造的硬幣。分治算法教案 長(zhǎng)沙市雅禮中學(xué) 朱全民 問題 1： 找出偽幣 ?給你一個(gè)裝有 1 6枚硬幣的袋子。 1 6枚硬幣中有一個(gè)是偽造的，并且那個(gè)偽造的硬幣比真的硬幣要輕一些。 ?為了幫助你完成這一任務(wù)，將提供一臺(tái)可用來比較兩組硬幣重量的儀器，比如天平。 方法 1 ?任意取 1枚硬幣，與其他硬幣進(jìn)行比較，若發(fā)現(xiàn)輕者，這那枚為偽幣。 方法 2 ?將硬幣分為 8組，每組 2個(gè)，每組比較一次，若發(fā)現(xiàn)輕的，則為偽幣。 方法 3 分析 ?上述三種方法 ,分別需要比較 15次 ,8次 ,4次 ,那么形成比較次數(shù)差異的根本原因在哪里 ? ?方法 1:每枚硬幣都至少進(jìn)行了一次比較 ,而有一枚硬幣進(jìn)行了 15次比較 ?方法 2:每一枚硬幣只進(jìn)行了一次比較 ?方法 3:將硬幣分為兩組后一次比較可以將硬幣的范圍縮小到了原來的一半 ,這樣充分地利用了只有 1枚偽幣的基本性質(zhì)。每個(gè)月將有兩名雇員會(huì)因其優(yōu)異的表現(xiàn)分別被獎(jiǎng)勵(lì)一個(gè)金塊。根據(jù)這種方式，除非有新的金塊加入袋中，否則第一名雇員所得到的金塊總是比第二名雇員所得到的金塊重。假設(shè)有一臺(tái)比較重量的儀器，我們希望用最少的比較次數(shù)找出最輕和最重的金塊?？梢杂煤瘮?shù) M a x通過 n1次比較找到最重的金塊。這樣，比較的總次數(shù)為 2n3。min:=a[1]。 if a[i]min then min:=a[i]。 可對(duì)上述改進(jìn)少 1次 max:=a[1]。 j:=i end。 {去掉最大的數(shù) a[j]} min:=a[1]。 找金塊的示例圖 方法 2： ? n≤2，識(shí)別出最重和最輕的金塊，一次比較就足夠了。第二步，分別找出在 A和 B中最重和最輕的金塊。第三步，通過比較 HA 和 HB，可以找到所有金塊中最重的；通過比較 LA 和 LB，可以找到所有金塊中最輕的。 分治過程 比較過程 分析 ?從圖例可
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1