Спасибо за интересную задачу! В условии вроде бы ясно звучало, что запрашиваемую сумму банкомат всегда может выдать (0:55), поэтому проверку на корректность входных данных не проводил (по принципу YAGNI). Та и в реальном проекте валидацию входных данных должна по идее осуществлять отдельная функция (согласно принципу SRP). Мне показалось, что в задании просилось найти не массив банкнот, а минимальное их количество, поэтому решил так: const iWantToGet = amount => { const banknotes = [100, 50, 20, 10]; let total = 0; for (const note of banknotes) { if (amount === 0) break; total += Math.floor(amount / note); amount %= note; } return total; }; ...если не очень важно константное время работы алгоритма, то можно и так: const iWantToGet = amount => { const banknotes = [100, 50, 20, 10]; let total = 0; for (const note of banknotes) { while (amount >= note) { amount -= note; total++; } } return total; }; ...а если на выходе таки нужен массив купюр, то можно переписать эдак: const iWantToGet = amount => { const banknotes = [100, 50, 20, 10]; let cash = []; for (const note of banknotes) { while (amount >= note) { amount -= note; cash.push(note); } } return cash; };
да, нужен массив банкнот, а не их количество. Я объект с их номиналами вывел. В каком виде это возвращать, озвучено вроде не было в видео :) Отличное решение. P.S. Эту задачу можно решить за O(1) если выводить именно объект.
Большое спасибо за видео) Я слышал еще про 3 версию этой задачи, где купюры не канонические(не 50 100 200 500, а, например 60 50 30 40) и ограничены в количестве. Будет очень классно если будет хотя бы теория по решению этой задачи.
Дима Хван окей, а какой тогда 2-ой вариант задачи? А то мы собственно на такой вот и готовили видео. Нашли 2 варианта: легкий (традиционный номинал и безлим кеша) и посложнее (количество банкнот лимитировано и они нестандартного номинала).
Сергей, большое спасибо за видео. Классные разборы =). Продолжай в том же духе! Из условия выбивается, но с возвращаемым объектом-счетчиком как-то лаконичнее смотрится. Особенно при тестах на больших числах. Решил через .reduce() и остаток от деления. Однострочечникам зайдет))): function iWantToGet(amountRequired) { const availableNotes = [100, 50, 20, 10]; if (amountRequired (res[item] = Math.floor(amountRequired / item), amountRequired = amountRequired % item, res), {}) }
Большое спасибо за разбор, я использовал остаток от деления. Вот мое решение: function iWantToGet(ammountRequired){ let arr = [100, 50, 20, 10] let res = [] for(let i = 0; i < arr.length; i++){ a = Math.trunc(ammountRequired/arr[i]); while (a >0) { res.push(arr[i]) a--; } ammountRequired = ammountRequired%arr[i]; } return res; } console.log(iWantToGet(270))
Я с этой стороны зашёл) function bank(val) { const result ={}; const bills = [100, 50, 20, 10]; for (const bill of bills) { if (!Math.floor(val/bill)) { continue } result[bill] = Math.floor(val/bill); val %= bill; if (!val) {break} } return result } console.log(bank(160))
Вот так у меня вышло. Сейчас посмотрю ваше видео и если что оптимизирую function iWantToGet(amount) { const notes = [100, 50, 20, 10] if (amount < 10) { return false } let value = new Map() let back = 0 let i = 0 while (amount !== 0) { if (notes[i] amount) { back = amount value.set('change', back) return value } i++ } } return value }
То чувство, когда все хочется решать через reduce :) Мой вариант на рекурсии codesandbox.io/s/kind-shape-edwfo?file=/src/index.js Не стал делать дополнительную проверку на запрашиваемый ноль, функция и так вернет нужную мне структуру в этом случае
@@olduniverse9270 У меня есть смутное подозрение, что не зря банкноты делают именно таким номиналом, чтобы они не заходили за "вторую половину". Но если взять выдуманные 90, то тогда функция и правда округлит слишком грубо, когда могла бы выдать полностью всю сумму.
Андрей классно вышло! Тут как раз тот случай когда можно написать упрощенно все, учитывая текущие условия задачи. С другими условиями будет уже другая совсем задача и соотвественно алгоритм решения будет уже другой.
Алгоритм находит решение не всегда. Например: в банкомате купюры номиналом 50 и 20, а запрашиваемая сумма 60. Сумму можно выдать 3мя двадцатками, однако алгоритм сперва вычтет из 60 50, и потом не сможет реализовать оставшиеся 10 двадцатками.
делал по вашему примеру и не понял почему работает так: если мы вводим число 300, на 1 итерации берется 100(i = 0), это удовлетворяет нашему условию-добавляем купюру 100, выполнился шаг(i++). Следующая итерация (i = 1) - это 50, также удовлетворяет нашему условию(while (amountRequired - note >= 0)) и вроде бы все так, но почему то эта купюра не добавляется!? Все выводы случились на первой итерации. Почему так?Объясните плиз
если мы хотим получить 300 то делаем следующее 1) итерируемся по номиналам купюр. Первый номинал 100. 2) заходим в цикл while и пробуем взять столько купюр этого достоинства сколько можно - до тех пор пока количесвта не станет меньше либо равно нулю. то есть мы от 300 отняли 100. Остаток больше нуля. Еще раз снимаем 100. все еще остаток больше 0. Еще раз снимаем 100. вот теперь остаток 0. и мы закончили выдачу. Если бы заказали выдачу 280: 1) в цикле выбираем номинал 100 2) пробуем снять 100. Получилось остаток 180 > 0 3) значит снимаем еще 100. Остаток 80. 4) пробуем снять еще 100. остаток -20. Значит эта операция не проходит и мы выходим из while. 5) итерируемся на следующий номинал 50 6) пробуем снять 50. остаток 30. 7) пробуем снять еще 50. остаток -20 - значит операция не подходит, выходим из while 8) выбираем следующий номинал 20 9) пробуем снять 20. остаток 10 10) еще пробуем снять 20. остаток -10 - - значит операция не подходит, выходим из while 11) выбираем следующий номинал 10 12)пробуем снять 10. остаток 0. 13) завершаем программу и возвращаем массив снятых номиналов
Что то мое решение ни на чье не похоже... Я что то делаю не так? Или мб я как то не правильно понял задание? function iWantToGet(money = 0) { bills = [100, 50, 20, 10] sumBill = 0 bills.forEach((bill) => { if (money > 0) { countMoney = parseInt(money/bill) if (countMoney !== 0) console.log('Купюр по ' + bill + 'рублей' + ' - ' + countMoney) sumBill += countMoney money = money%bill } }) console.log('Всего купюр - ' + sumBill) }
вообще, алгоритм не универсальный и работает далеко не на всех availableNotes. пример, availableNotes = [5,3,2] iWantToGet(14) вернет [5,5,3], а хотелось бы [5,5,2,2], т.к у банкомата есть возможность выдать всю сумму
Данный алгоритм работает только для определенного набора банкнот. Об этом я сказал в видео, и это же написано в условии. То о чем вы пишите, это уже другая задача. Вот тут ее решение: ua-cam.com/video/x-BsFzVadKM/v-deo.html Приятного просмотра!
@@frontendscience во-первых, спасибо за обратную связь и ваш труд. "удобные" номиналы и "алгоритм работает только для определенного набора банкнот" - это не равные утверждения, второе не дает двусмысленности, в отличие фразы "удобные" номиналы. просто я из тех, кто ставит на паузу и пытается сперва сам решить, отсюда и уточнение, возникшее при самостоятельном решении. а за разборы и объяснения ОГРОМНОЕ СПАСИБО, у вас прекрасно получается рассказать просто о сложном.
@@IlyaShaforostoff Благодарю. Рад, что Вам нравится! Так и не понял, в чем вопрос с купюрами. Я прямо копирую цитату из описания: "В этом видео мы рассмотрим более простую версию задачи: у нас будет неограниченное количество банкнот в банкомате, а также "удобные" номиналы, доступные к выдаче: 100, 50, 20, 10.". Помимо слова "удобные" даже привел конкретные примеры чтобы проиллюстрировать наиболее ходовые купюры. И в самом видео прям с 15 секунды я объяснял, что у задачи есть много вариантов и сразу предупредил о том, что снял несколько видео - сегодняшнее по самому легкому варианту этой задачи, и далее описание условий. 1:18 "и последнее обязательное условие к этой задаче...." про номиналы купюр, которыми располагает банкомат. Это круто, что Вы нажимаете на паузу и решаете самостоятельно, но условие не забывайте дослушать до конца.)
Решение у автора слабое. Данный алгоритм работает только для указанных номиналов - 100, 50, 20, 10. Если номиналы будут другими, то такой жадный алгоритм может выдавать неправильный ответ с точки зрения первого условия - минимальности выдаваемых банкнот. Например, если номиналы 100, 90, 20 и запрашивается 180, то алгоритм автора выдаст - 100, 20, 20, 20, 20 т. е. 5 банкнот, тогда как оптимальным является 90, 90 - 2 банкноты.
Мое решение: const iWantToGet = ammountRequired => { if (ammountRequired % 10) return 'Enter an amount in multiples of 10' if (ammountRequired { let noteCount = ammountRequired / note for (let i = 1; i
function iWantToGet(ammountRequired) { const result = [] const banknotes = [100, 50, 20, 10] let rest = ammountRequired if (rest > 0) { for (let index = 0; index < banknotes.length; index++) { while (banknotes[index]
![Lp. Сердце Вселенной #60 РОЖДЕНИЕ ЛОЛОЛОШКИ [Финал] • Майнкрафт](http://i.ytimg.com/vi/YoR0pAV9FVQ/mqdefault.jpg)
Спасибо за интересную задачу!
В условии вроде бы ясно звучало, что запрашиваемую сумму банкомат всегда может выдать (0:55), поэтому проверку на корректность входных данных не проводил (по принципу YAGNI). Та и в реальном проекте валидацию входных данных должна по идее осуществлять отдельная функция (согласно принципу SRP).
Мне показалось, что в задании просилось найти не массив банкнот, а минимальное их количество, поэтому решил так:
const iWantToGet = amount => {
const banknotes = [100, 50, 20, 10];
let total = 0;
for (const note of banknotes) {
if (amount === 0) break;
total += Math.floor(amount / note);
amount %= note;
}
return total;
};
...если не очень важно константное время работы алгоритма, то можно и так:
const iWantToGet = amount => {
const banknotes = [100, 50, 20, 10];
let total = 0;
for (const note of banknotes) {
while (amount >= note) {
amount -= note;
total++;
}
}
return total;
};
...а если на выходе таки нужен массив купюр, то можно переписать эдак:
const iWantToGet = amount => {
const banknotes = [100, 50, 20, 10];
let cash = [];
for (const note of banknotes) {
while (amount >= note) {
amount -= note;
cash.push(note);
}
}
return cash;
};
да, нужен массив банкнот, а не их количество. Я объект с их номиналами вывел. В каком виде это возвращать, озвучено вроде не было в видео :)
Отличное решение.
P.S. Эту задачу можно решить за O(1) если выводить именно объект.
Большое спасибо за видео) Я слышал еще про 3 версию этой задачи, где купюры не канонические(не 50 100 200 500, а, например 60 50 30 40) и ограничены в количестве. Будет очень классно если будет хотя бы теория по решению этой задачи.
Дима Хван окей, а какой тогда 2-ой вариант задачи? А то мы собственно на такой вот и готовили видео. Нашли 2 варианта: легкий (традиционный номинал и безлим кеша) и посложнее (количество банкнот лимитировано и они нестандартного номинала).
Пока не смотрел твоего решения, но у меня получилось так:
function iWantToGet(ammountRequired) {
const values = [100, 50, 20, 10];
const result = {};
for (let item of values) {
if (ammountRequired >= item) {
result[item] = Math.floor(ammountRequired / item);
ammountRequired %= item;
}
if (ammountRequired === 0) {
break;
}
}
return result
};
Благодарю, что поделился. Хорошо вышло
Сергей, большое спасибо за видео. Классные разборы =). Продолжай в том же духе!
Из условия выбивается, но с возвращаемым объектом-счетчиком как-то лаконичнее смотрится. Особенно при тестах на больших числах. Решил через .reduce() и остаток от деления. Однострочечникам зайдет))):
function iWantToGet(amountRequired) {
const availableNotes = [100, 50, 20, 10];
if (amountRequired
(res[item] = Math.floor(amountRequired / item), amountRequired = amountRequired % item, res), {})
}
Спасибо - классное и простое решение
Благодарю за поддержку! Рад что было полезно!
Большое спасибо за разбор, я использовал остаток от деления. Вот мое решение:
function iWantToGet(ammountRequired){
let arr = [100, 50, 20, 10]
let res = []
for(let i = 0; i < arr.length; i++){
a = Math.trunc(ammountRequired/arr[i]);
while (a >0) {
res.push(arr[i])
a--;
}
ammountRequired = ammountRequired%arr[i];
}
return res;
}
console.log(iWantToGet(270))
Благодарю за решение! Вышло хорошо
Я с этой стороны зашёл)
function bank(val) {
const result ={};
const bills = [100, 50, 20, 10];
for (const bill of bills) {
if (!Math.floor(val/bill)) {
continue
}
result[bill] = Math.floor(val/bill);
val %= bill;
if (!val) {break}
}
return result
}
console.log(bank(160))
Отлично вышло!
Спасибо, что поделились
Вот так у меня вышло. Сейчас посмотрю ваше видео и если что оптимизирую
function iWantToGet(amount) {
const notes = [100, 50, 20, 10]
if (amount < 10) {
return false
}
let value = new Map()
let back = 0
let i = 0
while (amount !== 0) {
if (notes[i] amount) {
back = amount
value.set('change', back)
return value
}
i++
}
}
return value
}
а почему через остаток от деления никто не предлагает решать? а массив составляет через Array(size).fill(note), потом делаем concat'ы например
То чувство, когда все хочется решать через reduce :) Мой вариант на рекурсии codesandbox.io/s/kind-shape-edwfo?file=/src/index.js Не стал делать дополнительную проверку на запрашиваемый ноль, функция и так вернет нужную мне структуру в этом случае
ну для простого вариант неплохой. Теперь попробуй запросить 180, когда есть банкноты по 100 и 90
@@olduniverse9270 У меня есть смутное подозрение, что не зря банкноты делают именно таким номиналом, чтобы они не заходили за "вторую половину". Но если взять выдуманные 90, то тогда функция и правда округлит слишком грубо, когда могла бы выдать полностью всю сумму.
@@olduniverse9270 Такой вариант мы будем решать в следующий раз ;)
@@Андрей-й9ц6я такой вариант задачи - ждите через неделю )
Андрей классно вышло! Тут как раз тот случай когда можно написать упрощенно все, учитывая текущие условия задачи. С другими условиями будет уже другая совсем задача и соотвественно алгоритм решения будет уже другой.
А как это сделать на C#?
Алгоритм находит решение не всегда. Например:
в банкомате купюры номиналом 50 и 20, а запрашиваемая сумма 60. Сумму можно выдать 3мя двадцатками, однако алгоритм сперва вычтет из 60 50, и потом не сможет реализовать оставшиеся 10 двадцатками.
Это уже условия другой задачи. Вот ее решение: ua-cam.com/video/x-BsFzVadKM/v-deo.html
На будущее смотрите внимательно условия - полезный навык 😉
делал по вашему примеру и не понял почему работает так: если мы вводим число 300, на 1 итерации берется 100(i = 0), это удовлетворяет нашему условию-добавляем купюру 100, выполнился шаг(i++). Следующая итерация (i = 1) - это 50, также удовлетворяет нашему условию(while (amountRequired - note >= 0)) и вроде бы все так, но почему то эта купюра не добавляется!? Все выводы случились на первой итерации. Почему так?Объясните плиз
если мы хотим получить 300 то делаем следующее
1) итерируемся по номиналам купюр. Первый номинал 100.
2) заходим в цикл while и пробуем взять столько купюр этого достоинства сколько можно - до тех пор пока количесвта не станет меньше либо равно нулю.
то есть мы от 300 отняли 100. Остаток больше нуля. Еще раз снимаем 100. все еще остаток больше 0. Еще раз снимаем 100. вот теперь остаток 0. и мы закончили выдачу.
Если бы заказали выдачу 280:
1) в цикле выбираем номинал 100
2) пробуем снять 100. Получилось остаток 180 > 0
3) значит снимаем еще 100. Остаток 80.
4) пробуем снять еще 100. остаток -20. Значит эта операция не проходит и мы выходим из while.
5) итерируемся на следующий номинал 50
6) пробуем снять 50. остаток 30.
7) пробуем снять еще 50. остаток -20 - значит операция не подходит, выходим из while
8) выбираем следующий номинал 20
9) пробуем снять 20. остаток 10
10) еще пробуем снять 20. остаток -10 - - значит операция не подходит, выходим из while
11) выбираем следующий номинал 10
12)пробуем снять 10. остаток 0.
13) завершаем программу и возвращаем массив снятых номиналов
function iWantToGet(amount) {
// какое количество по 100
const po100 = Math.floor(amount / 100);
amount = amount % 100;
// какое количество по 50
const po50 = Math.floor(amount / 50);
amount = amount % 50;
// какое количество по 20
const po20 = Math.floor(amount / 20);
amount = amount % 20;
// какое количество по 10
const po10 = Math.floor(amount / 10);
amount = amount % 10;
}
Nice! :) Единственное там надо в конце добавить return {100: po100, 50: po50, 20: po20, 10: po10}
Что то мое решение ни на чье не похоже... Я что то делаю не так? Или мб я как то не правильно понял задание?
function iWantToGet(money = 0) {
bills = [100, 50, 20, 10]
sumBill = 0
bills.forEach((bill) => {
if (money > 0) {
countMoney = parseInt(money/bill)
if (countMoney !== 0)
console.log('Купюр по ' + bill + 'рублей' + ' - ' + countMoney)
sumBill += countMoney
money = money%bill
}
})
console.log('Всего купюр - ' + sumBill)
}
Все отлично - хорошее решение вышло :)
вообще, алгоритм не универсальный и работает далеко не на всех availableNotes.
пример,
availableNotes = [5,3,2]
iWantToGet(14) вернет [5,5,3], а хотелось бы [5,5,2,2], т.к у банкомата есть возможность выдать всю сумму
Данный алгоритм работает только для определенного набора банкнот. Об этом я сказал в видео, и это же написано в условии. То о чем вы пишите, это уже другая задача. Вот тут ее решение: ua-cam.com/video/x-BsFzVadKM/v-deo.html Приятного просмотра!
@@frontendscience во-первых, спасибо за обратную связь и ваш труд.
"удобные" номиналы и "алгоритм работает только для определенного набора банкнот" - это не равные утверждения, второе не дает двусмысленности, в отличие фразы "удобные" номиналы.
просто я из тех, кто ставит на паузу и пытается сперва сам решить, отсюда и уточнение, возникшее при самостоятельном решении.
а за разборы и объяснения ОГРОМНОЕ СПАСИБО, у вас прекрасно получается рассказать просто о сложном.
@@IlyaShaforostoff Благодарю. Рад, что Вам нравится!
Так и не понял, в чем вопрос с купюрами. Я прямо копирую цитату из описания: "В этом видео мы рассмотрим более простую версию задачи: у нас будет неограниченное количество банкнот в банкомате, а также "удобные" номиналы, доступные к выдаче: 100, 50, 20, 10.". Помимо слова "удобные" даже привел конкретные примеры чтобы проиллюстрировать наиболее ходовые купюры.
И в самом видео прям с 15 секунды я объяснял, что у задачи есть много вариантов и сразу предупредил о том, что снял несколько видео - сегодняшнее по самому легкому варианту этой задачи, и далее описание условий. 1:18 "и последнее обязательное условие к этой задаче...." про номиналы купюр, которыми располагает банкомат.
Это круто, что Вы нажимаете на паузу и решаете самостоятельно, но условие не забывайте дослушать до конца.)
Очень хотелось бы увидеть код этой же задачи на Python
вот так годно или нет?))
const availibleNotes = [100, 50, 20, 10]
let result = []
function iWantToGet (amountRequired) {
let remainder = amountRequired
for (i = 0; i < availibleNotes.length; i++) {
if (remainder < availibleNotes[i] ) {
result[i] = 0
} else {
result[i] = Math.floor(remainder / availibleNotes[i])
remainder = remainder - availibleNotes[i]
}
} return result
}
console.log(iWantToGet(160))
console.log(iWantToGet(251))
console.log(iWantToGet(5))
console.log(iWantToGet(-10))
Благодарю за решение! все очень понятно вышло! 💪
const iWantToGet = (value) => {
let result = []
while(value > 0){
if(value >= 100){
result.push(100)
value -= 100
}else if(value >= 50){
result.push(50)
value -= 50
}else if(value >= 20){
result.push(20)
value -= 20
}else{
result.push(10)
value -= 10
}
}
return result
}
function iWantToGet(amount) {
const notes = [100, 50, 20, 10]
let myAmount = amount;
const result = [];
for(let i = 0; myAmount > 0;) {
if(myAmount - notes[i] >= 0) {
myAmount = myAmount - notes[i];
result.push(notes[i]);
} else {
i += 1;
}
}
return result;
}
Благодарю за решение!
Здравствуйте! Спасибо вам за труды!
function iWantToGet(ammountRequired) {
const availableNotes = [100, 50, 20, 10];
const result = [];
let i = 0;
while(i < availableNotes.length) {
if (ammountRequired >= availableNotes[i]) {
ammountRequired -= availableNotes[i];
result.push(availableNotes[i]);
} else {
i++;
}
}
return result;
}
iWantToGet(365);
если клиент захочет снять миллиард, то банкомат зависнет
На моем локальном компе с миллиардом стабильно отрабатывает за 300ms - с чего бы ему виснуть? это простейшие арифметические операции.
@@frontendscience он зависнет от вопроса "а не охренел ли клиент".
@@anazkomult 😂
Решение у автора слабое. Данный алгоритм работает только для указанных номиналов - 100, 50, 20, 10. Если номиналы будут другими, то такой жадный алгоритм может выдавать неправильный ответ с точки зрения первого условия - минимальности выдаваемых банкнот. Например, если номиналы 100, 90, 20 и запрашивается 180, то алгоритм автора выдаст - 100, 20, 20, 20, 20 т. е. 5 банкнот, тогда как оптимальным является 90, 90 - 2 банкноты.
Мое решение:
const iWantToGet = ammountRequired => {
if (ammountRequired % 10) return 'Enter an amount in multiples of 10'
if (ammountRequired {
let noteCount = ammountRequired / note
for (let i = 1; i
function iWantToGet(ammountRequired) {
const result = []
const banknotes = [100, 50, 20, 10]
let rest = ammountRequired
if (rest > 0) {
for (let index = 0; index < banknotes.length; index++) {
while (banknotes[index]
Спасибо
Ваш код на Java:
import java.util.ArrayList;
public class Bancomat1 {
public static void main(String[] args) {
System.out.println(getMoney(160));
}
private static ArrayList getMoney(int money) {
int[] notes = {100, 50, 20, 10};
ArrayList result = new ArrayList();
if (money > 0) {
for (int i = 0; i < notes.length; i++) {
while (money - notes[i] >= 0) {
money -= notes[i];
result.add(notes[i]);
}
}
} else {
return result;
}
return result; } }
// немного в лоб решил
function iWantToGet(amountRequired) {
cash = {};
giveBanknote(10, giveBanknote(20, giveBanknote(50, giveBanknote(100, amountRequired))));
return cash;
}
function giveBanknote (banknote, restAmount) {
if (restAmount >= banknote) {
cash[`${banknote}`] = Math.floor(restAmount / banknote);
return restAmount % banknote;
}
return restAmount;
}
console.log(iWantToGet(380));
// 100 50 20 10
const arr = [100, 50, 20, 10];
const iWantGetMany = (count) => {
let summToGet = count;
const res = arr.map((nominal) => {
// const countOfNominal = (count - (count % nominal)) / nominal;
const countOfNominal = parseInt(summToGet / nominal);
summToGet = summToGet % nominal;
return countOfNominal;
});
return res;
};
console.log(iWantGetMany(570));