分治策略-展示頁
2025-02-01 11:57本頁面
【正文】 系數(shù) (a， b， c， d均為實數(shù) )，并約定該方程存在三個不同實根 (根的范圍在 100至 100之間)，且根與根之差的絕對值 =1。分治策略的解題思路 if 問題不可分 then begin 直接求解； 返回問題的解；end else begin 對原問題進行分治； 遞歸對每一個分治的部分求解 歸并整個問題，得出全問題的解；end。v 分治求解可用一個遞歸過程來表示。 分治思想問題 S問題 S問題 S的解問題 S1 ……問題 S2 問題 Si 問題 Sn……S1的解 ……S2的解 Si的解 Sn的解……問題的分解子集解的合并子問題求解分治思想v 由分治法所得到的子問題與原問題具有相同的類型。若子問題足夠小，則可直接求解。v 其三個步驟如下；1. 分解 (Divide)：將原問題分成一系列子問題。 證明令 n=2kC(2K)=2C(2K1)+2 =2[2C(2K2)+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+2K1C(n)=3n/2 2分治思想v 分治 (divideandconquer)就是 “分而治之 ”的意思，其實質就是將原問題分成 n個規(guī)模較小而結構與原問題相似的子問題；然后遞歸地解這些子問題，最后合并其結果就得到原問題的解。由 c(2)=1, 使用迭代方法可知 c(n) = 3n/2 2。v 對于 N枚金塊，我們可以推出比較次數(shù)的公式：假設 n是 2的次冪， c(n)為所需要的比較次數(shù)。在第二步中，若 n＞ 2，則遞歸地應用分而治之方法。設 A中最重和最輕的金塊分別為 HA 與 LA，以此類推， B中最重和最輕的金塊分別為 HB 和 LB。v n＞ 2，第一步，把這袋金塊平分成兩個小袋 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個元素中找到最大的 }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]。v 算法如下：max:=a[1]。找到最重的金塊后，可以從余下的 n1個金塊中用類似的方法通過 n2次比較找出最輕的金塊。方法 1 v 假設袋中有 n 個金塊。如果有新的金塊周期性的加入袋中，則每個月都必須找出最輕和最重的金塊。按規(guī)矩，排名第一的雇員將得到袋中最重的金塊，排名第二的雇員將得到袋中最輕的金塊。問題 2： 金塊問題v 有一個老板有一袋金塊。最多可能有 8次比較。最多可能有 15次比較。利用這臺儀器，可以知道兩組硬幣的重量是否相同。你的任務是找出這枚偽造的硬幣。分治算法教案長沙市雅禮中學 朱全民問題 1： 找出偽幣v 給你一個裝有 1 6枚硬幣的袋子。 1 6枚硬幣中有一個是偽造的，并且那個偽造的硬幣比真的硬幣要輕一些。v 為了幫助你完成這一任務，將提供一臺可用來比較兩組硬幣重量的儀器，比如天平。 方法 1v 任意取 1枚硬幣，與其他硬幣進行比較，若發(fā)現(xiàn)輕者，這那枚為偽幣。 方法 2v 將硬幣分為 8組，每組 2個，每組比較一次，若發(fā)現(xiàn)輕的，則為偽幣。 方法 3分析v上述三種方法 ,分別需要比較 15次 ,8次 ,4次 ,那么形成比較次數(shù)差異的根本原因在哪里 ?v方法 1:每枚硬幣都至少進行了一次比較 ,而有一枚硬幣進行了 15次比較v方法 2:每一枚硬幣只進行了一次比較v方法 3:將硬幣分為兩組后一次比較可以將硬幣的范圍縮小到了原來的一半 ,這樣充分地利用了只有 1枚偽幣的基本性質。每個月將有兩名雇員會因其優(yōu)異的表現(xiàn)分別被獎勵一個金塊。根據(jù)這種方式，除非有新的金塊加入袋中，否則第一名雇員所得到的金塊總是比第二名雇員所得到的金塊重。假設有一臺比較重量的儀器，我們希望用最少的比較次數(shù)找出最輕和最重的金塊?？梢杂煤瘮?shù) M a x通過 n1次比較找到最重的金塊。這樣，比較的總次數(shù)為 2n3。min:=a[1]。 if a[i]min then min:=a[i]?？蓪ι鲜龈倪M少 1次max:=a[1]。 j:=i end。 {去掉最大的數(shù) a[j]}min:=a[1]。找金塊的示例圖方法 2：v n≤2，識別出最重和最輕的金塊，一次比較就足夠了。第二步，分別找出在 A和 B中最重和最輕的金塊。第三步，通過比較 HA 和 HB，可以找到所有金塊中最重的；通過比較 LA 和 LB，可以找到所有金塊中最輕的。分治過程比較過程分析v 從圖例可以看出，當有 8個金塊的時候，方法 1需要比較 15~16次，方法 2只需要比較 10次 ,那么形成比較次數(shù)差異的根本原因在哪里 ?v 其原因在于方法 2對金塊實行了分組比較。方
電大資料相關推薦
鄂ICP備17016276號-1