№№ заданий Пояснения Ответы Ключ Добавить инструкцию Критерии
Источник Раздел кодификатора Ф ИПИ Справка
PDF-версия PDF-версия (вертикальная) PDF-версия (крупный шрифт) PDF-версия (с большим полем) Версия для копирования в MS Word
Вариант № 5173857

1.

Найдите значение выражения 1116 + 118 : 112. Ответ запишите в двоичной системе счисления.

2.

Логическая функция F задаётся выражением (x ∧ ¬y) \/ (yz) \/ ¬w. На рисунке приведён фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F ложна. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных w, x, y, z. Все строки в представленном фрагменте разные.

 

Перем.1Перем.2Перем.3Перем.4
????????????
0
100
100

 

В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (без разделителей).

3.

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

 

ABCDEF
A4
B4636
C64
D32
E6425
F5

 

Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

4.

В фрагменте базы данных представлены сведения о родственных отношениях. На основании приведённых данных определите количество человек, у которых есть родной брат с разницей не более 5 лет.

 

 

Таблица 1
IDФамилия_И. О.ПолГод рождения
2053Сухорук К.К.М1975
2065Лопухова В.А.Ж1980
2086Зарецкий А.А.М1972
2097Сухорук Е.К.Ж2004
2118Ларина О.Д.Ж1996
2124Сухорук И.К.М2001
2135Кольцова Т.Х.Ж1995
2156Рац А.П.М1993
2181Сухорук Т.Н.М2015
2203Сухорук П.И.Ж2018
2052Гнатюк О.А.М1952

 

Таблица 2
ID_РодителяID_Ребенка
20652097
20532118
20522065
20522086
20532135
20522053
20652124
20862156
21562181
21562203

5.

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, М, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 010, Б — 011, И — 10. Какое наименьшее количество двоичных знаков потребуется для кодирования слова ГРАММ?

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

6.

Исполнитель Чертежник имеет перо, которое можно поднимать, опускать и перемещать. При перемещении опущенного пера за ним остается след в виде прямой линии. У исполнителя существуют следующие команды:

Сместиться на вектор (а, Ь) – исполнитель перемещается в точку, в которую можно попасть из данной, пройдя а единиц по горизонтали и b – по вертикали.

Запись: Повторить 5[ Команда 1 Команда 2] означает, что последовательность команд в квадратных скобках повторяется 5 раз.

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

Сместиться на вектор (5,2)

Сместиться на вектор (-3, 3)

Повторить 3[Сместиться на вектор (1,0)]

Сместиться на вектор (3, 1)

На каком расстоянии от начала координат будет находиться исполнитель Чертежник в результате выполнения данного алгоритма?

7.

На предприятии работают 100 человек. Каждый из них владеет как минимум одним иностранным языком (английским, немецким или французским). На следующей диаграмме отражено количество человек, владеющих каждым из языков.

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

Определить количество человек, владеющих только английским языком, если говорят на английском и немецком, но не знают французского 2 человека.

8.

Запишите число, которое будет напечатано в результате выполнения следующей программы. Для Вашего удобства программа представлена на пяти языках программирования.

 

БейсикPython

DIM S, N AS INTEGER

S = 0

N = 0

WHILE 2*S*S < 10*S

     S = S + 1

     N = N + 2

WEND

PRINT N

s = 0

n = 0

while 2*s*s < 10*s:

    s = s + 1

    n = n + 2

print(n)

ПаскальАлгоритмический язык

var s, n: integer;

begin

s := 0;

n := 0;

while 2*s*s < 10*s do

begin

    s := s + 1;

    n := n + 2;

end;

writeln(n)

end.

алг

нач

цел n, s

n := 0

s := 0

нц пока 2*s*s < 10*s

    s := s + 1

    n := n + 2

кц

вывод n

кон

Си++

#include <iostream>

using namespace std;

int main()

{  int s = 0, n = 0;

    while (2*s*s < 10*s) { s = s + 1; n = n + 2; }

    cout << n << endl;

    return 0;

}

 

9.

Автоматическая фотокамера производит растровые изображения размером 640×480 пикселей. При этом объём файла с изображением не может превышать 320 Кбайт, упаковка данных не производится. Какое максимальное количество цветов можно использовать в палитре?

10.

В корзине лежат черные и белые шары. Среди них 18 черных шаров. Сообщение о том, что достали белый шар, несет 2 бита информации. Сколько всего шаров в корзине?

11.

Ниже на пяти языках программирования записаны две рекурсивные функции (процедуры): F и G.

 

БейсикPython

DECLARE SUB F(n)

DECLARE SUB G(n)

 

SUB F(n)

    IF n > 0 THEN G(n - 1)

END SUB

 

SUB G(n)

    PRINT "*"

    IF n > 1 THEN F(n - 2)

END SUB

def F(n):

    if n > 0:

        G(n - 1)

 

def G(n):

    print("*")

    if n > 1:

        F(n - 2)

ПаскальАлгоритмический язык

procedure F(n: integer); forward;

procedure G(n: integer); forward;

 

procedure F(n: integer);

begin

    if n > 0 then

        G(n - 1);

end;

 

procedure G(n: integer);

begin

    writeln('*');

    if n > 1 then

        F(n - 2);

end;

алг F(цел n)

нач

    если n > 0 то

        G(n - 1)

    все

кон

алг G(цел n)

нач

    вывод "*"

    если n > 1 то

        F(n - 2)

    все

кон

Си

void F(int n);

void G(int n);

 

void F(int n){

    if (n > 0)

         G(n - 1);

}

 

void G(int n){

    printf("*");

    if (n > 1)

         F(n - 2);

}

 

Сколько символов «звёздочка» будет напечатано на экране при выполнении вызова F(11)?

12.

Маской подсети называется 32-разрядное двоичное число, которое определяет, какая часть IP-адреса компьютера относится к адресу сети, а какая часть IP-адреса определяет адрес компьютера в подсети. В маске подсети старшие биты, отведенные в IP-адресе компьютера для адреса сети, имеют значение 1; младшие биты, отведенные в IP-адресе компьютера для адреса компьютера в подсети, имеют значение 0.

Если маска подсети 255.255.224.0 и IP-адрес компьютера в сети 206.158.124.67, то номер компьютера в сети равен_____

13.

Автоматическое устройство осуществило перекодировку информационного сообщения на русском языке, первоначально записанного в 16-битном коде Unicode, в 8-битную кодировку КОИ-8. При этом информационное сообщение уменьшилось на 480 бит. Какова длина сообщения в символах?

14.

Исполнитель РОБОТ умеет перемещаться по прямоугольному лабиринту, начерченному на плоскости, разбитой на клетки. Между соседними по сторонам клетками может стоять стена.

Система команд исполнителя РОБОТ содержит восемь команд. Четыре команды - это команды перемещения:

вверх

вниз

влево

вправо


При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →. Если на пути РОБОТа окажется стена, он разрушится.

Четыре команды проверяют отсутствие стены у каждой стороны той клетки, где находится РОБОТ:

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

снизу свободно

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

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


Цикл

ПОКА <условие>

последовательность команд

КОНЕЦ ПОКА

выполняется, пока условие истинно.

В конструкциях ПОКА условие может содержать команды проверки, а также слова И, ИЛИ, НЕ.

Схема лабиринта:

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

НАЧАЛО

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

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

               вниз

          КОНЕЦ ПОКА

          вправо

     КОНЕЦ ПОКА

КОНЕЦ

15.

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города А в город М, проходящих через город В?

16.

Запись числа 338 в системе счисления с основанием N содержит 3 цифры и оканчивается на 2. Чему равно максимально возможное основание системы счисления?

17.

В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» — символ «&».

В таблице приведены запросы и количество найденных по ним страниц

некоторого сегмента сети Интернет.

 

ЗапросНайдено страниц, тыс.
Ростов & (Орёл & Курск | Белгород)370
Ростов & Белгород204
Ростов & Орёл & Курск & Белгород68

 

Какое количество страниц (в тыс.) будет найдено по запросу

 

Ростов & Орёл & Курск?

 

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

18.

Для какого наибольшего целого числа А формула

 

((x ≤ 9) →(x ⋅ x ≤ A)) ⋀ ((y ⋅ y ≤ A) → (y ≤ 9))

 

тождественно истинна, то есть принимает значение 1 при любых целых неотрицательных x и y?

19.

В программе описан одномерный целочисленный массив с индексами от 0 до 10. Ниже представлен записанный на разных языках программирования фрагмент одной и той же программы, обрабатывающей данный массив:

 

 

БейсикPython

s = 0

n = 10

FOR i = 0 TO n-3

    s = s+A(i)-A(i+2)

NEXT i

s = 0

n = 10

for i in range(0,n-2):

    s = s + A[i] - A[i+2]

ПаскальАлгоритмический язык

s:=0;

n:=10;

for i:=0 to n-3 do begin

    s:=s+A[i]-A[i+2]

end;

s:=0

n:=10

нц для i от 0 до n-3

    s:=s+A[i]-A[i+2]

кц

Си++

s = 0;

n=10;

for (i = 0; i <= n-3; i++) {

    s=s+A[i]-A[i+2];

}

 

В начале выполнения этого фрагмента в массиве находились трёхзначные натуральные числа. Какое наибольшее значение может иметь переменная s после выполнения данной программы?

20.

Ниже на пяти языках программирования записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа: L и M. Укажите наибольшее число x, при вводе которого алгоритм печатает сначала 3, а потом 5

 

БейсикPython

DIM X, L, M, Q AS INTEGER

INPUT X

Q = 6

L = 0

WHILE X >= Q

    L = L + 1

    X = X - Q

WEND

M = X

IF M < L THEN

    M = L

    L = X

ENDIF

PRINT L

PRINT M

x = int(input())

Q = 6

L = 0

while x >= Q:

    L = L + 1

    x = x - Q

M = x

if M < L:

    M = L

    L = x

print(L)

print(M)

ПаскальАлгоритмический язык

var x, L, M, Q: integer;

begin

    readln(x);

    Q := 6;

    L := 0;

    while x >= Q do

    begin

        L := L + 1;

        x := x - Q;

    end;

    M := x;

    if M < L then

    begin

        M := L;

        L := x;

    end;

    writeln(L);

    writeln(M);

end.

алг

нач

    цел x, L, M, Q

    ввод x

    Q := 6

    L := 0

    нц пока x >= Q

        L := L + 1

        x := x - Q

    кц

    M := x

    если M < L

        то

            M := L

            L := x

    все

    вывод L, нс, M

кон

Си++

#include <iostream>

using namespace std;

int main()

{

    int x, L, M, Q;

    cin >> x;

    Q = 6;

    L = 0;

    while (x >= Q){

        L = L + 1;

        x = x - Q;

    }

    M = x;

    if(M < L){

        M = L;

        L = x;

    }

    cout << L << endl << M endl;

}

 

21.

Определите, какое число будет напечатано в результате выполнения следующего алгоритма:

 

 

БейсикПаскаль

DIM A, B, T, M, R AS INTEGER

A = -5: B = 5

M = A: R = F(А)

FOR T = A TO B

    IF F(T) > R THEN

        M = T

        R = F(T)

    END IF

NEXT T

PRINT R

FUNCTION F(x)

    F = (x+5)*(x+3)

END FUNCTION

var a,b,t,M,R: integer;

    Function F(x:integer): integer;

        begin

            F := (x+5)*(x+3)

        end;

begin

    a := -5; b := 5;

    M := a; R := F(a);

    for t := a to b do begin

        if (F(t) > R) then begin

            M := t;

            R := F(t)

        end

    end;

    write(R)

end.

Си++Алгоритмический

#include <iostream>

using namespace std;

int F(int x)

{

return (x+5)*(x+3);

}

int main()

{

    int a, b, t, M, R;

    a = -5; b = 5;

    M = a; R = F(a);

    for (t = a; t <= b; t++) {

        if (F(t) > R) {

            M = t; R = F(t);

        }

    }

    cout « R « endl;

}

алг

нач

цел a, b, t, M, R

a := -5; b := 5

M := a; R := F(a)

нц для t от a до b

если F(t) > R

то

M := t; R := F(t)

все

кц

вывод R

кон

алг цел F(цел x)

нач

знач := (x+5)*(x+3)

кон

Python

def f(x):

    return (x+5)*(x+3)

a = -5

b = 5

M = a

R = f(a)

for t in range(a, b+1):

    if (f(t) > R):

        M = t

        R = f(t);

print(R)

 

22.

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

 

1. прибавь 1

2. прибавь 2.

 

Первая из них увеличивает число на экране на 1, вторая — на 2. Сколько различных чисел можно получить из числа 2 с помощью программы, которая содержит не более 4 команд?

23.

Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, x6, x7, x8 которые удовлетворяют всем перечисленным ниже условиям?

 

(x1≡x2)—>(x2≡x3) = 1

(x2≡x3)—>(x3≡x4) = 1

...

(x6≡x7)—>(x7≡x8) = 1

 

В ответе не нужно перечислять все различные наборы значений переменных x1, x2, x3, x4, x5, x6, x7, x8 при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

24.

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

 

 

БейсикPython

DIM A, S AS DOUBLE

DIM K AS INTEGER

INPUT A

K = 0

S = 1

WHILE S >= A

K = K + 1

S = S + 1.0/K

WEND

PRINT K

END

a = float(input())

k = 0

s = 1

while s>=a:

    k = k + 1

    s = s + 1.0/k

print(k)

ПаскальАлгоритмический язык

var a, s: real;

k: integer;

begin

read(a);

k := 0;

s := 1;

while s>=a do begin

k := k + 1;

s := s + 1.0/k;

end;

write(k);

end.

алг

нач

вещ a, s

цел k

ввод a

k := 0

s := 1

нц пока s>=a

k := k + 1

s := s + 1.0/k

кц

вывод k

кон

Си++

#include <iostream>

using namespace std;

int main(){

double a, s;

int k;

cin >> a;

k = 0;

s = 1;

while (s>=a) {

k = k + 1;

s = s + 1.0/k;

}

cout « k « endl;

return 0;

}

 

 

Последовательно выполните следующее.

1. Напишите, что выведет эта программа при вводе числа 1.4.

2. Сколько существует натуральных чисел А, при вводе которых программа выведет ответ 1?

3. Найдите в программе все ошибки (их может быть одна или несколько).

Для каждой ошибки выпишите строку, в которой она допущена, и приведите эту же строку в исправленном виде. Обратите внимание: Вам нужно исправить приведённую программу, а не написать свою. Вы можете только заменять ошибочные строки, но не можете удалять строки или добавлять новые. Заменять следует только ошибочные строки: за исправления, внесённые в строки, не содержащие ошибок, баллы будут снижаться.

25.

На пустой шахматной доске в одной из клеток стоит шахматный конь. Опишите на русском языке или на одном из языков программирования алгоритм получения списка клеток, которые конь может достичь за один ход из данной клетки. На вход программы поступают два целых числа: х, у (1 < х,у < 8) — координаты клетки, в которой стоит конь. На выходе программы должен быть выведен список пар целых чисел — координаты клеток, достижимых конём из исходной клетки за один ход.

26.

Два игрока играют в следующую игру. На координатной плоскости стоит фишка. Игроки ходят по очереди. В начале игры фишка находится в точке с координатами (3, −5). Ход состоит в том, что игрок перемещает фишку из точки с координатами (x, y) в одну из трёх точек: или в точку с координатами (x + 3, y), или в точку с координатами (x, y + 4), или в точку с координатами (x, y + 5). Выигрывает игрок, после хода которого расстояние по прямой от фишки до точки с координатами (0, 0) больше 9 единиц. Кто выиграет при безошибочной игре обоих игроков — игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.

Постройте дерево партии для выигрышной стратегии (в виде рисунка или таблицы).

27.

В телевизионном танцевальном марафоне с определением победителя с помощью телезрителей после каждого тура объявляется sms-голосование, в котором зрители указывают наиболее понравившуюся им пару из максимум 16 пар, которые участвуют в проекте. Вам предлагается написать программу, которая будет обрабатывать результаты sms-голосования по данному вопросу. Результаты голосования получены в виде номеров пар (каждый элемент списка соответствует одному sms-сообщению).

 

Вам предлагается два задания с похожими условиями: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору. Задание Б более сложное, его решение оценивается выше. Итоговая оценка выставляется как максимальная из оценок за задания А и Б.

 

Задание А. Имеется набор данных, состоящий из 15 чисел.

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

Максимальная оценка за правильную программу – 2 балла.

 

Задание Б. Имеется набор данных, состоящий из целых чисел. Набор может быть очень большим.

Напишите программу для решения этой задачи.

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

Программа считается эффективной по времени, если время работы программы пропорционально количеству пар чисел N, т. е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.

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

Максимальная оценка за правильную программу, эффективную по времени и памяти, — 4 балла.

Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, — 3 балла.

 

Следует учитывать, что количество голосов в списке может быть очень велико. Перед текстом программы кратко опишите используемый Вами алгоритм решения задачи. На вход программе в первой строке подаётся количество пришедших sms-сообщений N. В каждой из последующих N строк записан номер пары от 1 до 16.Пример входных данных:

 

4

2

16

3

2

 

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

 

2 2

3 1

16 1