Алгоритм изменения монет JS - PullRequest
Новая
       36

Алгоритм изменения монет JS

0 голосов
/ 09 декабря 2018

Я пытался найти решение для этого алгоритма в течение 3-4 дней, но, похоже, ничего не работает, и доступные решения для меня немного более продвинуты.Это должно быть решено только с помощью условных выражений, поэтому нет рекурсии или динамического программирования.

Мне нужно определить наименьшее количество монет, необходимое для внесения изменений, с учетом следующих номиналов: 1, 0,5, 0,2, 0,1, 0,05, 0,02 и 0,01.

Вводится следующее:

Цена товара

Сумма, уплаченная клиентом

Текущие идеи: 

let price = +gets();
let paidSum = +gets();
//gets is used to accept number input
let change = paidSum - price;

Я подумал, что мог бы использовать Math.floor для выделения целочисленной частии вычесть это, но тогда я понятия не имею, что делать с оставшейся суммой.

По модулю будет работать, чтобы проверить, содержит ли оставшаяся сумма какое-либо из оставшихся значений для изменения, а затем снова вычитать, пока я не достигну нуля?

Я понимаю, что это не лучший сформулированный вопрос, ноЯ в растерянности, и я выполнил все остальные задачи, кроме этого.Благодаря.

Ответы [ 2 ]

0 голосов
/ 07 марта 2019 
var coins;
var coinArray = {};
var output = {};


/* Method to get coin value without decimal point - it is required because 
* javascript will consider 5.6 as 6 if we do Math.round()
*/
function getRoundFigureCoinValue(x) {
    return (x * 10 - ((x * 10) % 10)) / 10;
}

// Method to calculate possible combination of coins
function calculateCoins(input) {
    let largestPossibleCoin = 1;

    if (input) {
        coins.forEach((x) => {
            if (input >= x) {
                largestPossibleCoin = x;
            }
        });
        let remainingCents = input % largestPossibleCoin;
        output[largestPossibleCoin] = getRoundFigureCoinValue(
            (input / largestPossibleCoin).toFixed(1)
        );
        if (remainingCents && input > 1) {
            calculateCoins(remainingCents);
        }

        return largestPossibleCoin;
    }
}

// Method to be called to get output.
function calculatePossibleCoinCombinations(value) {
    if (isNaN(value) || +value <= 0) {
        console.log('Invalid input');
        return;
    } else {
        console.log('Possible combinations are:')
        value = +value;
    }

    coins = [1, 5, 10, 25];
    while (coins.length) {
        let largestPossibleCoin = calculateCoins(value) || 0;
        let outputString = '';
        coins = coins.filter((x) => x < largestPossibleCoin);
        Object.keys(output).forEach((key) => {
            outputString += `${output[key]} - ${key} cents; `;
        })
        console.log(outputString);
        output = {};
    }
}


/*
Sample inputs:
 calculatePossibleCoinCombinations('89');
 calculatePossibleCoinCombinations(10);
 calculatePossibleCoinCombinations(0);
 calculatePossibleCoinCombinations('someString');
 calculatePossibleCoinCombinations(-10)
*/
0 голосов
/ 09 декабря 2018

С указанными вами номиналами проблема проще, чем общая задача создания изменений .В этом конкретном случае мы можем быть уверены, что использование наибольшего номинала, не превышающего сумму, которую нужно заплатить, всегда приводит к оптимальному решению.

Таким образом, нет необходимости в рекурсии или динамическом программировании.Подойдет простой цикл.

Здесь я буду игнорировать дополнительный «слой» получения цены счета и суммы, которую платит клиент.В конце концов, единственное, что имеет значение, это сумма изменения, которую нужно вернуть клиенту.Таким образом, этот фрагмент запрашивает сумму изменения и возвращает монеты, которые должны быть указаны как изменение. 

function getChange(amount) {
    amount *= 100; // Convert to number of cents
    var denominations = [1, 2, 5, 10, 20, 50, 100]; // cents
    var result = [];
    while (amount > 0) {
        var coin = denominations.pop(); // Get next greatest coin
        var count = Math.floor(amount/coin); // See how many times I need that coin
        amount -= count * coin; // Reduce the amount with that number of coins
        if (count) result.push([coin/100, count]); // Store count & coin
    }
    return result;
}

// I/O management

change.oninput = function () {
    var coins = getChange(this.value);
    result.textContent = coins.map(([coin, count]) => `${count} x $${coin}`).join(" + ");
};
To be paid to customer: <input id="change">
<div>Coins to pay: <span id="result"></span></div>
...