--PAGE_BREAK--
В этом случае правильный ответ будет записан в виде:
HBAF
Ответ: ___________________________.
В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» – символ «&».
В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.
Запрос
Найдено страниц
(в тысячах)
Шахматы | Теннис
7770
Теннис
5500
Шахматы & Теннис
1000
Какое количество страниц (в тысячах) будет найдено по запросу
Шахматы?
Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.
Ответ: ___________________________.
У исполнителя Кузнечик две команды:
1. прибавь 3,
2. вычти 2.
Первая из них увеличивает число на экране на 3, вторая – уменьшает его на 2 (отрицательные числа допускаются).
Программа для Кузнечика – это последовательность команд. Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 5 команд?
Ответ: ___________________________.
Определите, какое число будет напечатано в результате выполнения следующего алгоритма (для Вашего удобства алгоритм представлен на четырех языках):
Ответ: ___________________________.
Сколько существует различных наборов значений логических переменных x1, x2,… x9, x10, которые удовлетворяют всем перечисленным ниже условиям?
((x1 ≡ x2) \/ (x3 ≡ x4)) /\ (¬(x1 ≡ x2) \/ ¬(x3 ≡ x4)) =1
((x3 ≡ x4) \/ (x5 ≡ x6)) /\ (¬(x3 ≡ x4) \/ ¬(x5 ≡ x6)) =1
((x5 ≡ x6) \/ (x7 ≡ x8)) /\ (¬(x5 ≡ x6) \/ ¬(x7 ≡ x8)) =1
((x7 ≡ x8) \/ (x9 ≡ x10)) /\ (¬(x7 ≡ x8) \/ ¬(x9 ≡ x10)) =1
В ответе не нужно перечислять все различные наборы значений x1, x2,… x9, x10, при которых выполнена данная система равенств. В качестве ответа вам нужно указать количество таких наборов.
Ответ: ___________________________.
Часть 3
Требовалось написать программу, при выполнении которой с клавиатуры считываются координаты точки на плоскости (x,
y – действительные числа) и определяется принадлежность этой точки заданной закрашенной области (включая границы). Программист торопился и написал программу неправильно.
Бейсик
Паскаль
INPUT x, y
IF y>=x THEN
IF y>=0 THEN
IF y
PRINT«принадлежит»
ELSE
PRINT "непринадлежит"
ENDIF
ENDIF
ENDIF
END
var x,y: real;
begin
readln(x,y);
if y>=x then
if y>=0 then
if y
write('принадлежит')
else
write('не принадлежит')
end.
Си
Алгоритмический
язык
void main(void){
float x,y;
scanf("%f%f",&x,&y);
if (y>=x)
if (y>=0)
if (y
printf(«принадлежит»);
else
printf(«не принадлежит»);
}
алг
нач
вещx,y
ввод x,y
еслиy>=xто
если y>=0 то
если yто
вывод 'принадлежит'
иначе
вывод'не принадлежит'
все
все
все
кон
Последовательно выполните следующее.
1. Перерисуйте и заполните таблицу, которая показывает, как работает программа при аргументах, принадлежащих различным областям (A, B, C, D, E, F, Gи H).
Точки, лежащие на границах областей, отдельно не рассматривать.
Область
Условие 1
(y>=x)
Условие 2
(y>=0)
Условие 3
(y)
Программа выведет
Область обрабатывается верно
A
B
C
D
E
F
G
H
В столбцах условий укажите «да», если условие выполнится, «нет» если условие не выполнится, "—" (прочерк), если условие не будет проверяться, «не изв.», если программа ведет себя по-разному для разных значений, принадлежащих данной области. В столбце «Программа выведет» укажите, что программа выведет на экран. Если программа ничего не выводит, напишите "—" (прочерк). Если для разных значений, принадлежащих области, будут выведены разные тексты, напишите «не изв». В последнем столбце укажите «да» или «нет».
2. Укажите, как нужно доработать программу, чтобы не было случаев ее неправильной работы. (Это можно сделать несколькими способами, достаточно указать любой способ доработки исходной программы.)
Дан целочисленный массив из 20 элементов. Элементы массива могут принимать целые значения от 0 до 1000. Опишите на русском языке или на одном из языков программирования алгоритм, позволяющий найти и вывести минимальное значение среди элементов массива, которые имеют чётное значение и не делятся на три. Гарантируется, что в исходном массиве есть хотя бы один элемент, значение которого чётно и не кратно трем.
Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но использовать все описанные переменные не обязательно.
Паскаль
Алгоритмический язык
const
N= 20;
var
a: array[1..N] ofinteger;
i, j, min: integer;
begin
fori:= 1 toNdo
readln(a[i]);
…
end.
алг
нач
целN=20
целтабa[1:N]
целi, j, MIN
нц для iот1 до N
вводa[i]
кц
...
кон
Бейсик
СИ
N=20
DIM A(N) AS INTEGER
DIM I, J, MIN AS INTEGER
FOR I = 1 TO N
INPUT A(I)
NEXT I
…
END
#include
#define N 20
void main(void){
int a[N];
int i, j, min;
for (i=0; i
scanf("%d", &a[i]);
…
}
Русский (естественный) язык
Объявляем массив Aиз 20 элементов.
Объявляем целочисленные переменные I, J, MIN.
В цикле от 1 до 20 вводим элементы массива Aс 1-го по 20-й.
…
В качестве ответа вам необходимо привести фрагмент программы (или описание алгоритма на естественном языке), который должен находиться на месте многоточия. Вы можете записать решение также на другом языке программирования (укажите название и используемую версию языка программирования, например BorlandPascal 7.0) или в виде блок-схемы. В этом случае вы должны использовать те же самые исходные данные и переменные, какие были предложены в условии (например, в образце, записанном на естественном языке).
продолжение
--PAGE_BREAK--
У исполнителя Утроитель две команды, которым присвоены номера:
1. прибавь 1,
2. умножь на 3.
Первая из них увеличивает число на экране на 1, вторая – утраивает его.
Программа для Утроителя – это последовательность команд.
Сколько есть программ, которые число 1 преобразуют в число 29?
Ответ обоснуйте.
В командных олимпиадах по программированию для решения предлагается не больше 11 задач. Команда может решать предложенные задачи в любом порядке. Подготовленные решения команда посылает в единую проверяющую систему соревнований. Вам предлагается написать эффективную, в том числе по используемой памяти, программу, которая будет статистически обрабатывать пришедшие запросы, чтобы определить наиболее популярные задачи. Следует учитывать, что количество запросов в списке может быть очень велико, так как многие соревнования проходят с использованием Интернет.
Перед текстом программы кратко опишите используемый вами алгоритм решения задачи.
На вход программе в первой строке подаётся количество пришедших запросов N. В каждой из последующих N строк записано название задачи в виде текстовой строки. Длина строки не превосходит 100 символов, название может содержать буквы, цифры, пробелы и знаки препинания.
Пример входных данных:
6
А+B
Крестики-Нолики
Прямоугольник
Простой делитель
А+В
Простой делитель
Программа должна вывести список из трёх наиболее популярных задач с указанием количества запросов по ним. Если в запросах упоминаются менее трех задач, то выведите информацию об имеющихся задачах. Если несколько задач имеют ту же частоту встречаемости, что и третья по частоте встречаемости задача, их тоже нужно вывести.
Пример выходных данных для приведённого выше примера входных данных:
А+В 2
Простой делитель 2
Крестики-Нолики 1
Прямоугольник 1
Система оценивания экзаменационной работы по информатике и ИКТ
Ответы к заданиям с выбором ответа
Ответы к заданиям с кратким ответом
Критерии оценивания заданий с развернутым ответом
Требовалось написать программу, при выполнении которой с клавиатуры считываются координаты точки на плоскости (x,
y – действительные числа) и определяется принадлежность этой точки заданной закрашенной области (включая границы). Программист торопился и написал программу неправильно.
Бейсик
Паскаль
INPUT x, y
IF y>=x THEN
IF y>=0 THEN
IF y
PRINT«принадлежит»
ELSE
PRINT«не принадлежит»
ENDIF
ENDIF
ENDIF
END
var x,y: real;
begin
readln(x,y);
if y>=x then
if y>=0 then
if y
write('принадлежит')
else
write('не принадлежит')
end.
Си
Алгоритмический
язык
void main(void){
float x,y;
scanf("%f%f",&x,&y);
if (y>=x)
if (y>=0)
if (y
printf("принадлежит");
else
printf(«не принадлежит»);
}
алг
нач
вещ x,y
ввод x,y
если y>=xто
если y>=0 то
если yx*xто
вывод 'принадлежит'
иначе
вывод 'не принадлежит'
все
все
все
кон
Последовательно выполните следующее.
1. Перерисуйте и заполните таблицу, которая показывает, как работает программа при аргументах, принадлежащих различным областям (A, B, C, D, E, F, Gи H).
Точки, лежащие на границах областей, отдельно не рассматривать.
Область
Условие 1
(y>=x)
Условие 2
(y>=0)
Условие 3
(y)
Программа выведет
Область обрабатывается верно
A
B
C
D
E
F
G
H
В столбцах условий укажите «да», если условие выполнится, «нет» если условие не выполнится, "—" (прочерк), если условие не будет проверяться, «не изв.», если программа ведет себя по-разному для разных значений, принадлежащих данной области. В столбце «Программа выведет» укажите, что программа выведет на экран. Если программа ничего не выводит, напишите "—" (прочерк). Если для разных значений, принадлежащих области, будут выведены разные тексты, напишите «не изв». В последнем столбце укажите «да» или «нет».
2. Укажите, как нужно доработать программу, чтобы не было случаев ее неправильной работы. (Это можно сделать несколькими способами, достаточно указать любой способ доработки исходной программы.)
Содержание верного ответа и указания по оцениванию
(допускаются иные формулировки ответа, не искажающие его смысла)
Элементы ответа:
1.
Область
Условие 1
(y>=x)
Условие 2
(y>=0)
Условие 3
(yx*x)
Программа выведет
Область обрабатыва-ется верно
A
да
да
нет
не принадлежит
да
B
да
нет
—
—
нет
C
нет
—
—
—
нет
D
нет
—
—
—
нет
E
да
да
да
принадлежит
да
F
да
нет
—
—
нет
G
нет
—
—
—
нет
H
нет
—
—
—
нет
2. Возможная доработка (Паскаль):
if (x=x) or (x>=0) and (y>=0) and (y
write('принадлежит')
else
write('не принадлежит')
Возможны и другие способы доработки.
Пример:
if (y=0) or (y>=x)) then
write('принадлежит')
else
write('не принадлежит')
Указания по оцениванию
Баллы
Обратите внимание! В задаче требуется выполнить три следующих действия.
1. Указать для каждой области, как будет работать программа — заполнить таблицу.
2. Исправить ошибку, связанную с неверной расстановкой операторных скобок (отсутствуют случаи ELSE). Исправлением этой ошибки может быть либо добавление случая ELSE к каждому условию IF, либо объединение всех условий IF в одно при помощи конъюнкции.
В сложных случаях это действие считается выполненным, если программа выдает одно из двух сообщений «принадлежит» или «не принадлежит» для любых чисел x и y, при этом программа не стала работать хуже, чем раньше, то есть для всех точек, для которых программа ранее выдавала верный ответ, доработанная программа также должна выдавать верный ответ.
3. Исправить ошибку в проверяемых условиях: приведенным трем ограничениям не удовлетворяют точки плоскости, у которых yx*
x,
y>=
xи
yа также
yx*
x,
yxи
y>=0. Исправлением этой ошибки может быть разбиение области на две части и использование дизъюнкции либо отбрасывание от большей области ее части.
В сложных случаях это действие считается выполненным, если верно определена закрашенная область, то есть программа выводит сообщение «принадлежит» для всех точек закрашенной области и только для них, для точек вне закрашенной области программа выводит «не принадлежит» или не выводит ничего.
В целом, критерий оценки работ такой: количество баллов равно количеству выполненных действий. Детально критерии для каждого случая рассмотрены ниже.
Задание выполнено полностью:
1) Правильно заполнена вся таблица.
2) Написана правильно работающая программа, т.е. программа для всех пар чисел x, y верно определяет принадлежность точки закрашенной области.
В работе (во фрагментах программ) допускается наличие отдельных синтаксических ошибок, не искажающих замысла автора решения.
3
1. Правильно выполнены два действия из трех.
При этом:
а) Действие по заполнению таблицы засчитывается, даже если ошибки есть, но не более, чем в одной строке.
б) При написании операций сравнения допускается одно неправильное использование строгих/нестрогих неравенств (считается несущественной ошибкой, погрешностью записи). Например, вместо «y>=-x» один раз используется «y>-x».
в) Если ученик написал программу, которая отличается от правильной программы (с учетом п.б) только расстановкой скобок в логических выражениях (например, неправильно учтены приоритеты операций), то считается, что выполнено одно действие по исправлению ошибок из двух.
В работе (во фрагментах программ) допускается наличие отдельных синтаксических ошибок, не искажающих замысла автора решения.
2
Правильно выполнено только одно действие из трех.
При этом:
а) Действие по заполнению таблицы засчитывается, если ошибки есть не более, чем в двух строках (в отличие от предыдущего пункта).
б) При написании операций сравнения допускается любое количество неправильных использований строгих/нестрогих неравенств (т.е. не учитывается корректность работы программы на границах областей)
в) Если ученик написал программу, которая отличается от правильной программы только расстановкой скобок в логических выражениях (например, неправильно учтены приоритеты операций), то считается, что выполнено одно действие по исправлению ошибок из двух.
В работе (во фрагментах программ) допускается наличие отдельных синтаксических ошибок, не искажающих замысла автора решения.
.
1
Ни один из пунктов задания не выполнен, т.е. не выполнены критерии, позволяющие поставить ученику 1 балл.
0
Максимальный балл
3
Дан целочисленный массив из 20 элементов. Элементы массива могут принимать целые значения от 0 до 1000. Опишите на русском языке или на одном из языков программирования алгоритм, позволяющий найти и вывести минимальное значение среди элементов массива, которые имеют чётное значение и не делятся на три. Гарантируется, что в исходном массиве есть хотя бы один элемент, значение которого чётно и не кратно трем.
Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но использовать все описанные переменные не обязательно.
Паскаль
Алгоритмический язык
const
N = 20;
var
a: array [1..N] of integer;
i, j, min: integer;
begin
for i := 1 to N do
readln(a[i]);
…
end.
алг
нач
целN=20
целтабa[1:N]
целi, j, MIN
нц для iот1 до N
ввод
a[i]
кц
...
кон
Бейсик
СИ
N=20
DIM A(N) AS INTEGER
DIM I, J, MIN AS INTEGER
FOR I = 1 TO N
INPUT A(I)
NEXT I
…
END
#include
#define N 20
void main(void){
int a[N];
int i, j, min;
for (i=0; i
scanf("%d", &a[i]);
…
}
Русский (естественный) язык
Объявляем массив Aиз 20 элементов.
Объявляем целочисленные переменные I, J, MIN.
В цикле от 1 до 20 вводим элементы массива Aс 1-го по 20-й.
…
0> продолжение
--PAGE_BREAK--
В качестве ответа вам необходимо привести фрагмент программы (или описание алгоритма на естественном языке), который должен находиться на месте многоточия. Вы можете записать решение также на другом языке программирования (укажите название и используемую версию языка программирования, например BorlandPascal 7.0) или в виде блок-схемы. В этом случае вы должны использовать те же самые исходные данные и переменные, какие были предложены в условии (например, в образце, записанном на естественном языке).
Содержание верного ответа и указания по оцениванию
(допускаются иные формулировки ответа, не искажающие его смысла)
На языке Паскаль
min:=1000;
for i:=1 to N do
if (a[i] mod 2=0) and (a[i] mod 30) and (a[i]
min:=a[i];
writeln(min);
На Алгоритмическом языке
MIN:= 1000
нцдля i от 1 до N
еслиmod(a[i],2)=0 иmod(a[i],3)0 иa[i]
то
MIN:= a[i]
все
кц
выводMIN
На языке Бейсик
MIN= 1000
FORI= 1 TON
IF (A(I) MOD 2 = 0) AND (A(I) MOD 3 0) AND (A(I) THEN
MIN= A(I)
END IF
NEXT I
PRINT MIN
На языке СИ
min=1000;
for (i=0; i
if (a[i]%2==0 && a[i]%3!=0 && a[i]
min=a[i];
printf("%d", min);
На естественном языке
Записываем в переменную MIN начальное значение, равное 1000. В цикле от первого элемента до двадцатого находим остаток от деления элемента исходного массива на два и на три. Если остаток от деления на два равен нулю и остаток от деления на три не равен нулю, то сравниваем значение текущего элемента массива со значением переменной MIN. Если текущий элемент массива меньше MIN, то записываем в MIN значение этого элемента массива. Переходим к следующему элементу.
После завершения цикла выводим значение переменной MIN.
Указания по оцениванию
Баллы
Предложен правильный алгоритм, выдающий верное значение.
Допускается запись алгоритма на другом языке, использующая аналогичные переменные. В случае, если язык программирования использует типизированные переменные, описания переменных должны быть аналогичны описаниям переменных на естественном языке. Использование нетипизированных или необъявленных переменных возможно только в случае, если это допускается языком программирования, при этом количество переменных и их идентификаторы должны соответствовать условию задачи. В алгоритме, записанном на языке программирования, допускается наличие отдельных синтаксических ошибок, не искажающих замысла автора программы.
2
В любом варианте решения может присутствовать не более одной ошибки из числа следующих.
1. Не инициализируется или неверно инициализируется переменная MIN (например, ей присваивается значение a[1] или число, меньшее 1000).
2. Неверно осуществляется проверка чётности элемента массива.
3. На чётность проверяется не значение элемента, а его индекс.
4. Неверно осуществляется проверка делимости на три.
5. На делимость на три проверяется не значение элемента, а его индекс.
6. В условии проверки на делимость вместо логической операции «И» используется логическая операция «ИЛИ».
7. Отсутствует вывод ответа.
8. Используется переменная, не объявленная в разделе описания переменных.
9. Не указано или неверно указано условие завершения цикла.
10.Индексная переменная в цикле не меняется (например, в цикле while) или меняется неверно.
11.Неверно расставлены операторные скобки.
1
Ошибок, перечисленных в п. 1–11, две или больше, или алгоритм сформулирован неверно.
Максимальный балл
2
У исполнителя Утроитель две команды, которым присвоены номера:
1. прибавь 1,
2. умножь на 3.
Первая из них увеличивает число на экране на 1, вторая – утраивает его.
Программа для Утроителя – это последовательность команд.
Сколько есть программ, которые число 1 преобразуют в число 29?
Ответ обоснуйте.
Содержание верного ответа и указания к оцениванию
(допускаются иные формулировки ответа, не искажающие его смысла)
Обозначим R(n)– количество программ, которые преобразуют число 1 в число n. Обозначим t(n) наибольшее кратное трем, не превосходящее n.
Обе команды исполнителя увеличивают исходное число, поэтому общее количество команд в программе не может превосходить 28.
Верны следующие соотношения:
1. Если n не делится на 3, то тогда R(n)=
R(t(n)), так как существует единственный способ получения
nиз
t(n)– прибавлением единиц.
2. Пусть n делится на 3.
ТогдаR(n)= R(n/3)+R(n-1)= R(n/3)+R(n-3)(если n>3).
При n=3 R(n) = 2 (два способа: прибавлением двух единиц или однократным умножением на 3).
Поэтому достаточно постепенно вычислить значения R(n) для всех чисел, кратных трем и не превосходящих 29: сначала вычисляем R(1), затем R(3), R(6) и т.д.
Имеем:
R(2)=1
R(3) = 2 = R(4)=R(5)
R(6) = R(2)+R(3) =1+2 = 3 = R(7)=R(8)
R(9) = R(3)+R(6) =2+3 =5 = R(10)=R(11)
R(12) = R(4)+R(9) = 2+5 = 7 = R(13)=R(14)
R(15) = R(5)+R(12) =2+7 =9 = R(16)=R(17)
R(18) = R(6)+R(15) = 3+9 = 12 = R(19)=R(20)
R(21) = R(7)+R(18) = 3+12 = 15 = R(22)=R(23)
R(24) = R(8)+R(21) = 3+ 15 = 18 = R(25)=R(26)
R(27) = R(9)+R(24) = 5 + 18 = 23 = R(28)=R(29)
Ответ: 23
Другая форма решения
Будем решать поставленную задачу последовательно для чисел 1, 2, 3, …, 29 (то есть для каждого из чисел определим, сколько программ исполнителя существует для его получения). Количество программ, которые преобразуют число 1 в число n, будем обозначать через R(n). Число 1 у нас уже есть, значит, его можно получить с помощью “пустой” программы. Любая непустая программа увеличит исходное число, т.е. даст число, больше 1. Значит, R(1) = 1. Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Если число не делится на три, то оно может быть получено только из предыдущего с помощью команды прибавь 1. Значит, количество искомых программ для такого числа равно количеству программ для предыдущего числа: R(i) = R(i-1). Если число на 3 делится, то вариантов последней команды два: прибавь 1 иумножь на 3, тогда R(i) = R(i-1) + R(i/3). Заполним соответствующую таблицу по приведенным формулам слева направо:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1
1
2
2
2
3
3
3
5
5
5
7
7
7
9
16
17
18
19
20
21
22
23
24
25
26
27
28
29
9
9
12
12
12
15
15
15
18
18
18
23
23
23
При этом ячейки, относящиеся к числам, которые не делятся на 3, можно в решении и опустить (за исключением первого и последнего чисел):
1
3
6
9
12
15
18
21
24
27
30
31
1
2
3
5
7
9
12
15
18
23
28
28
Указания по оцениванию
Баллы
Правильное указание количества возможных программ со строгим доказательством правильности (одним из приведенных выше способов или любым другим).
3
Два балла ставятся в одном из двух случаев:
1. Правильное указание количества возможных программ, основанное на верных рассуждениях, но доказательство правильности неполно. В частности, оценка в 2 балла выставляется в случае, если просто перечислены все правильные программы и не доказано отсутствие других программ, кроме приведенных.
2. Приведены правильные и строгие рассуждения, доведенные до конца, но в вычислениях допущена арифметическая ошибка, в результате чего получен неверный ответ.
2
Представленное решение обладает одним из свойств
1. Указано, что нужно рассматривать значения n, меньшие, чем 29, и приведены правильные рекуррентные соотношения (см. выше), возможно, неполные.
2. Правильно выписаны и обоснованы значения R(n)для небольших n
.
3. Правильно написан ответ, но нет его обоснования.
1
Не выполнено ни одно из перечисленных выше условий
Максимальный балл
3
продолжение
--PAGE_BREAK--