VPF::Способы формирования числа - Форум программистов

noyew

Дата 18.3.2014, 18:03 (ссылка)

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

Загрузка ...

Новичок

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

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

1

Это сообщение отредактировал(а) noyew - 19.3.2014, 18:49

Pawl

Дата 18.3.2014, 18:30 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата(noyew @ 18.3.2014, 18:03

)

Дано натуральное число n≤99. Получить все способы формирования n с помощью чисел 1, 5, 10 и 20 сложением.

Эти числа можно использовать только по 1 разу или по многу раз? я имею ввиду, возможен ли вариант представления 99 как суммы 99-то единиц?

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

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

noyew

Дата 18.3.2014, 22:45 (ссылка)

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

Загрузка ...

Новичок

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

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

Pawl, да, возможен

Pawl

Дата 19.3.2014, 07:36 (ссылка)

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

Загрузка ...

Опытный

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

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

Код


import java.util.HashMap;
import java.util.LinkedList;
import java.util.ArrayList;

public class Coin {
    private int [] coins = {1, 5, 10, 20};
    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 = 99;
        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());
    }
}

Вывод:

Код


{1=99}
{5=1, 1=94}
{5=2, 1=89}
{5=3, 1=84}
{1=79, 5=4}
{1=74, 5=5}
{5=6, 1=69}
{1=64, 5=7}
{1=59, 5=8}
{5=9, 1=54}
...
всего 250 комбинаций

слева от знакак равенства - число, справа - сколько раз оно может встречаться.

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

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

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