Вики-учебник Подготовка к ЕГЭ/Информатика/Алгоритмизация и программирование/Умение исполнять алгоритм

Текущая версия на 18:19, 22 февраля 2009

Шаблон:Campus

[править] Описание задания

[править] Примеры решения

[править] Формальное исполнение алгоритма, записанного на естественном языке (A12)

2008 год

Между четырьмя крупными аэропортами, обозначенными кодами DLU, IGT, OPK и QLO, ежедневно выполняются авиарейсы. Приведён фрагмент расписания перелётов между этими аэропортами:

Путешественник находится в аэропорту 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-е место (считая слева направо).

Решение:

Пронумеруем наши последовательности (строки) и подсчитаем количество цифр в каждой из них. Полученные данные сведем в следующую таблицу:

Первое: очевидно, что количество символов в строке можно вычислить по формуле: 2 ⁿ⁺¹ - 1, где n - номер строки. Тогда количество символов в восьмой строке будет равно 2⁹ - 1= 511. Далее, в каждой строке можно выделить середину – символ, стоящий на позиции с= 2ⁿ- . Нетрудно видеть, что в середине каждой строки стоит символ А, которым заканчивается предыдущая строка, и за ним вновь следуют символы предыдущей строки.

Второе: первые 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)?

Решение:

Продолжим строки, чтобы понять закономерность четных элементов:

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

Ответ: 85

[править] Умение исполнять алгоритм,записанный на естественном языке (В8)

"Задача 2"

Строки (цепочки символов латинских букв) создаются по следующему правилу:

Первая строка состоит из одного символа - латинской буквы «А». Каждая из последующих цепочек создается такими действиями: в очередную строку сначала записывается буква, чей порядковый номер в алфавите соответствует номеру строки (на i-м шаге пишется «i»-я буква алфавита), к ней справа дважды подряд приписывается предыдущая строка. Вот первые 4 строки, созданные по этому правилу:

(1) A

(2) BAA

(3) СВААВАА

(4) DCBAABAACBAABAA

Латинский алфавит (для справки): ABCDEFGHIJKLMNOPQRSTUVWXYZ

Определите количество букв D в первых одиннадцати строках.

Решение:

Пронумеруем наши последовательности (строки) и подсчитаем количество букв D в каждой из них. Полученные данные сведем в следующую таблицу:

Первое: очевидно, что количество букв D в строке можно вычислить по формуле: 2 ^n-4 , где n - номер строки. Тогда количество букв D в одиннадцатой строке будет равно 2⁷= 128. Второе: Найдем суммарное количество букв D с 4 по 11 строки. Получим ответ.

Ответ:255

[править] Основные причины ошибок, которые допускают учащиеся

Назад к разделу Алгоритмизация и программирование

Назад к разделу Вики-учебник для подготовки к ЕГЭ/Раздел Информатика