算法設(shè)計與分析 課件 4.2-分治法 - 引例-尋找金塊

算法設(shè)計與分析分治引例-尋找金塊信息工程大學(xué)國家級實驗教學(xué)示范中心計算機學(xué)科組規(guī)劃教材算法設(shè)計與分析Python案例詳解微課視頻版已知條件：某老板有一袋金塊。每個月將有兩名雇員會因其優(yōu)異的表現(xiàn)分別被獎勵一個金塊。按規(guī)矩，排名第一的雇員將得到袋中最重的金塊，排名第二的雇員將得到袋中最輕的金塊。工具：一臺天枰，可用來比較金塊的重量。問題：用最少的比較次數(shù)找出最輕和最重的金塊。方法一假設(shè)袋中有n個金塊：

先找最重的金塊：n-1次比較

再找最輕的金塊：n-2次比較方法一算法描述：max:=a[1];fori:=2tondo//n-1次比較，找n個元素中最大ifa[i]>maxthenbegin max:=a[i];j:=i;end;fori:=j+1tondoa[i-1]:=a[i];//去掉最大的數(shù)a[j]min:=a[1];fori:=2ton-1do//n-2次比較，找剩下元素中最小ifa[i]<minthenbegin min:=a[i];方法二n≤2，找出最重和最輕的金塊，一次比較；n＞2step1:把金塊平分成兩個小袋A和B；step2:分別找出在A和B中最重和最輕的金塊（HA與LA、HB和LB分別表示A和B中最重和最輕的金塊）；step3:比較HA和HB找到最重的金塊；比較LA和LB找到最輕的金塊。

step2中，若n>2，則遞歸的繼續(xù)平分為兩部分。方法二10，8，2，4，5，3，9，110，8，2，45，3，9，110，82，45，39，1方法二10，82，45，39，1第一輪比較4次比較10，42，85，93，1第二輪比較4次比較10，29，110，92，1第三輪比較10，12次比較共10次比較算法分析當(dāng)有8個金塊的時候，方法1需要比較15次，方法2只需要比較10次。比較次數(shù)差異的根本原因是什么?方法2：對金塊實行了分組比較。對于n(n是2的次冪)枚金塊，比較次數(shù)c(n)：

方法1：c(n)=(n-1)+(n-2)=2n-3

方法2：c(n)=2c(n/2)+2,c(2)=1,=3n/2-2淘汰賽法思想：先按淘汰賽法找出最大項；再在首輪敗者中（包括首輪未參加比較的項）找出最小項。方法三1.找出最大項需要n-1次比較2.參加找“最小”的項數(shù)至多有

n/2

個，故可用

n/2-1次比較找到最小項。共：n-1+n/2-1=3n/2-2次比較。【定理】：用比較算法類中的任一算法，找出n項表中的最大項和最小項，在最壞情況下，至少要比較3n/2-2