VPF::[java] обмен монет - Форум программистов

CrasyMen

Дата 5.10.2013, 13:58 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 264
Регистрация: 19.12.2006

Репутация: нет
Всего: 3

Допустим есть такие номиналы монет - 1,2,5,10,25,50.
1 монету можно разменять только одним способом - {1}
2 - двумя способами {1 + 1, 2}
5 - 4 {1 + 1 + 1 + 1 + 1, 1 + 1 + 1 + 2, 1 + 2 + 2, 5}
......
Сколькими различными способами можно разменять доллар (100 центов)?

Метод должен возвращать количество вариантов в зависимости от входного параметра.

--------------------

Человек просто обязан ошибаться, раз другие учатся на его ошибках.
[color=skyblue]Хочу сменить ник и сменю как только дадут такую возможность.[/color]

CrasyMen

Дата 5.10.2013, 17:39 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 264
Регистрация: 19.12.2006

Репутация: нет
Всего: 3

Работает, но пока не все тесты проходит

Код


import java.util.List;

import static org.junit.Assert.*;
import org.junit.Test;

public class CoinsCounterTest {

  @Test
  public void test0() {
    List<String> options = CoinsCounter.getOptions(0);
    assertEquals(0, options.size());
  }

  @Test
  public void test1() {
    List<String> options = CoinsCounter.getOptions(1);
    assertEquals(1, options.size());
    assertEquals("1", options.get(0));
  }

  @Test
  public void test2() {
    List<String> options = CoinsCounter.getOptions(2);
    assertEquals(2, options.size());
    assertTrue(options.contains("1+1"));
    assertTrue(options.contains("2"));
  }

  @Test
  public void test5() {
    List<String> options = CoinsCounter.getOptions(5);
//    assertEquals(4, options.size());
    assertTrue(options.contains("1+1+1+1+1"));
    assertTrue(options.contains("2+2+1"));
    assertTrue(options.contains("5"));
    
    assertTrue(options.contains("2+1+1+1"));
  }

  @Test
  public void test14() {
    List<String> options = CoinsCounter.getOptions(14);
//    assertEquals(4, options.size());
    assertTrue(options.contains("1+1+1+1+1+1+1+1+1+1+1+1+1+1"));
    assertTrue(options.contains("2+2+2+2+2+2+2"));
    assertTrue(options.contains("5+5+2+2"));
    assertTrue(options.contains("10+2+2"));

    assertTrue(options.contains("5+2+2+2+2+1"));
    assertTrue(options.contains("5+2+2+2+1+1+1"));
    assertTrue(options.contains("5+2+2+1+1+1+1+1"));
    assertTrue(options.contains("5+2+1+1+1+1+1+1+1"));
    assertTrue(options.contains("5+1+1+1+1+1+1+1+1+1"));
  }
}

Код


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CoinsCounter {
  private static List<Integer> coins = Arrays.asList(50, 25, 10, 5, 2, 1);

  public static List<String> getOptions(int sum) {
    List<String> result = new ArrayList<String>();

    for (int coin : coins) {
      result.addAll(check(sum, coin));
    }

    return result;
  }

  private static List<String> check(int sum, int coin) {
    List<String> result = new ArrayList<String>();

    String option = "";
    if (coin > 0) {
      int count = calculate(coin, sum);
      if (count > 0) {
        option = join(coin, count);
        if (count * coin < sum) {
          for (String item : getOptions(sum - (count * coin))) {
            result.add(option + "+" + item);
          }
        } else {
          if (!option.isEmpty()) {
            result.add(option);
          }
        }
      }
    }
    return result;
  }

  public static int calculate(int coin, int sum) {
    return sum / coin;
  }

  private static String join(int coin, int count) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < count; i++) {
      sb.append("+").append(coin);
    }
    if (sb.length() > 0) {
      sb.deleteCharAt(0);
    }

    return sb.toString();
  }
}

--------------------

Pawl

Дата 5.10.2013, 18:31 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 649
Регистрация: 22.4.2008
Где: Витебск

Репутация: 14
Всего: 28

Код


/** прграмма, выводящая на экран все возможные количества монет заданого достоинства так, чтобы они
 * составляли определенную сумму денег
 */
import java.util.HashMap;
import java.util.LinkedList;
import java.util.ArrayList;

public class Coin {
    private int [] coins = {1, 2, 5, 10, 25, 50};
    private LinkedList<Integer> moneys = new LinkedList<>();
    private HashMap<Integer, Integer> list = new HashMap<>();
    private ArrayList<HashMap<Integer, Integer>> summs = new ArrayList<>();
    private int count = 0;

    public ArrayList<HashMap<Integer, Integer>> calc(int s) {
        if (s < 0) {
            count--;
            return null;
        }

        if (s == 0) {
            for (int i = 0; i < count; i++) {
                if (!list.containsKey(moneys.get(i))) {
                    list.put(moneys.get(i), 1);
                } else {
                    list.put(moneys.get(i), list.get(moneys.get(i)) + 1);
                }
            }
            if (!summs.contains(list)) {
                summs.add(new HashMap<Integer, Integer>(list));
            }
            
            list.clear();
            count--;
            return summs;
        }

        for(int i = 0; i < coins.length; i++) {
            if (count == 0 || moneys.get(count - 1) >= coins[i]) {
                if(moneys.size() > count) {
                    moneys.set(count, coins[i]);
                } else {
                    moneys.add(count, coins[i]);
                }
                count++;
                calc(s - coins[i]);
            }
        }
        count--;
        return summs;
    }

    public static void main(String ...args) {
        int s = 5;
        Coin c = new Coin();
        ArrayList<HashMap<Integer, Integer>> coin = c.calc(s);
        for (HashMap<Integer, Integer> cc : coin) {
            System.out.println(cc);
        }
        System.out.println(coin.size());
    }
}

--------------------

В действительности всё совсем не так, как на самом деле

CrasyMen

Дата 5.10.2013, 19:09 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 264
Регистрация: 19.12.2006

Репутация: нет
Всего: 3

Pawl, большое спасибо. Лови плюсик в репу)

--------------------

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »