Задания (стр. 3 )

сверху свободно снизу свободно

слева свободно справа свободно

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

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

1 4

НАЧАЛО

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

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

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

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

КОНЕЦ

Решение: Легко понять, что для того, чтобы исполнитель вернулся обратно в ту клетку, откуда он начал движения, четыре стенки должны быть расставлены так, чтобы он упирался в них сначала при движении влево, затем – вниз, вправо и, наконец, вверх. На рис.1 синяя точка обозначает клетку, начав с которой РОБОТ вернется обратно.

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

Обратим внимание, что возможны еще «вырожденные» варианты, как показано на рис.2. На рис.3 показаны те клетки, которые соответствуют условию задачи.

Рис. 1

Рис.2

Рис.3

Часть 2

B1. В базе данных хранятся записи, содержащие информацию о датах. Каждая запись содержит три поля: год (число от 1 до 2100), номер месяца (число от 1 до 12) и номер дня в месяце (число от 1 до 31). Каждое поле записывается отдельно от других полей с помощью минимально возможного числа бит. Определите минимальное количество бит, необходимых для кодирования одной записи.

Решение: Нужно определить минимально возможные размеры в битах для каждого из трех полей и сложить их.

Для кодирования года (число от 1 до 2100) потребуется 12 бит (212=4096>2100). Для номер месяца (число от 1 до 12) потребуется 4 бита (24 = 16 ≥ 12). Для номера дня в месяце (число от 1 до 31) потребуется 5 бит (25=32>31). Таким образом, всего требуется 12+4+5=21 бит.

Ответ: 21

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

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

Начальные значения	a= -3	b=11
a<=4	да
a:=a+2	-1
b:=b-1		10
a<=4	да
a:=a+2	1
b:=b-1		9
a<=4	да
a:=a+2	3
b:=b-1		8
a<=4	да
a:=a+2	5
b:=b-1		7
a<=4	нет
b:=b-1		6
a:=a+1	6
b>0		да
b:=b-1		5
a:=a+1	7
b>0		да
b:=b-1		4
a:=a+1	8
b>0		да
b:=b-1		3
a:=a+1	9
b>0		да
b:=b-1		2
a:=a+1	10
b>0		да
b:=b-1		1
a:=a+1	11
b>0		да
b:=b-1		0
a:=a+1	12
b>0		нет

Ответ: 12

B3. У исполнителя Калькулятор две команды, которым присвоены номера:

1. прибавь 2

2. умножь на 3

Выполняя первую из них, Калькулятор прибавляет к числу на экране 2, а выполняя вторую, утраивает его. Запишите порядок команд в программе получения из 0 числа 56, содержащей не более 5 команд, указывая лишь номера команд. (Например, программа 21211 – это программа:

умножь на 3

прибавь 2

умножь на 3

прибавь 2

прибавь 2,

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

Решение: Попробуем решить задачу «обратным ходом», начав с числа 56.

1)  Раз 56 не делится на 3, то последней командой может быть увеличение на 2, поэтому над стрелкой записан номер команды 1:

2)  число 54 делится на 3, поэтому предыдущая команда – умножение на 3:

3)  число 18 делится на 3, поэтому предыдущая команда - тоже умножение на 3:

4)  очевидно, что предыдущая команда – тоже умножение на 3:

5)первой командой должна быть команда прибавь 2:

Получили полную цепочку. Таким образом, правильный ответ – 12221, эта программа состоит из 5 команд.

Ответ: 12221

B4. Петя записал IP-адрес школьного сервера на листке бумаги и положил его в карман куртки. Петина мама случайно постирала куртку вместе с запиской. После стирки Петя обнаружил в кармане четыре обрывка с фрагментами IP-адреса. Эти фрагменты обозначены буквами А, Б, В и Г. Восстановите IP-адрес. В ответе укажите последовательность букв, обозначающих фрагменты, в порядке, соответствующем IP-адресу.

Решение: Каждое из 4-х чисел в IP-адресе должно быть в интервале от 0 до 255, поэтому сразу определяем, что фрагмент Б – самый последний, так как в противном случае одно из чисел получается больше или 505).

Фрагмент Г (число 22) может быть только первым, поскольку варианты 2.1922 и 5.16222 дают число, большее 255.

Из фрагментов А и В первым должен быть А, иначе получим 225.1622> 255). Таким образом, верный ответ – ГАВБ.

Ответ: ГАВБ

B5. Укажите через запятую в порядке возрастания все десятичные числа, не превосходящие 30, запись которых в четверичной системе счисления оканчивается на 31?

Решение: Для решения задачи достаточно рассмотреть следующие числа в четверичной системе счисления: 314, 1314 и перевести их в десятичную систему счисления:

314=3*4+1=1310

1314=1*42+3*4+1=2910

Ответ: 13 29

B6. Сколько секунд потребуется модему, передающему сообщения со скоростью 32000 бит/с, чтобы передать 16-цветное растровое изображение размером 800 ´ 600 пикселей, при условии, что в каждом байте закодировано максимально возможное число пикселей?

Решение: Обозначим через V=32000бит/с – скорость модема, через S=600×800×4 бит – величину растрового изображения. Так как изображение 16-цветное, то отводится 4 бита на цвет (16=24 по формуле Хартли). Тогда время, требуемое для передачи этого изображения можно вычислить по формуле:

T=S : V=600×800×24 : 32000=60 (c).

Ответ: 60

B7. Перед началом Турнира Четырех болельщики высказали следующие предположения по поводу своих кумиров:

А) Макс победит, Билл – второй;

В) Билл – третий, Ник – первый;

С) Макс – последний, а первый – Джон.

Когда соревнования закончились, оказалось, что каждый из болельщиков был прав только в одном из своих прогнозов. Какое место на турнире заняли Джон, Ник, Билл, Макс? (В ответе перечислите подряд без пробелов места участников в указанном порядке имен.)

Решение: Надо помнить, что в каждом высказывании есть одно истинное утверждение, и одно – ложное. Если предположить, что Макс победит, то высказывание С) будет неверным в обоих утверждениях, что противоречит условию. Если предположить, что утверждение Джон – первый в высказывании С) – верно, тогда в высказывании А) будет верным утверждение, что Билл – второй. Но тогда мы получим, что в высказывании В) оба утверждения неверны, что противоречит условию. Остается предположить, что Ник – первый. Тогда из высказывания А) следует, что Билл – второй, а из высказывания С) – Макс _ последний. В этом случае в каждом высказывании есть одно верное утверждение и одно неверное, что не противоречит условию. Из высказываний мы определили, что на турнире 1 место занял Ник, 2 место – Билл и 4 место – Макс. Следовательно, 3 место занял Джон.

(Обратите внимание, как правильно записывается ответ.)

Ответ: 3124

B8. Цепочки символов (строки) создаются по следующему правилу. Первая строка состоит из одного символа, это цифра 1. Каждая из следующих цепочек создается так. Сначала записывается порядковый номер данной строки, далее дважды записывается вся цепочка цифр из предыдущей строки. Первые 4 строки, созданные по этому правилу, выглядят следующим образом:

1

211

3211211

Сколько раз в общей сложности встречается в 9-й строке цифра 1?

Решение: Эта задача легко решается, если обратить внимание, как меняется количество единиц от ряда к ряду.

(0)1 k=1=20

(1)211 k=2=21

(2)3211211 k=4=22

211 k=8=23

. . .

k=512=29

Ответ: 512

B9. В таблице приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета:

Запрос	Количество страниц (тыс.)
пирожное | выпечка	14200
пирожное	9700
пирожное & выпечка	5100

Сколько страниц (в тысячах) будет найдено по запросу

выпечка

Решение: По запросу пирожное | выпечка выдается множество страниц, в которых встречаются или одно слово или другое. По запросу пирожное & выпечка выдается множество страниц, в которых встречаются оба слова вместе. По запросам пирожное и выпечка выдается множество страниц, в которых встречается только данное слово. Следовательно, чтобы получить количество страниц, найденных по запросу выпечка надо выполнить следующие вычисления:

14200 +5100 – 9700=9600

Ответ: 9600

B10. Сколько различных решений имеет уравнение

(((K → M) → (M Ù L Ù N)) Ú ((K Ù M) → (M Ú L Ú N))) Ù (L Ù M) = 1

где K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений K, L, M и N, при которых выполнено данное равенство. В качестве ответа вам нужно указать только количество таких наборов.

Решение: Надо помнить, что:

· импликация ложна, если из истины следует ложь, во всех остальных случаях она истинна;

· конъюнкция истинна, если все утверждения истинны, во всех остальных случаях она ложна;

· дизъюнкция ложна, если все утверждения ложны, во всех остальных случаях она истинна.

Уравнение имеет решение, если выражения (((K → M) → (M Ù L Ù N)) Ú ((K Ù M) → (M Ú L Ú N))) и (L Ù M) – истинны. Второе выражение истинно, если L=1 и M=1. Первое выражение всегда истинно, т. к. выражение (K Ù M) всегда будет ложным, независимо от K, т. к. M=1, отсюда выражение ((K Ù M) → (M Ú L Ú N)) – истинно, следовательно и все выражение (((K → M) → (M Ù L Ù N)) Ú ((K Ù M) → (M Ú L Ú N))) – истинно при любых значениях K и N. Таким образом, получаем 4 набора переменных, при которых уравнение имеет решение:

L=1 M=1 K=0 N=0

L=1 M=1 K=0 N=1

L=1 M=1 K=1 N=0

L=1 M=1 K=1 N=1.

Ответ: 4

ЧАСТЬ 1

За правильный ответ на каждое задание части 1 ставится 1 балл. Если указаны два и более ответов (в том числе правильный), неверный ответ или ответ отсутствует – 0 баллов.

№ Задания	Ответ	№ Задания	Ответ
A1	4	A10	3
A2	2	A11	2
A3	4	A12	4
A4	4	A13	1
A5	1	A14	2
A6	3	A15	2
A7	1	A16	1
A8	4	A17	3
A9	2	A18	2

ЧАСТЬ 2

За правильный ответ на задания В1–В10 ставится 1 балл, за неверный ответ или его отсутствие – 0 баллов.

№	Ответ
B1	21
B2	12
B3	12221
B4	ГАВБ
B5	13 29
B6	60
B7	3124
B8	512
B9	9600
B10	4