Текст книги "Книга-тренажер: «Базовая подготовка к ЕГЭ по информатике в компьютерной форме». Авторский курс"

Задача №10. Текстовый редактор

Для решения данных заданий используем текстовый редактор Word. Для вызова поиска и замены текста необходимо нажать во вкладке Главная кнопку Заменить, также можно использовать сочетание клавиш CTRL+F.

Пример 10.1

Определите, сколько раз в тексте произведения А. С. Пушкина «Капитанская дочка» встречается слово «заикнулась».

Решение:

Откроем файл по ссылке https://yadi.sk/i/3tGyiNGCR2ULHQ. Далее нажмем кнопку Найти. В графе «Найти» введем с большой или маленькой буквы (регистр при поиске не имеет значения, т.к. компьютер ищет все слова и с большой, и с маленькой буквы) слово «заикнулась». И далее, нажав клавишу «Enter» 2 раза, мы найдем 2 слова «заикнулась».

Ответ: 2.

Пример 10.2

С помощью текстового редактора определите, сколько раз, не считая сносок, встречается слово «долг» или «Долг» в тексте романа в стихах А. С. Пушкина «Евгений Онегин». Другие формы слова «долг», такие как «долги», «долгами» и т.д., учитывать не следует. В ответе укажите только число.

Решение:

Откроем файл по ссылке https://yadi.sk/i/lGWR6yAKMR35EA. Откроем вкладку «Найти», далее «Расширенный поиск». В графе «Заменить» введем слово «долг» и после него нажмем клавишу «Пробел». Обращаю внимание, что если вы не нажмете клавишу «Пробел», то компьютер будет искать все слова, которые нам не подходят, а именно «долг», «долги» и т. д. Далее в графе «Заменить» напишем любой знак, например, *. И нажмем кнопку «Заменить все». Произойдет всего 1 замена.

Ответ: 1.

Задачи для самостоятельного решения

Задача 10.3

С помощью текстового редактора определите, сколько раз, не считая сносок, встречается слово «ты» или «Ты» в тексте романа в стихах А. С. Пушкина «Евгений Онегин». Другие формы слова «ты», такие как «твой» и т.д., учитывать не следует. В ответе укажите только число. (ссылка на файл https://yadi.sk/i/Mt-JVMA-SVrq0A)

Задача 10.4

Определите, сколько раз в тексте произведения А. С. Пушкина «Дубровский» встречается существительное «ключ» в любом числе и падеже. (ссылка на файл находится по ссылке https://yadi.sk/i/2ENdOjEe_UeASg).

Глава 6. Информационные модели

Задача №11. Информационный объем сообщения

Для решения заданий данного типа необходимо знать пару формул. Приведем их. 2ⁱ=N, где N – это мощность алфавита, i – вес одного символа в битах. I=i*k, I – информационный объем сообщения, i – вес одного символа в битах, k – количество символов.

Пример 11.1

При регистрации в компьютерной системе каждому объекту сопоставляется идентификатор, состоящий из 15 символов и содержащий только символы из 8-символьного набора: А, В, C, D, Е, F, G, H. В базе данных для хранения сведений о каждом объекте отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование идентификаторов, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно идентификатора, для каждого объекта в системе хранятся дополнительные сведения, для чего отведено 24 байта на один объект. Определите объём памяти (в байтах), необходимый для хранения сведений о 30 объектах. В ответе запишите только целое число – количество байт.

Решение:

Имеем, что один символ может состоять из 8-символьного набора: А, В, C, D, Е, F, G, H, значит, 2ⁱ=8=N, тогда i=3 бита весит один символ. Всего же символов 15. Значит, вес одного идентификатора равен 3*15=45 бит=6 байт (округляем в большую сторону до 6, чтобы хватило объема для хранения идентификатора). Чтобы подсчитать объем памяти одного пользователя, необходимо дополнительные сведения на один идентификатор сложить с весом одного идентификатора. И тогда I=6+24=30 байт на одного пользователя. Всего пользователей 30, то общий объем памяти 20-ти пользователей равен 30*30=900 байт

Ответ: 900.

Пример 11.2

При регистрации на сервере каждый пользователь получает уникальный персональный код, состоящий из 17 символов, каждый из которых может быть одной из 26 заглавных латинских букв или одной из 10 цифр. При этом в базе данных сервера формируется запись, содержащая этот код и дополнительную информацию о пользователе. Для представления кода используют посимвольное кодирование, все символы кодируют одинаковым минимально возможным количеством битов, а для кода в целом выделяется минимально возможное целое количество байтов. Для хранения данных о 30 пользователях потребовалось 3000 байт. Сколько байтов выделено для хранения дополнительной информации об одном пользователе? В ответе запишите только целое число – количество байтов.

Решение:

Т.к. каждый символ может быть одной из 26 заглавных латинских букв или одной из 10 цифр, то N=26+10=36, 2ⁱ=36, тогда i=6. I=k*i=17*6=102 бита=13 байт. Мы знаем, что для 30-ти пользователей потребовалось 3000 байт вместе с дополнительной информацией, значит, для одного пользователя потребуется 3000/30=100 байт. Чтобы подсчитать количество байт для хранения дополнительной информации о пользователе, необходимо из общего количества информации для одного пользователя вычесть количество информации для кода. Итого получаем 100—13=87 байт.

Ответ: 87.

Пример 11.3

Ракетчик принимает сигналы. Каждый сигнал представляет собой совокупность двух полей – номер датчика (целое число от 1 до 300) и уровень сигнала (целое число от 0 до 5000). Каждое поле кодируется одинаковым и минимально возможным количеством бит, каждое поле при этом кодируется отдельно. Все сигналы записываются друг за другом без разделителей. При этом вся последовательность сигналов записывается с помощью минимально возможного целого количества байт.

Определите объем дискового пространства, необходимого для хранения последовательности из 325 сигналов.

Решение:

По формуле 2ⁱ=N=300, то номер датчика кодируется с помощью i=9 бит. По формуле 2ⁱ=N=5000, то уровень сигнала кодируется с помощью i=13 бит.

Один сигнал весит 9 +13 = 22 бит. Всего 325 сигналов, значит, 22*325 = 7150 бит. Или 894 Байта.

Ответ: 894.

Задачи для самостоятельного решения

Задача 11.3

Для регистрации на сайте необходимо продумать пароль, состоящий из 10 символов. Он должен содержать хотя бы 3 цифры, а также строчные или заглавные буквы латинского алфавита (алфавит содержит 26 букв). В базе данных для хранения сведения о каждом пользователе отведено одинаковое и минимальное возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственного пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт одинаковое для каждого пользователя. Для хранения сведений о 30 пользователях потребовалось 870 байт. Сколько байт выделено для хранения дополнительных сведений об одном пользователе? В ответе запишите только целое число – количество байт.

Задача 11.4

Каждый объект, зарегистрированный в информационной системе, получает уникальный код из 14 символов, каждый из которых может быть одной из 26 заглавных латинских букв или одной из 10 цифр. Для представления кода используют посимвольное кодирование, все символы кодируют одинаковым минимально возможным количеством битов, а для кода в целом выделяется минимально возможное целое количество байтов. Кроме того, для каждого объекта в системе выделено 79 байт для хранения содержательной информации. Сколько байтов потребуется для хранения данных (код и содержательная информация) о 30 объектах? В ответе запишите только целое число – количество байтов.

Задача 11.5

Казино завело для хранения результатов клиентов базу данных. В базе данных решено хранить следующую информацию: имя клиента и его фамилию. Известно, что для каждого поля решили использовать одинаковое и минимально возможное количество бит, для всей записи (все 2 поля) – минимально возможное целое количество Байт. Сколько байт необходимо выделить для хранения результата игры в казино, если в них участвовало 52 клиента?

Имя клиента находится в диапазоне от 1 до 1000. В качестве фамилии клиента используется строка из 10 символов, каждый из которых может быть одной из заглавных букв русского алфавита. Фамилия клиента кодируется посимвольно, каждый символ кодируется с помощью одинакового и минимально возможного количества бит.

Задача №12. Исполнители с фиксированным набором команд

В этой задаче используется в основном описание алгоритмов на псевдокоде (условном алгоритмическом языке, включающем в себя и элементы языка программирования, и элементы обычного естественного языка).

Пример 12.1

Команда «Заменить» (v, w). Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды «Заменить» (111, 27) преобразует строку 05111150 в строку 0527150.

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 70 идущих подряд цифр 8? В ответе запишите полученную строку.

 
НАЧАЛО
ПОКА нашлось (2222) ИЛИ нашлось (8888)
ЕСЛИ нашлось (2222)
ТО заменить (2222, 88)
ИНАЧЕ заменить (8888, 22)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
 

Решение:

Отработаем один проход алгоритмической конструкции «то» и «иначе». Для этого запишем начальное условие семьдесят восьмерок 8 (70). Применим к восьмеркам команду «Заменить» 8888, 22 и получим 228 (66) (две двойки и 66 восьмерок). Применим еще раз эту же команду и получим 22228 (62). Далее применим команду «Заменить» (2222, 88) и получим 8 (64). Таким образом, можем сделать вывод, что за отработку логической конструкции «то» и «иначе» количество восьмерок уменьшается каждый раз на 6 (70—6=64). Тогда 11*6=66, т.е. за 11 проходов убралось 66 восьмерок и осталось 70—66=4 восьмерки. 4444, заменим их командой заменить 8888, 22. И получим 22.

Решим задачу cпособом программирования на языке Python.

 
s = '8' * 70 # объявление строки из cемидесяти единиц
while ('2222' in s) or ('8888' in s): # пока строка содержит 2222 или 8888, то цикл выполняется
    if  '2222' in s:
        s = s.replace('2222',"88",1)# замена 2222 на 88, всего один раз
    else:
        s = s.replace('8888', «22», 1)
print(s)
Ответ: 22.
 
 
Пример 12.2
 

Команда «Заменить» (v, w). Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды «Заменить» (111, 27) преобразует строку 05111150 в строку 0527150.

Дана программа для исполнителя Редактор:

 
НАЧАЛО
ПОКА нашлось (111) ИЛИ нашлось (2222)
ЗАМЕНИТЬ (111, 22)
ЗАМЕНИТЬ (2222, 11)
КОНЕЦ ПОКА
КОНЕЦ
 

На вход исполнителю была подана цепочка, состоящая только из символов 1.

В результате работы исполнителя Редактор получена строка – максимальное число, которое может быть получено в результате работы исполнителя.

Определите минимальную длину исходной строки, если известно, что она больше 101.

Решение:

Способом программирования на языке Python

 
for i in range(100, 105):
    n = i
    s = '1' * n # cоздаем исходные списки из единиц
    while ('111' in s) or ('2222' in s): # преобразовываем исходную строку
        s = s.replace('111', '22', 1)
        s = s.replace('2222', '11', 1)
    print(s, i)
 

В качестве ответа получим, что строка 102 превратилась в строку 11.

Ответ: 102.

Пример 12.3

Исполнитель Телепорт существует в лабиринте – поле, представленном в виде квадрата 6х6. Робот имеет две команды: влево, вправо, вверх и вниз, которые перемещают его на клетку влево, вправо, вверх или вниз соответственно. Стены при этом игнорируются. При попытке выхода за границы лабиринта исполнитель разрушается.

Цикл

ПОКА условие

последовательность команд

КОНЕЦ ПОКА

 
выполняется, пока условие истинно.
В конструкции
ЕСЛИ условие
ТО команда1
ИНАЧЕ команда2
 

КОНЕЦ ЕСЛИ

выполняется команда1 (если условие истинно) или команда2 (если условие ложно). Сколько клеток лабиринта соответствуют требованию, что, начав движение в ней и выполнив предложенную программу, Телепорт уцелеет и закончит работу в клетке начала движения?

 
НАЧАЛО
ПОКА <слева свободно>
вправо
КОНЕЦ ПОКА
ПОКА <сверху свободно>
вниз
КОНЕЦ ПОКА
ПОКА <справа свободно>
влево
КОНЕЦ ПОКА
ПОКА <снизу свободно>
вверх
КОНЕЦ ПОКА
КОНЕЦ
 

Решение:

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

При движении из А5 имеем следующий маршрут: А5-А4-выход за границы.

B5 – D5 – D3 – A3 – A5

E5 – E4 – E5 – подходит

D4 – F4 – выход за границы

С3 – выход за границы

С2 – Е2 – E1 – E2

E2 – E1

A1 – (не заходит в цикл) – подходит

B1 – C1

C1 (не заходит в цикл) – подходит

D1 – выход за границы

E1 – F1 – выход за границы

F1 – выход за границы

Ответ: 3.

Пример 12.4

Команда «Заменить» (v, w). Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды «Заменить» (111, 27) преобразует строку 05111150 в строку 0527150.

На вход исполнителю подается цепочка символов, начинающаяся с 0 и содержащая только цифры 1 и 2.

 
НАЧАЛО
ПОКА нашлось (02) ИЛИ нашлось (01)
ЕСЛИ нашлось (01)
ТО заменить (01, 20)
ИНАЧЕ заменить (02, 2101)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
 

Известно, что в результате получилась строка, сумма цифр в которой равна 123. Какое наименьшее количество единиц могло быть в исходной строке?

Решение:

01 преобразуется в 20, 02 в 2101 по условию задачи. Тогда сделаем замену: вместо 01 поставим 20 и получим как на картинке сверху, что 02 преобразовалось в 2120. В конце 20=2+0=+2 и 2+1+2+0=+5. У нас спрашивают в задаче про минимальное число единиц, а они преобразуются в двойки по первому выражению на картинке, это значит, что нужно взять максимум двоек. Как это сделать? 24*5+3=123, тройка не подходит, т.к. не можем получить ее двойками. Как еще? 23*5+8=123. Т.е. 8=2+2+2+2, а ранее мы выяснили, что единица меняется на двойку по условию задачи, каждая двойка заменится на единицу, и ответ будет – четыре единицы.

Ответ: 4.

Задачи для самостоятельного решения

Задача 12.5

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.

А) заменить (v, w).

Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить (111, 27)

преобразует строку 05111150 в строку 0527150. Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.

Б) нашлось (v).

Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

 
Цикл
ПОКА условие
последовательность команд
КОНЕЦ ПОКА
выполняется, пока условие истинно
В конструкции
    ЕСЛИ условие
        ТО команда1
        ИНАЧЕ команда2
КОНЕЦ ЕСЛИ
 

выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 68 идущих подряд цифр 8? В ответе запишите полученную строку.

 
НАЧАЛО
ПОКА нашлось (222) ИЛИ нашлось (888)
    ЕСЛИ нашлось (222)
        ТО заменить (222, 8)
        ИНАЧЕ заменить (888, 2)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
 

Задача 12.6

Исполнитель Робот существует в лабиринте – поле, представленном в виде квадрата 6х6.

Робот имеет две команды: влево, вправо, вверх и вниз, которые перемещает его на клетку влево, вправо, вверх или вниз соответственно. При попытке выхода за границы лабиринта или столкновения со стеной Робот разрушается.

 
Цикл
ПОКА условие
последовательность команд
КОНЕЦ ПОКА
выполняется, пока условие истинно.
В конструкции
ЕСЛИ условие
ТО команда1
ИНАЧЕ команда2
КОНЕЦ ЕСЛИ
 

выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

Сколько клеток лабиринта соответствуют требованию, что, начав движение в ней и выполнив предложенную программу, РОБОТ уцелеет и остановится в закрашенной клетке. (клетка A1)?

 
НАЧАЛО
ПОКА <слева свободно ИЛИ снизу свободно>
ПОКА <снизу свободно>
вниз
КОНЕЦ ПОКА
ПОКА <слева свободно>
влево
КОНЕЦ ПОКА
КОНЕЦ ПОКА
КОНЕЦ
 

Задача №13. Поиск путей в графе

Модель – это искусственно созданный объект, дающий упрощенное представление о реальном объекте, процессе или явлении, отражающий существенные стороны изучаемого объекта с точки зрения цели моделирования. Моделирование – это построение моделей, предназначенных для изучения объектов, процессов или явлений. Распространенными информационными моделями являются графики, схемы, таблицы, диаграммы. Одним из распространенных видов моделей являются графы. Граф – это один из способов графического представления информации. Объекты представлены в нем как вершины (узлы), а связи между объектами как ребра (дуги). То есть граф – это набор вершин и связывающих их ребер. Путь в графе – это конечная последовательность вершин, каждая из которых (кроме последней) соединена со следующей ребром. Граф может содержать циклы (первая вершина пути может совпадать с последней). Обычно в задачах используют взвешенный граф, т.е. граф, в котором с каждым ребром связано число (вес). Например, расстояние, стоимость и т. д.

Граф может задаваться таблицей, в которой на пересечении строки и столбца с наименованиями вершин записано числовое значение (вес) ребра, соединяющего эти вершины.

Дерево – это граф, не имеющий циклов. В дереве существует один-единственный путь между любой парой вершин. Одна из вершин дерева (корень) не имеет входящих ребер, все остальные имеют ровно одно входящее ребро. Вершины, у которых нет исходящих ребер, называются листьями. Пример дерева ниже.

Пример 13.1

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города А в город М, проходящих через город В?

Решение:

Это задание проще всего решается графически. Начинаем с пункта А, т.к. из него считаются пути. Изначально обозначим его за первый путь. Далее в пути Б и Д ведут по одной стрелки, значит, путь равный одному в пункте А переносим в пункты Б и Д

.

Чтобы подсчитать количество путей в Г, мы посмотрим, что в него ведут две стрелки, первая – из А, вторая – из Д. Сделаем сложение этих пунктов: А +Д=1+1=2. В пункт В идет 3 стрелочки – из Б, А и Г. В= Б+А+Г=1+1+2=4. Дорогу из Г в З и из Б в Е – вычеркиваем, т.к. в них путь не проходит через В (условие задачи). Пункт Ж=В+З=4+4=8. И=Ж+З=8+4=12. К=И=12, Л=И=12. М=К+Л=12+12=24.

Ответ: 24.

Пример 13.2

На рисунке приведена схема дорог, соединяющих пункты А, Б, В, Г, Д, Е, Ж, З, И, К. Передвигаться можно только по указанным дорогам в указанном направлении. Определите количество маршрутов из А в И, которые проходят как через пункт Д, так и через пункт О.

Решение:

Пути должны проходить одновременно в условии через Д и О. На решенном внизу рисунке вычеркнем пути, которые нам не подходят, и отобразим количество путей на каждой вершине. В конечную вершину И идут две вершины: И=З+Ж=3+9=12.

Ответ: 12.

Пример 13.3

На рисунке приведена схема дорог, соединяющих пункты А, Б, В, Г, Д, Е, Ж, З, И, К. Передвигаться можно только по указанным дорогам в указанном направлении. Определите, сколько существует маршрутов длиной 5 из А в И. Длиной маршрута считать количество пройденных дорог.

Решение:

Данную задачу лучше всего решать деревом, простроив пути. Намеренно не делаю красивый рисунок, т.к. предлагаю вам делать также, например, в приложении «Ножницы» или Paint, т.к. на экзамене красота не важна, главное – сделать верно и быстро, т.к. время на экзамене ограниченно, а красиво у вас быстро не получится. Рассуждения приведены ниже, если понадобятся к рисунку.

По рисунку можем видеть, что там, где внизу нарисованы плюсики – это те дороги, которые имеют по 5 вершин. Остальные пути нам не подходят.

Ответ: 7.

Пример 13.4

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей, ведущих из города А в город Л и проходящих через участок дороги, который связывает город Д и Ж напрямую?

Решение:

На рисунке, что ниже – вычеркну те пути, что не подходят. И выделю путь ДЖ, через который обязан проходить наш путь по условию задачи. Из А в Д – три пути. Из Д в Ж ничего не меняется – тоже три пути. Из Ж в В – три пути. В И идут два пути – из В и Ж, И=3+3=6. В Л идут два пути – из Ж и И, Л= 6+3=9.

Ответ: 9.

Задачи для самостоятельного решения

Задача 13.5

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Какова длина самого длинного пути из города А в город М? Длиной пути считать количество дорог, составляющих этот путь.

Задача 13.6

На рисунке приведена схема дорог, соединяющих пункты А, Б, В, Г, Д, Е, Ж, З, И, К, Л. Передвигаться можно только по указанным дорогам в указанном направлении. Сколько существует маршрутов из А в Л?

Задача 13.7

На рисунке представлена схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л, М, Н, П, Р, С. По каждой дороге можно передвигаться только в направлении, указанном стрелкой. Сколько существует различных путей из пункта А в пункт С, проходящих через пункт Ж?