ЗАДАНИЯ С ОТВЕТАМИ ОЛИМПИАДЫ ПО ИНФОРМАТИКЕ 2020 ГОДА (ПАМЯТИ В.А. БУЦИКА)

 

  Главная      Учебники - Разные 

 

поиск по сайту            правообладателям  

 

 

 

 

 

 

 

 

 

 

 

 

ЗАДАНИЯ С ОТВЕТАМИ ОЛИМПИАДЫ ПО ИНФОРМАТИКЕ 2020 ГОДА (ПАМЯТИ В.А. БУЦИКА)

 

 

ЗАДАНИЯ ОЛИМПИАДЫ ПО ИНФОРМАТИКЕ 2020 Г. ПАМЯТИ В.А. БУЦИКА
Задание 1 (1 балл)
Найдите значение выражения
1116 +
118 :
112. Ответ запишите в двоичной системе
счисления.
Решение.
Переведем все числа в десятичную систему счисления, выполним действия и переведем
результат в двоичную систему счисления:
1116 = 16 + 1 = 1710,
118 = 8 + 1 = 910,
112 = 2 + 1 = 310,
17 + 9 : 3 = 17 + 3 = 2010,
20 = 16 + 4 = 101002
Ответ: 101002
Задание 2 (3 балла)
Логическая функция F задаётся выражением:
x z) x ¬y ¬z).
На рисунке приведён фрагмент таблицы истинности функции F, содержащий все наборы
аргументов, при которых функция F истинна. Определите, какому столбцу таблицы истинности
функции F соответствует каждая из переменных x, y, z.
Перем.
Перем. 2
Перем. 3
Функция
1
???
???
???
F
0
0
0
1
0
0
1
1
0
1
1
1
В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им
столбцы (сначала буква, соответствующая первому столбцу, затем буква, соответствующая
второму столбцу, и т. д.)
Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и таблица
истинности:
Перем.
Перем. 1
Функция
2
???
???
F
0
0
1
0
1
0
1
0
1
1
1
1
Тогда
1-му столбцу соответствует переменная y, а
2-му столбцу соответствует
переменная x. В ответе нужно написать: yx.
Решение.
Выражение равно 1, если хотя бы одна из двух скобок равна 1. Первая скобка равна 1 при
наборах переменных (0, 0, 1) и (0, 1, 1). Вторая скобка только при (0, 0, 0). Из третьего набора
выводов не сделать, из первых же двух понятно, что переменные идут в порядке x, y, z (x оба
раза 0, в первом столбце оба раза 0; z оба раза 1, третий столбец оба раза тоже 1).
Ответ: xyz.
Задание 3 (2 балла)
Между населёнными пунктами A, B, C, D, E, F, G построены дороги, протяжённость
которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между
пунктами нет.Определите длину кратчайшего пути между пунктами A и G. Передвигаться
можно только по указанным дорогам.
A
B
C
D
E
F
G
A
2
6
B
2
5
3
C
5
1
8
D
6
3
1
9
7
E
9
5
F
7
7
G
8
5
7
Решение.
Найдём все варианты маршрутов из A в G и выберем самый короткий.
Из пункта A можно попасть в пункты B и D.
Из пункта B можно попасть в пункты C и D.
Из пункта C можно попасть в пункты D и G.
Из пункта D можно попасть в пункты E и F.
Из пункта E можно попасть в пункт G.
Из пункта F можно попасть в пункт G.
A−B−C−D−E−G. Длина маршрута 22.
A−B−C−D−F−G. Длина маршрута 22.
A−B−C−G. Длина маршрута 15.
A−B−D−E−G. Длина маршрута 19.
A−B−D−F−G. Длина маршрута 19.
A−D−F−G. Длина маршрута 20.
A−D−E−G. Длина маршрута 20.
A−B−D−С−G. Длина маршрута 14.
Кратчайший путь равен 14.
Ответ: 14.
Задание 4 (2 балла)
Сколько записей удовлетворяют условию «Пол = 'ж' И Физика < Биология»?
Фамилия
Пол
Математика
История
Физика
Химия
Биология
Андреев
м
80
72
68
66
70
Борисов
м
75
88
69
61
69
Васильев
ж
85
77
73
79
74
а
Дмитриев
м
77
85
81
81
80
Егорова
ж
88
75
79
85
75
Захарова
ж
72
80
66
70
70
Решение.
Логическое "И" верно тогда и только тогда, когда истинны оба утверждения.Пол = 'ж' верно для
Фамилия
Пол
Математика
История
Физика
Химия
Биология
Андреев
м
80
72
68
66
70
Борисов
м
75
88
69
61
69
Васильева
ж
85
77
73
79
74
Дмитриев
м
77
85
81
81
80
Егорова
ж
88
75
79
85
75
Захарова
ж
72
80
66
70
70
Из них "Физика < Биология" верно только для Васильевой и Захаровой.
Ответ: 2.
Задание 5 (2 балла)
Для кодирования букв Д, X, Р, О, В решили использовать двоичное представление чисел 0,
1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного
представления). Закодируйте последовательность букв ХОРОВОД таким способом и результат
запишите восьмеричным кодом.
Решение.
Сначала следует представить данные в условии числа в двоичном коде:
Д
Х
Р
О
В
0
1
2
3
4
00
01
10
11
100
Затем закодировать последовательность букв: ХОРОВОД — 011110111001100. Теперь
разобьём это представление на тройки справа налево и переведём полученный набор чисел в
десятичный код, затем в восьмеричный (восьмеричное представление совпадает с десятичным
при разбиении тройками)011 110 111 001 100 — 36714.
Ответ:367148
Задание 6 (3 балла)
Исполнитель Вычислитель работает с целыми положительными однобайтными числами. Он
может выполнять две команды:
1. сдвинь биты числа влево на одну позицию
2. прибавь 1
Например, число 7 (000001112) преобразуется командой 1 в 14 (000011102). Для заданного
числа 14 выполнена последовательность команд 11222. Запишите полученный результат в
десятичной системе счисления.
Решение.
Если в старшем разряде нет единицы, то команда 1 удваивает число, следовательно,
получим следующее:
1: 14 => 28,
1: 28 => 56,
2: 56 => 57,
2: 57 => 58,
2: 58 => 59.
Ответ: 59.
Задание 7 (2 балла)
В ячейки диапазона C2:F6 электронной таблицы записаны числа, как показано на рисунке.
A
B
C
D
E
F
1
2
1
10
100
1000
3
2
20
200
2000
4
3
30
300
3000
5
4
40
400
4000
6
5
50
500
5000
В ячейке B3 записали формулу =C$4+$D5. После этого ячейку B3 скопировали в ячейку C1.
Какое число будет показано в ячейке C1?
Примечание: знак $ используется для обозначения абсолютной адресации.
Решение.
При копировании формулы из ячейки B3 в ячейку C1:C$4: меняется столбец и не меняется
номер строки.$D5: столбец не меняется, меняется номер строки.Номер столбца B меньше
номера столбца C на 1. Значит, столбец C станет столбцом D.Номер строки 1 на 2 больше
номера строки 3, значит, строка 5 станет строкой 3.Окончательный вид =D$4+$D3=30+20=50.
Ответ: 50.
Задание 8 (2 балла)
Автоматическая фотокамера производит растровые изображения размером 512 на 300
пикселей. При этом объём файла с изображением не может превышать 150 Кбайт, упаковка
данных не производится. Какое максимальное количество цветов можно использовать в
палитре?
Решение.
Объём растрового изображения находится как произведение количества пикселов в
изображении на объём памяти x, необходимый для хранения цвета одного пиксела:
512 · 300 · x < 150 · 213 бит, откуда x = 8 бит. Значит, в изображении можно использовать не
более 28 = 256 цветов.
Ответ: 256.
Задание 9 (2 балла)
Стереоаудиофайл передается со скоростью 32 000 бит/с. Файл был записан при среднем
качестве звука: глубина кодирования - 16 бит, частота дискретизации - 48 000 измерений в
секунду, время записи ─ 90 сек.Сколько времени будет передаваться файл? Время укажите в
секундах.
Решение.
Объём аудиофайла — это произведение частоты дискретизации на глубину кодирования и
время записи файла. Так как частота дискретизации 48 000 измерений в секунду, то за одну
секунду запоминается
48
000 значений сигнала. Глубина кодирования
16 бит. Ведётся
стереозапись, то есть запись с двух каналов, значит, объём памяти, необходимый для хранения
данных одного канала, умножается на 2. Для нахождения времени передачи файла, разделим
объём файла на скорость передачи:
Ответ: 4320.
Задание 10 (1 балл)
Некоторый алфавит содержит пять различных букв. Сколько трёхбуквенных слов можно
составить из букв данного алфавита (буквы в слове могут повторяться)?
Решение.
Если в алфавите M символов, то количество всех возможных «слов» (сообщений) длиной N
равно Q = MN. Из условия следует, что N = 3, M = 5. Следовательно, Q = 53 = 125.
Ответ: 125.
Задание 11 (3 балла)
Все четырёхбуквенные слова, составленные из букв С, Е, Н, О, записаны в алфавитном по-
рядке и пронумерованы, начиная с 1. Начало списка выглядит так:
1. ЕЕЕЕ
2. ЕЕЕН
3. ЕЕЕО
4. ЕЕЕС
5. ЕЕНЕ
Под каким номером в списке идёт первое слово, которое начинается с буквы С?
Решение.
Заменим буквы на цифры следующим образом: Е — 0, Н — 1, О — 2, С — 3.
1. 0000
2. 0001
3. 0002
4. 0003
5. 0010
Для нахождения первого слова, которое начинается с буквы С, нужно найти номер СЕЕЕ, то
есть 3000. Используется четырёхбуквенный алфавит, значит, нужно найти значение числа
30004 в десятичном виде. Им является число 19210, но поскольку номер в списке на единицу
больше самого числа, то остаётся добавить к получившемуся числу единицу. Получаем 193.
Ответ: 193.
Задание 12 (2 балла)
При регистрации в компьютерной системе каждому пользователю выдаётся пароль,
состоящий из
15 символов. Для построения идентификатора используют
15 букв из
определённого набора. В базе данных для хранения каждого пароля отведено одинаковое
минимально возможное целое число байт. При этом используют посимвольное кодирование
паролей, все символы кодируют одинаковым минимально возможным количеством бит. Кроме
пароля для каждого пользователя в системе хранятся дополнительные сведения, для чего
выделено 12 байт на каждого пользователя. Сколько байт нужно выделить для хранения
сведений о 400 пользователях?
Решение.
На кодирование одного символа из 15-буквенного алфавита требуется 4 бита. На один
пароль необходимо 4*15=60 бит. Минимальное количество байт, вмещающее 60 бит - 8. Итого
на одного пользователя необходимо8+12=20 байт. А на
400 пользователей нужно
20 *400=8000 байт.
Ответ: 8000.
Задание 13 (3 балла)
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По
каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город М, проходящих через город Г?
Решение.
Количество путей до города Х = количество путей добраться в любой из тех городов, из
которых есть дорога в Х.При этом, если путь не должен проходить через какой-то город, нужно
просто не учитывать этот город при подсчёте сумм. А если город, наоборот, обязательно
должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах
нужно брать только этот город.С помощью этого наблюдения посчитаем последовательно
количество путей до каждого из городов:
А = 1.
Д = А = 1.
Г = А + Д = 2.
В = Г = 2. (А и Б не учитываем, поскольку путь должен проходить через Г)
Е = В = 2. (Б не учитываем, поскольку путь должен проходить через Г)
З = В + Г = 4. (Д не учитываем, поскольку путь должен проходить через Г)
Ж = В + Е + З = 8.
И = Е + Ж + З = 14.
К = И = 14.
Л = И + К = 28.
М = Л + К = 42.
Примечание. Необходимо найти количество различных путей из города А в город М,
проходящих через город Г.
Ответ: 42.
Задание 14 (2 балла)
Значение выражения 498 + 724 − 7? записали в системе счисления с основанием 7.Сколько
нулей в этой записи?
Решение. Последовательно будем преобразовывать данное выражение:
Это вычитание 716-7 в системе счисления с основанием 7 будет выглядеть как пятнадцать
шестёрок и один ноль. А 724 как одна единица и 24 нуля.Таким образом, всего 24 − 15 = 9 нулей.
Ответ: 9.
Задание 15 (3 балла)
Какое число будет выведено на экран после выполнения программного кода?
Бейсик
Паскаль
program p1;
var
Sub program1()
c,i:integer;
Dim i, c As Integer
s:string;
Dim s As String
begin
i = 1
i:=1;
For c = 1 To 10
for c:=1 to 10 do
i = i + 10
begin
s = s &i \ 10
i:=i+10;
Print s
s:=s + idiv 10;
Next
writeln(s)
End Sub
end;
end.
Решение. Переменная iувеличивается на 10 при каждой итерации цикла FOR, значит
iбудет последовательно приобретать значения: 11, 21,31 и т.д. Строковая переменная sкаждый
раз справа дописывает значение, равное целочисленному делению переменной iна 10. Всего
цикл вызывается 10 раз. Значит вывод будет следующий:
Ответ:
1
12
123
1234
12345
123456
1234567
12345678
123456789
12345678910
Задание 16 (3 балла)
Пусть задан одномерный целочисленный массив M. Индексы массива: 0 — 30. Чему
будет равен 20-ый элемент массива после выполнения приведенного фрагмента программы?
Бейсик
Паскаль
c:=5;
for i:=1 to 29 do
begin
c = 5
m[i]:=1;
For i = 1 To 29
c:=5;
m(i) = 1
if i mod 2=0 then
If i Mod 2 = 0 Then
begin
c = c + 1
c:=c+1;
m(i + 1) = i * c
m[i+1]:=2
Else
end
m(i) = 1
else
End If
begin
Next
c:=c+2;
m[i]:= 1;
end;
end;A[i];
Решение. Первой директивой внутри цикла каждому элементу массива присваивается
значение
1. Внутри условия при четных значениях iследующему элементу массива (i+1)
присваивается значение 2, которые при работе со следующим (нечетным i) возвращаются к 1.
Таким образом элементы массива с 1-го по 29 будут равны 1.
Ответ:
1.
Задание 17 (4 балла)
Определите назначение программного кода. Замените строки из знака «~» на логически
верные.
Бейсик
Dim x, y, z, d, e As Single
MsgBox ("~~~~~~~~~~~~~~~~~~~~")
Input(x,y,z)
If (x < 0) Or (y < 0) Or (z < 0) Then
Print ("~~~~~~~~~~~~~~~~~~~~")
Else
If ((x + y) > z) And ((x + z) > y) And ((y + z) > x) Then
d = (x + y + z) / 2
e = Sqr(d * (d - x) * (d - y) * (d - z))
Print ("~~~~~~~~~~~~~~~~~~~~"& e)
Else
Print ("~~~~~~~~~~~~~~~~~~~~")
End If
End If
Паскаль
program Pr3;
varx,y,z,d,e:real;
begin
Writeln('~~~~~~~~~~~~~~~~~');
readln(x,y,z);
if (x<0) or (y<0) or (z<0) then writeln('~~~~~~~~~~~~~~~~~')
else begin
if ((x+y)>z) and ((x+z)>y) and ((y+z)>x) then
begin
d := (x + y + z) / 2;
e := Sqrt(d*(d-x)*(d-y)*(d-z));
writeln('~~~~~~~~~~~~~~~~~',e);
end
else writeln('~~~~~~~~~~~~~~~~~');
end;
end.
Решение. Программа служит для расчета площади треугольника по формуле Герона. При
вводе данных осуществляется логический контроль.
Ответ: Пример правильного кода:
program Pr3;
varx,y,z,d,e:real;
begin
Writeln('Введите значения трёх сторон треугольника');
readln(x,y,z);
if (x<0) or (y<0) or (z<0) thenwriteln('Длина стороны треугольника не может быть
отрицательной')
else begin
if ((x+y)>z) and ((x+z)>y) and ((y+z)>x) then
begin
d := (x + y + z) / 2;
e := Sqrt(d*(d-x)*(d-y)*(d-z));
writeln ('Площадь треугольника=',e);
end
elsewriteln('Треугольник c такими сторонами не существует');
end;
end.
Задание 18 (5 баллов)
Ученику Вове учитель задал задание при выполнении которого с
клавиатуры считываются координаты точки на плоскости (x, y -
действительные числа) и определяется принадлежность этой точки
заданной закрашенной области (включая границы). Вова поторопился
и написал программу неправильно. Помогите исправить программу.
Бейсик
Паскаль
INPUT x, y
varx,y: real;
IF y>=x THEN
begin
IF y>=0 THEN
readln(x,y);
IF y<=2-x*x THEN
if y>=x then
PRINT "принадлежит"
if y>=0 then
ELSE
if y<=2-x*x then
PRINT "не принадлежит"
write('принадлежит')
END IF
else
END IF
write('не принадлежит')
END IF
end.
END
Решение. Условно область можно разделить на две подобласти: слева от оси Y область
ограничена графиками y=2-x2и y=x, справа ограничена графиком y=2-x2 и осью X (y>0).
Соответственно будут проверены два условия:
(y<=2-x*x) and (y>=x) and (x<0)
(y<=2-x*x) and (y>=0) and (x>=0)
Если введенные координаты соответствуют приведенным требованиям, то точка попадает в
закрашенную область.
Ответ:
Бейсик
Паскаль
Dim x, y As Integer
program pr4;
Input x,y
varx,y: real;
If (y <= 2 - x * x) And (y >= x) And (x <
begin
0) Or (y <= 2 - x * x) And (y >= 0) And (x
readln(x,y);
>= 0) Then
if (y<=2-x*x) and (y>=x) and (x<0)
print ("принадлежит")
or (y<=2-x*x) and (y>=0) and (x>=0)
Else
then
print ("не принадлежит")
write('принадлежит')
End If
else
write('не принадлежит')
end.
Задание 19 (7 баллов)
По итогам переписи населения Омской области 2010 г. Население северных районов
составило:
Район
Население
Большереченский
27705
Большеуковский
7896
Знаменский
12224
Колосовский
12561
Тарский
45004
Тевризский
15134
Усть-Ишимский
13155
Написать программу, которая при вводе наименования района сообщает количество
проживающих жителей.
Решение. Способов решения несколько. Приведенный пример использует два одномерных
массива со строковыми (r - данные о наименованиях районов) и числовыми (c - численность
населения)данными. В массивах индексы районов соответствуют индексам количества
проживающего в них населения. В цикле производится поиск по массиву с наименованиями
элемента, равного введенному. Считывается значение из числового массива данных о
численности населения у элемента с соответствующим индексом. Если такой элемент найден,
то выводятся данные о численности, если нет - об ошибке.
Ответ:
Basic
Pascal
Dim r(1 To 7) As String
program pr5;
Dim c(1 To 7) As Single
var
Dim i, p As Integer
r: array [1..7] of string;
Dim n As String
c: array [1..7] of integer;
p = 0
i,p: integer;
r(1) = "Большереченский"
n: string;
c(1) = 27705
begin
r(2) = "Большеуковский"
p:=0;
c(2) = 7896
r[1]:='Большереченский';c[1]:=27705;
r(3) = "Знаменский"
r[2]:='Большеуковский';c[2]:=7896;
c(3) = 12224
r[3]:='Знаменский';c[3]:=12224;
r(4) = "Колосовский"
r[4]:='Колосовский';c[4]:=12561;
c(4) = 12561
r[5]:='Тарский';c[5]:=45004;
r(5) = "Тарский"
r[6]:='Тевризский';c[6]:=15134;
c(5) = 45004
r[7]:='Усть-Ишимский';c[7]:=13155;
r(6) = "Тевризский"
write ('Введите наименование района: ');
c(6) = 15134
readln (n);
r(7) = "Усть-Ишимский"
for i:=1 to 7 do
c(7) = 13155
if r[i]=n then
Debug.Print ("Введите наименование
p:=c[i];
района: ")
if p>0 then
Input n
writeln ('Число жителей = ', p)
For i = 1 To 7
else
If r(i) = n Then
writeln ('Введено неправильное
p = c(i)
наименование');
End If
end.
Next
If p > 0 Then
Print ("Число жителей = " &p)
Else
Print ("Введено неправильное
наименование")
End If
End Sub
Задание 20 (8 баллов)
Приведите код программы, которая находит все двузначные числа, сумма квадратов цифр
которых делится на 15.
Решение. В цикле от 10 до 99 перебираются все двузначные числа. Команда a:=idiv 10; (b =
iMod 10) высчитывает количество десятков (определяет первую цифру). Команда b:=imod 10; (b
= iMod 10)рассчитывает вторую цифру путем получения остатка от деления на
10. В
переменную с рассчитывается сумма квадратов цифр (c:=a*a+b*b;). Если остаток от деления с
на 15 равен 0, то данное число искомое.
Ответ:
Basic
Pascal
Sub pr6()
program pr6;
Dim i, a, b, c As Single
vari,a,b,c:integer;
For i = 10 To 99
begin
a = i \ 10
for i := 10 to 99 do
b = i Mod 10
begin
c = a * a + b * b
a:=i div 10;
If c Mod 15 = 0 Then
b:=i mod 10;
Print (i)
c:= a*a+b*b;
End If
if c mod 15=0 then
Next
begin
End Sub
write(i:4);
end;
end;
end.

 

 

 

 

 

 

 

 

 

///////////////////////////////////////