7.6. Задача «Максимальный оклад»

В этом параграфе вы разберёте нестандартную задачу на сортировку, которая проверяет не только знание алгоритмов, но и умение формулировать правильные правила сравнения. Она известна как классическая головоломка: из набора чисел нужно составить такое, которое даёт наибольшее значение при конкатенации.

На первый взгляд кажется, что достаточно отсортировать числа по убыванию. Но именно здесь скрыта ловушка: простая сортировка не приведёт к верному ответу. Главный вызов задачи — не сама сортировка, а корректное определение критерия, по которому строки должны сравниваться между собой. Это отличный пример того, что в алгоритмах важна не только техника реализации, но и точность в постановке правил.

Ключевые вопросы параграфа

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

Вопрос на собеседовании

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

Вспомните алгоритм для этой задачи, который работает с однозначными числами.

1LargestConcatenate(Numbers):
2    yourSalary = "" # пустая строка
3    while Numbers is not empty:
4        maxNumber = -infinity
5        for each number in Numbers:
6            if number >= maxNumber:
7                maxNumber = number
8        yourSalary = yourSalary + maxNumber # добавляем число в конец
9        Numbers.remove(maxNumber) # удалить из рассмотрения число maxNumber
10    return yourSalary

Такой алгоритм не всегда будет приводить к самой большой зарплате: например, при вводе из двух целых чисел 23 и 3 он выдаст 233, в то время как самое большое число — 323.

Не беспокойтесь, чтобы получить самую большую зарплату, вам всего лишь нужно заменить строку

1if number >= maxNumber:

на следующую:

1if IsBetter(number, maxNumber):
2

Для надлежаще реализованной функции IsBetter нужно учесть порядок цифр и их количество. Функции IsBetter(first, second) должна возвращать булеву величину сооветствующую ответу на вопрос: нужно ли ставить число first раньше числа second. Например, IsBetter(3, 23) выдаст True.

Остановитесь и подумайте:
Как бы вы реализовали IsBetter?

• Входные данные: Первая строка ввода содержит целое число . Вторая строка содержит целые числа .
• Выходные данные: Самое большое возможное число, которое состоит из .
• Ограничения: ; для всех .

Пример 1

Обратите внимание, что в этом случае приведённый выше алгоритм также выдаёт неправильный ответ 212.

Пример 2

Ввод состоит только из однозначных чисел, поэтому алгоритм выше выдаёт правильный ответ.

Пример 3

Тем не менее алгоритм LargestConcatenate (неверный) в этом случае приводит к правильному результату — ещё одно напоминание, что всегда стоит проверять правильность жадных алгоритмов!

Что дальше

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

Далее — подведение итогов. Вы вспомните, какие приёмы жадных алгоритмов вы освоили, в чём их сила и в чём ограничения.

А пока вы не ушли дальше — закрепите материал на практике:

• Отметьте, что урок прочитан, при помощи кнопки ниже.
• Пройдите мини-квиз, чтобы проверить, насколько хорошо вы усвоили тему.
• Перейдите к задачам этого параграфа и потренируйтесь.
• Перед этим — загляните в короткий гайд о том, как работает система проверки.

Хотите обсудить, задать вопрос или не понимаете, почему код не работает? Мы всё предусмотрели — вступайте в сообщество Хендбука! Там студенты помогают друг другу разобраться.

Ключевые выводы параграфа

• В некоторых задачах важно уметь сравнивать строки нестандартным способом — не по алфавиту, а по результату объединения.
• Простая сортировка не всегда даёт правильный результат: нужно чётко задать правило, по которому элементы упорядочиваются.
• Жадные стратегии применимы и к строкам, но требуют особенно внимательной формулировки критерия выбора.