Question

Вавтобусе 50 мест, которые обычно нумеруются числами от 1 до 50. вышло новое распоряжение, согласно которому код места не должен содержать цифр, а может состоять только из букв а, б, в и г. предложите кодирования номера места, так чтобы все коды были одинаковой (минимально возможной) длины и сохранялся порядок сортировки: если записать новые буквенные коды по алфавиту, соответствующие «старые номера» этих мест должны быть расположены по возрастанию. как бы вы закодировали номер места 49? в ответе код и опишите принцип.

Answer 1

По распоряжению алфавит должен состоять из четырех символов; А, Б, В. Г, поэтому запись любого числа с этого алфавита - это его представление в системе счисления по основанию 4.
Чтобы лучше понять эту идею, вспомним привычную нам запись чисел - десятичную. Она называется десятичной потому, что для записи чисел в ней используются десять знаков - от 0 до 9. Знаков десять и в соответствии с этим числа, ими записанные представляются в десятичной системе счисления. А если у нас таких знаков только восемь - от 0 до 7? Совершенно верно, это алфавит восьмеричной системы счисления. А если только два знака в алфавите - 0 и 1? Да, мы приходим к той самой двоичной системе.

Теперь, когда мы обосновали выбор системы счисления по основанию 4. посмотрим, сколько разрядов нам надо для представления самого большого из требуемых чисел - числа 49. Почему 49, а не 50, ведь мест 50? Да, мест 50, но они нумеруются от 1 до 50, а мы будем их кодировать числами от 0 до 49. Для "экономии" - чего нулю пропадать даром?
Переводим 49 в систему счисления по основанию 4. Тем самым делим на основание системы, пока есть что делить, т.е. пока не получим 0 в целой части.
49 / 4 = 12 и 1 в остатке.
12 / 4 = 3 и 0 в остатке
3 / 4 = 0 и остаток 3.
А теперь записываем остатки в обратном порядке: 301.
Итак, 49₁₀ = 301₄
Следовательно, нам достаточно иметь три разряда для записи номера любого места.
Осталось вспомнить, что вместо цифр 0,1,2,3 (а именно они составляют алфавит системы счисления по основанию четырые) мы должны писать буквы, да еще и в алфавитном порядке. Ну и ладно, тогда пусть так будет:
А - 0, Б - 1, В-2, Г-3. И наш максимальный номер 49₁₀ = 301₄ запишется в виде ГАБ.
А как закодировать место 49? Оно лишь на 1 меньше, чем максимальное 50, но 50 это у нас 301₄. отнимем 1 и получим 300₄, которое кодируется как ГАА. Это и есть ответ.