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

Пример 3.2

Файл к задаче https://clck.ru/3MqPm9

Решение: Заходим на лист «Артисты» и с помощью поиска находим исполнителя Guns N» Roses – его ID равен 88. Затем переходим на лист «Альбомы», находим столбец «ID исполнителя» и выбираем значение 88. Таким образом, находим все альбомы данного исполнителя – их ID: 90, 91, 92.

Далее переходим на лист «Треки». Включаем фильтр (в предыдущем задании описано, как это сделать), и в столбце «ID альбома» выбираем значения 90, 91, 92.

Теперь переходим к расчёту длительности треков. Напомним: в одной секунде – 1000 миллисекунд. Чтобы перевести миллисекунды в секунды, делим на 1000. Чтобы перевести секунды в минуты, делим результат на 60.

В ячейку I1 вводим формулу: = (СУММ (E1147:E1188) /1000) /60.

Результат вычисления: 205,9255 – это суммарная продолжительность всех треков альбомов исполнителя Guns N» Roses в минутах. Ответ: 205 (файл с готовым решением https://clck.ru/3MqR8m)

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

Задача 3.3

Файл к заданию: https://clck.ru/3Mrrko

Задача 3.4 Файл к заданию: https://clck.ru/3Mrryo

Задача 3.5

Файл к заданию: https://clck.ru/3MrsCy

Задача 3.5. Для групповых операций с файлами используются маски имен файлов. Маска представляет собой последовательность букв, цифр и прочих допустимых в именах файлов символов, в которых также могут встречаться следующие символы: символ»?» (вопросительный знак) означает ровно один произвольный символ. Символ «*» (звездочка) означает любую последовательность символов произвольной длины, в том числе «*» может задавать и пустую последовательность. Определите, какое из указанных имен файлов не удовлетворяет маске: bys??.*

1) byste. m 2) bys23.exe 3) bystem. dll 4) byszx.problem

Глава 3. Кодирование и линейные алгоритмы. Задача №4. Кодирование и декодирование информации

Кодирование информации – процесс преобразования сигнала из формы, удобной для непосредственного использования информации, в форму, удобную для передачи, хранения или автоматической переработки. Декодирование (операция, обратная кодированию) – перевод кодов в набор символов первичного алфавита. Кодирование может быть равномерное и неравномерное. При равномерном кодировании каждый символ исходного алфавита заменяется кодом одинаковой длины. На примере внизу мы видим, что все буквы имеют одинаковую длину – 2 бита, например, А=00, поэтому код равномерный.

При неравномерном кодировании разные символы исходного алфавита могут заменяться кодами разной длины.

Сообщение однозначно декодируемо с начала, если выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова. Сообщение однозначно декодируемо с конца, если выполняется обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова.

Пример 4.1. Для передачи сообщений, содержащих только буквы К, Л, М, Н, О, П, Р, решили использовать неравномерный двоичный код, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Известны кодовые слова, использованные для некоторых букв: К – 11, Л – 000, П – 0010, Р – 1011. Какое кодовое слово надо назначить для буквы М, чтобы код удовлетворял указанному условию и при этом длина слова МОЛОКО после кодирования была наименьшей? Если таких кодов несколько, укажите код с наименьшим числовым значением.

Решение:

Изобразим буквы К, Л, П, Р на дереве (рекомендую на экзамене прямо так и рисовать мышкой, как у меня выше нарисовано). По условию задачи необходимо, чтобы слово не являлось началом другого кодового слово, т.к. необходимо, чтобы выполнялось прямое условие Фано. Необходимо поставить в дерево две буквы: О и М, чтобы условие Фано выполнялось. Как это сделать? Т.к. буква О в слове «молоко» встречается 3 раза, то мы поставим эту букву на меньшую глубину дерева (01), чтобы получить наименьший код. Букву М, которая встречается всего 1 раз, поставим на большую глубину дерева (100). Итого имеем следующие длины: М=100=3, О=01=2*3 (т.к. 3 раза встречается, поэтому умножаем на 3) =6, Л=000=3, К=11=2. Длина кода равна=3+6+3+2=14. Ответ: 14.

Рассмотрим задачу на обратное условие Фано.

Пример 4.2. По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г. Для передачи используется двоичный код, допускающий однозначное декодирование. Для букв А, Б используются такие кодовые слова: А: 00011, Б: 1001, В: 01100. Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наибольшим числовым значением.

Решение: для выполнения прямого условия Фано букву Г мы можем поставить на свободную ветку дерева, то Г=11 (кратчайший путь), т.к. этот путь не будет являться ничьим началом кодового слова. При обратном условии Фано букву Г=10 можем поставить (кратчайший путь), т.к. 10 не является окончанием ни одного из приведенных кодовых слов в условии. Г=00 взять не можем, т.к. 00 является окончанием В, и тогда не выполняется обратное условие Фано. Из двух чисел 11 и 10 наибольшее – 11. Ответ: 11.

Пример 4.3. Для передачи данных по каналу связи используется 5битовый код. Сообщение содержит только буквы А, Б и В, которые кодируются следующими кодовыми словами: А – 11010, Б – 10111, В – 01101. При передаче возможны помехи. Однако некоторые ошибки можно попытаться исправить. Любые два из этих трёх кодовых слов отличаются друг от друга не менее чем в трёх позициях. Поэтому если при передаче слова произошла ошибка не более чем в одной позиции, то можно сделать обоснованное предположение о том, какая буква передавалась. (Говорят, что «код исправляет одну ошибку». ) Например, если получено кодовое слово 10110, считается, что передавалась буква Б. (Отличие от кодового слова для Б только в одной позиции, для остальных кодовых слов отличий больше.) Если принятое кодовое слово отличается от кодовых слов для букв А, Б, В более чем в одной позиции, то считается, что произошла ошибка (она обозначается «х»). Получено сообщение 11000 11101 10001 11111. Декодируйте это сообщение – выберите правильный вариант.

1) АххБ 3) хххх

2) АВхБ 4) АВББ

Решение: декодируем каждое слово сообщения. Первое слово: 11000 отличается от буквы А только одной позицией, поэтому на первом месте будет А. Второе слово: 11101 отличается от буквы В только одной позицией, поэтому на второй позиции будет В. Третье слово: 10001 отличается от любой буквы более чем одной позицией, поэтому третья позиция – x. Четвёртое слово: 11111 отличается от буквы Б только одной позицией, поэтому четвертая позиция – Б. Таким образом, ответ: АВхБ. Ответ: 2.

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

Задача 4.4. По каналу связи передаются сообщения, содержащие только четыре буквы: М, А, Р, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: М – 101, Р – 100, Т – 01. Укажите кодовое слово минимальной длины, которое можно использовать для буквы А. Если таких кодовых слов несколько, приведите кодовое слово с минимальным числовым значением.

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

Задача 4.5. По каналу связи передаются сообщения, содержащие только шесть букв: Я, Н, В, А, Р, Ь. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Н – 00, В – 01, Р – 10, Ь – 111. Укажите минимально возможную длину закодированной последовательности для слова ВАРВАР.

Задача №5. Анализ, исполнение и построение линейного алгоритма для исполнителя

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

Система счисления – способ записи чисел с помощью определённого набора символов (цифр). Самая привычная – десятичная система (основание 10): цифры от 0 до 9. В информатике часто используют: Двоичную систему (основание 2): цифры 0 и 1. Восьмеричную (основание 8): цифры от 0 до 7. Шестнадцатеричную (основание 16): цифры 0—9 и буквы A (это число 10) —F (это число15).

Перевод числа из одной системы в другую – важный навык для решения хтой задачи. Строка – это последовательность символов, например: «1010» или «ABCD». В Python строки записывают в кавычках: одинарных «…» или двойных «…". Можно обращаться к символам строки по индексу:

s = «hello»

s [0] #даст ’h’.

Строки можно перебирать, разбивать (метод split ()) и соединять (join ()). Список – упорядоченная изменяемая коллекция элементов. Например: [1, 2, 3, 4] или [’a’, ’b’, ’c’]. К элементам списка обращаются по индексу: a [0], a [1] и т. д. Списки удобны для хранения последовательностей символов или чисел. Методы списков: append () – добавить элемент в конец. pop () – удалить элемент.

Работа с системами счисления в Python.

Есть встроенные функции:

int (s, base) – переводит строку s из системы с основанием base в десятичное число;

bin (n) – переводит число n в двоичную строку;

oct (n) – переводит в восьмеричную;

hex (n) – переводит в шестнадцатеричную.

s = «1011»

num = int (s, 2) # перевели из двоичной в десятичную (num = 11)

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

s = input () # Например, «101101»

count_ones = s.count («1») # вычисляет количество цифр один в строке s

Итог:

· Знание систем счисления помогает правильно интерпретировать данные;

· Строки – удобный способ хранить и обрабатывать числа в текстовом виде;

· Списки помогают работать с последовательностями символов или чисел, когда нужна изменяемость или сложная обработка;

· Используйте функции Python для конвертации и обработки данных;

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

Пример 5.1. Алгоритм получает на вход натуральное число N и строит по нему новое число R следующим образом:

1. Строится двоичная запись числа N.

2. Складываются все цифры полученной двоичной записи. В конец записи (справа) дописывается остаток от деления суммы на 2.

3. Предыдущий пункт повторяется для записи с добавленной цифрой.

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

Пример. Дано число N = 13. Алгоритм работает следующим образом:

1. Двоичная запись числа N: 1101.

2. Сумма цифр двоичной записи 3, остаток от деления на 2 равен 1, новая запись 11011.

3. Сумма цифр полученной записи 4, остаток от деления на 2 равен 0, новая запись 110110.

4. Результат работы алгоритма R = 54.

При каком наименьшем числе N в результате работы алгоритма получится R> 170? В ответе запишите это число в десятичной системе счисления.

Решение: рассмотрим первое попавшееся число, которое больше 170. 171=10101011. У этого числа отделим последние два разряда 171= 101010 | 11 не походит, т.к., выполняя второе правило, алгоритм сложит все единицы, которые стоят слева от вертикальной линии 1+1+1=3, а затем 3 разделим на 2 без остатка и получим 1 и запишем эту единица справа от числа 101010 1. Затем снова применим второе правило к получившемуся числу 101010 | 1. И получим уже новое число 101010 | 10. Получившееся число 10101010=170 по условию задачи должно быть равно 171. Понятно, что 171 не равно 170, поэтому число 171 не подходит. Берем число 172=10101100. Проверяем его на второе правило 2 раза и видим, что число 172 подходит. Осталось только число 10101100 без двух правых нулей перевести в десятичную систему счисления. Получаем 101011=43. Ответ: 43.

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

for n in range (42,64):

r = list (bin (n) [2: ]) # преобразуем число сначала в двоичную систему счисления и потом переводим его список строк

    for i in range (len (r)):        r [i] = int (r [i]) # преобразуем каждую строку (двоичная цифра) в целый тип данных    r += [sum (r) %2] # добавляем остаток от деления справа от числа    r += [sum (r) % 2] # добавляем остаток от деления справа от числа    for i in range (len (r)):        r [i] = str (r [i]) # обратный перевод в список строк    if int (»». join (r), 2)> 170:# переводим в целочисленный тип и проверяем на условие задачи        print (n)        breakОтвет: 43.

Пример 5.2. На вход алгоритма подается натуральное число N. Алгоритм строит по нему новое число R следующим образом.

1) Строится двоичная запись числа N.

2) К этой записи дописываются разряды по следующему правилу:

если два последних разряда одинаковые, дописывается 0, иначе дописывается 1.

3) К полученной записи дописывается еще один бит по правилу в пункте 2.

Полученная таким образом запись является двоичной записью искомого числа R.

Укажите минимальное число N, при вводе которого получится значение R больше, чем 61.

В ответе полученное число запишите в десятичной системе.

Решение: узнаем, какое число N может быть, чтобы в результате получилось 61.

61 = 111101 2

Убираем два младших разряда и исполняем алгоритм.

15=1111 2 -> (если два последних разряда одинаковые, то применяем первое правило) -> 111102 -> (два последних разряда разные) -> 111101 2 = 61.

Следовательно, из числа N = 15 10 получается R = 6110. Значит, для того чтобы получить число большее 61, необходимо взять следующее N = 16.

Второй способ решения этой задачи заключается в том, что, как и в первой задаче, мы перебираем по порядку все числа большие 61. Числа 62, 63 под условие алгоритма не подходят, т.к. два последних разряда не соответствуют двум алгоритмам из условия, т.е., например, 62= 1111102, где, откидывая 2 последних разряда, получаем число 111112, и из данного мы не можем получить число 1111102, применив 2 алгоритма из условия. 64=10000002 под условие алгоритма походит, отбрасываем два правых разряда по условию задачи и получаем 100002=16. Ответ: 16.

Пример 5.3. Автомат получает на вход четырехзначное число. По этому числу строится новое число по следующим правилам.

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

2. Полученные два числа записываются друг за другом в порядке возрастания (без разделителей).

Пример. Исходное число: 5431. Произведения: 5 * 4 = 20; 3 * 1 = 3. Результат: 320. Укажите максимальное число, в результате обработки которого автомат выдаст число 1216.

Решение: рассмотрим число 1216. Так как это два произведения двух одноразрядных чисел, имеем два числа 12 и 16.

12 = 2*6 = 3*4

16 = 2*8

Максимально возможная цифра в найденных произведениях – 8. Т.к. необходимо получить максимальное число по условию задачи, значит, максимальное искомое число начинается на 82. Для получения 12 используется максимальное число – 6. Следовательно, оставшиеся два разряда 62. Ответ: 8262.

Пример 5.4. Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду сместиться на (a, b), где a, b – целые числа. Эта команда перемещает Чертёжника из точки с координатами (x, y) в точку с координатами (x + a, y + b). Например, если Чертёжник находится в точке с координатами (4, 2), то команда сместиться на (2, —3) переместит Чертёжника в точку (6, —1).

Цикл

ПОВТОРИ число РАЗ

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

КОНЕЦ ПОВТОРИ

означает, что последовательность команд будет выполнена указанное число раз (число должно быть натуральным).

Чертёжнику был дан для исполнения следующий алгоритм (количество повторений и смещения в первой из повторяемых команд неизвестны):

НАЧАЛОсместиться на (—1, 4)ПОВТОРИ… РАЗсместиться на (…, …)сместиться на (—1, —2)КОНЕЦ ПОВТОРИсместиться на (—23, —12)

КОНЕЦ

После выполнения этого алгоритма Чертёжник возвращается в исходную точку. Какое наибольшее число повторений могло быть указано в конструкции «ПОВТОРИ… РАЗ»?

Решение: будем считать, что Чертёжник находится в начале координат. После выполнения команды сместиться на (—1, 4) Чертёжник окажется в точке с координатами (—1, 4). После выполнения цикла Чертёжник переместится, по оси икс Чертёжник сместится на -1+n (-1+x) -23 и по игреку на 4+n (-2+y) -12, где n, x, y – неизвестные. В результате последнего перемещения Чертёжник должен переместиться в начало координат, то есть:

– 1+n (-1+x) -23=0 и 4+n (-2+y) -12=0

В первом и втором уравнении перенесем цифры в правую часть и получим 1+23=24 и 12—8=8. Остается только найти наибольший общий делитель чисел 24 и 8. Это число 8. Ответ: 8.

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

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

НАЧАЛО

ПОКА <снизу свободно>

вниз

КОНЕЦ ПОКА

ПОКА <слева свободно>

влево

КОНЕЦ ПОКА

ПОКА <сверху свободно>

вверх

КОНЕЦ ПОКА

ПОКА <справа свободно>

вправо

КОНЕЦ ПОКА

КОНЕЦ

Решение: заметим, что в общем случае Робот идет сначала до стены вниз, затем влево, потом вверх и заканчивает маршрут движением вверх, до стены.

Один из главных приёмов в решении этой задачи – проверять клетки группами, а не по одной.

Проверим почти все клетки Робота на предмет того, подходит ли алгоритм:

– A6 – маршрут вниз-вверх – подходит;

– F6 – маршрут влево-вправо – подходит;

– D5 – маршрут вниз-влево, вверх, вправо – подходит;

– E5 – маршрут вниз-влево, вверх, вправо (остановка в D5) – не подходит;

– B4 – маршрут вниз-вверх-вправо (остановка в D4) – не подходит;

– C4 – не двигается, стоит на одном месте – подходит;

– C2 – не двигается, стоит на одном месте – подходит;

– F5 – маршрут вниз-вверх – подходит;

– F4 – вниз-вверх (остановка F5) – не подходит;

– F3 – вниз-вверх (остановка F5) – не подходит;

– F2 – вниз-вверх (остановка F5) – не подходит;

– F1 – вверх (остановка F5) – не подходит;

– A2 – вверх (остановка в А6) – не подходит;

– A1 – не двигается – подходит;

– E1 – влево-вверх-вправо (остановка в D4) – не подходит.

Задача, конечно, нудная, т.к. проверять нужно все клетки, в которых вы сомневаетесь. Понятно, что клетки пустые, где нет стенок, в них Робот начать и остановиться не сможет, поэтому эти клетки можно не проверять. Иногда такие задачи дают на экзамене, и лучше вычеркивать клетки в приложении «Ножницы». Здесь нужна высокая степень концентрации. Ответ: 7.

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

Задача 5.6. На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом:

1) Строится двоичная запись числа N.

2) К этой записи дописываются справа ещё два разряда по следующему правилу: если N чётное, в конец числа (справа) дописывается сначала ноль, а затем единица. В противном случае, если N нечётное, справа дописывается сначала единица, а затем ноль.

Например, двоичная запись 100 числа 4 будет преобразована в 100012, а двоичная запись 111 числа 7 будет преобразована в 111102.

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью числа R – результата работы данного алгоритма.

Укажите минимальное число R, которое больше 102 и может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.

Задача 5.7. Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду сместиться на (a, b), где a, b – целые числа. Эта команда перемещает Чертёжника из точки с координатами (x, y) в точку с координатами (x + a, y + b). Например, если Чертёжник находится в точке с координатами (4, 2), то команда сместиться на (2, —3) переместит Чертёжника в точку (6, —1).

Цикл ПОВТОРИ число РАЗ последовательность команд

КОНЕЦ ПОВТОРИ означает, что последовательность команд будет выполнена указанное число раз (число должно быть натуральным). Чертёжнику был дан для исполнения следующий алгоритм (количество повторений и смещения в первой из повторяемых команд неизвестны):

НАЧАЛОсместиться на (4, 6)ПОВТОРИ… РАЗсместиться на (…, …)сместиться на (-1, -2)КОНЕЦ ПОВТОРИсместиться на (20, 30)КОНЕЦ

После выполнения этого алгоритма Чертёжник возвращается в исходную точку. Какое наибольшее число повторений могло быть указано в конструкции «ПОВТОРИ… РАЗ»?

Задача 5.8. Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости, включает в себя 4 команды-приказа и 4 команды проверки условия.

Команды-приказы: вверх, вниз, влево, вправо

При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →.

Если РОБОТ начнёт движение в сторону находящейся рядом с ним стены, то он разрушится, и программа прервётся.

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

НАЧАЛОПОКА <слева свободно ИЛИ сверху свободно>ЕСЛИ <слева свободно>ТО влевоИНАЧЕ вверхКОНЕЦ ЕСЛИКОНЕЦ ПОКАКОНЕЦ

Задача №6. Простейшие алгоритмы управления исполнителями и вычислительных алгоритмов

Пересечение фигур – это общая часть двух или более геометрических объектов. Если говорить в терминах кругов Эйлера, то это область, которая входит одновременно в оба круга. Объединение фигур – это вся площадь, покрываемая обеими фигурами вместе. В задачах вместо кругов могут использоваться полуокружности, прямоугольники или любые другие многоугольники. Обращаем внимание на условие задачи: нужно ли учитывать точки на границе фигуры или нет. Это важно при вычислении площади и количества точек. Если точки входят в область, то просто перемножаем длину на ширину. Если точки на границе не учитываются, то из длины и ширины вычитаем по единице, и только затем перемножаем полученные значения. Если в задаче возникает несколько отдельных фигур, то для упрощения расчётов считаем количество точек по каждой области отдельно, а затем складываем результаты. Например, если в команде указано вперед (5), и точки на линии включаются, то количество точек будет 6, так как добавляется ещё одна начальная точка: 5 +1 = 6. При нахождении длины стороны по количеству точек, если точки учитываются, то из общего количества отнимаем 1, так как расстояние между точками на отрезке меньше, чем количество самих точек. Обратите внимание, что в разных средах программирования поведение черепахи по умолчанию разное: В Python (модуль turtle) черепашка изначально смотрит вдоль оси X. В Кумире – черепаха изначально направлена вдоль оси Y. Сергей Сергеевич Крылов – разработчик контрольно-измерительных материалов (КИМов) ЕГЭ по информатике – комментирует обновления задачи №6. Он подчёркивает важные моменты, на которые стоит обращать внимание при решении: Уточнено ли, опущен ли хвост в начале? Если сказано, что «изначально хвост поднят», то не нужно дополнительно опускать его в алгоритме. Уточнено ли направление взгляда черепахи? Если сказано, что она смотрит вдоль оси абсцисс, а среда – Кумир, то черепаху необходимо повернуть вправо на 90 градусов в начале, потому что по умолчанию она направлена вдоль оси ординат. Ниже в таблице приводятся справочные команды, которые могут использоваться при решении подобных задач.