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

1.

Вычислите значение выражения 8216 + 1E16. Ответ запишите в десятичной системе счисления.

2.

Каждое из логических выражений F и G содержит 7 переменных. В таблицах истинности выражений F и G есть ровно 7 одинаковых строк, причём ровно в 6 из них в столбце значений стоит 0.

Сколько строк таблицы истинности для выражения F ∧ G содержит 0 в столбце значений?

3.

На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах.

 

П1П2П3П4П5П6П7
П112151117
П212181321
П318162320
П4151316
П51114
П6172314
П72120

 

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, в какой пункт ведёт самая короткая дорога из пункта А.

4.

На городской тур олимпиады по математике отбираются те учащиеся, кто набрал на районном туре не менее 12 баллов или полностью решил хотя бы одну из двух самых сложных задач (№ 6 или № 7). За полное решение задач 1–4 даётся 2 балла; задач 5, 6 — 3 балла; задачи 7 — 4 балла. Дан фрагмент таблицы результатов районного тура.

 

ФамилияПолЗадача

№ 1

Задача

№ 2

Задача

№ 3

Задача

№ 4

Задача

№ 5

Задача

№ 6

Задача

№ 7

Айвазянж1021033
Житомирскийм2222233
Иваненкож2110123
Лимоновм2111223
Петраковм2001020
Рахимовм2220201
Суликашвилиж1111123
Толкачёваж2221220

 

Сколько девочек из этой таблицы прошли на городской тур?

5.

По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д, Е. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано; для букв A, Б, В используются такие кодовые слова: А — 0, Б — 101, В — 110.

Какова наименьшая возможная суммарная длина всех кодовых слов? Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. Коды, удовлетворяющие условию Фано, допускают однозначное декодирование.

6.

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

1. Складываются отдельно первая и вторая, вторая и третья, третья и четвёртая цифры заданного числа.

2. Наименьшая из полученных трёх сумм удаляется.

3. Оставшиеся две суммы записываются друг за другом в порядке неубывания без разделителей.

Пример. Исходное число: 1984. Суммы: 1 + 9 = 10, 9 + 8 = 17, 8 + 4 = 12.

Удаляется 10. Результат: 1217.

Укажите наименьшее число, при обработке которого автомат выдаёт результат 613.

7.

Дан фрагмент электронной таблицы:

 

ABC
134
2=(A1 + B1+2)/(C1 – B1)=( 2*C1 – 2)/ A1=B1*C1/(B1 – A1)

 

Какое целое число должно быть записано в ячейке A1, чтобы построенная после выполнения вычислений диаграмма по значениям диапазона ячеек A2:С2 соответствовала рисунку?

8.

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

 

 

БейсикPython

DIM N, S AS INTEGER

N = 1

S = 0

WHILE N <= 101

    S = S + 7

    N = N + 1

WEND

PRINT S

n = 1

s = 0

while n <= 101:

    s += 7

    n += 1

print(s)

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

var n, s: integer;

begin

    n := 1;

    s := 0;

    while n <= 101 do

    begin

        s := s + 7;

        n := n + 1;

    end;

    writeln(s);

end.

алг

нач

    цел n, s

    n := 1

    s := 0

    нц пока n <= 101

        s := s + 7

        n := n + 1

    кц

    вывод s

кон

Си++

#include <iostream>

using namespace std;

int main() {

    int n, s;

    n = 1, s = 0;

    while (n <= 101) {

        s = s + 7;

        n = n + 1;

    }

    cout << s << endl;

    return 0;

}

 

9.

У Аркадия есть доступ в Интернет по высокоскоростному одностороннему радиоканалу, обеспечивающему скорость получения информации 220бит в секунду. У Григория нет скоростного доступа в Интернет, но есть возможность получать информацию от Аркадия по телефонному каналу со средней скоростью 216 бит в секунду. Григорий договорился с Аркадием, что тот скачает для него данные объёмом 11 Мбайт по высокоскоростному каналу и ретранслирует их Григорию по низкоскоростному каналу.

 

Компьютер Аркадия может начать ретрансляцию данных не раньше, чем им будут получены первые 1024 Кбайт этих данных.

 

Каков минимально возможный промежуток времени (в секундах) с момента начала скачивания Аркадием данных до полного их получения Григорием? В ответе укажите только число, слово «секунд» или букву «с» добавлять не нужно.

10.

Двое играют в «крестики-нолики» на поле 4 на 4 клетки. Какое количество информации (в битах) получил второй игрок, узнав ход первого игрока?

11.

Ниже на пяти языках программирования записан рекурсивный алгоритм F.

 

 

БейсикPython

SUB F(n)

    IF n > 0 THEN

         F(n \ 3)

         F(n − 3)

         PRINT N

    END IF

END SUB

 

def F(n):

    if n > 0:

        F(n // 3)

        F(n − 3)

        print(n)

 

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

procedure F(n: integer);

begin

    if n > 0 then begin

        F(n div 3);

        F(n − 3);

        write(n)

    end

end;

 

алг F(цел n)

нач

    если n > 0 то

        F(div(n,3))

        F(n − 3)

        вывод n

    все

кон

 

С++

void F (int n)

{

     if (n > 0) {

        F (n / 3);

        F (n − 3);

        std::cout << n;

    }

}

 

 

 

Запишите подряд без пробелов и разделителей все числа, которые будут напечатаны на экране при выполнении вызова F(9). Числа должны быть записаны в том же порядке, в котором они выводятся на экран.

12.

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

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

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

Для узла с IP-адресом 93.138.161.94 адрес сети равен 93.138.160.0. Какое наименьшее количество нулей может быть в двоичной записи маски?

13.

В некоторой базе данных хранятся записи, содержащие информацию о некоторых датах. Каждая запись содержит три поля: номер года (число от 1 до 2100), номер месяца (число от 1 до 12) и номер дня в месяце (число от 1 до 30). Каждое поле записывается отдельно от других полей с использованием минимально возможного количества бит. Определите минимальное количество бит, необходимое для кодирования одной записи. (Ответ дайте в битах.)

14.

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

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

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

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

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

Цикл

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

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

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

 

НАЧАЛО

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

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

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

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

КОНЕЦ

15.

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

 

16.

Значение выражения 416 + 234 − 8 записали в системе счисления с основанием 2. Сколько цифр 1 содержится в этой записи?

17.

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

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

 

ЗапросНайдено страниц (в тысячах)
Франция & Германия274
Германия & (Франция | Австрия)467
Франция & Германия & Австрия104

 

Какое количество страниц (в тысячах) будет найдено по запросу Германия & Австрия?

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

18.

Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n.

Так, например, 14&5 = 11102&01012 = 01002 = 4.

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

 

x&51 = 0 ∨ (x&41 = 0 → x&А = 0)

 

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

19.

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

 

 

БейсикPython

s = 0

n = 10

FOR i = 2 TO n

    s=s+A(i)*A(i)-A(i-1)*A(i-1)

NEXT i

s=0

n=10

for i in range(2,n+1):

    s=s + A[i]*A[i]-A[i-1]*A[i-1]

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

s:=0;

n:=10;

for i:= 2 to n do begin

    s:=s+A[i]*A[i]-A[i-1]*A[i-1];

end;

s:=0

n:=10

нц для i от 2 до n

    s:=s + A[i]*A[i]-A[i-1]*A[i-1];

кц

Си++

s = 0;

n = 10;

for (i = 2; i <= n; i++) {

    s=s + A[i]*A[i]-A[i-1]*A[i-1];

}

 

 

В начале выполнения этого фрагмента в массиве находились числа 1, 12, 23, 34, 45, 56, 67, 78, 89, 90, т. е. A[1]=1, A[2]=12 и т.д. Чему будет равно значение переменной s после выполнения данного фрагмента?

20.

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

 

БейсикPython

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

x = int(input())

a = 0; b = 0

while x > 0:

  a = a + 1

  if (x % 2 ==0):

    b += x%10

  x=x / / 10

print(a, b)

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

program b20;

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.

алг

нач

    цел 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

кон

Си++

#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;

    return 0;

}

 

21.

Напишите в ответе число различных значений входной переменной k, при которых программа выдаёт тот же ответ, что и при входном значении k = 55. Значение k = 55 также включается в подсчёт различных значений k. Для Вашего удобства программа приведена на пяти языках программирования.

 

 

Бейсик Python

DIM K, I AS LONG

INPUT K

I = 0

WHILE F(I) < K

    I = I + 1

WEND

PRINT I

FUNCTION F(N)

    F = 3*N*N+1

END FUNCTION

def f(n):

    return 3*n*n+1

k = int(input())

i = 0

while f(i) < k:

    i = i + 1

print(i)

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

алг

нач

    цел i, k

    ввод k

    i := 0

    нц пока f(i) < k

        i := i+1

    кц

    вывод i

кон

алг цел f(цел n)

нач

    знач := 3*n*n+1

кон

var k, i : longint;

function f(n: longint):longint;

begin

    f := 3*n*n+1

end;

begin

    readln(k);

    i := 0;

    while (f(i)<k) do

        i := i+1;

    writeln(i)

end.

Си++

#include <iostream>

using namespace std;

long f(long n) {

    return 3*n*n+1;

}

int main()

{

    long k, i;

    cin >> k;

    i = 0;

    while (f(i)<k)

        i++;

    cout << i << endl;

}

 

22.

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

 

1. прибавь 1

2. прибавь 2.

 

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

23.

Сколько существует различных наборов значений логических переменных x1, x2,…, x7, y1, y2, ..., y7, которые удовлетворяют всем перечисленным ниже условиям?

 

((x1y1) → (x2y2)) ∧ (x1y1) = 1

((x2y2) → (x3y3)) ∧ (x2y2) = 1

...

((x6y6) → (x7y7)) ∧ (x6y6) = 1

(x7y7) = 1

 

В ответе не нужно перечислять все различные наборы значений переменных x1, x2, ..., x7, y1, y2, ..., y7, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

24.

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

 

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

var х, у: real;

begin

readln(x, у);

if у <= sin(x) then

if у >= 1 − x then

if у >= 0 then

write('принадлежит')

else

write('не принадлежит')

end.

INPUT x, у

IF у <= SIN(x) THEN

IF у >= 1 − x THEN

IF у >= 0 THEN

PRINT "принадлежит"

ELSE

PRINT "не принадлежит"

ENDIF

ENDIF

ENDIF

END

Си++Алгоритмический язык
int main(void)

{

float x, у;

cin >> x >> y;

if (y <= sin(x))

if (у >= 1 − x)

if (y >= 0)

cout << "принадлежит";

else

cout << "не принадлежит";

}

алг

нач

вещ х, у

ввод X, у

если у <= sin (х) то

если у >= 1 − х то

если у >= 0 то

вывод ' принадлежит '

иначе

вывод 'не принадлежит'

все

все

все

кон

Python

x = float(input())

y = float(input())

if у <= sin(x):

    if у >= 1 − x:

        if у >= 0:

            print("принадлежит")

        else:

            print("не принадлежит")

 

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

1. Перерисуйте и заполните таблицу, которая показывает, как работает программа при аргументах, принадлежащих различным областям (A, B, C, D, E, F, G и H).

Точки, лежащие на границах областей, отдельно не рассматривать. В столбцах условий укажите "да", если условие выполнится, "нет", если условие не выполнится, "—" (прочерк), если условие не будет проверяться, "не изв.", если программа ведет себя по-разному для разных значений, принадлежащих данной области. В столбце "Программа выведет" укажите, что программа выведет на экран. Если программа ничего не выводит, напишите "—" (прочерк). Если для разных значений, принадлежащих области, будут выведены разные тексты, напишите "не изв". В последнем столбце укажите "да" или "нет".

 

2. Укажите, как нужно доработать программу, чтобы не было случаев ее неправильной работы. (Это можно сделать несколькими способами, достаточно указать любой способ доработки исходной программы.)

 

 

ОбластьУсловие 1

(у <= sin(x))

Условие 2

(у >= 1 − x)

Условие 3

(у >= 0)

Программа выведетОбласть обрабатывается

верно

A
В
С
D
Е
F
G
Н

25.

Дан целочисленный массив из 40 элементов. Элементы массива могут принимать целые значения от 0 до 10 000 включительно. Опишите на естественном языке или на одном из языков программирования алгоритм, который находит количество элементов массива, меньших 100, не делящихся на 3, после чего заменяет в массиве соответствующие значения на найденное количество. После чего выводит полученный массив на экран.

 

 

БейсикPython

CONST N = 40

DIM A (1 TO N) AS INTEGER

DIM I, J, K AS INTEGER

FOR I = 1 TO N

     INPUT A(I)

NEXT I

     END

# допускается также

# использовать две

# целочисленные

# переменные j, k

a = []

n = 40

for i in range(n):

     a.append(int(input()))

...

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

const n = 40;

var

    a: array [0..n-1] of integer;

     i, j, k: integer;

begin

    for i := 0 to n-1 do

        readln(a[i]);

     ...

end.

алг

нач

цел N = 40

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

цел i, j, k

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

ввод a[i]

кц

...

кон

Си++

#include <iostream>

using namespace std;

#define n 40

     int main() {

     int a[n]; int i, j, k;

     for (i = 0; i < n; i++) std::cin >> a[i];

    ...

     return 0;

}

 

26.

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

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

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Например, при начальных позициях (6, 36), (7, 35), (9, 34) выигрышная стратегия есть у Пети. Чтобы выиграть, ему достаточно удвоить количество камней во второй куче.

 

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

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

 

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

 

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

27.

На вход программе (как вариант, из входного файла text.dat) подаётся текст на английском языке. Ввод этих символов заканчивается точкой (другие символы, отличные от «.» во входных данных отсутствуют; в программе на языке Бейсик символы можно вводить по одному в строке, пока не будет введена точка). Требуется написать как можно более эффективную программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет определять и выводить на экран, какая английская буква встречается во входной последовательности чаще всего и сколько именно раз. Строчные и прописные буквы при этом не различаются. Если таких букв несколько, то программа должна выводить на экран ту из них, которая стоит по алфавиту раньше.

Например, пусть файл содержит следующую информацию:

It is not a simple task. Yes!

Тогда чаще всего встречаются буквы I, S, T. (слово Yes в подсчете не участвует, так как расположено после точки). Следовательно, в данном случае, программа должна вывести

I 3.