Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.HashMap;
- public class CallsComparison {
- private static HashMap<Long, Long> memory = new HashMap<Long, Long>();
- private static HashMap<Long, Long> map = new HashMap<Long, Long>();
- public static final long LOWER_BOUND = 200_000_000_000L;
- public static final long NUMBER_OF_TRIES = 1_000L;
- public static final long UPPER_BOUND = LOWER_BOUND + NUMBER_OF_TRIES;
- private static long numCallsCoins = 0;
- private static long numCallsChanger = 0;
- public static void main(String[] args) {
- memory.put(0L, 0L);
- for (long i = LOWER_BOUND; i <= UPPER_BOUND; i++) {
- changer(i);
- }
- memory = null;
- for (long i = LOWER_BOUND; i <= UPPER_BOUND; i++) {
- coins(i);
- }
- System.out.println("changer needed " + numCallsChanger
- + " function calls");
- System.out.println("coins needed " + numCallsCoins + " function calls");
- System.out.println("the call ratio changer/coins is: "
- + ((double) numCallsChanger / (double) numCallsCoins));
- System.out.println("numCallsChanger - numCallsCoins = " + (numCallsChanger - numCallsCoins));
- }
- public static Long changer(long coin) {
- numCallsChanger++;
- if (!memory.containsKey(coin)) {
- long tmp = changer(coin / 4L) + changer(coin / 3L)
- + changer(coin / 2L);
- memory.put(coin, tmp > coin ? tmp : coin);
- }
- return memory.get(coin);
- }
- public static long coins(long n) {
- numCallsCoins++;
- if (!map.containsKey(n)) {
- map.put(n, (n > (n / 2) + (n / 3) + (n / 4) ? n : coins(n / 2)
- + coins(n / 3) + coins(n / 4)));
- }
- return map.get(n);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement