Задание 19 (7 баллов)

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

Задание 1 (1 балл)

Найдите значение выражения 11₁₆ + 11₈: 11₂. Ответ запишите в двоичной системе счисления.

Решение.

Переведем все числа в десятичную систему счисления, выполним действия и переведем результат в двоичную систему счисления:

      11₁₆ = 16 + 1 = 17₁₀,

11₈ = 8 + 1 = 9₁₀,

11₂ = 2 + 1 = 3₁₀,

17 + 9: 3 = 17 + 3 = 20₁₀,

20 = 16 + 4 = 10100₂

Ответ: 10100₂

Задание 2 (3 балла)

Логическая функция F задаётся выражением:

(x ∧ z) ∨ (x ∧ y ∧ z).

На рисунке приведён фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F истинна. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z.

 

Перем. 1	Перем. 2	Перем. 3	Функция
???	???	???	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.

Ответ:36714₈

Задание 6 (3 балла)

Исполнитель Вычислитель работает с целыми положительными однобайтными числами. Он может выполнять две команды:

1. сдвинь биты числа влево на одну позицию

2. прибавь 1

Например, число 7 (00000111₂) преобразуется командой 1 в 14 (00001110₂). Для заданного числа 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 · 2¹³ бит, откуда x = 8 бит. Значит, в изображении можно использовать не более 2⁸ = 256 цветов.

Ответ: 256.

Задание 9 (2 балла)

Стереоаудиофайл передается со скоростью 32 000 бит/с. Файл был записан при среднем качестве звука: глубина кодирования – 16 бит, частота дискретизации – 48 000 измерений в секунду, время записи ─ 90 сек.Сколько времени будет передаваться файл? Время укажите в секундах.

Решение.

Объём аудиофайла — это произведение частоты дискретизации на глубину кодирования и время записи файла. Так как частота дискретизации 48 000 измерений в секунду, то за одну секунду запоминается 48 000 значений сигнала. Глубина кодирования 16 бит. Ведётся стереозапись, то есть запись с двух каналов, значит, объём памяти, необходимый для хранения данных одного канала, умножается на 2. Для нахождения времени передачи файла, разделим объём файла на скорость передачи:

Ответ: 4320.

Задание 10 (1 балл)

Некоторый алфавит содержит пять различных букв. Сколько трёхбуквенных слов можно составить из букв данного алфавита (буквы в слове могут повторяться)?

Решение.

Если в алфавите M символов, то количество всех возможных «слов» (сообщений) длиной N равно Q = M^N. Из условия следует, что N = 3, M = 5. Следовательно, Q = 5³ = 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. Ис­поль­зу­ет­ся четырёхбук­вен­ный ал­фа­вит, зна­чит, нужно найти зна­че­ние числа 3000₄ в де­ся­тич­ном виде. Им яв­ля­ет­ся число 192₁₀, но по­сколь­ку номер в спис­ке на еди­ни­цу боль­ше са­мо­го числа, то остаётся до­ба­вить к по­лу­чив­ше­му­ся числу еди­ни­цу. По­лу­ча­ем 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 балла)

Значение выражения 49⁸ + 7²⁴ − 7? записали в системе счисления с основанием 7.Сколько нулей в этой записи?

Решение. Последовательно будем преобразовывать данное выражение:

Это вычитание 7¹⁶-7 в системе счисления с основанием 7 будет выглядеть как пятнадцать шестёрок и один ноль. А 7²⁴ как одна единица и 24 нуля.Таким образом, всего 24 − 15 = 9 нулей.

Ответ: 9.

Задание 15 (3 балла)

	Какое число будет выведено на экран после выполнения программного кода?
Бейсик		Паскаль
Sub program1() Dim i, c As Integer Dim s As String i = 1 For c = 1 To 10 i = i + 10    s = s &i \ 10    Print s Next End Sub		program p1; var c,i:integer; s:string; begin i:=1; for c:=1 to 10 do begin i:=i+10; s:=s + idiv 10; writeln(s) 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 m(i) = 1 If i Mod 2 = 0 Then   c = c + 1 m(i + 1) = i * c Else m(i) = 1 End If Next		c:=5; for i:=1 to 29 do begin m[i]:=1; c:=5; if i mod 2=0 then begin c:=c+1;    m[i+1]:=2 end else begin 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 IF y>=x THEN IF y>=0 THEN IF y<=2-x*x THEN PRINT "принадлежит" ELSE PRINT "не принадлежит" END IF END IF END IF END	varx,y: real; begin readln(x,y); if y>=x then if y>=0 then if y<=2-x*x then    write('принадлежит') else write('не принадлежит') 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 Input x,y If (y <= 2 - x * x) And (y >= x) And (x < 0) Or (y <= 2 - x * x) And (y >= 0) And (x >= 0) Then print ("принадлежит") Else print ("не принадлежит") End If	program pr4; varx,y: real; begin readln(x,y); if (y<=2-x*x) and (y>=x) and (x<0) or (y<=2-x*x) and (y>=0) and (x>=0) then write('принадлежит') else write('не принадлежит') end.

Задание 19 (7 баллов)

По итогам переписи населения Омской области 2010 г. Население северных районов составило:

Район	Население
Большереченский	27705
Большеуковский	7896
Знаменский	12224
Колосовский	12561
Тарский	45004
Тевризский	15134
Усть-Ишимский	13155

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

Решение. Способов решения несколько. Приведенный пример использует два одномерных массива со строковыми (r – данные о наименованиях районов) и числовыми (c – численность населения)данными. В массивах индексы районов соответствуют индексам количества проживающего в них населения. В цикле производится поиск по массиву с наименованиями элемента, равного введенному. Считывается значение из числового массива данных о численности населения у элемента с соответствующим индексом. Если такой элемент найден, то выводятся данные о численности, если нет – об ошибке.

Ответ:  

Basic

Pascal

Dim r(1 To 7) As String Dim c(1 To 7) As Single Dim i, p As Integer Dim n As String p = 0 r(1) = "Большереченский" c(1) = 27705 r(2) = "Большеуковский" c(2) = 7896 r(3) = "Знаменский" c(3) = 12224 r(4) = "Колосовский" c(4) = 12561 r(5) = "Тарский" c(5) = 45004 r(6) = "Тевризский" c(6) = 15134 r(7) = "Усть-Ишимский" c(7) = 13155 Debug.Print ("Введите наименование района: ") Input n For i = 1 To 7 If r(i) = n Then p = c(i) End If Next If p > 0 Then Print ("Число жителей = " &p) Else Print ("Введено неправильное наименование") End If End Sub

program pr5; var r: array [1..7] of string; c: array [1..7] of integer; i,p: integer; n: string; begin p:=0; r[1]:='Большереченский';c[1]:=27705; r[2]:='Большеуковский';c[2]:=7896; r[3]:='Знаменский';c[3]:=12224; r[4]:='Колосовский';c[4]:=12561; r[5]:='Тарский';c[5]:=45004; r[6]:='Тевризский';c[6]:=15134; r[7]:='Усть-Ишимский';c[7]:=13155; write ('Введите наименование района: '); readln (n); for i:=1 to 7 do if r[i]=n then p:=c[i]; if p>0 then    writeln ('Число жителей = ', p) else writeln ('Введено неправильное наименование'); end.