Вики-учебник Подготовка к ЕГЭ/Информатика/Алгоритмизация и программирование/Умение исполнять алгоритм
Описание задания
Примеры решения
Формальное исполнение алгоритма, записанного на естественном языке (A12)
2008 год
Между четырьмя крупными аэропортами, обозначенными кодами DLU, IGT, OPK и QLO, ежедневно выполняются авиарейсы. Приведён фрагмент расписания перелётов между этими аэропортами:
Аэропорт вылета | Аэропорт прилета | Время вылета | Время прилета |
---|---|---|---|
QLO | IGT | 06:20 | 08:35 |
ЮТ | DLU | 10:25 | 12:35 |
DLU | IGT | 11:45 | 13:30 |
ОРК | QLO | 12:15 | 14:25 |
QLO | DLU | 12:45 | 16:35 |
IGT | QLO | 13:15 | 15:40 |
DLU | QLO | 13:40 | 17:25 |
DLU | ОРК | 15:30 | 17:15 |
QLO | ОРК | 17:35 | 19:30 |
ОРК | DLU | 19:40 | 21:55 |
Путешественник находится в аэропорту DLU в полночь (0:00). Определите самое раннее время, когда он может оказаться в аэропорту QLO.
1) 15:40;
2) 16:35;
3) 17:15;
4) 17:25.
Решение:
Договоримся указывать аэропорт и время вылета/прибытия в виде пары (аэропорт, время). Из таблицы можно выделить три маршрута:
1.(DLU,13:40) (QLO,17:25)
2.(DLU, 11:45) (IGT, 13:30) пересадка (IGT,13:15) (QLO,15:40)
3. (DLU,15:30) (ОРК, 17:15) пересадка (ОРК,12:15) (QLO, 14:25)
Нетрудно видеть, что для второго и третьего маршрута во время пересадки придется потратить не менее половины суток на ожидание. Поэтому самое раннее время, когда можно оказаться в аэропорту 17:25.
Ответ: 4.
Умение исполнить алгоритм для конкретного исполнителя с фиксированным набором команд (А18)
Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости: вверх, вниз, влево, вправо.
При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх , вниз , влево, вправо. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ: снизу свободно, слева свободно, справа свободно, слева свободно. Цикл ПОКА < условие > команда выполняется, пока условие истинно, иначе происходит переход на следующую строку. Если РОБОТ начнет движение в сторону стены, то он разрушится и программа прервется. Сколько клеток лабиринта соответствуют требованию, что, выполнив предложенную программу, РОБОТ уцелеет и остановится в той же клетке, с которой он начал движение?
НАЧАЛО
ПОКА < снизу свободно > вправо
ПОКА < справа свободно > вверх
ПОКА < сверху свободно > влево
ПОКА < слева свободно > вниз
КОНЕЦ
1) 1;
2) 2;
3) 3;
4) 4.
Ответ: 2.
Умение исполнять алгоритм в среде формального исполнителя (В5)
На экране есть два окна, в каждом из которых написано по числу. У исполнителя Сумматор две команды, которым присвоены номера:
1. запиши сумму чисел в первое окно
2. запиши сумму чисел во второе окно
Выполняя первую из них, Сумматор складывает числа в окнах и заменяет этой суммой число в первом окне, а выполняя вторую, складывает числа и заменяет этой суммой число во втором окне. Запишите порядок команд в программе получения из пары чисел 1 и 2 пары чисел 11 и 19, содержащей не более 5 команд, указывая лишь номера команд.
(Например, программа 21211 это программа
запиши сумму чисел во второе окно
запиши сумму чисел в первое окно
запиши сумму чисел во второе окно
запиши сумму чисел в первое окно
запиши сумму чисел в первое окно
которая преобразует пару чисел 1 и 0 в пару чисел 8 и 3.)
Решение:
Обозначим исходную конфигурацию в виде вектора (1,0), где его первая координата- первое окно, а вторая координата – второе окно. Приведем необходимую последовательность операторов для получения конфигурации (8,3).
Начало(1,0)
запиши сумму чисел во второе окно (1,1)
запиши сумму чисел в первое окно (2,1)
запиши сумму чисел во второе окно (2,3)
запиши сумму чисел в первое окно (5,3)
запиши сумму чисел в первое окно (8,3)
Ответ: 21211
Умение исполнять алгоритм,записанный на естественном языке (В8)
Строки (цепочки символов латинских букв) создаются по следующему правилу:
Первая строка состоит из одного символа - латинской буквы «А». Каждая из последующих цепочек создается такими действиями: в очередную строку сначала записывается буква, чей порядковый номер в алфавите соответствует номеру строки (на i-м шаге пишется «i»-я буква алфавита), к ней справа дважды подряд приписывается предыдущая строка. Вот первые 4 строки, созданные по этому правилу:
(1) A
(2) BAA
(3) СВААВАА
(4) DCBAABAACBAABAA
Латинский алфавит (для справки): ABCDEFGHIJKLMNOPQRSTUVWXYZ
Запишите семь символов подряд, стоящие в восьмой строке со 126-го по 132-е место (считая слева направо).
Решение:
Пронумеруем наши последовательности (строки) и подсчитаем количество цифр в каждой из них. Полученные данные сведем в следующую таблицу:
Номер строки | Цепочка символов строки | Количество цифр в строке |
---|---|---|
(0) | A | 1 |
(1) | BAA | 3 |
(2) | СВААВАА | 7 |
(3) | DCBAABAACBAABAA | 15 |
…. | ……………….. | … |
(8) | IHGFEDCBA | 511 |
Первое: очевидно, что количество символов в строке можно вычислить по формуле: 2 n+1 - 1, где n - номер строки. Тогда количество символов в восьмой строке будет равно 29 - 1= 511. Далее, в каждой строке можно выделить середину – символ, стоящий на позиции с= 2n- . Нетрудно видеть, что в середине каждой строки стоит символ А, которым заканчивается предыдущая строка, и за ним вновь следуют символы предыдущей строки.
Второе: первые n+1 символов строки (n) образуют первые n+1 символов алфавита, записанные в обратном порядке. Назовем их префиксом строки.
Рекурсивная структура n-ой строки в общем виде такова:
Строка( n)=Префикс строки длины n+1..GFEDCBA || строка (n-1) || строка (n-1),
строка (n-1) - cередина
где символ || означает конкатенацию строк. За счет добавления в начало строки одного нового символа, середина строки (n-1) в следующей строке получает смещение на 1 вправо. Учитывая приведенные соображения, выделяя символы середины, можно определить символы восьмой строке со 126-го по 132-е место.
Ответ: ABAAGFE
2008 год
В6
Цепочки символов (строки) создаются по следующему правилу. Первая строка состоит из одного символа – цифры «1». Каждая из последующих цепочек создается следующим действием: в очередную строку дважды записывается предыдущая цепочка цифр (одна за другой, подряд), а в конец приписывается еще одно число – номер строки по порядку (на i-м шаге дописывается число «i»). Вот первые 4 строки, созданные по этому правилу:
(1) 1
(2) 112
(3) 1121123
(4) 112112311211234
Сколько раз в общей сложности встречаются в восьмой строке четные цифры (2, 4, 6, 8)?
Решение:
Продолжим строки, чтобы понять закономерность четных элементов:
Номер строки | Элементы строки | Количество четных цифр |
---|---|---|
(1) | 1 | 0 |
(2) | 112 | 1 |
(3) | 1121123 | 2 |
(4) | 112112311211234 | 5 |
(5) | 1121123112112341121123112112345 | 10 |
(6) | 112112311211234112112311211234511211231121123411211231121123456 | 21 |
(7) | --------- | 42 |
(8) | --------- | 85 |
Количество четных чисел в каждой следующей строке должно быть в два раза больше, чем в предыдущей, так как длина строки тоже увеличивается в два раза, но когда номер строки четный, то к исходному удвоенному числу прибавляется ещё единица.
Ответ: 85
Умение исполнять алгоритм,записанный на естественном языке (В8)
"Задача 2"
Строки (цепочки символов латинских букв) создаются по следующему правилу:
Первая строка состоит из одного символа - латинской буквы «А». Каждая из последующих цепочек создается такими действиями: в очередную строку сначала записывается буква, чей порядковый номер в алфавите соответствует номеру строки (на i-м шаге пишется «i»-я буква алфавита), к ней справа дважды подряд приписывается предыдущая строка. Вот первые 4 строки, созданные по этому правилу:
(1) A
(2) BAA
(3) СВААВАА
(4) DCBAABAACBAABAA
Латинский алфавит (для справки): ABCDEFGHIJKLMNOPQRSTUVWXYZ
Определите количество букв D в первых одиннадцати строках.
Решение:
Пронумеруем наши последовательности (строки) и подсчитаем количество букв D в каждой из них. Полученные данные сведем в следующую таблицу:
Номер строки | Цепочка символов строки | Количество букв D в строке |
---|---|---|
(4) | DCBAABAACBAABAA | 1 |
(5) | EDCBAABAACBAABAADCBAABAACBAABAA | 2 |
(6) | ... | 4 |
(7) | ... | 8 |
…. | ……………….. | … |
(11) | ... | 128 |
Первое: очевидно, что количество букв D в строке можно вычислить по формуле: 2 n-4 , где n - номер строки. Тогда количество букв D в одиннадцатой строке будет равно 27= 128. Второе: Найдем суммарное количество букв D с 4 по 11 строки. Получим ответ.
Ответ:255
Основные причины ошибок, которые допускают учащиеся
Назад к разделу Алгоритмизация и программирование
Назад к разделу Вики-учебник для подготовки к ЕГЭ/Раздел Информатика