2019-2020年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 分治法.doc

《2019-2020年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 分治法.doc》由會員分享，可在線閱讀，更多相關《2019-2020年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 分治法.doc（3頁珍藏版）》請在裝配圖網(wǎng)上搜索。

2019-2020年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 分治法 分治算法的基本思想是將一個規(guī)模為N的問題分解為K個規(guī)模較小的子問題，這些子問題相互獨立且與原問題性質相同。求出子問題的解，就可得到原問題的解。 分治法解題的一般步驟： （1）分解，將要解決的問題劃分成若干規(guī)模較小的同類問題； （2）求解，當子問題劃分得足夠小時，用較簡單的方法解決； （3）合并，按原問題的要求，將子問題的解逐層合并構成原問題的解。 分治法應用 例1、 比賽安排(noip1996) 設有2^n(n<=6)個球隊進行單循環(huán)比賽,計劃在2^n-1天內完成,每個隊每天進行一場比賽。設計一個比賽的安排,使在2^n-1天內每個隊都與不同的對手比賽。例如n=2時的比賽安排為: 隊 1 2 3 4 比賽 1-2 3-4 第一天 1-3 2-4 第二天 1-4 2-3 第三天 算法分析：此題很難直接給出結果，我們先將問題進行分解，設m=2^n，將規(guī)模減半，如果n=3(即m=8),8個球隊的比賽，減半后變成4個球隊的比賽（m=4），4個球隊的比賽的安排方式還不是很明顯，再減半到兩個球隊的比賽(m=2)，兩個球隊的比賽安排方式很簡單，只要讓兩個球隊直接進行一場比賽即可： 1 2 2 1 分析兩個球隊的比賽的情況不難發(fā)現(xiàn)，這是一個對稱的方陣，我們把這個方陣分成4部分（即左上，右上，左下，右下），右上部分可由左上部分加1（即加m/2）得到，而右上與左下部分、左上與右下部分別相等。因此我們也可以把這個方陣看作是由M=1的方陣所成生的，同理可得M=4的方陣： 1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1 同理可由M=4方陣生成M=8的方陣： 1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 4 3 2 1 8 7 6 5 5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4 3 2 1 這樣就構成了整個比賽的安排表。 在算法設計中，用數(shù)組a記錄2^n個球隊的循環(huán)比賽表，整個循環(huán)比賽表從最初的1*1方陣按上述規(guī)則生成2*2的方陣，再生成4*4的方陣，……直到生成出整個循環(huán)比賽表為止。變量h表示當前方陣的大小,也就是要生成的下一個方陣的一半。 源程序： var i,j,h,m,n:integer; a:array[1..32,1..32]of integer; begin readln(n); m:=1;a[1,1]:=1;h:=1; for i:=1 to n do m:=m*2; repeat for i:=1 to h do for j:=1 to h do begin a[i,j+h]:=a[i,j]+h;{構造右上角方陣} a[i+h,j]:=a[i,j+h];{構造左下角方陣} a[i+h,j+h]:=a[i,j];{構造右下角方陣} end; h:=h*2; until h=m; for i:=1 to m do begin for j:=1 to m do write(a[i,j]:4); writeln; end; end. 在分治算法中，若將原問題分解成兩個較小的子問題，我們稱之為二分法，由于二分法劃分簡單，所以使用非常廣泛。使用二分法與使用枚舉法求解問題相比較，時間復雜度由O（N）降到O（log2N），在很多實際問題中，我們可以通過使用二分法，達到提高算法效率的目的，如下面的例子。 例2 一元三次方程求解（noipxxtg） 題目大意：給出一個一元三次方程f(x)=ax3+bx2+cx+d=0 ,求它的三個根。所有的根都在區(qū)間[-100，100]中，并保證方程有三個實根，且它們之間的差不小于1。 算法分析：在講解枚舉法時，我們討論了如何用枚舉法求解此題，但如果求解的精度進一步提高，使用枚舉法就無能為力了，在此我們再一次討論如何用二分法求解此題。 由題意知（i,i+1）中若有根，則只有一個根，我們枚舉根的值域中的每一個整數(shù)x(-100≤x≤100),設定搜索區(qū)間[x1，x2]，其中x1=x，x2=x+1。若： ⑴f(x1)=0，則確定x1為f(x)的根； ⑵f(x1)*f(x2)<0，則確定根x在區(qū)間[x1，x2]內。 ⑶f(x1)*f(x2)>0，則確定根x不在區(qū)間[x1，x2]內，設定[x2，x2+1]為下一個搜索區(qū)間； 若確定根x在區(qū)間[x1，x2]內，采用二分法，將區(qū)間[x1，x2]分成左右兩個子區(qū)間：左子區(qū)間[x1，x]和右子區(qū)間[x，x2]（其中x=（x1+x2）/2）。如果f(x1)*f(x)≤0，則確定根在左區(qū)間[x1，x]內，將x設為該區(qū)間的右界值（x2=x），繼續(xù)對左區(qū)間進行對分；否則確定根在右區(qū)間[x，x2]內，將x設為該區(qū)間的左界值（x1=x），繼續(xù)對右區(qū)間進行對分； 上述對分過程一直進行到區(qū)間的間距滿足精度要求為止（即x2-x1<0.005）。此時確定x1為f(x)的根。 源程序： {$N+} var x:integer; a,b,c,d,x1,x2,xx:extended; function f(x:extended):extended; begin f:=((a*x+b)*x+c)*x+d; end; begin read(a,b,c,d); for x:=-100 to 100 do begin x1:=x;x2:=x+1; if f(x1)=0 then write(x1:0:2, ) else if f(x1)*f(x2)<0 then begin while x2-x1>=0.005 do begin xx:=(x1+x2)/2; if f(x1)*f(xx)<=0 then x2:=xx else x1:=xx; end;{while} write(x1:0:2, ); end; {then} end;{for} end.