Advertisement
nimcap

Brilliant King Arthur's knights

Jul 23rd, 2013
128
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.35 KB | None | 0 0
  1. package com.anlak.optimization;
  2.  
  3. import java.util.Iterator;
  4. import java.util.LinkedList;
  5. import java.util.List;
  6.  
  7.  
  8. /*
  9.  * There are p knights sitting at positions [1,2,...p] at King Arthur's round
  10.  * table. In order to choose the leader, Arthur starts counting at position 1
  11.  * and dismisses every rth seated knight until only 1 knight remains. The
  12.  * remaining seated knight becomes the leader. Let C(p,r) be the integer
  13.  * position of the eventual leader when the table starts out with p knights and
  14.  * every rth seated one is dismissed. Let T =
  15.  * C(999,11)+C(121,12)+C(2,1)+C(15,16)+C(99,3). What is T? Details and
  16.  * assumptions C(4,2)=1. The knights start seated at positions 1, 2, 3, 4.
  17.  * Arthur dismisses them in this order: 2, 4, 3. The knight seated at position 1
  18.  * becomes the leader.
  19.  */
  20.  
  21. public class Brillant
  22. {
  23.     public static int c( int n, int r )
  24.     {
  25.         List<Integer> x = new LinkedList<Integer>();
  26.        
  27.         for (int i = 1; i <= n; i++)
  28.             x.add(i);
  29.        
  30.         Iterator<Integer> iter = x.listIterator(n);
  31.        
  32.         while (x.size() > 1)
  33.         {
  34.             for (int i = 0; i < r; i++)
  35.             {
  36.                 if (!iter.hasNext())
  37.                     iter = x.iterator();
  38.                 iter.next();
  39.             }
  40.            
  41.             iter.remove();
  42.         }
  43.        
  44.         return x.get(0);
  45.     }
  46.    
  47.     public static void main( String[] args )
  48.     {
  49.         System.out.println(c(999, 11) + c(121, 12) + c(2, 1) + c(15, 16) + c(99, 3));
  50.     }
  51. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement