第2章递归与分治策略

: 1. 2. 3. Strassen 4. 5. 6. 7. 8. 9... 2

T(n) = n T(n/2) T(n/2) T(n/2) T(n/2) 3

T(n) = n n/2 n/2 n/2 n/2 T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4 4

T(n) = n n/2 n/2 n/2 n/2 T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4 5

T(n) = n n/2 n/2 n/2 n/2 T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4 6

[ ]N! [ 1] {U1,U2,U3,,Un } k Un n N>=1 N!=N*(N-1)! N=1 0!=1 K! K (K-1)! 9

[ ]N! [ 2] 1 k Un Uk Uk k=0 0!=1 N! 0! #include <iostream.h> int f(int x){ return(f(x-1)); } main(){ cout<<f(10); } 10

[ ]N! [ 3] 1 2 long f(int n){ if (n==0) return(1); n! = 1 n( n 1)! n n = > 0 0 else return(n*f(n-1)); } 11

[ 4] long f(int n){ } if (n==0) else return(1); return(n*f(n-1)); main(){ int n; cin>>n; cout<<endl<<f(n); } n! = 1 n( n 1)! n n = > 0 0 12

2 1 n = 0 F( n) = 1 n = 1 F( n 1) + F( n 2) n > 1 n Fibonacci int fibonacci(int n){ if (n <= 1) return 1; return fibonacci(n-1)+fibonacci(n-2); } 13

[ ] n=0 m>0 n>0 #include "stdio.h" long int ack(int m,int n){ if(m<0 n<0) { printf("\n not exit!\n"); exit(0); } if(m==0) return(n+1); else if (n==0) return( ack((m-1),1) ); else return ( ack((m-1),ack(m,n-1)) ); } n + 1 Ack( m, n) Ack( m 1,1) Ack(( m 1), Ack( m, n 1)) n = 0 n, m > 0 main(){ int mm, nn; long int a; printf("\n Please enter M,N "); scanf("%d,%d",&mm,&nn); a=ack(mm,nn); printf("\n ack(%d,%d)=%d\n",mm,nn,a); } 14 m = 0

[ ] [ ] 15

4 void perm(int list[], int k, int m){ // list[k..m] if(k==m){ // k=m list[0..m] for(int i=0;i<=m;i++) printf("%d ",list[i]); printf("\n"); } } else{ list[0..k] for(int i=k; i<=m; i++){ // list[k+1..m] swap(list[k], list[i]); perm(list, k+1, m); // list[k+1..m] swap(list[k], list[i]); } void swap(int &a,int &b){ // } int temp; temp=a; a=b; b=temp; } void main(){ int p[10]={1,2,3,4,5,6,7,8,9}; perm(p,0,2); // p[0..2] } k<m list[k..m] list[k] list[k+1..m] 16

[ ] 17

q(n, m) q(n, m) 1. q(n, 1) = 1, n>=1 1, n=1+1+1+...+1 2. q(n, m) = q(n, n), m >= n n n q(1, m) = 1 3. q(n, n) = 1 + q(n, n - 1) n =n n <= n-1 4. q(n, m) = q(n, m-1) + q(n-m, m), n > m > 1 n m n =m n <= m-1 n n m n =m m n-m n2 q(n-m, m) n1 m-1 q(n,m-1) 18

5 unsigned integer_div( unsigned n, unsigned m ) { if ( n < 1 m < 1 ) return 0; if ( n == 1 m == 1 ) return 1; if ( n == m ) q( n, m) = q( n, return 1 + integer_div( n, m - 1 ); if ( n < m ) return integer_div( n, n ); return integer_div( n, m - 1 ) + integer_div( n - m, m ); } 1 q( n, n) 1+ q( n, n 1) m 1) + q( n m, m) n = 1, m = 1 n < m n = m n > m > 1 #include <iostream> unsigned integer_div( unsigned n, unsigned m ); int main(){ unsigned a; cout << " "; cin >> a; cout << " " << integer_div( a, a ) << " \n"; return 0; } 19

6 [ ] 3 A B C A n A C 3 [ ] n 20

6 [ ] n=1 A C n>1 (n-1) A B A C B A C B (n-1) B C A 21

6 Hanoi void hanoi(int n, int a, int b, int c) { if (n > 0) { hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); } } 22

6 4 N A C 2 N 1 64 18446744073709511615 19 N 64 5800 150 23

,,, f(x,n)= n + ( n 1) + ( n 2) + + 1+ x x=3.1,n=15 x=8.1,n=10,?,, 26

divide-and-conquer 27

divide-and-conquer(p) { if ( P <= n0) adhoc(p); // divide P into smaller subinstances P1,P2,...,Pk // for (i=1,i<=k,i++) yi=divide-and-conquer(pi); // return merge(y1,...,yk); // } k (balancing) 29

n a[0:n-1] n x ; x a a[mid] x=a[mid] x L n=1 x mid x<a[mid] a a[i] x x a x a[mid] x a[mid] x x>a[i] a[mid] x x a x 30

7 n a[0:n-1] n x template<class Type> int BinarySearch(Type a[], const Type& x, int l, int r) { } while (r >= l){ int m = (l+r)/2; if (x == a[m]) return m; if (x < a[m]) r = m-1; else l = m+1; } return -1; while while O(logn) O(1) O(logn) 31

8 X,Y n, XY. : 1 1, O(n 2 ). n(n=2 K) 2, n/2 X=A 2 n/2 +B y= C 2 n/2 +D XY (A 2 n/2 +B) (C 2 n/2 +D) AC2 n +(AD+CB)2 n/2 +BD XY 4 n/2,3 2n,2 ( 2 n 2 n/2 ).XY T(n) T(1)= O(1) T(n)= T(n) =O(n 2 ) T(n)= 4T(n/2)+ O(n) : XY AC2 n +[(A-B)(D-C)+AC+BD]2 n/2 +BD XY 3 n/2,6. 2 T(1)= O(1) T(n)= T(n)= 3T(n/2)+ O(n) T(n) =O(n log3 ) 33

8 n XY = ac 2 n + ((a-b)(d-c)+ac+bd) 2 n/2 + bd int MULT(X, Y,n){ // X Y 2 2n X Y XY } S:=SIGN(X)*SIGN(Y); //S X Y X:=ABS(X); Y:=ABS(Y); //X Y if n=1 if (X=1)and(Y=1) return(s) else return(0) else{ A=X n/2 ; B=X n/2 ; C=Y n/2 ; D=Y n/2 ; ml=mult(a,c,n/2); m2=mult(a-b,d-c,n/2); m3=mult(b,d,n/2); S=S*(m1*2 n +(m1+m2+m3)*2 n/2 +m3); return(s); } 34

XY = ac 2 n + ((a-b)(d-c)+ac+bd) 2 n/2 + bd x 2368 y 3925 xy d 10 A 23 B 68 C 39 D 25 n 4 1 AC 23 39 897 2 BD 68 25 1700 3 A B D C AC BD 68 23 39 25 897 1700 45 14 897 1700 3227 XY 897 10 4 3227 10 2 1700 9294400 35

A=(a ij ) n n,b=(b ij ) n n, C=A B=(c ij ) n n c = n a i, j K= 1 b k, j A = a a 11 21 a a 12 22, B = b b 11 21 b b 12 22 36

= = 22 21 12 11 22 21 12 11 b b b b a a a a AB C + + + + = 22 22 12 21 21 22 11 21 22 12 12 11 21 12 11 11 b a b a b a b a b a b a b a b a = 22 21 12 11 c c c c 8 = = 22 21 12 11 22 21 12 11, b b b b B a a a a A

A = a a 11 21 a a 12 22, B = b b 11 21 b b 12 22 8 7

:C22 = M5+M1 M3 M7 n A=(a = (A 11 +A 22 )(B ij 11 ) n n +B,B=(b 22 ) +A ij ) n n 11,(BC=A B=(c 12 B 21 ) ij ) c = n n i, j a b K= 1 (A C n n 2 21 +A,n 22 ) B 2 11 (A (n-1). 11 A 21 )(B T(n)=O(n 11 +B 12 3 ) =A : A,B n/2(n=2 11 B 11 +A 11 B 22 +A 22 B 11 +A K ), : 22 B 22 +A 11 B 12 A 11 B 22 A 21 B 11 A 22 B 11 A 11 B 11 = A11 A12 B11 B12 = C11 C12 C A A21 A22 B 11 B 21 B 12 +A 21 B 22 C 11 +A 21 C 21 B 12 22 =A 21 B 12 +A 22 B 22 n=2, C; n>2,c 8 n/2 4. T(2)= O(1) T(n)= : T(n)=O(n 3 ) T(n)= 8T(n/2)+O(n 2) M 1 =A 11 (B 12 B 21 ) M 6 = (A 12 +A 22 )(B 21 +B 22 ) M 2 = (A 11 +A 12 )B M 7 = (A 11 A 21 )(B 11 +B 12 ) 22 C 11 =M 5 + M 4 M 2 +M M 6 3 = (A 21 +A 22 )B 11 C 12 = M 1 +M M 2 4 = A 22 (B 21 B 11 ) C 21 = M 3 +M 4 M 5 = (A 11 +A 22 )(B 11 +B 22 ) C 22 = M 5 +M 1 M 3 M 7 k, j C 11 =A 11 B 11 +A 12 B 21 C 12 =A 11 B 11 +A 12 B 21 C 21 =A 11 B 11 +A 12 B 21 C 22 =A 11 B 11 +A 12 B 21 40

} Strassen void STRASSEN(n, A, B, C){ if n=2 then MATRIX_MULTIPLY(A,B,C) // else { // A B STRASSEN( n/2 A 11 B 12 B 22 M 1 ) STRASSEN( h/2 A 11 +A 12 B 22 M 2 ) STRASSEN( n/2 A 21 +A 22 B 11 M 3 ) STRASSEN( n/2 A 22 B 21 B 11 M 4 ) STRASSEN( n/2 A 11 +A 22 B 11 +B 22 M 5 ) STRASSEN( n/2 A 12 -A 22 B 21 B 22 M 6 ) STRASSEN( n/2 A 11 +A 21 B 11 +B 12 M 7 ) A C = A 11 21 A A 12 22 B B 11 21 B B 12 22 = C C M 1 =A 11 (B 12 B 21 ) M 2 = (A 11 +A 12 )B 22 M 3 = (A 21 +A 22 )B 11 M 4 = A 22 (B 21 B 11 ) M 5 = (A 11 +A 22 )(B 11 +B 22 ) 11 21 C C 12 22 41

: 2 k 2 k, 2 2k k 0, 2 2k. L 2 L 2 k 2 k (4 k 1)/3 42

k>0, 2 k 2 k 4 2 k-1 2 k-1 4 3 3. L 3. 3 L, 4 1 1. : T(k) 2 k 2 k, k=0 O(1) k>0, 3 O(1), 4, 4T(k-1), T(k)= O(1) 4T(k-1)+ O(1) : T(k)=θ(4 k ) 43

board title 0 tr tc / dr dc / void chessboard(int tr, int tc, int dr, int dc, int size){ if (size == 1) return; board[tr + s - 1][tc + s] = t; int t = tile++ // L // s = size/2; // chessboard(tr, tc+s, tr+s-1, tc+s, s);} // // if (dr < tr + s && dc < tc + s) if (dr >= tr + s && dc < tc + s) // // chessboard(tr, tc, dr, dc, s); chessboard(tr+s, tc, dr, dc, s); else { // else { // t L // t L board[tr + s][tc + s - 1] = t; board[tr + s - 1][tc + s - 1] = t; // // chessboard(tr+s, tc, tr+s, tc+s-1, s);} chessboard(tr, tc, tr+s-1, tc+s-1, s);} // // if (dr >= tr + s && dc >= tc + s) if (dr < tr + s && dc >= tc + s) // // chessboard(tr+s, tc+s, dr, dc, s); chessboard(tr, tc+s, dr, dc, s); else { // t L else { // board[tr + s][tc + s] = t; // t L // chessboard(tr+s, tc+s, tr+s, tc+s, s);} } 44

2.5 (merge) : n : n 1, ;, n k(k=2) A,B,,. [49] [38] [65] [97] [76] [13] [27] [38 49] [65 97] [13 76] [27] [38 49 65 97] [13 27 76] [13 27 38 49 65 76 97] 45

template<class T> void merge(t C[], T d[],int l, int m, int r) temlplate <class type> { // c[l:m],c[m,r] d[l,r] void MergeSort(Type a[], int left, int right) int: i=l, // { if (1eft < right) // j=m+1, // int i = (left + right ) /2; k=l; // MergeSort(a, 1eft, i) MergeSort(a, i+1, right) while ((i<=m)&&(j<=r)) Merge(a, b, 1eft, i, right) if c[i]<=c[j] d[k++]=c[i++] copy(a, b, left, right); // else d[k++]=c[j++] } } : T(n)= d n<=1 T(n)= 2T(n/2)+cn : T(n)=θ(nlogn) // if (i>m) for (int q=j; q<=r;q++) d[k++]=c[q] else for(int q=i ;q<=m q++) d[k++]=c[q] } 46

: a[ p: r ] (1) : a (pivot) a[p: r] 3 :: a[p: q-1], a[q], a[q+1:r], a[p:q-1] a[q], a[q+1: r] a[q]; q (2) : a[p:q-1] a[q+1:r ] (3) : a[ p:q-1], a[q], a[q+1:r ] a[p:r] 47

template <class Type> void QuickSoft(Type a[], int p, int r){ if(p<r){ int q=partition(a, p, r) QuickSort(a, p, q-1); QuickSoft(a, q+1, r); } } template<class Type> int Partion(Type a[ ],int p, int r ) { int i=p; j=r+1; type x=a[p] while(true) { while(a[++i] < x) while(a[ j] > x) if (i>=j ) break; swap(a[i],a[j]); } a[p] = a[j] a[ j] = x; return j } 48

template <class Type> void randomizedquicksoft(type a[], int p, int r) { if (p<r) { int q=randomizedpartition(a, p, r) randomizedquicksort(a, p, q-1); randomizedquicksoft(a, q+1, r); }} template <class Type> int randomizedpartition(type a[], int p, int r) { int i=random( p, r) swap( a[i], a[p] ) return Partition (a,p,r) 49

2 2 Ο ( n ) ( n ) Ο O (1).................. 2 O (n logn ) ( n ) Ο O(logn) O (n logn ) O (n logn ) O (1) O (n logn ) O (n logn ) O (n ) O (k (n +m )) O (k (n +m )) O (m ) 50

2.7 : n k. : A, A1 <=A2, J, K J, K A1 K, K>J, K A2 K-J., template < class Type > Type RandomizedSelect (a[ ], int p, int r, int k) { if (p==r) return a[ p ]; int i = RandomizedPartition(a, p, r) // i j=i-p+l // A1 if ( k <= j ) return RandomizedSelect(a, p, i, k); else return RandomizedSelect(a, i + 1, r, k - j); } 51

2 (0< <1 ) O(n) 52

n n/5 5 5 n/5 select n/5 n/5 2 53

:, O(n : : r=5, n=27, a=[ 2, 6, 8, 1, 4, 10, 20, 6, 22, 11, 9, 8, 4, 3, 7, 8, 16, 11, 10, 8, 2, 14, 15, 1, 12, 5, 4 ] : [ 2, 6, 8, 1, 4 ], [10, 20, 6, 22, 11], [9,8, 4, 3, 7], [8, 16, 11, 10, 8], [2, 14, 15, 1, 12], [5 4] : [4, 11, 7, 10, 12, 4], 7, :a[1:11]=[2 6 1 4 6 4 3 2 1 5 4],a[12]=[7], a[13:27]=[8, 10, 20, 22, 11, 9, 8, 8, 16, 1l, 10, 8, 14, 15, 12] k<12 a[1:11] k=12 k>12 a[13:27] (k-12) 54

: template<classtype> Type Select(Type a[], int p, int r, int k ){ if (r-p<75) { a[p:r] return a[p+k-1] } for(int i=0;i<=(r-p-4)/5; i++) // r-p-4 n-5 a[p+5*i] a[p+5*i-4] 3 a[p+i] //, Type x=select(a, p, p+(r-p-4)/5, (r-p-4)/10); int i=partition(a,p,r,x) j=i-p+1; if (k<=j) return Select(a,p,i,k) else return Select(a,i+1,r,k-j) } 55

p3,q3 58

59 p3,q3 2 2 2 2 2 36 25 3) / (2 2) / ( )) ( ) ( ( )) ( ) ( ( d d d v y u y v x u x = + + n+1 n

6 p P2 S2 l p S2 R l p l d 6 P1 P2 S y P1 P1 P2 6 60

4 1 2 3 4 1 1 2 3 4 2 1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1 4 64

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 65

Catalan [ ] n H(n) H(n) Catalan n=5 H(5)=5 [ ] Catalan Catalan n 66

Catalan [ ] n H(n) H(n) Catalan n=5 H(5)=5 [ ] V1 V2 Vn n-3 n-3 V1Vi H(i)*H(n-i+2) Vi V3V4 Vn-1 V1 V2 V3 Vn 2 1/2 H(n)=n (1/2)H(i)*H(n-i+2) i=3,4,,n-1 (1/2) H(n)=n/2*(n-3)) H(i)*H(n-i+2) i=3,4,,n-1 H(2)=H(3)=1 H(3)=1 67

Catalan [ ] n H(n) H(n) Catalan n=5 H(5)=5 [ ], 68

//ex4.cpp #include <iostream.h> #define MAXN 100 long f(int x){ if (x==3) return(1); else return((4*x-10)*f(x-1)/(x-1)); } main(){ int n; cout<<"\nplease input N for a Catalan number:"; cin>>n; if ( (n<=maxn) && (n>=3) ) cout<<"the answer is:"<<f(n); } 69

Catalan H(2)=1 H(3)=1 H1 H2 H3 Catalan n n=22 n H2=1 Catalan Catalan 70

Catalan 1 n 71

[ ] s n s={a 1,a 2, a n }, s k s1,s2 s3 1. s i <> 2. s i s j = 3. s 1 s 2 s 3. s k =s (1<=I, j<=k, i<>j) s 1,s 2 s k s ; s n k, n k s(n, k) [ ] S 1 2 3 4 k 3 S 6 6 1 2 3 4 1 3 2 4 1 4 2 3 2 3 1 4 2 4 1 3 3 4 1 2 S k : 72

[ ] n a 1 a n k S(n k) : 1. a n k a 1 a n-1 k 1 S(n 1 k 1) ; 2. a n k a n {a 1 a n-1 k S(n 1 k) a n k k k k (n 1 k) a 1 a n k : S(n k) S(n 1 k 1)+k S(n 1 k) (n >1 k 1) 73

s(n,k) : 1. n (n 0) 0; n n k k n S(n k) 0 2. n n n 1: S(n, 1)=1 S(n, n)=1 S(n k) : S(n k) S(n 1 k 1)+k S(n 1 k) (n > k k 1) S(n k) 0 (n < k) (k 0 n) S(n k) 1 (k=1) (k n) 74

S(n k), S(n, k) long S(int n,int k){ long count; if(k=0)or(k>n) count =0 else if(k=1 k=n) count =1 else count =s(n-1,k-1)+k*s(n-1,k); return count } 75

[ ] n n n<=20 4 0 3 4 5 6 ( 4 0 3 4 5 6 ) 76

[ ] n 2 1 3 1 2. n n-1 n-1 n max=1+2+ (n-1)=n(n-1)/2, g[1..max], g[i]=0 // i g[i]=1 // i (0<=i<=max) 77

i=1,2,3 n=4 1. g[0]=1 2. (n-1)*1+0=3, g[3]=1; 3. (n-2)*2=4 4., n-2 *2+0=4 g[4]=1 (n-2)*2+1=5 g[5]=1 5. n-1 *1+3 (n-1)*1+0=3 g[3]=1 (n-1)*1+2=5 g[5]=1 (n-1)*1+3=6 g[6]=1 n=4 0 3 4 5 6 5 78

n=4 m = m-r r + r = m-r *r+r 1<=r<=m void try(int m, int j) //m j { if m>0 // for(int r=m; r<=1; r--) try(m-r, j+r*(m-r)) else g[j]:=1; // n j } 79

n 1. max=n(n-1)/2 2. g 3. g[i] try[n,0]; 4. total=0; for( i=0 ;i<= max;i++{ if( g[i]==1) total:=total+1; total i } 80

1. n 1 1 2 4 3 5 3 1 2 4 6 7 8 10 9 11 8 2 1 6 7 14 3 4 5 13 12 n=1 n=2 n=3 n=4 2 81

2. n 3 3. a b 3 5 7 9 11 13 14 12 10 8 6 4 82

4. n n 83

5. [ ] 9 9 9 3 3 9 1 9 1 2 9457379436893142312385629218 84

6. [ 85

http://acm.pku.edu.cn/judgeonline/ 1018 1050 1083 86

第2章 递归与分治策略