Подготовка к ЕГЭ по информатике

Подготовка к ЕГЭ по информатике

2-е издание, исправленное

Биллиг В.А.

Национальный Открытый Университет “ИНТУИТ”
2016

2

Подготовка к ЕГЭ по информатике/ В.А. Биллиг - М.: Национальный Открытый Университет
“ИНТУИТ”, 2016

Курс будет полезен школьникам, сдающим ЕГЭ по информатике.
В лекциях рассказывается как решать некоторые задачи разделов A, B и С экзамена по информатике.

(c) ООО “ИНТУИТ.РУ”, 2013-2016
(c) Биллиг В.А., 2013-2016

3

Позиционные системы счисления. Представление целых чисел

Формальный алгоритм перевода десятичного числа в систему с основанием p.

Для записи целых чисел можно использовать разные способы. Такие способы принято
называть системами счисления. Например, целое число можно записывать
последовательностью “палочек”. Число 5 выглядит при таком способе как |||||. Понятно,
что такой способ хорош только для записи небольших чисел. Для записи целых чисел,
особенно дат, иногда применяют римскую систему счисления. В этой системе 2013 год
записывается следующим образом MMXIII.

Основным способом записи чисел является их запись в различных позиционных
системах счисления. Для записи числа в позиционной системе счисления используется
некоторое множество символов, называемых цифрами системы счисления.
Общепринято использовать 10 цифр - 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, значения которых задают
первые 10 чисел натурального ряда. Число используемых цифр задает основание
системы счисления. В привычной со школьной скамьи десятичной системе счисления
используются 10 цифр. В двоичной системе счисления с основанием 2 используются
две цифры - 0 и 1. В позиционных системах счисления с основанием , где 
обычно используются первые p из приведенных 10 цифр. В системах счисления с
основанием 
десяти приведенных цифр не хватает, поэтому необходимы другие

символы для записи цифр. В широко используемой при работе с компьютерами 16-
иричной системе счисления, где необходимо 16 цифр, наряду с цифрами 0 - 9 в
качестве цифр используют начальные буквы латинского алфавита - A, B, C, D, E, F,
задающие соответственно числа от 10 до 15.

В любой системе счисления основание системы счисления – число  – всегда
записывается как число 10. Поясним причину этого на примере десятичной системы.
Число 9 можно записать, используя цифру 9, но, если прибавить к 9 единицу, то на
следующее число цифры уже не будет. Поэтому в позиционных системах в таких
случаях число записывается с помощью двух цифр как число 10 – в младшем разряде
пишется 0, а в старшем 1. В двоичной системе счисления числа 0 и 1 можно записать с
помощью цифр, но, если прибавить к 1 единицу, то для двойки уже цифры нет,
поэтому в двоичной системе число 2 записывается с помощью двух цифр, как число 10.

Вопрос: Чему равно число, записанное в системе счисления с основанием p как 
?

Ответ: Эта запись означает число p в привычной для нас десятичной системе
счисления.

Вопрос: В каких системах счисления справедливы утверждения?

Ответы: ( В системах с основаниями соответственно: 4, 3, 2, в любых системах с
основанием 
)

4

Рассмотрим привычную для нас запись числа 
 в десятичной системе счисления.

Не задумываясь, мы ответим, что число 
 состоит из 7-и сотен, 5-и десятков и 4-х

единиц.

В общем случае запись 
, где 
 – цифры системы счисления означает:

(*)

где  – основание системы счисления. Учитывая, что в любой системе счисления 

, то справедлива и такая запись:

(**)

Вот точное определение:

Запись числа в позиционной системе счисления означает разложение числа по
степеням основания. В роли коэффициентов выступают цифры системы счисления.

Понимание этого факта и соответствующего ему представления числа 
соотношением (*) достаточно для решения многих задач экзамена ЕГЭ.

Задача 1: Сколько единиц в двоичной записи числа 130?

Ответ: 2.

Решение. Число 
. Остальные коэффициенты равны 0.

Полное решение задачи. Поскольку максимальная степень двойки равна 7, то число
130 в двоичной системе будет содержать 8 цифр – 2 единицы и 6 нулей 

Задача 1 решается мгновенно, если помнить степени числа 2

Задача 2: Сколько нулей в троичной записи числа 130?

Ответ: 0

Решение: Используя разложение по степеням основания 3, число 130 можно
представить:

Задача 2 может потребовать некоторых вычислений из-за того, что со степенями
тройки сложнее работать, чем со степенями двойки, которые обычно помнит наизусть
каждый ученик, изучающий информатику.

Задача 3: Чему равно число, записанное как 
 в пятеричной системе счисления?

Ответ: 

5

Решение: Это обратная задача по отношению к задаче 1. Здесь зная цифры и основание
системы счисления нужно восстановить число, используя соотношение (*).

Задача 4: Число 
 записать в двоичной системе счисления?

Ответ: 

Решение: Задача записи числа 
 в системе счисления с основанием , если задана его

запись в системе с основанием , решается в два этапа. На первом этапе число
переводится в десятичную систему, на втором этапе – в систему с основанием .

Формальный алгоритм перевода десятичного числа в систему с
основанием p

Алгоритм достаточно прост. На пальцах он выглядит так. Необходимо
последовательно делить число на p - основание системы счисления. Остатки от
деления дают цифры для записи числа в системе с основанием p.

Приведу обоснование алгоритма:

Воспользуемся представлением (*) для записи числа N.

1. Положим 
;

2. Представим число M в виде: 
3. Нетрудно видеть: 
, где операция % означает остаток от деления;

4. Вычислим новое значение 
 где операция / означает деление нацело.

Результатом этой операции является число, от которого отрезана последняя
цифра; Полученное число сохраняет представление (*).

5. Операции 3 и 4 будем повторять  раз, получая каждый раз очередную цифру в

разложении 
 по степеням основания .

Вот как выглядит точная запись этого алгоритма в виде функции на языке С#:

  /// <summary>
    /// Перевод десятичного числа N 
    /// в систему счисления с основанием p
    /// </summary>
    /// <param name="N"> переводимое число</param>
    /// <param name="p">основание системы счисления</param>
    /// <returns>
    /// строка, задающая запись числа 
    /// в системе с основанием p
    /// </returns>

6

    static string Perevod10ToP(int N, int p)
    {
      string result = "";
      int M = N;
      while (M != 0)
      {
        result = (M % p).ToString() + result;
        M = M / p;
      }
      return result;
    }
    

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

Задача 5: Число 77 в системе счисления с основанием p заканчивается на 0, а число 29 в
этой системе заканчивается на 1. Чему равно p – основание системы счисления?

Ответ: 7

Решение: При обосновании алгоритма перевода было показано, что с учетом
представления (*) любое число может быть записано в виде:

Отсюда следует возможность представить наши числа 77 и 29 следующим образом:

Следовательно, справедливо соотношение:

Произведение двух целых, отличных от 1, равно 49 в том и только в том случае, когда:

Задача 6: Двузначное число N в системах счисления с основаниями 3 и 7 заканчивается
одной и той же цифрой. Укажите минимально возможное значение N.

Ответ: 21

Решение: N представимо в виде:

Следовательно, справедливо соотношение:

7

Минимальное значение для N получается при:

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

Задача 7:

При выполнении фрагмента программы на печать выводятся два числа - 3 и 18.

Каким может быть минимальное (максимальное) значение числа 
 в этом случае?

  int a = 0, b = 0;
  while (N != 0)
  {
    a = a + 1;  //число цифр в числе
    b = b + N % 10;  //сумма цифр
    N = N / 10;
  }
  Console.WriteLine(" a = " + a.ToString());
  Console.WriteLine(" b = " + b.ToString());
    

Ответ: минимальное 
; максимальное 

Решение: Если в качестве основания системы использовать число 10, то алгоритм
позволяет разобрать десятичное число на цифры. Переменная a играет роль счетчика
цикла, задавая тем самым число цифр в числе. Переменная  в данном фрагменте
вычисляет сумму цифр. Задача сводится к определению к-значного числа по заданной
сумме его цифр. Если сумма трех цифр числа равна 18, то первой цифрой у числа с
минимальным значением может быть цифра 1. Две оставшиеся цифры в сумме дают
17, откуда и следует ответ. Для максимального числа, последней цифрой может быть 0,
а две старшие цифры могут быть равны 9.

Задача 8:

При выполнении фрагмента программы на печать выводятся два числа - 3 и 18.

Перечислите все возможные значения числа 
 в этом случае?

  int a = 0, b = 1;
  while (N != 0)
  {
    a = a + 1;  //число цифр в числе
    b = b * N % 10;  //произведение цифр

8

    N = N / 10;
  }
  Console.WriteLine(" a = " + a.ToString());
  Console.WriteLine(" b = " + b.ToString());
    

Ответ: (129, 136, 163, 192, 219, 233, 291, 316, 323, 332, 361, 613, 631, 912, 921)

Решение: Эта задача является вариацией предыдущей задачи. Здесь необходимо
определить возможное значение трехзначного числа, зная произведение его цифр. В
ответе перечислены все возможные решения.

9

Тексты. Кодирование

Кодирование словами переменной длины.

В основе каждого текста лежит алфавит – конечное множество символов. В основе
текстов на русском языке лежит алфавит, называемый кириллицей, состоящий из 33
строчных и 33 заглавных букв алфавита. Тексты английского языка построены на
основе латиницы – алфавита, содержащего 26 строчных и 26 заглавных букв. Конечно
алфавит, на основе которого строятся тексты на естественных языках, содержит не
только буквы, но и цифры, знаки операций и множество других специальных
символов.

Пусть задан алфавит , содержащий m символов:

Словом 
 в алфавите  называют любую последовательность символов алфавита:

где 
 – это символы алфавита. Число символов в слове –  называют длиной слова.

Справедливо утверждение:

Число различных слов длины k, которые можно построить в алфавите из m символов,
равно: 

Справедливость утверждения легко доказывается по индукции.

Базис индукции: при 
, утверждение справедливо, поскольку словами длины 1

являются m символов алфавита.

Шаг индукции: Пусть утверждение справедливо при некотором . Это означает, что
построено 
 слов длины . Из каждого слова можно построить m новых слов длины 

, приписывая к слову поочерёдно m символов алфавита. Таким образом, слов

длины 
 будет:

Это простое, но важное утверждение, которое в том или ином виде используется при
решении различных задач.

Алфавит компьютера

Тексты, которые хранятся в памяти компьютера, используют один из самых
примитивных алфавитов, состоящий всего из двух символов:

10