Java Reference
In-Depth Information
1 /**
2 * Recursively construct a perfectly balanced BinarySearchTreeWithRank
3 * by repeated insertions in O( N log N ) time.
4 * t should be empty on the initial call.
5 */
6 public static void buildTree( BinarySearchTreeWithRank<Integer> t,
7 int low, int high )
8 {
9 int center = ( low + high ) / 2;
10
11 if( low <= high )
12 {
13 t.insert( center );
14
15 buildTree( t, low, center - 1 );
16 buildTree( t, center + 1, high );
17 }
18 }
19
20 /**
21 * Return the winner in the Josephus problem.
22 * Search tree implementation.
23 */
24 public static int josephus( int people, int passes )
25 {
26 BinarySearchTreeWithRank<Integer> t =
27 new BinarySearchTreeWithRank<Integer>( );
28
29 buildTree( t, 1, people );
30
31 int rank = 1;
32 while( people > 1 )
33 {
34 rank = ( rank + passes ) % people;
35 if( rank == 0 )
36 rank = people;
37
38 t.remove( t.findKth( rank ) );
39 people--;
40 }
41
42 return t.findKth( 1 );
43 }
figure 13.3
An O ( N log N ) solution of the Josephus problem
 
Search WWH ::




Custom Search