Разбираем задачу №16 в ЕГЭ по информатике.
Обратите внимание, здесь будет не только пример решения, но и разбор задания по существу.
Для примера я беру демоверсию 2020 года (актуальная на момент написания статьи) с сайта fipi.ru.
Очень короткая формулировка, локаничная
Прежде чем приступать к решению этого примера, посмотрим в спецификацию к демоверсии.
Не менее лаконично, чем само задание, нам указывают на знание позиционных систем счисления. Обратите внимание: не алгоритм построения записи в системе с другим основанием, а знание самих систем счисления. Это важное уточнение, скоро будет видно, почему.
Кодификатор нам говорит то же самое
При этом от нас хотят видеть уже не использование готовых моделей, а построение новых. Ну, что ж. Займёмся этим.
Позиционные системы счисления
Я уже пальцы о клавиатуру стёр, описывая всякие хитрости, которые относятся к позиционным системам счисления. Этому посвящены многие мои статьи: 1, 2, 3, 4, 5, 6, 7, 8, 9. Из них нам понадобятся три: Позиционные системы счисления, Быстрый и точный перевод в двоичную систему счисления и Вычитание с переходом через десяток. Крайне рекомендую прочитать или перечитать их заново. Они слишком громоздкие, чтобы переписывать их сюда, но коротко напомню.
Число в позиционной записи состоит из цифр, каждая цифра имеет свой вес. Немного точнее: каждая цифра показывает, сколько болтов/гаек/шайб у нас имеется. И на картинке над каждой цифрой записана "цена" (вес) разряда. Три единицы, четыре семёрки, два раза по сорок девять и два раза по триста сорок три.
Заметим, что это всё степени основания системы счисления (семёрки). Это важно, потому что на этом построено задание.
Переводы между системами
Так для краткости называют процесс замены записи числа в системе с одним основанием на запись того же числа в системе с другим основанием. Есть универсальнейший способ деления "уголком" с остатком, который позволяет переводить из любой СС в любую. У него есть масса недостатков и одно преимущество - он очень легко алгоритмизуется. Нам он не подойдёт. Нам придётся подбирать цифры, а не вычислять, потому что вычислений будет очень много. Я об этом скажу. Подробно именно о подборе цифр я не писал, но в в статьях о нём говорится.
Для нашего задания потребуется не совсем та заготовка, которую я предлагал раньше:
Каждое слагаемое надо будет записывать отдельно: 4⁸, 2⁸ и 8.
Алгоритмы выполнения арифметических операций
В позиционных системах счисления очень легко реализуются алгоритмы вычислений: сложение и вычитание "столбиком", умножение и деление. Их часто считают единственными возможными, однако это не так. Я всегда считал их самыми ущербными из возможных, но теперь нам именно они и понадобятся. Пока поговорим о сложении и вычитании (больше и не надо).
Операции сложения и вычитания в позиционных системах счисления могут быть выполнены поразрядно. Это значит, что единицы складываются с единицами, десятки с десятками и т.д. При сложении возможно переполнение какого-то разряда, тогда происходит размен на более ценный. При вычитании наоборот может возникнуть недостача, и тогда происходит размен старшего разряда. Об этом я подробно написал в статье Вычитание с переходом через десяток.
Разбор задания
Большинству напрашивается метод решения "в лоб" - выполнить действия, записать число в десятичной СС, перевести в двоичную "уголком", а потом просто пересчитать единицы. Немного потренировавшись, можно свести время выполнения к требуемым двум минутам.
Однако модификация задания просто с увеличением показателя степени приведёт к существенному удлинению алгоритма за счёт увеличения количества итераций.
Задание на картинке даст уже перевод в троичную делением на три числа 58149737153134694987389281 в десятичной записи. Результат перевода: 1000000000000000000222222222222222222222222222222222200.
Потребуется 55 делений на 3 (считая последнее 1/3=0 ост 1).
А я встречал варианты с возведением в 2014 степень (очень любят в показатель степени номер года пихать).
На "коротком" задании из демоверсии я покажу принцип решения таких задач.
Мы не будем выполнять действия сразу, потому что степень основания системы счисления в ней очень красиво записывается. У нас речь идёт о двоичной системе счисления, поэтому лучше всего будет работать с числом 2. Попробуем быстро записать 2⁸ в двоичной системе. Возьмём правый вариант заготовки (со степенями)
Вот прямо видно, что для того, чтобы набрать 2⁸ потребуется поставить единицу в девятой (считая справа налево) клеточке единицу, а остальные восемь заполнить нулями:
Видите? Не пришлось ничего возводить, ничего делить. Просто поставили единицу. Это не только двоичная система, 3³⁴ будет выглядеть в троичной системе точно так же:
Очень длинные степени можно записывать через многоточия. Посчитать количество нулей всегда легко будет.
У нас остались слагаемые 4⁸ и 8. Их таким способом перевести будет уже невозможно, но самые нетерпеливые читатели уже готовы заменить 4 на 2²: 4⁸ = (2²)⁸ = 2¹⁶, а восьмёрку на 2³. Так и надо делать, тк подзадача - привести к виду "(основание системы) в степени (целое число)"
Теперь мы имеет три слагаемых:
А дальше выполняем поразрядное сложение и вычитание "столбиком". В двоичной системе это немного непривычно, но выполнение очень простое.
1. Если при сложении в каком-то разряде получается >=2, то размениваем на следующий разряд.
2. Если при вычитании возникает ситуация (меньшее)-(большее), то надо разменивать старшие разряды.
Сначала сложение:
А вот с вычитанием проблема. Я запишу его в пару этапов (листаем галерею):
Давайте прокомментирую для тех, кому трудно:
На рис 1 в разряде 2³ возникает вычитание 0-1 - невозможное для нас тут. Нужно разменивать старшие разряды. Ближайший, который вообще можно разменять - 2⁸. Его размениваем на два по 2⁷ (рис 2). Именно на 2, а не на 10 или 9, потому что СС у нас двоичная. В троичной системе был бы размен на три и так далее.
Всё равно не хватает для выполнения действия, поэтому один из двух 2⁷ меняем на два 2⁶ (рис 3). Над каждым разрядом, из которого я брал для размена, ставлю точку (просто чтобы было похоже на второй класс).
И так далее мы размениваем до тех пор, пока не сможем вычесть каждый разряд вычитаемого из каждого разряда уменьшаемого(рис 4). И вот теперь можем вычитать:
Заметьте, я в клеточках в двоичной системе счисления писал двойки (привет, Бэндер), хотя их не существует. Это вспомогательные промежуточные записи, как в статье про вычитание в одной клеточке я писал "13".
Теперь выполняем подсчёт единиц: одна вначале, и пять в середине. Итого 6
Ответ: 6.
Высокие степени
Часто попадаются задания с такими степенями, что все цифры за 2 минуты записать нереально (да и некуда). Типа 1024 или 2014. Писать можно через многоточия:
Легко посчитать, сколько единиц от 4й степени до 27й вычитанием.
Но тут есть подводный камень, о который все бьются. Это будет не 27-4=23, а другое число (на 1 больше или на 1 меньше). Я всегда рекомендую записать ряд чисел от 1 до 9, выбрать границы (например 3 и 8) и посчитать, сколько цифр от 3 до 8 включительно:
1 2 3 4 5 6 7 8 9
Их будет 6, но если вычесть из 8-3, то получится 5. Значит, от 4 до 27 будет тоже не 23, а 24 числа.
Совсем необязательный камень, но будет очень обидно, если споткнётесь. Запоминать увеличение на 1 не следует, потому что в случае не от 3 до 8, а мужду 3 и 8, надо будет уменьшать. Чтобы не запутаться, пользуйтесь рядом небольших чисел подряд.
Недвоичная система счисления
Такой простой размен идёт только в двоичной системе. Но во втором примере речь идёт уже о троичной (я и семиричную видел). В троичной системе размен будет на 3 идти, а не на 2. И из этой тройки будем дальше забирать только одну штуку, поэтому останется два:
Заключение
Это очень простое и одновременно очень сложное задание имеет решаемость в 54,9% - всего на пару процентов больше, чем 24 задание из "c-части". Сложность заключается именно в том, что в школах, на курсах и с репетиторами все учат только способы перевода - деление уголком и сложение степеней. Даже перевод из шестнадцатиричной в двоичную осуществляют через десятичную. Знания о принципах работы позиционных систем счисления не имеют однозначно прямого отношения к информатике, но они имеют стопроцентное применение в арифметике.
В начальной школе проходят же все эти алгоритмы - сложение, вычитание, умножение и деление. Но я знаю очень мало людей (даже взрослых), которые самостоятельно смогли бы эти же алгоритмы применить на недесятичной системе счисления. Это от того, что мы запоминаем не весь алгоритм, а его оптимизированную под десятичную систему версию, и работаем с ней не как хомо сапиенсы, а как арифмометры. И только человек, который действительно понимает основы систем счисления, может перестроить алгоритм.
