Задание 14 ЕГЭ по информатике: системы счисления

Любое значение можно записать в системе счисления с любым основанием, и задание строится на том, что запись иногда видна без вычислений. Если в выражении сложены и вычтены степени тройки, то в троичной записи ответа стоят нули, единицы и двойки на заранее предсказуемых местах, и считать цифры можно, ни разу не переведя число в десятичную систему. Если в числе есть неизвестная цифра, угадывать место нечем, и тут помогает короткий перебор в программе. Две этих ситуации покрывают почти всё, что спрашивается.

Ответом служит одно число, и то, что именно это за число, выясняется из последней строки условия: количество цифр определённого вида, значение в десятичной записи, частное, основание. Перепутанный вопрос стоит задания целиком, поэтому последнюю строку читают первой. Номер и тему сверяйте по демоверсии 2027 года. Общие приёмы перевода (двоичные и шестнадцатеричные группы, сравнение записей) собраны в статье про системы счисления на ЕГЭ, здесь они не повторяются, и речь только о том, как этой темой пользуется данное задание. Общую карту первой части даёт разбор первой части ЕГЭ по информатике.

Степени одного основания

Основа метода — четыре факта о записи по основанию b, и о каждом полезно знать, почему он верен:

• b в степени k записывается единицей и k нулями, а длина записи на единицу больше показателя;
• сумма двух степеней с разными показателями даёт две единицы на своих местах и нули между ними;
• разность b в степени n и b в степени k при n больше k записывается цепочкой из n минус k цифр, каждая из которых на единицу меньше основания, и k нулями в конце;
• если к такой разности прибавить степень с показателем больше n, получится единица в старшем разряде, группа нулей и готовая цепочка: записи не пересекаются.

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

Проверьте первый факт на маленьком примере, чтобы не принимать его на веру: три в четвёртой минус три в первой равно 78. Правило обещает три двойки и один нуль, то есть 2220 по основанию три. Переведите обратно: 2·27 + 2·9 + 2·3 = 78. Совпало.

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

Разбор одного условия

Пусть значение выражения 9 в шестой степени плюс 3 в восьмой минус 27 записано в троичной системе, и надо сказать, сколько в записи двоек. Привожу к основанию три: три в двенадцатой, плюс три в восьмой, минус три в третьей. Разность последних двух членов выражения — это пять двоек и три нуля: 22222000. Старший член, три в двенадцатой, добавляет единицу далеко слева, а между ней и двойками остаются нули. Двоек в записи пять.

Проверяется ответ вычислением: три в восьмой минус три в третьей равно 6561 минус 27, то есть 6534. Это 2·3267, а 3267 — как раз сумма пяти степеней тройки от 3 в третьей до 3 в седьмой. Если сошлось, число двоек подтверждено двумя независимыми способами.

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

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

Неизвестная цифра и перебор

Условия другого рода дают число с буквой вместо цифры, например число из трёх цифр по основанию восемь, где в середине стоит x, и просят найти наименьшее или наибольшее x, при котором оно делится на заданное. Руками это решается сведением к остаткам, и сильные ученики так и делают: число 3x4 по основанию восемь равно 196 плюс 8x, а 196 как раз делится на семь, значит, остаётся 8x, которое даёт тот же остаток, что и x. Подходят x равное нулю и семи. Для x, равного семи, число равно 252, частное при делении на семь составляет 36.

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

Идея перебора проста: цифра x принимает значения от нуля до основания минус один, для каждого значения число переводится в десятичную запись, проверяется делимость, подходящие значения собираются в список. Больше ничего программа не делает. В Python для перевода из строки сразу в число есть встроенная функция: например, int("374", 8) вернёт 252 для случая с x, равным семи, и подставлять цифру в строку можно в цикле. Обратную работу, из числа в запись по основанию, встроенной функции не имеет: пишется цикл, где остаток от деления на основание даёт очередную цифру, а целое деление уменьшает число, и цифры затем разворачиваются в обратном порядке.

Когда руками, а когда программой

Моя позиция: если в условии есть степени, начинайте с рук, а если неизвестная цифра, то с программы, и в обоих случаях проверяйте вторым способом. С этим можно спорить, ведь программа справляется и со степенями, пусть число вычисляется длинным целым, и для Python это действительно так. Но программа даёт только ответ, а руками вы видите структуру записи и заметите, что в вопросе речь о нулях, хотя вы искали двойки. В C++ у этого выбора есть ещё причина: девять в двадцатой степени уже не помещается в знаковое 64-разрядное целое, и переполнение молча портит ответ, а рука с правилом разности степеней не знает о таком пределе. Сравнение языков в этом смысле подробно описано в статье Python или C++ для ЕГЭ.

Что стоит прочитать дважды

Ловушек в записи ответа немного, и все они сидят в условии, вычисление тут ни при чём. Когда сказано «сколько цифр», считайте цифры; сумма цифр — другой вопрос. Когда сказано «в десятичной записи», переводите ответ обратно, даже если решение велось по основанию семь. Когда основание больше десяти, цифры десять и далее записываются буквами, и в вашей программе или на листе нужно точно понимать, какая буква какому значению соответствует. Ученики, у которых шестнадцатеричные цифры в голове лежат прочно, забывают, что в системе с основанием двенадцать буква старше B не бывает вообще.

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

Как отрабатывать

Полезнее всего короткая ежедневная разминка. Берётся выражение из двух-трёх степеней одного основания, ученик пишет запись ответа на листе, а потом проверяет её программой за полминуты. Такой цикл закрепляет правило разности степеней лучше, чем сорок решённых задач подряд: каждый раз видно, в чём именно была неточность. Пока правило не запомнилось, держите перед глазами пример с 78 и сверяйте с ним очередную цепочку.

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

Третья ступень не про программу вовсе. Раз в неделю возьмите условие и скажите вслух, какой вопрос в нём задан: количество цифр, их сумма, значение, основание. Звучит как детский приём, но потери здесь не математические, и слово сказанное вслух ловит их лучше, чем перечитывание глазами.

Какой пробел за этим стоит

Различайте причины. Не получается перевести обычное число между системами, то есть вы медленно делите в столбик или путаете направление остатков. Это пробел в самой теме, он закрывается за несколько занятий и тренировкой на десятке чисел, а школьный курс информатики эту тему обычно проходит, хотя и на простых примерах. Если перевод вы делаете, но не видите структуру записи в выражениях со степенями, это отработка одного приёма, и разобранный выше пример с разностью степеней годится как ежедневная разминка. Когда теория понятна, но перебор не удаётся записать программой, дело в программировании, и общий разбор языка и среды поможет больше, чем ещё одно задание по теме: как устроен курс информатики в школе и в каком порядке в нём что учить.

Начать поиск:

• репетиторы по информатике для подготовки к ЕГЭ
• все репетиторы для подготовки к ЕГЭ
• репетиторы по информатике, все направления

Предыдущее задание второй половины — про электронные таблицы, задание 9; следующее, где снова нужна уверенность с большими числами, — рекурсия в задании 16. Остальной экзамен собран в разборе структуры ЕГЭ по информатике.

Вопросы и ответы

Можно ли пользоваться калькулятором? Что именно стоит на рабочем месте, указано в правилах проведения экзамена. Рассчитывать на встроенный калькулятор можно, но ручной разбор записи всё равно быстрее.

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

Что делать, если основание больше десяти? Цифры от десяти и далее записываются буквами по порядку: A равно десяти, B одиннадцати и так далее. В программе функция int принимает такие записи для оснований до тридцати шести, а при переводе в обратную сторону буквы приходится подставлять самому. Как они обозначены в условии вашего года, смотрите в демоверсии.

Что быстрее: вручную или программой? Для степеней вручную, для неизвестной цифры программой.

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