Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Mar 6th, 2013  |  syntax: Java  |  size: 1.56 KB  |  views: 32  |  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 CallsComparison {
  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 = 200_000_000_000L;
  8.         public static final long NUMBER_OF_TRIES = 1_000L;
  9.         public static final long UPPER_BOUND = LOWER_BOUND + NUMBER_OF_TRIES;
  10.         private static long numCallsCoins = 0;
  11.         private static long numCallsChanger = 0;
  12.  
  13.         public static void main(String[] args) {
  14.                 memory.put(0L, 0L);
  15.                 for (long i = LOWER_BOUND; i <= UPPER_BOUND; i++) {
  16.                         changer(i);
  17.                 }
  18.                 memory = null;
  19.                 for (long i = LOWER_BOUND; i <= UPPER_BOUND; i++) {
  20.                         coins(i);
  21.                 }
  22.  
  23.                 System.out.println("changer needed " + numCallsChanger
  24.                                 + " function calls");
  25.                 System.out.println("coins needed " + numCallsCoins + " function calls");
  26.                 System.out.println("the call ratio changer/coins is: "
  27.                                 + ((double) numCallsChanger / (double) numCallsCoins));
  28.                 System.out.println("numCallsChanger - numCallsCoins = " + (numCallsChanger - numCallsCoins));
  29.         }
  30.  
  31.         public static Long changer(long coin) {
  32.                 numCallsChanger++;
  33.                 if (!memory.containsKey(coin)) {
  34.                         long tmp = changer(coin / 4L) + changer(coin / 3L)
  35.                                         + changer(coin / 2L);
  36.                         memory.put(coin, tmp > coin ? tmp : coin);
  37.                 }
  38.  
  39.                 return memory.get(coin);
  40.         }
  41.  
  42.         public static long coins(long n) {
  43.                 numCallsCoins++;
  44.                 if (!map.containsKey(n)) {
  45.                         map.put(n, (n > (n / 2) + (n / 3) + (n / 4) ? n : coins(n / 2)
  46.                                         + coins(n / 3) + coins(n / 4)));
  47.                 }
  48.                 return map.get(n);
  49.         }
  50. }