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

1.

Вычислите сумму чисел X и Y, если

 

Х=2348

Y=5716

 

Ответ запишите в двоичной системе счисления.

2.

Логическая функция F задаётся выражением (x ∨ y) → (y ≡ z).

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

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

 

Переменная 1Переменная 2Переменная 3Функция
?????????F
000
00

 

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

Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности:

 

Переменная 1Переменная 2Функция
??????F
010

 

Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.

3.

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

 

ABCDEF
A217
B248
C43
D8336
E32
F1762

 

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

4.

Ниже представлены две таблицы из базы данных. Каждая строка таблицы 2 содержит информацию о ребёнке и об одном из его родителей. Информация представлена значением поля ID в соответствующей строке таблицы 1. Определите на основании приведённых данных ID племянницы Иваненко М. И. В ответе запишите только цифры ID.

Пояснение: племянницей считается дочь брата или сестры.

 

Таблица 1
IDФамилия_И. О.Пол
1015Иваненко Н. А.Ж
1023Иваненко М. И.М
1033Будай В. С.Ж
1035Будай С. С.М
1043Коладзе Л. А.М
1073Будай М. А.Ж
2022Иваненко И. М.М
2024Иваненко М. М.М
2032Будай А. И.Ж
2042Коладзе А. С.Ж
2044Родэ О. С.М
2046Родэ М. О.М
2052Ауэрман А. М.Ж
.........

Таблица 2
ID_РодителяID_Ребенка
10151035
10232024
10232052
10351033
10352044
10732052
10732024
20221023
20222032
20321033
20322044
20422032
20421023
......

5.

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

 

БукваКодовое слово
А11
Б0010
Г1011
Е0011

БукваКодовое слово
И
М01
Р000
Т1010

 

Укажите кратчайшее кодовое слово для буквы И. Если таких кодов несколько, укажите код с наименьшим числовым значением.

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

6.

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.

1) Строится двоичная запись числа N.

2) К этой записи дописываются справа ещё два разряда по следующему правилу:

     а) складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;

     б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на 2.

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.

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

7.

На рисунке приведен фрагмент электронной таблицы. Определите, чему будет равно значение, вычисленное по следующей формуле =СУММ(B1:C4)+F2*E4–A3

 

ABCDEF
1134820
24-5-2155
3555555
4231442

 

8.

Определите, что будет напечатано в результате выполнения программы (записанной ниже на разных языках программирования):

 

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

DIM N, S AS INTEGER

N = 0

S = 1

WHILE S <= 1000

S = S * 2

N = N + 2

WEND

PRINT N

var n, s: integer;

begin

    n := 0;

    s := 1;

    while s <= 1000 do

    begin

        s := s * 2;

        n := n + 2;

    end;

    write(n)

end.

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

#include <iostream>

using namespace std;

int main()

{

    int n, s;

    n = 0;

    s = 1;

    while (s <= 1000)

    {

        s = s * 2;

        n = n + 2;

    }

    cout << n << endl;

}

алг

нач

цел n, s

n := 0

s := 1

нц пока s <= 1000

    s := s * 2

    n := n + 2

кц

вывод n

кон

Python

n = 0

s = 1

while s <= 1000:

    s *= 2

    n += 2

print(n)

 

9.

Производилась двухканальная (стерео) звукозапись с частотой дискретизации 64 кГц и 24-битным разрешением. В результате был получен файл размером 72 Мбайт, сжатие данных не производилось. Определите приблизительно, сколько времени (в минутах) проводилась запись. В качестве ответа укажите ближайшее к времени записи целое число.

10.

Сколько слов длины 5, начинающихся с согласной буквы и заканчивающихся гласной буквой, можно составить из букв З, И, М, А? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.

11.

Алгоритм вычисления значения функции F(n), где n задан следующими соотношениями:

 

F(1) = 1;

F(2)=2;

F(n) = 3*F(n−1) − 2*F(n−2), при n >2.

 

Чему равно значение функции F(7)? В ответе запишите только натуральное число.

12.

В терминологии сетей TCP/IP маской сети называется двоичное число, определяющее, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу самого узла в этой сети. Обычно маска записывается по тем же правилам, что и IP-адрес, – в виде четырёх байтов, причём каждый байт записывается в виде десятичного числа. При этом в маске сначала (в старших разрядах) стоят единицы, а затем с некоторого разряда – нули. Адрес сети получается в результате применения поразрядной конъюнкции к заданному IP-адресу узла и маске.

Например, если IP-адрес узла равен 231.32.255.131, а маска равна 255.255.240.0, то адрес сети равен 231.32.240.0.

Для узла с IP-адресом 111.81.200.27 адрес сети равен 111.81.192.0. Чему равно наибольшее возможное значение третьего слева байта маски? Ответ запишите в виде десятичного числа.

13.

В велокроссе участвуют 235 спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для всех спортсменов. Какой объём памяти будет использован устройством, когда промежуточный финиш прошли 190 велосипедистов? (Ответ дайте в байтах.)

14.

Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости:

вверх вниз влево вправо

При выполнении этих команд РОБОТ перемещается на одну клетку соответственно: вверх, вниз, влево, вправо.

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

сверху
свободно
снизу
свободно
слева
свободно
справа
свободно

Цикл

ПОКА < условие> команда

выполняется, пока условие истинно, иначе происходит переход на следующую строку.

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

 

НАЧАЛО

ПОКА <справа свободно> вправо

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

ПОКА <слева свободно> влево

ПОКА <сверху свободно> вверх

КОНЕЦ

15.

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

16.

Десятичное число 59 в некоторой системе счисления записывается как 214. Определите основание системы счисления.

17.

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

 

 

ЗапросНайдено страниц

(в тысячах)

Диана & (Аврора | Паллада)800
Диана & Аврора & Паллада220
Диана & Аврора550

 

Компьютер печатает количество страниц (в тысячах), которое будет найдено по следующему запросу:

 

Диана & Паллада .

 

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

18.

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наименьшего натурального числа А формула

 

ДЕЛ(x, А) → (¬ДЕЛ(x, 21) + ДЕЛ(x, 35))

 

тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной x)?

Задание К. Ю. Полякова

19.

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

 

 

Бейсик Python

c = 0

FOR i = 1 TO 8

    IF A(i)=A(0) THEN

        c = c + 1

        t=A(i+1)

        A(i+1)= A(i)

        A(i)= t

    ENDIF

NEXT i

PRINT c

c = 0

for i in range(1, 9):

    if A[i] == A[0]:

        c += 1

        t=A[i+1]

        A[i+1]= A[i]

        A[i]= t

print(c)

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

c := 0

нц для i от 1 до 8

    если A[i] = A[0] то

        c := c + 1

        t:=A[i+1]

        A[i+1]:= A[i]

        A[i]:= t

    все

кц

вывод c

c := 0;

for i := 1 to 8 do

    if A[i] = A[0] then

    begin

        inc(c);

        t:=A[i+1];

        A[i+1]:= A[i];

        A[i]:= t;

    end;

writeln(c);

Си++

c = 0;

for (i = 1; i <= 8; i++)

    if (A[i] == A[0])

    {

        c++;

        t=A[i+1];

        A[i+1]= A[i];

        A[i]= t;

    }

cout « c « endl;

 

В начале выполнения этого фрагмента в массиве находились числа 3, 2, 4, 6, 3, 10, 12, 14, 16, 18 т. е. А[0]=3, А[1]=2 и т. д. Чему будет равно значение переменной с после выполнения данной программы?

20.

Ниже на пяти языках программирования записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа a и b. Укажите наименьшее из таких чисел x, при вводе которых алгоритм печатает

сначала 3, а потом 25.

 

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

DIM X, A, B AS INTEGER

INPUT X

A = 0: B = 0

WHILE X > 0

    A = A + 1

    IF (X MOD 2) <> 0 THEN

        B = B+(X MOD 10)

    END IF

    X = X\10

WEND

PRINT A

PRINT B

var x, a, b: integer;

begin

    readln(x);

    a := 0; b := 0;

    while x > 0 do

        begin

            a := a + 1;

            if(x mod 2) <> 0 then

                b := b+(x mod 10);

            x := x div 10;

        end;

    writeln(a); write(b);

end.

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

#include <iostream>

using namespace std;

int main()

{

    int x, a, b;

    cin >> x;

    a = 0; b = 0;

    while (x > 0){

        a = a+1;

        if ((x%2)!=0){

            b = b+(x%10);

        }

        x = x/10;

    }

    cout << a << endl << b endl;

}

алг

нач

цел x, a, b

ввод x

a := 0; b := 0

нц пока x > 0

    a := a+1

    если mod(x,2) <> 0 то

        b := b+mod(x,10)

    все

    x := div(x,10)

кц

вывод a, нс, b

кон

Python

x = int(input())

a = 0

b = 0

while x > 0:

    a += 1

    if (x % 2) != 0:

        b += (x % 10)

    x //= 10

print(a)

print(b)

 

21.

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

 

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

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

A = -20: B = 20

M = A: R = F(А)

FOR T = A TO B

    IF F(T) < R THEN

        M = T

        R = F(T)

    END IF

NEXT T

PRINT M

FUNCTION F(x)

    F = 2*(x-9)*(x-9)+12

END FUNCTION

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

    Function F(x:integer): integer;

        begin

            F := 2*(x-9)*(x-9)+12

        end;

begin

    a := -20; b := 20;

    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(M)

end.

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

#include <iostream>

using namespace std;

int F(int x)

{

return 2*(x-9)*(x-9)+12;

}

int main()

{

    int a, b, t, M, R;

    a = -20; b = 20;

    M = a; R = F(a);

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

        if (F(t) < R) {

            M = t; R = F(t);

        }

    }

    cout « M « endl;

}

алг

нач

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

a := -20; b := 20

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

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

если F(t) < R

то

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

все

кц

вывод M

кон

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

нач

знач := 2*(x-9)*(x-9)+12

кон

Python

def f(x):

    return 2*(x-9)*(x-9)+12

a = -20

b = 20

M = a

R = F(a)

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

    if (f(t) < R):

        M = t

        R = f(t);

print(M)

 

22.

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

 

1. умножь на 15,

2. подели на 2.

 

Первая из них увеличивает число на экране в 15 раз, вторая – уменьшает его в 2 раза. Программа для Калькулятора – это последовательность команд. Сколько различных чисел можно получить из числа 4096 с помощью программы, которая содержит ровно 12 команд?

23.

Сколько различных решений имеет уравнение J ∧ ¬K ∧ L ∧ ¬M ∧ (N ∨ ¬N) = 0, где J, K, L, M, N — логические переменные?

В ответе не нужно перечислять все различные наборы значений J, K, L, M и N, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

24.

Дано целое неотрицательное число N. Необходимо вывести два ближайших к нему точных квадрата в порядке возрастания. Например, для N = 2016 нужно вывести числа 1936 и 2025 (1936 = 442, 2025 = 452), а для N = 9 нужно вывести числа 4 и 9.

Для решения этой задачи ученик написал программу, но, к сожалению, его программа — неправильная.

Ниже эта программа для Вашего удобства приведена на пяти языках программирования.

 

 

БейсикPython

DIM N, K AS INTEGER

INPUT N

K = 1

WHILE K*K <= N

  K = K + 1

WEND

PRINT K-1, K

END

n = int(input())

k = 1

while k*k <= n:

    k = k + 1

print(k-1,k)

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

алг

нач

  цел n, k

  ввод n

  k := 1

  нц пока k*k <= n

    k := k + 1

  кц

  вывод k-1, " ", k

кон

var n, k: integer;

begin

  read(n);

  k := 1;

  while k*k <= n do

    k := k + 1;

  writeln(k-1, " ", k)

end.

Си++

#include <iostream>

using namespace std;

    int main(){

    int n, k;

    cin >> n;

    k = 1;

    while (k*k <= n)

        k = k + 1;

    cout << k-1 << k << endl;

    return 0;

}

 

 

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

 

1. Напишите, что выведет эта программа при вводе N = 2016.

2. Назовите значение N, при вводе которого программа выведет верный ответ. Укажите этот ответ.

3. Найдите в программе все ошибки (их может быть одна или несколько). ля каждой ошибки выпишите строку, в которой она допущена, и приведите эту же строку в исправленном виде. Достаточно указать ошибки и способ их исправления для одного языка программирования.

 

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

25.

Дан целочисленный массив из 20 элементов. Элементы массива могут принимать целые значения от −1000 до 1000 включительно. Опишите на естественном языке или на одном из языков программирования алгоритм, позволяющий найти и вывести минимальное значение среди положительных элементов массива, имеющих чётное значение. Если в исходном массиве нет элемента, значение которого чётно и положительно, то вывести сообщение «Не найдено».

Исходные данные объявлены так, как показано ниже на примерах для некоторых языков программирования и естественного языка. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать некоторые из описанных переменных.

 

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

N = 20

DIM A(N) AS INTEGER

DIM I, J, MIN AS INTEGER

FOR I = 1 TO N

    INPUT A(I)

NEXT I

...

END

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.

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

#include <iostream>

using namespace std;

#define N 20

int main() {

    int a[N];

    int i, j, min;

    for (i = 0; i < N; i++)

        cin >> a[i];

...

}

алг

нач

    цел N = 20

    целтаб a[1:N]

    цел i, j, min

    нц для i от 1 до N

        ввод a[i]

    кц

    ...

кон

Естественный язык

Объявляем массив А из 20 элементов.

Объявляем целочисленные переменные I, J, MIN.

В цикле от 1 до 20 вводим элементы массива А с 1-го по 20-й.

Python

// допускается также использовать

// целочисленные переменные j, min

a = []

n = 20

for i in range(0, n):

a.append(int(input()))

 

В качестве ответа Вам необходимо привести фрагмент программы (или описание алгоритма на естественном языке), который должен находиться на месте многоточия. Вы можете записать решение также на другом языке программирования (укажите название и используемую версию языка программирования, например, Free Pascal 2.4) или в виде блок-схемы. В этом случае Вы должны использовать те же самые исходные данные и переменные, какие были предложены в условии (например, в образце, записанном на естественном языке).

26.

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 6 камней, а в другой 9 камней; такую позицию в игре будем обозначать (6, 9). Тогда за один ход можно получить любую из четырёх позиций: (12, 9), (7, 9), (6, 10), (6, 18). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

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

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Например, при начальных позициях (21, 30) и (41, 20) выигрышная стратегия есть у Пети. Чтобы выиграть, ему достаточно удвоить количество камней во второй куче.

Задание 1

Для каждой из начальных позиций (10, 35), (6, 37) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.

Задание 2

Для каждой из начальных позиций (10, 34), (5, 37), (6, 36) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.

Задание 3

Для начальной позиции (5, 36) укажите, кто из игроков имеет выигрышную стратегию. Опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии. Постройте дерево всех партий, возможных при указанной Вами выигрышной стратегии. Представьте дерево в виде рисунка или таблицы.

27.

Дан набор из N целых положительных чисел. Из них нужно выбрать и вывести два числа так, чтобы их сумма была нечётна, а произведение делилось на 3 и при этом было максимально возможным. Выбранные числа можно выводить в любом порядке. Если есть несколько подходящих пар, можно выбрать любую из них. Если подходящих пар нет, нужно вывести 0.

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

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

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

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

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

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

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

Перед текстом программы кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.

Описание входных и выходных данных.

В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 1000). В каждой из последующих N строк записано одно натуральное число, не превышающее 100.

Пример входных данных:

5

1

2

3

4

5

Пример выходных данных для приведённого выше примера входных данных:

3 4

Из 5 чисел можно составить 10 пар. В данном случае условиям удовлетворяют две пары: (2, 3) и (3, 4). Суммы чисел в этих парах (5 и 7) нечётны, а произведения (6 и 12) делятся на 3. У всех остальных пар как минимум одно из этих условий не выполняется. Из двух возможных пар выводим ту, в которой больше произведение элементов.