【文章內容簡介】 r):integer。 begin var x:integer。 x:=1。 for i:=1 to n do x:=x*a。 power:=x。 end。 方法 2：分治算法 劃分：如果 n是偶數，考慮 x=n div 2， 否則考慮 x=(n1) div 2 遞歸求解：計算 ax。 合并：如果 n是偶數，則 an=(ax)2，否則 an=(ax)2*a 方法 2：分治算法 根據這個方法很容易寫出程序： function power(a,n:integer):integer。 Begin if n=0 begin power:=1。exit。end else if n mod 2=1 then //n為奇數的情況 begin x:=power(a,(n1)div 2)。 power:=((x*x)mod k*a)mod k。 end else begin //n為偶數的情況 x:=power(a,n div 2)。 power:=x*x mod k。 end。 End。 方法 3：用二進制實現(xiàn)快速冪計算 read(a,b,k)。//輸入三個數 t:=b。 while t0 do begin inc(len)。c[len]:=t mod 2。t:=t div 2。end。//轉為二進制 s:=1。 for i:=len downto 1 do //用二分法實現(xiàn) ab mod k begin s:=s*s mod k。 if c[i]=1 then s:=((a mod k)*s)mod k。//如果是奇數，就多乘 a end。 writeln(s)。//輸出 ab mod k 求解線性遞推關系 【 例題 】 Fibonacci數 【 題目描述 】 Fibonacci數列定義為： f[i]=f[i2]+f[i1] (i2)，其中f[1]=1,f[2]=1?，F(xiàn)在請你求 Fibonacci數列的第 n項。 【 文件輸入 】 輸入文件只有一行為一個整數 n(1=n=2^311)。 【 文件輸出 】 輸出文件只有一行為一個整數，表示 Fibonacci數列的第 n項 mod 32768的值。 【 樣例輸入 】 4 【 樣例輸出 】 3 【 數據范圍 】 對于 20%的數據， 1=n=1000 對于 40%的數據， 1=n=10000000 對于 100%的數據， 1=n=2^311 ? 樸素算法，肯定超時 procedure Fib(n:integer) Begin var i:integer。 f[0]:=0。f[1]:=1。 for i:=2 to n do f[i]:=f[i1]+f[i2]。 End。 先復習矩陣乘法 ?兩個 2*2矩陣相乘的公式為 ? 可用倍增法在 O(logn)時間內求出冪 (忽略高精度 ) ? ?? ?? ?? ?? ?2212231212111110. . . . . . .11101110?????????????????????????????????nnnnnnnnnnXFFXFFXFFFFFFF擴展練習： ? 若 f[i]=f[i1]+f[i2]+f[i3]，如何計算求出 f[n] 棋盤覆蓋問題 分析 循環(huán)日程表問題 【 例題 】 比賽安排 【 問題描述 】 設有 2n(n=6)個球隊進行單循環(huán)比賽 ,計劃在 2n 1天內完成，每個隊每天進行一場比賽。設計一個比賽的安排，使在 2n 1天內每個隊都與不同的對手比賽。例如 n=2時的比賽安排為： 隊 1 2 3 4 比賽 12 34 第一天 13 24 第二天 14 23 第三天 【 文件輸入 】 一個整數 n。 【 文件輸出 】 輸出比賽安排表。 【 樣例輸入 】 2 【 樣例輸出 】 12 34 13 24 14 23 ? 初看此題，感覺無法下手，因為沒有任何直接可用的算法和數據結構。 ? 仔細分析，可以發(fā)現(xiàn)，將問題進行分解，能找出規(guī)律。 ? 當 n=1時，共有 2個球隊參賽，一天就可以比完。 ? 當 n=2時，共有 4個球隊，需比賽 3天。從 2個球隊的比賽安排表中可以看出，左上角與右下角對稱，左下角與右上角對稱，左下角的值是由左上角值加 n得到的。 read(n)。 m:=1。a[1,1]:=1。h:=1。 for i:=1 to n do m=2*m。 //比賽總隊數 while(h=m)do //從一個球隊開始構造 begin 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。 end。 核心參考代碼 尋找最近點對 ? 給定平面上 n個點 ,找出其中的一對點的距離 ,使得在這 n個點的所有點對中 ,該距離為所有點對中最小的。（ n=60000） 分析 ? 【 問題簡述 】 給定平面上 n個點的坐標，找出其中歐幾里德距離最近的兩個點。 ? 【 方法 1】 枚舉算法。 需要枚舉 O(n2)個點對，每個距離的計算時間為 O(1)，故總的時間復雜度為 O(n2)。 有沒有更好的算法呢？ 【 方法 2】 分治算法 ? 先按照 X坐標排序，把所有點劃分成個數盡量相等的兩部分，分別求最近點對，設距離分別為 dL和 dr。 ? 合并：令 d=min{dL,dr}，則跨越兩邊的點對中，只有下面的豎條中的才有可能更近。 需要檢查豎條里的所有點對嗎？ ? 由 d的意義可知， P2中任何 2個 S中的點的距離都不小于 d。由此而來可以推出矩形 R中最多只有 6個 d/2*2/3*d的矩形(如下圖所示 )。 ? （反證法）若矩形 R中有多于 6個 S中的點，則由鴿籠原理易知至少有一個 d/2*2/3*d的小矩形中有 2個以上 S中的點。設 U， V是這樣 2個點，它們位于同一小矩形中，則： ? (X(U)X(V))2+(Y(U)Y(V))2=(d/2)2+(d/2)2=25d2/36 ? 因此， D(U,V)=5d/6d。這與 d的意義相矛盾。也就是說矩形 R中最多只有 6個 S中的點。 ? 由于這種稀疏性質，對于 P1中任一點 p， P2中最多只有 6個點與它構成最接近點對的候選者。 總結歸納 ? 分治是一種解題的策略，它的基本思想是： “ 如果整個問題比較復雜，可以將問題分化，各個擊破。 ” ? 分治包含 “ 分 ” 和 “ 治 ” 兩層含義，如何分，分后如何 “ 治 ” 成為解決問題的關鍵所在 ? 不是所有的問題都可以采用分治，只有那些能將問題分成與原問題類似的子問題，并且歸并后符合原問題的性質的問題，才能進行分治 ? 分治可