Демонстрационный вариант 2007 год

Успеха на экзамене!

 

 

 

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

Привычка свыше нам дана: Замена счастию она.

 

1)

44 бита

2)

704 бита

3)

44 байта

4)

704 байта

 

Решение: Сосчитаем количество символов в данной фразе(букв, пробелов, знаков препинания).

Букв – 36

Пробелов – 6

Знаков препинания – 2. Итого символов – 44. В Unicode: 1 символ – 16 - бит.

I = 44*16= 704 бита.

Верный ответ 2).

 

 

 

 

Световое табло состоит из лампочек, каждая из которых может находиться в двух состояниях («включено» или «выключено»). Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно было передать 50 различных сигналов?

 

1)

5

2)

6

3)

25

4)

50

 

Решение: Два состояния, значит 1 сигнал – 1 бит.    N = 2^I . N =50 Найдём I. При I =5 N = 32, При I = 6 N = 64.

Если 5 лампочек, то максимально можно передать 32 сигнала, а если 6, то 64 и 50 тем более.

Верный ответ 2).

 

 

 

 

Метеорологическая станция ведет наблюдение за влажностью воздуха. Результатом одного измерения является целое число от 0 до 100 процентов, которое записывается при помощи минимально возможного количества бит. Станция сделала 80 измерений. Определите информационный объем результатов наблюдений.

 

1)

80 бит

2)

70 байт

3)

80 байт

4)

560 байт

 

Решение: 100 = 2^I, I = 7 потому что, при I = 6 можно измерить только 2⁶ = 64.

Найдём объём результатов наблюдений 80* 7 = 560 бит = 70 байт.

Записать ответ 2).

 

 

 

 

 

Сколько единиц в двоичной записи числа 195?

 

1)

5

2)

2

3)

3

4)

4

 

Переведём 195 в двоичную систему счисления.

195 = 2⁷ + 2⁶ + 2 + 1 = 11000011₂.

Единиц – 4.

Верный ответ 4).

 

 

 

 

 

 

Значение выражения 10₁₆ + 10₈ · 10₂ в двоичной системе счисления равно

 

1)

1010

2)

11010

3)

100000

4)

110000

 

Решение: 10₁₆ + 10₈ · 10₂ = 16₁₀ + 8₁₀*2₁₀ = 16+16 = 32 = 2⁵ = 100000₂.

Верный ответ 3).

 

 

 

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

Примечание: знаком * обозначено умножение, знаком := обозначена операция присваивания.

 

1)

8

2)

16

3)

32

4)

12

 

Решение: Первый проход b:=b+1=1, a:=1*2=2, 2) b:=b+1=2, a:=2*2=4, 3) b:=b+1=3, a:=4*2=8, 4) b:=b+1=4, a:=8*2=16.

Верный ответ 2).

 

 

 

 

Определите значение целочисленных переменных a и b после выполнения фрагмента программы:

 

Бейсик	Паскаль	Алгоритмический
a = 1819 b = (a \ 100) * 10 + 9 a = (10*b – a) MOD 100 '\ и MOD – операции, вычисляющие результат деления нацело первого аргумента на второй и остаток от деления соответственно	a:= 1819; b:= (a div 100)*10+9; a:= (10*b–a) mod 100; {div и mod – операции, вычисляющие результат деления нацело первого аргумента на второй и остаток от деления соответственно}	a:= 1819 b:= div(a,100)*10+9 a:= mod(10*b – a,100) |div и mod – функции, вычисляющие результат деления нацело первого аргумента на второй и остаток от деления соответственно|

 

1)	a = 81, b = 199
2)	a = 81, b = 189
3)	a = 71, b = 199
4)	a = 71, b = 189

 

Решение: b:= (a div 100)*10+9 = (1819 div 100)*10 + 9 = 180+9=189.

a:= (10*b–a) mod 100 = (10*189 – 1819) mod 100 = 71mod100=71.

 

Верный ответ 4).

 

 

 

Значения двух массивов A[1..100] и B[1..100] задаются с помощью следующего фрагмента программы:

Сколько элементов массива B будут иметь положительные значения?

 

1)

10

2)

50

3)

90

4)

100

 

Решение: A[n] >0, если n>10 т.е. 90 значений. Циклы независимые.

B[n] >0, если A[n] >0, а n >0 т.к. изменяется от 1 до 100.

Таких значений будет 90.

Верный ответ 3).

 

 

 

Для какого числа X истинно высказывание

 

 ((X>3) \/(X<3))  –> (X<1)

 

1)

1

2)

2

3)

3

4)

4

 

 

Решение: Дизъюнкция истинна, если истинно хотя бы одно из высказываний.

Высказывание Х>3 истинно при Х = 4, а высказывание (X<3) ложно,  значит,  конъюнкция истинна.

Высказывание Х< 1 при X = 4 ложно. Из истины следует ложь – импликация ложна.

Высказывание Х>3 ложно при Х = 3, и высказывание (X<3) ложно,  значит,  конъюнкция ложна.

Высказывание Х< 1 при X = 3 ложно. Из лжи следует ложь – импликация истинна.

При Х=2 Получим из истины следует ложь - импликация ложна.

При Х=1 – аналогично.

Верный ответ 3).

 

 

 

 

 

 

Какое логическое выражение равносильно выражению ¬ (A /\ B) /\ ¬C?

 

1)	¬A \/ B \/ ¬C
2)	(¬A \/ ¬B) /\ ¬C
3)	(¬A \/ ¬B) /\ C
4)	¬A /\ ¬B /\ ¬C

 

Решение: Используя формулу де Моргана ¬ (A /\ B) /\ ¬C=(¬A \/ ¬B) /\ ¬C делаем вывод.

Верный ответ 2).

 

 

 

 

 

Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z.

Дан фрагмент таблицы истинности выражения F:

 

X	Y	Z	F
0	1	0	0
1	1	0	1
1	0	1	0

 

Какое выражение соответствует F?

 

1)	¬X \/ Y \/ ¬Z
2)	X /\ Y /\ ¬Z
3)	¬X /\ ¬Y /\ Z
4)	X \/ ¬Y \/ Z

 

Решение: Проверим 1) ¬X \/ Y \/ ¬Z = ¬0 \/ 1 \/ ¬0 =1 \/ 1 \/ 1=1 не подходит.

2) X /\ Y /\ ¬Z = 0 /\ 1 /\ ¬0 =0 /\ 1 /\ 1=0 - подходит

    Х /\ Y /\ ¬Z = 1/\ 1 /\ ¬0 = 1/\ 1 /\ 1 = 1 – подходит

    Х /\ Y /\ ¬Z = 1/\ 0 /\ ¬1 = 1/\ 0 /\ 0 = 0 – подходит.

Верный ответ 2).

 

 

 

 

 

Таблица стоимости перевозок устроена следующим образом: числа, стоящие на пересечениях строк и столбцов таблиц, означают стоимость проезда между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними.

Укажите таблицу, для которой выполняется условие: “Минимальная стоимость проезда  из А в B не больше 6”.

Стоимость проезда по маршруту складывается из стоимостей проезда между соответствующими  соседними станциями.

 

1)	2)	3)	4)
A B C D Е A     3 1   B     4   2 C 3 4     2 D 1         Е   2 2	A B C D Е A     3 1 1 B     4     C 3 4     2 D 1         Е 1   2	A B C D Е A     3 1   B     4   1 C 3 4     2 D 1         Е   1 2	A B C D Е A       1   B     4   1 C   4   4 2 D 1   4     Е   1 2

 

Решение: По первой. Из А в В можно попасть через С - АС=3, СВ = 4 не подходит =7>6.

 Из А в В через С, Е => AC = 3, CE=2, EB = 2 = 7>6 не подходит

По второй Из А в В через С – АС = 3, СВ = 4 не подходит =7>6

Из А в В через Е и С  –  АЕ = 1, ЕС = 2, СВ = 4 не подходит =7>6

По третьей Из А в В через С – АС = 3, СВ = 4 не подходит =7>6

По третьей Из А в В через С,E – AC = 3, CE = 2, EB = 1  получаем 6 = 6 . Необходимый вариант.

Верный ответ 3).

 

 

 

Для кодирования букв А, Б, В, Г решили использовать двухразрядные последовательные двоичные числа (от 00 до 11 соответственно). Если таким способом закодировать последовательность символов ГБВА и записать результат шестнадцатеричным кодом, то получится:

 

1)

138

2)

DBCA

3)

D8

4)

3120

 

Решение:  Запишем ГБВА кодом 11011000 и переведём в шестнадцатеричный код 11011000.

В этом коде 1000₂ = 8₁₀=8₁₆,  1101₂ = 13₁₀ = D₁₆

Получим 11011000₂ = D8₁₆

Верный ответ 3).

 

 

 

Для составления цепочек разрешается использовать бусины 5 типов, обозначаемых буквами  А, Б, В, Е, И. Каждая цепочка должна состоять из трех бусин, при этом должны соблюдаться следующие правила:

 

1)	на первом месте стоит одна из букв: А, Е, И,
2)	после гласной буквы в цепочке не может снова идти гласная, а после согласной – согласная,
3)	последней буквой не может быть А.

 

Какая из цепочек построена по этим правилам?

 

1)

АИБ

2)

ЕВА

3)

БИВ

4)

ИБИ

 

Решение: По первому условию исключаем вариант 3).

По второму: после гласной буквы в цепочке не может снова идти гласная, исключаем вариант 1).

Остались 2) и 4). По третьему варианту: последней буквой не может быть А, исключается вариант2). Остался 4).

Верный ответ 4).

 

 

 

 

Перемещаясь из одного каталога в другой, пользователь последовательно посетил каталоги  DOC, USER, SCHOOL, A:\, LETTER, INBOX. При каждом перемещении пользователь либо спускался в каталог на уровень ниже, либо поднимался на уровень выше. Каково полное имя каталога, из которого начал перемещение пользователь?

 

1)	A:\DOC
2)	A:\ LETTER\INBOX
3)	А:\SCHOOL\USER\DOC
4)	А:\DOC\USER\SCHOOL

 

Решение: А:\SCHOOL\USER\DOC . Сначала поднялся DOC, USER, SCHOOL, A:\, потом спустился LETTER, INBOX.

Верный ответ 3).

 

 

 

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

 

Фамилия	А	В	С
Иванов	3	2	1

 

За правильное решение задачи типа А участнику начислялся 1 балл, за решение задачи типа В – 2 балла и за решение задачи типа С – 3 балла. Победитель определялся по сумме баллов, которая у всех участников оказалась разная. Для определения победителя олимпиады достаточно выполнить следующий запрос:

 

1)	Отсортировать таблицу по возрастанию значения поля С и взять первую строку.
2)	Отсортировать таблицу по убыванию значения поля С и взять первую строку.
3)	Отсортировать таблицу по убыванию значения выражения А+2В+3С и взять первую строку.
4)	Отсортировать таблицу по возрастанию значения выражения А+2В+3С и взять первую строку.

 

 

Решение: Отсортировать таблицу по убыванию значения выражения А+2В+3С и взять первую строку.

Верный ответ 3).

 

 

 

 

Для хранения растрового изображения размером 64´64 пикселя отвели 512 байтов памяти. Каково максимально возможное число цветов в палитре изображения?

 

1)

16

2)

2

3)

256

4)

1024

 

Решение: Найдём глубину цвета. 64*64*I =  512*8 => I = 4096/4096 = 1бит.

Число цветов равно 2^I = 2¹ = 2.

Верный ответ 2).

 

 

 

В ячейке B1 записана формула =2*$A1. Какой вид приобретет формула, после того как ячейку B1 скопируют в ячейку C2?

Примечание: знак $ используется для обозначения абсолютной адресации.

 

1)

=2*$B1

2)

=2*$A2

3)

=3*$A2

4)

=3*$B2

 

Решение: =2*$A1 скопируется в C2 и примет вид =2*$A2.

 

*$A – абсолютная ссылка, 1 – относительная ссылка.

Верный ответ 2).

 

 

 

 

 

В цехе трудятся рабочие трех специальностей – токари (Т), слесари (С) и фрезеровщики (Ф). Каждый рабочий имеет разряд не меньший второго и не больший пятого. На диаграмме I отражено количество рабочих с различными разрядами, а на диаграмме II – распределение рабочих по специальностям.

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

 

I)                                                                                            II)

 

Имеются четыре утверждения:

А) Все рабочие третьего разряда могут быть токарями

Б) Все рабочие третьего разряда могут быть фрезеровщиками

В) Все слесари могут быть пятого разряда

Г) Все токари могут быть четвертого разряда

 

Какое из этих утверждений следует из анализа обеих диаграмм?

1)

А

2)

Б

3)

В

4)

Г

 

Решение:   Из двух диаграмм можно выбрать Т-3, С – 4, Ф – 5.

Делаем вывод: Все рабочие третьего разряда могут быть токарями.

Верный ответ 1).

 

 

 

 

В приведенном ниже фрагменте алгоритма, записанном на алгоритмическом языке, переменные a, b, c имеют тип «строка», а переменные i, k – тип «целое». Используются следующие функции:

Длина (a) – возвращает количество символов в строке a. (Тип «целое»)

Извлечь (a, i) – возвращает i-тый (слева) символ в строке a. (Тип «строка»)

Склеить (a, b) – возвращает строку, в которой записаны сначала все символы строки a, а затем все символы строки b. (Тип «строка»)

Значения строк записываются в одинарных кавычках
(Например, a := ‘дом’).

Фрагмент алгоритма:

i := Длина (a) k := 2 b := ‘А’ пока i > 0 нц c := Извлечь (a, i) b := Склеить (b, c) i := i – k кц b := Склеить (b, ‘Т’)

Какое значение будет у переменной b после выполнения вышеприведенного фрагмента алгоритма, если значение переменной a было ‘ПОЕЗД’?

 

1)

‘АДЕПТ’

2)

‘АДЗЕОП’

3)

‘АДТЕТПТ’

4)

‘АДЗОТ’

 

Решение: Вначале i = 5 Извлекаем Д Получаем ‘АД’, Извлекаем 5-2 = 3 => Е Получаем ‘АДЕ’, Извлекаем 3-2=1 – П, Получаем ‘АДЕП’. Всё. Склеиваем с Т.

Получим ‘АДЕПТ’

Верный ответ 1).

Часть В.

 

 

 

Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 22 оканчивается на 4.

 

22= 18 + 4=> Первое 14₁₈ = 24₉ = 34₆ .

Записать ответ 6,9,18.

 

 

 

 

 

Каково наибольшее целое число X, при котором истинно высказывание

(90<X·X) –> (X < (X -1)) ?

 

Решение: Импликация ложна, когда посылка истинна, следствие ложно, в остальных случаях истинна.

Посылка истинна 90<X*X => X>9 или X <-9

Проверим следствие при этих значениях Х > 9 => (X<(X-1))  - ложно. Импликация ложна.

Проверим следствие при этих значениях Х < - 9 => (X<(X-1)) – ложно. Импликация ложна.

Посылка ложна, если – 9 £ X £ 9. Проверим следствие. (X < (X -1)) – ложно. Импликация истинна.

Наибольшее число 9.

Записать ответ. 9.

 

 

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

1.  прибавь 2

2.  умножь на 3

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

умножь на 3

прибавь 2

умножь на 3

прибавь 2

прибавь 2,

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

 

  Решение: ((0+2)*3+2)*3+2+2 = 28 – шесть команд

Записать ответ 121211.

 

 

 

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

Один считает, что первой будет Наташа, а Маша будет второй.

Другой болельщик на второе место прочит Люду, а Рита, по его мнению, займет четвертое место.

Третий любитель тенниса с ними не согласился. Он считает, что Рита займет третье место, а Наташа будет второй.

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

Какое место на чемпионате заняли Наташа, Маша, Люда, Рита?

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

Первое высказывание первого болельщика истинно, а второе ложно.

Первое высказывание второго болельщика истинно, а второе ложно

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

 

	Наташа	Маша	Люда	Рита
I	1	0	0	0
II	0	0	1	0
III	0	0	0	1
IV	0	1	0	0

 

 

 

 

 

 

Противоречия условию нет. Правильное решение.

Записать ответ: 1423.

 

 

 

 

 

Скорость передачи данных через ADSL-соединение равна 256000 бит/c. Передача файла через это соединение заняла 2 минуты. Определите размер файла в килобайтах.

 

Решение: I = 256000 бит/c* 2*60 c = 30720000 бит = 30720000/8 байт = 384000байт =384000/1024 Килобайт =

 = 3750 килобайт.

Записать ответ: 3750.

 

 

 

 

 

 

Цепочки символов (строки) создаются по следующему правилу.

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

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

(1)       1

(2)       112

(3)       1121123

(4)       112112311211234

 

Сколько раз в общей сложности встречаются в восьмой строке четные цифры (2, 4, 6, 8)?

 

Решение:

Первая строка 1 цифра

Вторая строка 1*2+1 = 3 цифры(2 единицы, 1 двойка)

Третья строка 3*2+1 = 7 цифр(4 единицы, 2 двойки, 1 тройка)

Четвертая строка 7*2+1 = 15цифр(8 единиц, 4 двойки, 2 тройки, 1 четверка) и дальше

5) 15*+1=31(16(1), 8(2), 4(3), 2(4), 1(5))

6) 31*2+1=63(32(1), 16(2), 8(3), 4(4), 2(5), 1(6))

7) 63*2+1=127(64(1), 32(2), 16(3), 8(4), 4(5), 2(6),1(7))

8) 127*2+1=255(128(1), 64(2), 32(3), 16(4), 8(5), 4(6),2(7), 1(8)).

64 + 16+4+1 = 85.

Записать ответ: 85.

 

 

 

 

Доступ к файлу ftp.net , находящемуся на сервере txt.org, осуществляется по протоколу http. В таблице фрагменты адреса файла закодированы буквами от А до Ж. Запишите последовательность этих букв, кодирующую адрес указанного файла в сети Интернет.

 

 

A	.net
Б	ftp
В	://
Г	http
Д	/
Е	.org
Ж	txt

 

Решение: http://txt.org/ftp.net

Записать ответ: ГВЖЕДБА.

 

 

 

В таблице приведены запросы к поисковому серверу. Расположите обозначения запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по  каждому запросу.

Для обозначения логической операции “ИЛИ” в запросе используется символ |, а для логической операции “И” – &.

 

А	волейбол | баскетбол | подача
Б	волейбол | баскетбол | подача | блок
В	волейбол | баскетбол
Г	волейбол & баскетбол & подача

 

 

Решение: Г(волейбол & баскетбол & подача), В(волейбол | баскетбол), А(волейбол | баскетбол | подача),

Б(волейбол | баскетбол | подача | блок).

 

Записать ответ. ГВАБ.

 

 

 

Требовалось написать программу, которая решает уравнение «ax+b=0» относительно x для любых чисел a и b, введенных с клавиатуры. Все числа считаются действительными. Программист торопился и написал программу неправильно.

 

ПРОГРАММА  НА ПАСКАЛЕ	ПРОГРАММА  НА БЕЙСИКЕ	ПРОГРАММА НА СИ
var a, b, x: real; begin readln(a,b,x); if b = 0 then write('x = 0') else if a = 0 then write('нет решений') else write('x =',-b/a); end.	INPUT a, b, x IF b = 0 THEN PRINT "x = 0" ELSE IF a = 0 THEN PRINT "нет решений" ELSE PRINT "x=",-b/a ENDIF ENDIF END	void main(void) { float a,b,x;  scanf("%f%f%f",  &a,&b,&x);  if (b==0)  printf("x=0");  else  if (a==0)  printf("нет решений");  else  printf("x=%f",-b/a); }

 

Последовательно выполните три задания:

1) Приведите пример таких чисел a, b, x, при которых программа неверно решает поставленную задачу.

2) Укажите, какая часть программы является лишней.

3) Укажите, как нужно доработать программу, чтобы не было случаев ее неправильной работы. (Это можно сделать несколькими способами, поэтому можно указать любой способ доработки исходной программы).

 

 

 

Содержание верного ответа (допускаются иные формулировки ответа, не искажающие его смысла)

Элементы ответа: 1) a = 0   b = 0, x = 0(значение x можно не указывать, допустим ответ, что x – любое число) 2) Лишняя часть: не нужно вводить x с клавиатуры верно: readln(a,b); 3) Возможная доработка: readln(a,b); if a = 0 then if b = 0 then write('любое число') else write('нет решений') else write('x=',-b/a); (могут быть и другие способы доработки). При оценке других вариантов доработки программы нужно проверять, что поставленная цель достигается.

                                                                                                                                                                   

 

 

 

 

Опишите на русском языке или одном из языков программирования алгоритм поиска номера первого из двух последовательных элементов в целочисленном массиве из 30 элементов, сумма которых максимальна (если таких пар несколько, то можно выбрать любую из них).

 

 

Содержание верного ответа и указания по оцениванию (допускаются иные формулировки ответа, не искажающие его смысла)
Введем целочисленную переменную MaxSum, в которую будем заносить максимальную сумму двух последовательных элементов в просмотренной части массива, и переменную MaxNum, в которую будем заносить номер первого элемента в этой паре. Первоначально в эти переменные занесем сумму первых двух элементов и номер 1 соответственно. В цикле до конца массива: проверяем, превосходит ли сумма элементов очередной пары уже найденный максимум; если да, то заносим в переменную MaxSum новую сумму, а в переменную MaxNum – номер первого элемента пары. По окончании цикла выводим значение переменной MaxNum. Пример правильной и эффективной программы (на основе алгоритма, использующего однократный проход по массиву):
На языке Паскаль	На языке Бейсик
const N=30; var a:array[1..N] of integer; MaxSum, MaxNum, i: integer; begin MaxNum:=1; MaxSum:=a[1]+a[2]; for i:=2 to N-1 do begin if a[i]+a[i+1]>MaxSum then begin MaxNum:=i; MaxSum:=a[i]+a[i+1]; end end; writeln(MaxNum); end.	N=30 DIM i, MaxSum, MaxNum, a(N) AS INTEGER MaxNum=1 MaxSum=a(1)+a(2) FOR i = 2 TO N-1 IF a(i)+a(i+1)>MaxSum THEN  MaxNum=i MaxSum=a(i)+a(i+1) ENDIF NEXT i PRINT MaxNum END

 

	Баллы
Предложен правильный алгоритм, выдающий верное значение (в том числе и алгоритм, требующий двукратного прохода по массиву или создания массива сумм пар). Возможно использование числа 30 вместо константы. Возможно наличие отдельных синтаксических ошибок (пропущенные «;», неверная запись оператора присваивания и т.п.), не искажающих замысла автора программы.	2
Имеется не более двух ошибок из числа следующих: 1)         Не задано первое значение MaxNum 2)         Неверно задается первое значение MaxSum 3)         Не указано или неверно указано условие завершения цикла 4)         Индексная переменная в цикле не меняется 5)         Неверно расставлены операторные скобки	1
Ошибок, перечисленных выше, больше двух, или алгоритм сформулирован неверно.	0
Максимальный балл	2

   

 

 

Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй – 2 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче, или добавляет 1 камень в какую-то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 16 камней. Кто выигрывает при безошибочной игре – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.

 

 

Содержание верного ответа и указания по оцениванию (допускаются иные формулировки ответа, не искажающие его смысла)

Выигрывает второй игрок. Для доказательства рассмотрим неполное дерево игры, оформленное в виде таблицы, где в каждой ячейке записаны пары чисел, разделенные запятой. Эти числа соответствуют количеству камней на каждом этапе игры, в первой и второй кучах соответственно.

1 ход 2 ход 3 ход 4 ход   Старто вая позиция I-й игрок (все варианты хода) II-й игрок (выиг рыш ный ход) I-й игрок (все варианты хода) II-й игрок (один из вариан тов) Пояснение 3,2   3,3   4,3 4,4 12,4 Второй игрок выигрывает на четвертом ходу, после любого ответа первого игрока, например, утроив число камней в самой большой куче 9,4 27,4 3,12 3,36 3,5 3,15   4,2   4,3 Те же варианты третьего-четвертого ходов   9,2   27,2 Второй игрок выигрывает ответным ходом 3,6 18,3 Второй игрок выигрывает ответным ходом

 

 

Таблица содержит все возможные варианты ходов первого игрока. Из неё видно, что при любом ходе первого игрока у второго имеется ход, приводящий к победе.
Указания по оцениванию	Баллы
Правильное указание выигрывающего игрока и его ходов со строгим доказательством правильности (с помощью или без помощи дерева игры).	3
Правильное указание выигрывающего игрока, стратегии игры, приводящей к победе, но при отсутствии доказательства ее правильности.	2
При наличии в представленном решении одного из пунктов: 1. Правильно указаны все варианты хода первого игрока и возможные ответы второго игрока (в том числе и все выигрышные), но неверно определены дальнейшие действия и неправильно указан победитель. 2. Правильно указан выигрывающий игрок, но описание выигрышной стратегии неполно и рассмотрены несколько (больше одного, но не все!) вариантов хода первого игрока и частные случаи ответов второго игрока.	1
В представленном решении полностью отсутствует описание элементов выигрышной стратегии, и отсутствует анализ вариантов первого-второго ходов играющих (даже при наличии правильного указания выигрывающего игрока).	0
Максимальный балл	3

 

 

 

На вход программе подаются сведения о сдаче экзаменов учениками 9-х классов некоторой средней школы. В первой строке сообщается количество учеников N, которое не меньше 10, но не превосходит 100, каждая из следующих N строк имеет следующий формат: <Фамилия> <Имя> <оценки>, где <Фамилия> – строка, состоящая не более чем из 20 символов, <Имя> – строка, состоящая не более чем из 15 символов, <оценки> – через пробел три целых числа, соответствующие оценкам по пятибалльной системе. <Фамилия> и <Имя>, а также <Имя> и <оценки> разделены одним пробелом. Пример входной строки:

Иванов Петр 4 5 4

Требуется написать программу, которая будет выводить на экран фамилии и имена трех лучших по среднему баллу учеников. Если среди остальных есть ученики, набравшие тот же средний балл, что и один из трех лучших, то следует вывести и их фамилии и имена. Требуемые имена и фамилии можно выводить в произвольном порядке.

 

 

 

 

 

 

Содержание верного ответа и указания по оцениванию (допускаются иные формулировки ответа, не искажающие его смысла)

Программа верно читает входные данные, запоминая фамилии, имена и сумму баллов в массиве записей (или в нескольких массивах), сразу или за дополнительный просмотр подсчитывая три лучших по величине суммы баллов (так как количество экзаменов у всех учеников одинаковое, лучший средний балл соответствует лучшей сумме баллов). Затем за дополнительный просмотр этого массива распечатывается информация о тех учениках, которые набрали в сумме баллов не меньше третьей по величине суммы. Баллы начисляются только за программу, которая решает задачу хотя бы для частного случая (например, все ученики набрали различный средний балл).

 

Пример правильной и эффективной программы на языке Паскаль: var p:array[1..100] of record                          name:string;                          sum:integer;                        end;     c:char;     i,j,N,s1,s2,s3,m:integer; begin   readln(N);   for i:=1 to N do   begin     p[i].name:='';     repeat       read(c);       p[i].name:=p[i].name+c     until c=' '; {считана фамилия}     repeat       read(c);       p[i].name:=p[i].name+c     until c=' '; {считано имя}     p[i].sum:=0;     for j:=1 to 3 do     begin       read(m);       p[i].sum:=p[i].sum+m     end; {подсчитана сумма баллов}     readln;   end;

s1:=0; s2:=0; s3:=0;   for i:=1 to N do   begin     if p[i].sum>s1 then       begin         s3:=s2; s2:=s1;         s1:=p[i].sum       end else     if p[i].sum>s2 then       begin         s3:=s2; s2:=p[i].sum       end else     if p[i].sum>s3 then s3:=p[i].sum;   end;   for i:=1 to N do     if p[i].sum>=s3 then writeln(p[i].name); end.

 

Пример правильной программы на языке Бейсик: DIM i, j, n, s1, s2, s3, sum(100) AS INTEGER DIM s AS STRING DIM nm(100) AS STRING INPUT n FOR j = 1 TO n LINE INPUT s c$ = MID$(s, 1, 1) i = 1 WHILE NOT (c$ = " ")  i = i + 1  c$ = MID$(s, i, 1) WEND i = i + 1 c$ = MID$(s, i, 1) WHILE NOT (c$ = " ")  i = i + 1  c$ = MID$(s, i, 1) WEND nm(j) = MID$(s, 1, i) sum(j) = ASC(MID$(s, i + 1, 1)) - ASC("0") sum(j)=sum(j)+(ASC(MID$(s,i+3,1))-ASC("0")) sum(j)=sum(j)+(ASC(MID$(s,i+5,1))-ASC("0")) NEXT j s1 = 0: s2 = 0: s3 = 0 FOR j = 1 TO n   IF sum(j) > s1 THEN     s3 = s2: s2 = s1     s1 = sum(j)   ELSE   IF sum(j) > s2 THEN     s3 = s2: s2 = sum(j)   ELSE     IF sum(j) > s3 THEN s3 = sum(j)   END IF   END IF NEXT j FOR j = 1 TO n IF sum(j) >= s3 THEN PRINT nm(j) NEXT j END

 

Указания по оцениванию	Баллы
Программа работает верно, т.е. корректно выделяет из входных данных оценки, ищет три лучших суммы баллов и распечатывает учеников, набравших эти суммы. Допускается наличие в тексте программы одной синтаксической ошибки.	4
Программа работает в целом верно, но содержит по крайней мере две из следующих неточностей (нерациональностей): сохраняются не суммы баллов (средние баллы), а сами баллы и суммы перевычисляются несколько раз заново; явно вычисляются средние баллы, что приводит к сравнению вещественных чисел; при нахождении трех максимальных значений элементы массива переставляются местами; при печати сравнения производятся с каждым из трех максимальных элементов. Допускается наличие от одной до трех синтаксических ошибок: пропущен или неверно указан знак пунктуации, неверно написано или пропущено зарезервированное слово языка программирования, не описана или неверно описана переменная, применяется операция, недопустимая для соответствующего типа данных.	3
Программа работает в целом верно, но выводит только трех лучших учеников, даже если кто-то еще сдал экзамены не хуже. Возможно, в реализации алгоритма содержатся 1–2 ошибки (используется знак “<” вместо “>”, “or” вместо “and” и т.п.). Возможно, некорректно организовано считывание входных данных. Допускается наличие до пяти синтаксических ошибок: пропущен или неверно указан знак пунктуации, неверно написано или пропущено зарезервированное слово языка программирования, не описана или неверно описана переменная, применяется операция, недопустимая для соответствующего типа данных.	2
Программа неверно работает при некоторых входных данных и, возможно, содержит ошибку в алгоритме поиска трех максимальных элементов. Допускается до 4 различных ошибок в ходе решения задачи, в том числе описанных в критериях присвоения двух баллов. Допускается наличие от одной до семи синтаксических ошибок: пропущен или неверно указан знак пунктуации, неверно написано или пропущено зарезервированное слово языка программирования, не описана или неверно описана переменная, применяется операция, недопустимая для соответствующего типа данных.	1
Задание выполнено неверно	0
Максимальный балл	4

 

 

Задания части С выполнены как и в варианте. По остальным при обнаружении ошибки пишите progmat@list.ru

 

 

На главную