1.2 Задачи на Алгоритмизацию и программирование
Из демо 2005 .
B6 |
Записано 7 строк, каждая имеет свой номер – от «0»- до «6»-й.
В начальный момент в строке записана цифра 0 (ноль). На каждом из последующих 6 шагов выполняется следующая операция: в очередную строку записывается удвоенная предыдущая строка, а в конец строки приписывается очередная цифра.
Для удобства в скобках пишется номер строки (начиная с 0).
Ниже показаны первые строки, сформированные по описанному правилу:
(0) 0
(1) 001
(2) 0010012
(3) 001001200100123
Какая цифра стоит в последней строке на 123-м месте (считая слева направо)
Решение:
В первой строке 3 элемента – последняя цифра 1.
Во второй строке (3*2+1) = 7 – последняя цифра 2
(3) 7*2+1 = 15– последняя цифра 3
(4) 15*2+1=31– последняя цифра 4
(5) 31*2+1=63– последняя цифра 5
(6) 63*2+1 =127– последняя цифра 6, 126 – 5 , 125 – 4, 124 – 3, 123 – 2.
Ответ: цифра 2
Демо 2006
B6 |
Цепочки символов (строки) создаются по следующему правилу.
Первая строка состоит из одного символа – цифры «1».
Каждая из последующих цепочек создается такими действиями: в очередную строку дважды записывается цепочка цифр из предыдущей строки (одна за другой, подряд), а в конец приписывается еще одно число – номер строки по порядку.
Вот первые 4 строки, созданные по этому правилу:
(1) 1
(2) 112
(3) 1121123
(4) 112112311211234
Какая цифра стоит в седьмой строке на 120-м месте (считая слева направо)?
Решение:
В первой 1 цифра
Во второй 1*2+1=3
В третьей 3*2+1=7
В четвёртой 7*2+1=15
В пятой 15*2+1=31
В шестой 31*2+1 = 63
В седьмой 63*2+1=127
Седьмая строка оканчивается 11234567, значит 120-я цифра имеет значение 1.
Пример 6. (демо 2009)
Строки (цепочки символов латинских букв) создаются по следующему правилу.
Первая строка состоит из одного символа – латинской буквы «А».
Каждая из последующих цепочек создается такими действиями: в очередную строку сначала записывается буква, чей порядковый номер в алфавите соответствует номеру строки (на i-м шаге пишется «i»-я буква алфавита), к ней справа дважды подряд приписывается предыдущая строка.
Вот первые 4 строки, созданные по этому правилу:
(1) A
(2) BAA
(3) CBAABAA
(4) DCBAABAACBAABAA
Латинский алфавит (для справки):
ABCDEFGHIJKLMNOPQRSTUVWXYZ
Запишите семь символов подряд, стоящие в восьмой строке со 126-го по 132-е место (считая слева направо).
Решение.
8 строка начнется с символа H и со 2 по 128 , с 129 по 255 –й идут символы 7 строки.
Со 126 – 128 записаны три последних символа 7 строки, а со 129 -132 – первые четыре символа 7 строки.
Три последних символа всегда ВАА. 7 строка начинается с символа G, а затем F E D
Ответ: ВААGFED
Пример 1.
Имеется исполнитель Кузнечик, который живет на числовой оси. Система команд Кузнечика: “Вперед N” (Кузнечик прыгает вперед на N единиц); “Назад M” (Кузнечик прыгает назад на M единиц). Переменные N и M могут принимать любые целые положительные значения. Известно, что Кузнечик выполнил программу из 40 команд, в которой команд “Назад 2” на 10 больше, чем команд “Вперед 3”. Других команд в программе не было. На какую одну команду можно заменить эту программу, чтобы Кузнечик оказался в той же точке, что и после выполнения программы?
Решение:
Обозначив за Х – кол-во команд “Вперед 3 получим ур-ние Х+Х+10=40 Х=15 Значит команд “Вперед 3” было 15, а команд “Назад 2” – 25. Таким образом, кузнечик прыгнул вперед 3 х 15 = 45 единиц, а назад 2 х 25 = 50 единиц. То есть он оказался на 5 единиц левее точки из которой начал движение. Следовательно, эту программу можно заменить командой «назад 5».
Ответ: «Назад 5»
(из демо 2004)
B3 |
Имеется исполнитель Кузнечик, который живет на числовой оси. Система команд Кузнечика: “Вперед N” (Кузнечик прыгает вперед на N единиц); “Назад M” (Кузнечик прыгает назад на M единиц). Переменные N и M могут принимать любые целые положительные значения. Известно, что Кузнечик выполнил программу из 50 команд, в которой команд “Назад 2” на 12 больше, чем команд “Вперед 3”. Других команд в программе не было. На какую одну команду можно заменить эту программу, чтобы Кузнечик оказался в той же точке, что и после выполнения программы?
Решение:
Х+Х+12 = 50 Х= 19
Вперед 3 х 19 = 57 единиц; назад 2 х 31 = 62 единицы. Ответ: «Назад 5»
Пример 2
Исполнитель Черепашка перемещается на экране компьютера, оставляя след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существуют две команды:
Вперед n, где n ‑ целое число, вызывающая передвижение черепашки на n шагов в направлении движения.
Направо m, где m ‑ целое число, вызывающая изменение направления движения на m градусов по часовой стрелке.
Запись Повтори 4 [Команда1 Команда2 ]означает, что последовательность команд в скобках повторится 4 раза.
Черепашке был дан для исполнения следующий алгоритм:
Повтори 4 [Вперед 10 Направо 120]
Какая фигура появится на экране?
1) | Незамкнутая ломаная линия |
2) | Правильный треугольник |
3) | Квадрат |
4) | Правильный пятиугольник |
Решение Черепашка прочертит 4 линии, но последний отрезок полностью совпадет с первым, т. к. после третьего выполнения черепашка обернется вокруг своей оси и окажется в той же точке, так что на экране появится треугольник. Ответ 2. (в книге опечатка)
Основные порталы (построено редакторами)