Деньги, деньги, деньги, рублики...

Маша, глянь! Этот покупатель расплатился за батон одной монетой в 25 копеек!

(Из советского анекдота)

Сколько задач разбросано вокруг нас! Их не нужно даже искать - надо только оглянуться по сторонам и немножко задуматься...

В самом деле, почему у нас были именно такие монеты: 1, 2, 3, 5, 10, 15, 20, 50 копеек, а также металлический рубль? Конечно, историки и нумизматы могут по-своему ответить на этот вопрос, но и у меня есть некоторые соображения.

Для простоты я буду называть все деньги "монетами" (даже если это бумажные купюры), а множество всех выпущенных в обращение монет - монетной системой.

Как мне кажется, хорошая монетная система должна обладать двумя качествами - "экономичностью" и "удобностью". Оба понятия здесь требуют разъяснений.

Под "экономичностью" я понимаю вот что: любая сумма копеек (меньшая рубля) должна выплачиваться без сдачи не очень большим числом монет, и при этом само количество номиналов монет тоже должно быть не очень большим. Приведу два крайних случая: можно ограничиться всего одной 1-копеечной монетой, но тогда для уплаты 100 копеек потребуется 100 монет. А можно начеканить монеты всех номиналов от 1 до 100 - тогда на любую сумму хватит одной монетки, но зато у нас в карманах вечно будет гора мелочи, в которой отыскать нужную монетку будет просто невозможно.

Иными словами, монетная система тем "экономичнее", чем меньше величина K₁=max(m,k₁,k₂,...,k₁₀₀), где m - число монет, а k_i - наименьшее количество монет, требуемое для уплаты i копеек.

Для нашей советской системы m=9, а наибольшее число монет, которое требовалось для уплаты некоторого числа копеек - шесть. (Именно столько монет нужно для того, чтобы набрать 89, 94 или 99 копеек.) Таким образом, K₁=9. Кстати, если бы "трешки" и "пятнашки" не было, то все равно любую сумму от 1 до 100 копеек можно было бы заплатить не более чем шестью монетами, но K₁ было бы равно 7. Кстати, без "трешки" и "пятнашки" получается именно та монетная система, которая принята в Америке для долларовых бумажек: существуют купюры 1, 2, 5, 10, 20, 50 и 100 долларов.

Задача 1. Является ли американская система наиболее экономичной из всех возможных? Например, можно ли придумать систему, в которой диапазон от 1 до 100 содержит всего шесть монет, и при этом любую сумму можно заплатить не более чем шестью монетами? Если да, то какие это монеты?

Разумеется, я не предлагаю решать эту и последующие задачи вручную. Компьютер с ними может справиться гораздо быстрее и эффективнее. Для решения на компьютере задача 1 может быть сформулирована короче и точнее: найти монетную систему, для которой величина K₁ минимальна.

Можно предложить и другие показатели, пригодные для оценки экономичности монетной системы. Неплохими характеристиками являются K₂=m*max(K₁,K₂,...,K₁₀₀) и k₃=m*(K₁+K₂+...+K₁₀₀) - чем они меньше, тем лучше.

Например, для нынешней российской системы (в тысячах рублей, с "монетами" 1, 5, 10, 50 и 100 тысяч) m=5, K₂=5*10=50 и k₃=5*501=2505. А для американской - K₂=7*6=42 и k₃=7*341=2387. (Вычислить сумму K₁+...+K₁₀₀ несложно, и я это вычисление не привожу).

Задача 2. Существует ли монетная система, для которой K₂ не больше 40? Найдите систему с наименьшим значением K₂. Какие в ней монеты?

Задача 3. Существует ли монетная система, для которой k₃ < 2000? Найдите систему с наименьшим k₃. Какие в ней монеты?

Теперь - об "удобности" систем. Как мы обычно набирали мелочью, скажем, 39 копеек (если считать, что у нас были в кармане любые монеты)? Брали монету в 20 копеек, затем 15, потом 3 и, наконец, копейку. То есть каждый раз выбирается наибольшая монета из возможных. Опишем этот алгоритм немного более формально:

Алгоритм Pay (Summa). Если Summa=0, то ничего платить уже не надо. Пусть S>0. Найдем X - величину самой крупной монеты, не большей, чем Summa. Тогда возьмем монету X, а для нахождения остальных монет выполним алгоритм Pay(Summa-X). Конец алгоритма.

Такие алгоритмы (в которых на каждом шаге выбирается наибольшая возможная величина), обычно называют жадными.

Будем называть монетную систему удобной, если для любой суммы (не только от 1 до 100) жадный алгоритм дает наименьшее число монет, которым эту сумму можно заплатить.

Наша российская монетная система, а также американская и советская - удобные (хотите - верьте, хотите - проверяйте или доказывайте). А если бы вместо пятикопеечной монеты в советской монетной системе была 7-копеечная, то "удобность" пропала бы: жадный алгоритм для суммы 14 копеек дает три монеты (14=10+3+1), а при использовании 7-копеечной монеты достаточно всего двух.

Задача 4. Являются ли самые экономичные монетные системы (которые получены в задачах 1, 2 и 3) удобными? Если нет, то найдите самые экономичные из удобных монетных систем.

Задача 5. Пусть в монетной системе M монет. Придумать алгоритм, проверяющий, является ли она удобной. Число действий алгоритма может зависеть от M, но не от величин номиналов монет.

До сих пор мы рассматривали идеальную ситуацию, когда для уплаты можно использовать все монеты, при этом каждую - столько раз, сколько надо. Реальная же картина бывает обычно другой: мы платим немного больше, чем должны, и получаем сдачу. Особенно охотно мы пользуемся этим, если сдача невелика по сравнению с заплаченной суммой. Например, чтобы заплатить 39 копеек, мы всегда предпочитали отдать две двадцатикопеечные монеты и получить копейку сдачи. При этом в уплате участвуют всего три монеты (а не 5).

Пусть s_i - наименьшее количество монет, которое необходимо, чтобы заплатить сумму i со сдачей. Рассмотрим величины S₁=max(m,s₁,...,s₁₀₀), S₂=m*max(s₁,...,s₁₀₀) и S₃=m*(s₁+s₂+...+s₁₀₀).

Задача 6. Дана монетная система и число i. Придумайте алгоритм для определения s_i.

Задача 7. Для каждой из трех рассмотренных монетных систем (советская, американская, российская) вычислите S₁, S₂ и S₃.

Задача 8. Найдите монетные системы, для которых величины S₁, S₂, S₃ принимают наименьшее возможное значение.

Ваши решения задач можно направлять электронной почтой по адресу kk@knop.spb.ru (или обычной почтой - в редакцию "Компьютерры"). Лучшие результаты будут переданы в Центробанк России для проведения денежной реформы.