Chapter 3 分治策略 習(xí)題

1、南京理工大學(xué) 習(xí)題6.5 給出在一個(gè)整數(shù)數(shù)組 A1n 中求出所有元素和的分治算法。 輸入：n個(gè)元素的數(shù)組 A1n 輸出：數(shù)組 A1n 總所有元素之和 1. ArraySum(A,1,n) 過程ArraySum(A,low,high) 1. if high low = 0 return Alow 2. if high low 0 3. mid ?( low+high)/2? 4. return ArraySum(A,low,mid)+ArraySum(A,mid+1,high) 5. end if (1) , n1 ( ) ( /2)( /2) , n1 T n T nT n ? ? ? ? ?

2、 ( )( )T nn? ? 南京理工大學(xué) public static int arraySum(int A,int low,int high) if(high - low = 0) return Alow; else if(high - low 0) int mid = (int)Math.floor(high+low)/2); return arraySum(A,low,mid)+arraySum(A,mid+1,high); else return Integer.MIN_VALUE; public static void main(String args) int A=1,2,3,4,

3、5; int result = arraySum(A,1,2); System.out.println(result); 南京理工大學(xué) 習(xí)題6.6 整數(shù)數(shù)組 A1n ，x為一整數(shù)。給出一個(gè)分治算法，找出 x在A中出現(xiàn)的頻 度。 輸入：整數(shù)數(shù)組 A1n ，整數(shù)x 輸出：x在數(shù)組 A1n 中出現(xiàn)的頻度 1.Frequence(A,1,n,x) 過程Frequence (A,low,high,x) 1. if high low = 0 2. if Alow = x return 1 3. else return 0; 4. end if 5. if high low 0 6. mid ?( low+

4、high)/2 ? 7. return Frequence(A,low,mid,x)+Frequence(A,low+1,high,x) 8. end if (1) , n1|n=2 ( ) ( /2)( /2) , n2 T n T nT n ? ? ? ? ? ( )( )T nn? ? 南京理工大學(xué) public static int frequence(int A,int low, int high,int x) if (high - low 0 ) return -1; else if(high - low = 0 ) if (Alow=x) return 1; else retur

5、n 0; else int mid = (int)Math.floor(high+low)/2); return frequence(A,low,mid,x)+frequence(A,mid+1,high,x); public static void main(String args) int A=7, 5 ,3,2,4,6,7,3,5,7,8; int result = frequence(A,0,A.length-1,2); System.out.println(result); 南京理工大學(xué) Algorithm: MERGESORT(Alowhigh) 輸入：待排序數(shù)組Alow,.hig

6、h 輸出：Alowhigh按非降序排列 1. if lowhigh then 2. if (high low + 1 = m) then INSERTSORT(A,low,high) 3. else 4. mid?(low+high)/2? 5. MERGESORT(A, low, mid) 6. MERGESORT(A, mid+1, high) 7. MERGE(A, low, mid, high) 8. end if 9. end if 習(xí)題6.16 考慮修改MERGESORT 算法。將算法應(yīng)用到輸入數(shù)組 A1n 上并不 斷遞歸調(diào)用，直到子問題的規(guī)模變得相對(duì)很小，即m或是小于 m。此時(shí)轉(zhuǎn)

7、向INSERTSORT.。 南京理工大學(xué) 分析 2 () , n ( ) 2 ( /2)1 , n O mm C n C nnm ? ? ? ? ? ( )(1)/2C mm m? ( )2( / 2 )21 kkk C nC nkn? /2knm? ( )2( )21l(1)/2og1 kk n nn C nC mknn m m m ? 1 m? mn? ( )log1C nnnn? (1)/2n n ? (1)/2logn mnn?2log1mn? 見課本p107 南京理工大學(xué) 習(xí)題6.38 解釋當(dāng)輸入已按降序排列時(shí)算法 QUICKSORT 的行為，可以假定輸入元 素是互不相同的。 Explain the behavior of Algorithm QUICKSORT when the input is already stored in decre