Алгоритмизация

Подробно разобраны задания с выбором одного и кратким ответом по теме "Алгоритмизация". Можно использовать для подготовки к ЕГЭ и ГИА. 

Задания с кратким ответом:

№ 10

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

Первая строка состоит из одного символа – латинской буквы «А». Каждая из последующих цепочек создается такими действиями:

• Сначала дважды записывается предыдущая строка;

• Затем к ней приписывается следующая по алфавиту буква;

Пример:

(1) A

(2) AAB

(3) AABAABC

(4) AABAABCAABAABCD

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

Запишите четыре символа подряд, стоящие в седьмой строке со 123-го по 126-е место (считая слева направо).

Алгоритмизация

Задания с выбором одного ответа

№ 1

Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на

клетчатой плоскости:

При выполнении этих команд РОБОТ перемещается на одну клетку соответственно: вверх

↑, вниз ↓, влево ←, вправо →.

Четыре команды служат для проверки истинности условия отсутствия соответствующей

стены у той клетки, где находится РОБОТ:

Цикл ПОКА условие команда выполняется, пока условие истинно, иначе происходит

переход на следующую строку. Если РОБОТ начнет движение в сторону стены, то он

разрушится, и выполнение программы прервется.

Сколько клеток лабиринта соответствуют требованию, что, выполнив предложенную

программу, РОБОТ уцелеет и остановится в той же клетке, с которой он начал

выполнение программы?

НАЧАЛО

ПОКА вниз

ПОКА вправо

ПОКА вверх

ПОКА влево

КОНЕЦ

A B C D E F

1) 1 2) 2 3) 3 4) 4

Решение:

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

движения появится стена.

Для решения этой задачи также ограничим перебор, определим:

1. траекторию движения РОБОТа, описанную заданным алгоритмом;

2. клетки, в которых РОБОТ может остановиться,

и проверим выполнение алгоритма только для клеток, в которых РОБОТ может

остановиться.

Будем называть успешным движение РОБОТа, при котором он не разрушится.

Подходит только клетка В5.

Ответ: 1.

№ 2

Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на

клетчатой плоскости:

При выполнении этих команд РОБОТ перемещается на одну клетку соответственно: вверх

↑, вниз ↓, влево ←, вправо →.

Четыре команды служат для проверки истинности условия отсутствия соответствующей

стены у той клетки, где находится РОБОТ:

Цикл ПОКА условие команда выполняется, пока условие истинно, иначе происходит

переход на следующую строку. Если РОБОТ начнет движение в сторону стены, то он

разрушится, и выполнение программы прервется.

Сколько клеток лабиринта соответствуют требованию, что, выполнив предложенную

программу, РОБОТ уцелеет и остановится в той же клетке, с которой он начал

выполнение программы?

НАЧАЛО

ПОКА влево

ПОКА вниз

ПОКА вправо

ПОКА вверх

КОНЕЦ

1) 1 2) 2 3) 3 4) 4

Решение:

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

движения появится стена.

Для решения этой задачи также ограничим перебор, определим:

1. траекторию движения РОБОТа, описанную заданным алгоритмом;

2. клетки, в которых РОБОТ может остановиться,

и проверим выполнение алгоритма только для клеток, в которых РОБОТ может

остановиться.

Будем называть успешным движение РОБОТа, при котором он не разрушится.

Подходит только клетка Е3.

Ответ: 1.

№ 3

Петя пригласил своего друга Сережу в гости, но не сказал ему код от цифрового замка

своего подъезда, а послал следующее SMS-сообщение: “в последовательности цифр 4, 7,

2, 1, 9 все числа меньше пяти увеличить на 1, а из всех больших пяти вычесть 1, затем

удалить из полученной последовательности все нечетные числа”. Выполнив действия,

указанные в сообщении, Сережа получил следующий код для цифрового замка:

1. 628 2) 42 3) 68 4) 428

Решение:

Выполним алгоритм получения кода по шагам.

1) все цифры, меньше пяти увеличить на 1: 57329

2) из всех больших пяти вычесть 1: 56328

3) удалить все нечетные числа : 628

Ответ: № 1

4+1 7-1 2+1 1+1 9-1

5 6 3 2 8

6 2 8

Ответ: 628.

№ 4

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

по следующим правилам.

1. Записывается результат сложения значений старших разрядов заданных чисел.

2. К нему дописывается результат сложения значений средних разрядов этих чисел по

такому правилу: если он меньше первой суммы, то второе полученное число

приписывается к первому слева, иначе – справа.

3. Итоговое число получают приписыванием справа к полученному после второго шага

числу суммы значений младших разрядов исходных чисел.

Пример. Исходные трехзначные числа: 328, 207. Поразрядные суммы: 5,2,15.

Результат:2515

Определите, какое из предложенных чисел может быть результатом такой операции.

1) 15117 2) 19213 3) 181717 4) 11146

Решение:

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

которых представляет собой сумму двух однозначных чисел.

• Сумма цифр старших разрядов принадлежит отрезку [2, 18]. Минимальные цифры в

старших разрядах трехзначного числа равны 1, минимальная сумма старших разрядов

равна 2. Максимальные цифры в разрядах равны 9, максимальная сумма равна 18.

• Суммы цифр остальных разрядов принадлежат отрезку [0, 18].

По заданию можно определить, что вторая часть числа должна быть больше первой.

Рассмотрим каждое из предложенных чисел:

1) 15117 – варианты представления числа: 15 11 7 и 15 1 17.

11

2) 19213 – каким бы образом мы не разбили это число на три части, одна из них всегда

будет больше 18, значит вариант ответа неверный

3) 181717 – можно разбить число на 18, 17 и 17. 17

4) 11146 – можно разбить число на 11 14 6. 14 11. Ответ верный.

Ответ: 4

№ 5

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

по следующим правилам.

1. Записывается результат сложения значений старших разрядов заданных чисел.

2. К нему дописывается результат сложения значений средних разрядов этих чисел по

такому правилу: если он меньше первой суммы, то второе полученное число

приписывается к первому справа, иначе – слева.

3. Итоговое число получают приписыванием справа к полученному после второго шага

числу суммы значений младших разрядов исходных чисел.

Пример. Исходные трехзначные числа 721, 195. Поразрядные суммы: 8, 11, 6. Результат:

1186.

Определите, какое из предложенных чисел может быть результатом такой операции.

1) 1112 2) 151612 3) 19118 4) 12045

Решение:

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

которых представляет собой сумму двух однозначных чисел.

• Сумма цифр старших разрядов принадлежит отрезку [2, 18]. Минимальные цифры в

старших разрядах трехзначного числа равны 1, минимальная сумма старших разрядов

равна 2. Максимальные цифры в разрядах равны 9, максимальная сумма равна 18.

• Суммы цифр остальных разрядов принадлежат отрезку [0, 18].

По заданию можно определить, что вторая часть числа должна быть меньше первой.

Рассмотрим каждое из предложенных чисел:

1) 1112 – варианты представления числа: 1 11 2, 1 1 12 и 11 1 2.

В первых двух вариантах 11 1 и 1=1 ответ не подходит.

А третий вариант 1

2) 151612 – можно разбить число на 15 16 12.

16 15, ответ неверный.

3)19118– – каким бы образом мы не разбили это число на три части, одна из них всегда

будет больше 18, значит вариант ответа неверный

4) 12045 – можно разбить число на 12 04 5.

Десятичная запись числа начинается с 0 (04), ответ неверный.

Ответ: 1

Задания с кратким ответом

№ 6

Исполнитель Робот ходит по клеткам клетчатой доски, переходя по одной из команд

вверх, вниз, вправо, влево в соседнюю клетку в указанном направлении. Робот

выполнил следующую программу:

вправо, вправо, вверх, влево, вправо, влево, влево, вверх, вправо.

Укажите наименьшее возможное число команд в программе, приводящей Робота из той

же начальной клетки в ту же конечную.

Решение: «взаимное сокращение» команд. Будем вычеркивать из

заданной последовательности пары взаимно обратных команд (вверх-вниз или вправо-

влево).

вправо, вправо, вверх, влево, вправо, влево, влево, вверх, вправо.

Осталось три команды: вверх, вверх, вправо.

Ответ:3.

№ 7

У исполнителя Вычислитель две команды, которым присвоены номера:

1. прибавь 3

2. умножь на 4

Выполняя первую из них, Вычислитель прибавляет к числу на экране 1, а выполняя

вторую, увеличивает его в четыре раза. Запишите порядок команд в программе получения

из числа 2 числа 152, содержащей не более пяти команд, указывая лишь номера команд.

(Например, программа 12111 – это программа

прибавь 3

умножь на 4

прибавь 3

прибавь 3

прибавь 3

которая преобразует число 1 в число 25).

Решение: Для наглядного представления вариантов решений подобной задачи удобно

использовать дерево. По условию задачи можно использовать не более пяти команд, поэтому дерево

должно иметь не более пяти уровней. Дерево будем строить по уровням (в ширину) – от

каждого узла верхнего уровня порождаются два узла следующего уровня.

Ответ: 22112

№ 8

Специализированный процессор работает с двоичными положительными целыми

однобайтовыми числами. Он может выполнять две команды:

1. сдвиг числа влево на один двоичный разряд

2. вычти 1

Для заданного десятичного числа 14 процессором выполнена последовательность

команд 11222. Запишите полученный результат в десятичной системе счисления.

Определим результат выполнения последовательности команд 212112 для

исходного числа 14 = 1110₂:

Таким образом, в результате выполнения заданной последовательности команд

получено число 53.

Ответ: 53.

№ 9

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

строка состоит из одного символа – латинской буквы «А». Каждая из последующих

цепочек создается такими действиями: в очередную строку сначала записывается буква,

чей порядковый номер в алфавите соответствует номеру строки (на i-м шаге пишется i-я

буква алфавита), к ней слева дважды подряд приписывается предыдущая строка.

Вот первые 4 строки, созданные по этому правилу:

(1) A

(2) AAB

(3) AABAABC

(4) AABAABCAABAABCD

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

ABCDEFGHIJKLMNOPQRSTUVWXYZ

Имеется задание:

«Определить пять символов, стоящих в n-й строке начиная с позиции 2n–1– 2, считая от

левого края цепочки».

Выполните это задание для n = 9

Решение:

Определим количество символов Ni в i-той строке: Ni = Ni_–1*2+1; N₁ = 1.

Вычислим номер символа, стоящего на позиции 2^n-1 – 2, для n=9 номер символа

равен 2⁸– 2=254. Нам необходимо определить пять символов, стоящих на позициях 254, 255, 256, 257 и 258 соответственно.

Первые 255 символов девятой строки есть восьмая строка. На 255-ой позиции в

восьмой строке стоит символ H. На 254-ой позиции в восьмой строке стоит символ G, последний символ седьмой повторяющейся строки. В девятой строке сразу за 255-м символом начинается повтор восьмой строки с начала, то есть AABAAB…....

Покажем эти позиции в строке:

Ответ: GHAAB

№ 10

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

Первая строка состоит из одного символа – латинской буквы «А». Каждая из

последующих цепочек создается такими действиями:

• Сначала дважды записывается предыдущая строка;

• Затем к ней приписывается следующая по алфавиту буква;

Пример:

(1) A

(2) AAB

(3) AABAABC

(4) AABAABCAABAABCD

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

Запишите четыре символа подряд, стоящие в седьмой строке со 123-го по 126-е место

(считая слева направо).

Решение:

Определим количество символов Ni в i-той строке: Ni = Ni_–1*2+1; N₁ = 1.

Вычислим номер символа, стоящего на позиции 2^n-1 – 1, для n=7 номер символа

равен 2⁷– 1=127. Нам необходимо определить пять символов, стоящих на позициях 123, 124, 125 и 126 соответственно.

На 127-ой позиции в седьмой строке стоит символ G. На 126-ой позиции в седьмой строке стоит символ F, последний символ шестой повторяющейся строки. Перед F – E. Перед E - D. И так далее.

Покажем эти позиции в строке:

Ответ: CDEF

№ 11

Определите значение переменной B после выполнения фрагмента алгоритма,

представленного блок-схемой:

Знаком := обозначена операция присваивания.

В ответе укажите одно число – значение переменной B.

Решение:

При решении задач такого типа могут применяться трассировочные таблицы как

первого, так и второго вида. Однако, поскольку алгоритм содержит циклическую

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

Устанавливаем контрольную точку в заголовке цикла с условием В

Для данного алгоритма получим следующую трассировочную таблицу:

Ответ: 7