Алгоритм задачи о билетах и сдаче В кассах кинотеатра много людей стоящих в очереди. У каждого из них есть банкнота в 100, 50 или 25 долларов

Рейтинг: -3Ответов: 3Опубликовано: 25.07.2023

В кассах кинотеатра много людей, стоящих в огромной очереди. У каждого из них есть банкнота в 100, 50 или 25 долларов. Билет стоит 25 долларов. Вася в настоящее время работает клерком. Он хочет продать билет каждому человеку в этой очереди. Может ли Вася продать каждому билет и отдать сдачу, если у него изначально нет денег и он продает билеты строго в том порядке, в котором люди следуют в очереди?

Верните true, если Вася может продать каждому билет и отдать сдачу, в противном случае верните false.

Может ли Вася продать каждому билет и отдать сдачу?

Условия:

  • принимает массив из купюр(banknotesArray) номиналом 25, 50, 100.

  • возвращает(return) true если возможно выдать всем сдачу, или false если нет.

function isPossibleToGiveChange(banknotesArray) {

//Your code here

}

//Примеры вызова:

isPossibleToGiveChange([25, 25, 50]); // => true

isPossibleToGiveChange([25, 100]); // => false

isPossibleToGiveChange([25, 25, 50, 100]); // => true

isPossibleToGiveChange([25, 50, 100]); // => false

isPossibleToGiveChange([‘25’, ‘25’, ‘50’, ‘100’]); // => true

isPossibleToGiveChange([‘25’, ‘50’, ‘100’]); // => false

javascript массивы функции
Источник: Stack Overflow на русском

Ответы

▲ 2

Предложу вот такой вариант решения этой задачки...

function test(arr) {
  const t = 25
  const am = []
  for (let i = 0; i < arr.length; i++) {
    let val = arr[i] - t
    // сумма совпала со стоимостью билета
    if (!val) {
      // добавили полученную сумму
      am.push(arr[i])
      continue
    }
    // сортируем полученные деньги по убыванию
    am.sort((a, b) => b - a)
    let ok = false
    const a = []
    // проверяем можемли дать сдачу и запоминаем какими именно купюрами
    for (let i = 0; i < am.length; i++) {
      const v = val - am[i]
      if (v < 0) continue
      a.push(i)
      if (!v) {
        ok = true
        break
      }
      val = v
    }
    // не смогли дать сдачу
    if (!ok) return false
    // удаляем купюры которые отдали как сдачу
    for (let i = a.length -1; i > -1 ; i--) {
      am.splice(a[i], 1)
    }
    // добавили полученную сумму
    am.push(arr[i])
  }
  return true
}

// Примеры вызова:
console.info(test([ 25, 25, 50 ])); // true
console.info(test([ 25, 100 ])); // => false
console.info(test([ 25, 25, 50, 100 ])); // => true
console.info(test([ 25, 50, 100 ])); // => false
console.info(test([ 25, 25, 50, 100 ])); // => true
console.info(test([ 25, 50, 100 ])); // => false

console.info(test([ 25, 50, 25, 50, 25, 100 ])); // => true
console.info(test([ 25, 25, 50, 50, 100 ])); // => false

▲ 1

Интересно было подумать, мое решение было бы таким:

  1. Мы заводим переменную (money), в которой храним наши деньги.
  2. Мы проходим циклом по нашим платежам.
    1. Мы отнимаем от нашего платежа стоимость билета.
    2. Мы отнимаем от наших денег результат полученный выше.
    3. Проверяем сколько у нас осталось денег, если мы ушли в минус - мы не можем дать сдачу и возвращает false.
    4. Если же сдача у нас имеется - мы прибавляем к нашим деньгам стоимость билета.
  4. Если же мы дошли до финального return, значит сдачу везде мы могли выдать - возвращаем true.

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

const TICKET_COST = 25;

function isPossibleToGiveChange(banknotesArray)
{
    let money = 0;

    for (let i = 0; i < banknotesArray.length; i++)
    {
        money -= banknotesArray[ i ] - TICKET_COST;
        if (money < 0)
        {
            return false;
        }

        money += TICKET_COST;
    }

    return true;
}

// Примеры вызова:

console.info(isPossibleToGiveChange([ 25, 25, 50 ])); // true
console.info(isPossibleToGiveChange([ 25, 100 ])); // => false
console.info(isPossibleToGiveChange([ 25, 25, 50, 100 ])); // => true
console.info(isPossibleToGiveChange([ 25, 50, 100 ])); // => false
console.info(isPossibleToGiveChange([ 25, 25, 50, 100 ])); // => true
console.info(isPossibleToGiveChange([ 25, 50, 100 ])); // => false
.as-console-wrapper { max-height: 100% !important; }

▲ 1
  1. Делаем словарь купюр, которые впоследствии используем для сдачи
  2. Учитывая, что для сдачи с 50 всего один вариант, а для сдачи со 100 - два варианта, можно так и прописать в коде. Комментарии в коде.

function isPossibleToGiveChange(banknotesArray) {
    cb = {100: 0, 50: 0, 25: 0}; // словарь купюр
    for (let i = 0; i < banknotesArray.length; i++) {
        x = parseInt(banknotesArray[i]);
        if (x === 50) if (cb[25]) cb[25]--; else return false; // если сдачи с 50 нет, то выход с false
        if (x === 100) {
            if (cb[50] && cb[25]) { // проверяем первый вариант сдачи - 50+25
                cb[50]--;   // убираем купюру 50 из словаря
                cb[25]--;   // убираем купюру 25 из словаря
            } else if (cb[25] > 2) // проверяем второй вариант сдачи - 25+25+25
                cb[25] -= 3; // убираем 3 купюры 25 из словаря
            else return false; // если сдачи с 100 нет, то выход с false
        }
        cb[x]++; // если смогли сдать сдачу, кладем полученную купюру в словарь
    }
    return true; // если смогли сдать сдачу на все купюры, то возвращаем true
}

//Примеры вызова:

[[25, 25, 50],
    [25, 100],
    [25, 25, 50, 100],
    [25, 50, 100],
    ["25", "25", "50", "100"],
    ["25", "50", "100"]
].forEach(item => console.log(item + ' => ' + isPossibleToGiveChange(item)));