Подготовка к ЕГЭ по информатике
Покупка
Новинка
Тематика:
Общая информатика
Издательство:
ИНТУИТ
Автор:
Биллиг Владимир Арнольдович
Год издания: 2016
Кол-во страниц: 38
Дополнительно
Доступ онлайн
В корзину
Курс будет полезен школьникам, сдающим ЕГЭ по информатике.
В лекциях рассказывается как решать некоторые задачи разделов A, B и С экзамена по информатике.
Тематика:
ББК:
УДК:
ОКСО:
- ВО - Бакалавриат
- 00.03.03: Информатика
- ВО - Специалитет
- 00.05.03: Информатика
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов.
Для полноценной работы с документом, пожалуйста, перейдите в
ридер.
Подготовка к ЕГЭ по информатике 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
Доступ онлайн
В корзину