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. }