This week only. Pastebin PRO Accounts Christmas Special! Don't miss out!Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Mar 6th, 2013  |  syntax: Java  |  size: 1.42 KB  |  views: 36  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. import java.util.HashMap;
  2.  
  3. public class SpeedComparison {
  4.        
  5.         private static HashMap<Long, Long> memory = new HashMap<Long, Long>();
  6.         private static HashMap<Long, Long> map = new HashMap<Long, Long>();
  7.         public static final long LOWER_BOUND = 10_000_000_000L;
  8.         public static final long UPPER_BOUND = 10_001_000_000L;
  9.        
  10.        
  11.         public static void main(String[] args) {
  12.                 memory.put(0L, 0L);
  13.                 long time1 = System.currentTimeMillis();
  14.                 for(long i = LOWER_BOUND; i <= UPPER_BOUND; i++){
  15.                         changer(i);
  16.                 }
  17.                 long time2 = System.currentTimeMillis();
  18.                 for(long i = LOWER_BOUND; i <= UPPER_BOUND; i++){
  19.                         coins(i);
  20.                 }
  21.                 long time3 = System.currentTimeMillis();
  22.                
  23.                 System.out.println("changer needed " + (time2 - time1) + " milliseconds");
  24.                 System.out.println("coins needed " + (time3 - time2) + " milliseconds");
  25.                 double changerTime = (time2 - time1);
  26.                 double coinsTime = (time3 - time2);
  27.                 System.out.println("the speed ratio changer/coins is: " + (changerTime/coinsTime));
  28.         }
  29.  
  30.  
  31.         public static Long changer(long coin) {
  32.                 if (!memory.containsKey(coin)){
  33.                         long tmp = changer(coin/4L) + changer(coin/3L) + changer(coin/2L);
  34.                         memory.put(coin, tmp > coin ? tmp : coin);
  35.                 }
  36.                
  37.                 return memory.get(coin);
  38.         }
  39.        
  40.         public static long coins(long n) {
  41.                 if (!map.containsKey(n)) {
  42.                         map.put(n, (n > (n / 2) + (n / 3) + (n / 4) ? n : coins(n / 2)
  43.                                         + coins(n / 3) + coins(n / 4)));
  44.                 }
  45.                 return map.get(n);
  46.         }
  47.  
  48. }
clone this paste RAW Paste Data