Отыщите минимальное число монет, позволяющее дать любую сдачу

Есть два способа интерпретации этого вопроса. Они приводят к разным ответам, и поэтому вам лучше спросить интервьюера, что он имеет в виду (или подготовить оба варианта ответов). Одна интерпретация заключается в том, чтобы отыскать наименьший ассортимент монет, позволяющий дать точную сдачу от 1 до 99 центов. Назовем такой комплект универсальным набором для выдачи сдачи. Сколько монет будет в этом наборе?

В задаче используются монеты США. Доллар США (USD, $), равный 100 центам. В обращении находятся монеты – penny (1 цент), nickel (5 центов), dime (10 центов), quarter (25 центов), half dollar (50 центов), а также 2 и 1 доллар.

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

Ответ легкий, поскольку монеты в Америке специально подобраны по номиналу так, чтобы облегчить сдачи. Каждая монета по стоимости, по крайней мере, вдвое дороже предыдущей. Это означает, что вы можете использовать следующий алгоритм для выдачи сдачи, равной Х центов.

Если требуемая сдача Х равна 50 центам и более, положите 50-центовую монету и вычтите эту сумму из Х.

Если Х теперь равно 25 центам или более, положите четвертак (25 центов) и вычтите его из Х.

Разделите новое значение Х на 10 и выделите целую часть. Положите в кассу 10-центовики в количестве, равном целой части.

Если оставшаяся сумма равна 5 центам и более, положите в кассу 5-центовик и вычтите остаток из суммы.
Разделите оставшуюся сумму на центы и положите в кассу 1-центовые монеты в количестве последнего остатка.
Это правило не только работает, но и позволяет вам выдать любую сдачу при наличии минимально возможного числа монет. Вы можете, например, пропустить первую строку и использовать два четвертака вместо одной 50-центовой монеты, но это означает, что вам потребуется дополнительная монета.

Хотите дать любую сумму сдачи минимальным числом монет? Всегда имейте в своем распоряжении одну 50-центовую, один четвертак, один 5-центовик, причем каждую из этих монет достаточно иметь только в одном экземпляре. Вам также может потребоваться два 10-центовика (скажем, если надо выдать сдачу, равную 20 центам) и не более четырех 1-центовых монет (чтобы выдать 4 цента). Это означает, что у вас должны быть девять монет на общую сумму, равную 1,04 доллара. Это универсальный набор, позволяющий выдать любую сдачу. Очевидно, чтобы дать сдачу с доллара, вам никогда не потребуется использовать все девять монет сразу.

Альтернативная интерпретация вопроса такова: каково наименьшее число Х, при котором вам никогда не потребуется больше Х монет, чтобы выдать сдачу. Фактически здесь спрашивается, для выдачи, какой сдачи вам потребуется больше всего монет. Может быть, вы полагаете, что больше всего монет вам будет нужно для сдачи, равной 99 центам? Вы правы. Для этого вам потребуется восемь монет, а именно одна 50-центовая, четвертак, два 10-центовика и четыре 1-центовика. Восемь монет также потребуется и для сдачи, равной 94 центам (по сравнению с предыдущим набором вместо одного 10-центовика вы воспользуетесь 5-центовиком).

Этот вопрос считается довольно запутанным и используется в психологических тестах на креативность.

Разбор по книге «Действительно ли Вы достаточно умны, чтобы работать в Google?»