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

1.

Сколько существует целых чисел x, для которых выполняется неравенство 2A16 < x < 618?

В ответе укажите только количество чисел, сами числа писать не нужно.

2.

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

xyz) ∨ (¬x ∧ ¬yz) ∨ (¬x ∧ ¬y ∧ ¬z).

 

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

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

 

Перем. 1Перем. 2Перем. 3Функция
?????????F
0001
1001
1011

 

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

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

 

Перем. 1Перем. 2Функция
??????F
001
010
101
111

 

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

3.

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

 

ABCDEFG
A26
B253
C518
D63197
E95
F77
G857

 

Определите длину кратчайшего пути между пунктами A и G. Передвигаться можно только по указанным дорогам.

4.

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

 

Таблица 1
IDФамилия_И.О.Пол
1674Жук М.Б.Ж
1702Баль А.П.М
1769Черняк И.Б.М
1834Ререх А.И.Ж
2046Черняк П.И.М
2060Радек П.А.Ж
2094Черняк Б.Ф.М
2192Чиж Д.К.Ж
2425Рерих Л.А.Ж
2435Черняк А.Б.Ж
2607Малеев К.Г.М
2679Баль П.А.М
2816Черняк Т.И.Ж
2946Панина Р.Г.Ж
2968Тесленко Г.Р.Ж
2998Рерих В.И.Ж

Таблица 2
ID_РодителяID_Ребенка
17022679
17692046
17692816
17692997
20941674
20941769
20942435
21921674
21921769
21922435
24352679
29682997
29682046
29682816
29972060
29972425

5.

Для кодирования некоторой последовательности, состоящей из букв И, К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Л использовали кодовое слово 1, для буквы М – кодовое слово 01. Какова наименьшая возможная суммарная длина всех пяти кодовых слов?

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

6.

Автомат обрабатывает натуральное число N (0 ≤ N ≤ 255) по следующему алгоритму:

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

2. Все цифры двоичной записи заменяются на противоположные (0 на 1, 1 на 0).

3. Полученное число переводится в десятичную запись.

4. Из нового числа вычитается исходное, полученная разность выводится на экран.

Пример. Дано число N = 13. Алгоритм работает следующим образом.

1. Восьмибитная двоичная запись числа N: 00001101.

2. Все цифры заменяются на противоположные, новая запись 11110010.

3. Десятичное значение полученного числа 242.

4. На экран выводится число 242 − 13 = 229.

 

Какое число нужно ввести в автомат, чтобы в результате получилось 111?

7.

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

 

 

АBCD
19...25
2=B2+C2+D2=C2=(A1–D1)*(B1-5)=(A1–D1)*C1

 

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

8.

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

 

 

БейсикPython

DIM K, S AS INTEGER

S = 5

K = 0

WHILE K < 15

    K = K + 2

    S = S + K

WEND

PRINT S

s = 5

k = 0

while k < 15:

    k += 2

    s += k

print(s)

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

var k, s: integer;

begin

       s:=5;

       k:=0;

      while k < 15 do begin

            k:=k+2;

            s:=s+k;

       end;

      write(s);

end.

алг

нач

    цел k, s

    s := 5

    k := 0

    нц пока k < 15

        k := k + 2

        s := s + k

    кц

    вывод s

кон

Си++

#include <iostream>

using namespace std;

int main() {

    int s, k;

    s = 5, k = 0;

    while (k < 15) {

        k = k + 2;

        s = s + k;

    }

    cout << s << endl;

    return 0;

}

 

9.

Текстовый документ хранился в 8-битной кодировке КОИ-8. Этот документ был преобразован в 16-битную кодировку Unicode, при этом размер памяти, необходимой для хранения документа увеличился на 4 Кбайт. При этом хранится только последовательность кодов символов. Укажите, сколько символов в документе. В ответе запишите только число.

10.

Алексей составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Алексей использует 5-буквенные слова, в которых есть только буквы A, B, C, X, причём буква X может появиться на первом месте или не появиться вовсе. Сколько различных кодовых слов может использовать Алексей?

11.

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

 

БейсикPython

DECLARE FUNCTION F(n)

DECLARE FUNCTION G(n)

FUNCTION F(n)

  IF n > 2 THEN

    F = F(n - 1) + G(n-2)

  ELSE

    F = 1

  END IF

END FUNCTION

FUNCTION G(n)

  IF n > 2 THEN

    G = G(n - 1) + F(n-2)

  ELSE

    G = 1

  END IF

END FUNCTION

def F(n):

  if n > 2:

    return F(n-1)+ G(n-2)

  else: return 1

def G(n):

  if n > 2:

  return G(n-1) + F(n-2)

  else: return 1

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

function F(n: integer): integer;

begin

  if n > 2 then

    F := F(n - 1) + G(n - 2)

  else

    F := 1;

end;

function G(n: integer): integer;

begin

  if n > 2 then

    G := G(n - 1) + F(n - 2)

  else

    G := 1;

end;

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

нач

  если n > 2

    то

      знач := F(n - 1) + G(n - 2)

    иначе

      знач := 1

  все

кон

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

нач

  если n > 2

    то

      знач := G(n - 1) + F(n - 2)

    иначе

      знач := 1

  все

кон

Си

int F(int n)

{

  if (n > 2)

    return F(n-1) + G(n-2);

  else return 1;

}

int G(int n)

{

  if (n > 2)

    return G(n-1) + F(n-2);

  else return 1;

}

 

Чему будет равно значение, вычисленное при выполнении вызова F(7)?

12.

В терминологии сетей TCP/IP маской подсети называется 32-разрядное двоичное число, определяющее, какие именно разряды IP-адреса компьютера являются общими для всей подсети - в этих разрядах маски стоит 1. Обычно маски записываются в виде четверки десятичных чисел - по тем же правилам, что и IP-адреса. Для некоторой подсети используется маска 255.255.255.224. Сколько различных адресов компьютеров теоретически допускает эта маска, если два адреса (адрес сети и широковещательный) не используют?

13.

Автомобильный номер состоит из нескольких букв (количество букв одинаковое во всех номерах), за которыми следуют 4 цифры. При этом используются 10 цифр и только 4 буквы: А, В, Т, О. Нужно иметь не менее 1 000 000 различных номеров. Какое наименьшее количество букв должно быть в автомобильном номере?

 

14.

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.

 

1. заменить (v, w)

2. нашлось (v)

 

Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w, вторая проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из одной единицы и 75 стоящих справа от нее нулей? В ответе запишите сколько нулей будет в конечной строке.

 

НАЧАЛО

ПОКА нашлось (10) ИЛИ нашлось (1)

    ЕСЛИ нашлось (10)

        ТО заменить (10, 001)

        ИНАЧЕ заменить (1, 00)

    КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

15.

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

 

16.

Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 23 оканчивается на 2.

 

17.

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

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

 

ЗапросНайдено страниц
(в тысячах)
Тредиаковский68
Тредиаковский & Жуковский14
Сикорский320
Сикорский | Жуковский584
Сикорский | Тредиаковский388
Жуковский366

 

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

 

Тредиаковский | Жуковский | Сикорский?

 

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

18.

На числовой прямой даны два отрезка: P = [5, 30] и Q = [14, 23]. Укажите наибольшую возможную длину промежутка A, для которого формула

 

((x ∈ P) ≡ (x ∈ Q)) → ¬(x ∈ A)

 

тождественно истинна, то есть принимает значение 1 при любом значении переменной х.

19.

Значения элементов двухмерного массива A[1..10,1..10] сначала равны 0. Затем выполняется следующий фрагмент программы:

 

 

БейсикPython

FOR i = 1 TO 4

    FOR j = 2 TO 5

        A(i,j) = A(i,j)+4

        A(j,i) = A(j,i)+5

    NEXT j

NEXT i

 

for i in range(1, 5):

    for j in range(2, 6):

        A[i][j] = A[i][j]+4

        A[j][i] = A[j][i]+5

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

for i:=1 to 4 do

    for j:=2 to 5 do begin

        A[i,j] : = A[i,j]+4;

        A[j,i] : = A[j,i]+5;

    end;

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

    нц для j от 2 до 5

        A[i,j] : = A[i,j]+4

        A[j,i] : = A[j,i]+5

    кц

кц

Си++

for (i = 1; i <= 4; i++) {

    for (j = 2; j <= 5; j++) {

        A[i][j] = A[i][j]+4;

        A[j][i] = A[j][i]+5;

    }

}

 

 

Сколько элементов массива будут равны 9?

20.

Ниже на пяти языках программирования записан алгоритм. Получив на вход число x, этот алгоритм печатает число M. Известно, что x > 100. Укажите наименьшее такое (т.е. большее 100) число x, при вводе которого алгоритм печатает 26.

 

БейсикPython

DIM X, L, M AS INTEGER

INPUT X

L = X

M = 65

IF L MOD 2 = 0 THEN

    M = 52

ENDIF

WHILE L <> M

IF L > M THEN

    L = L – M

ELSE

    M = M – L

ENDIF

WEND

PRINT M

x = int(input())

L = x

M = 65

if L % 2 == 0:

    M = 52

while L != M:

    if L > M:

        L = L - M

    else:

        M = M - L

print(M)

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

var x, L, M: integer;

begin

    readln(x);

    L := x;

    M := 65;

    if L mod 2 = 0 then

        M := 52;

    while L <> M do

        if L > M then

            L := L - M

        else

            M := M – L;

    writeln(M);

end.

 

алг

нач

    цел x, L, M

    ввод x

    L := x

    M := 65

    если mod(L,2)=0

        то

            M := 52

    все

    нц пока L <> M

        если L > M

            то

                L := L – M

            иначе

                M := M – L

        все

    кц

    вывод M

кон

Си++

#include <iostream>

using namespace std;

int main()

{

    int x, L, M;

    cin >> x;

    L = x;

    M = 65;

    if (L % 2 == 0)

        M = 52;

    while (L != M){

        if(L > M)

            L = L - M;

        else

            M = M - L;

    }

    cout « M « endl;

}

 

21.

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

 

БейсикPython

    DIM K, I AS LONG

    INPUT K

    I = 12

    WHILE I > 0 AND F(I) > K

        I = I − 1

    WEND

    PRINT I

 

    FUNCTION F(N)

        F = N * N * N

    END FUNCTION

def F(n):

    return n * n * n

 

k = int(input())

i = 12

while (i > 0 and F(i) > k):

    i = i − 1

print (i)

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

var k, i :longint;

function F(n: longint) : longint;

begin

    F := n * n * n;

end;

 

begin

     readln(k);

     i := 12;

    while (i > 0) and (F(i) > k) do

         i := i − 1;

    writeln(i);

end.

алг

нач

    цел i, k

    ввод k

    i := 12

    нц пока i > 0 и f(i) > k

        i := i − 1

    кц

    вывод i

кон

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

нач

    знач := n * n * n

кон

Си++

#include <iostream>

using namespace std;

 

long F(long n)

{

    return n * n * n

}

 

int main()

{

    int k, i;

    cin >> k;

    i = 12;

    while (i > 0 && F(i) > k)

        i−−

    cout << i;

return 0;

}

 

22.

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

 

1. прибавь 4,

2. вычти 3.

 

Первая из них увеличивает число на экране на 4, вторая – уменьшает его на 3. Если в ходе вычислений появляется отрицательное число, он выходит из строя и стирает написанное на экране. Программа для Калькулятора – это последовательность команд. Сколько различных чисел можно получить из числа 0 с помощью программы, которая содержит ровно 17 команд?

23.

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

 

(x1 → x2) ∧ (x2 → x3) ∧ (x3 → x4) ∧ (x4 → x5) = 1

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) ∧ (y4 → y5) = 1

(z1 → z2) ∧ (z2→ z3) ∧ (z3 → z4) ∧ (z4→ z5) = 1

x1 ∨ y1 ∨ z1 = 1

 

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

24.

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

 

 

БейсикPython

INPUT с, х

IF с>0 THEN

PRINT "нет решений"

ELSE

PRINT "х=",SQR(-с)

или х=",-SQR(-с)

ENDIF

END

c = float(input())

x = float(input())

if c > 0:

    print("нет решений")

else:

    print('х=',sqrt(-с),

' или х=',-sqrt(-с))

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

var с,х: real;

begin

readln (с,х);

if с>0 then

write ('нет решений')

else

write ('х=',sqrt(-с),

' или х=',-sqrt(-с));

end.

алг

нач

    вещ c,x

    если c > 0 то

        вывод 'нет решений'

    иначе

        вывод 'х=',sqrt(-с),

' или х=',-sqrt(-с)

    все

кон

Си++

#include <iostream>

using namespace std;

int main(void)

{ float c,x;

cin >> c >> x;

if (c>0)

cout << "нет решений";

else

cout << ""х="" << sqrt(-с) << " или х=" << -sqrt(-с)) << endl;

}

 

 

Последовательно выполните три задания:

1) Приведите пример таких чисел с, х, при которых программа неверно решает поставленную задачу.

2) Укажите, какая часть программы является лишней.

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

25.

Дан массив, содержащий 2018 положительных целых чисел, не превышающих 30 000. Необходимо определить, сколько в этом массиве элементов, десятичная и шестнадцатеричная запись которых содержит одинаковое количество цифр.

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

Запрещается использовать переменные, не описанные ниже, но разрешается не использовать часть из описанных.

 

 

БейсикPython

CONST N=2018

DIM A(N) AS INTEGER

DIM B, I, K, L, M AS INTEGER

FOR I = 1 TO N

    INPUT A(I)

NEXT I

END

# кроме уже указанных

# допускается использование

# целочисленных переменных

# k, b, l, m

a = []

N = 2018

for i in range(0, N):

    a.append(int(input()))

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

const

    N=2018;

var

    a: array [1..N] of integer;

    b, i, k, l, m: integer;

begin

    for i:=1 to N do

        readln(a[i]);

    …

end.

алг

нач

    цел N=2018

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

    цел b, i, k, l, m

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

        ввод a[i]

    кц

    …

кон

Си++

#include <iostream>

using namespace std;

const int N=2018;

int main(){

    int a[N];

    int b, i, k, l, m;

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

        cin >> a[i];

    …

    return 0;

}

 

 

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

26.

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

Задание 1. а) Укажите все такие значения числа S, при которых Паша может выиграть в один ход. Обоснуйте, что найдены все нужные значения S, и укажите выигрывающий ход для каждого указанного значения S. б)Укажите такое значение S, при котором Паша не может выиграть за один ход, но при любом ходе Паши Вася может выиграть своим первым ходом. Опишите выигрышную стратегию Васи.

Задание 2. Укажите 2 таких значения S, при которых у Паши есть выигрышная стратегия, причём Паша не может выиграть за один ход и может выиграть своим вторым ходом независимо от того, как будет ходить Вася. Для каждого указанного значения S опишите выигрышную стратегию Паши.

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

27.

На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре не важен). Необходимо определить количество пар, для которых произведение элементов не кратно 14.

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

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

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

4

2

6

5

42

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

3

Пояснение. Из четырёх заданных чисел можно составить 6 попарных произведений: 2 · 6, 2 · 5, 2 · 42, 6 · 5, 6 · 42, 5 · 42. Из них на 14 не делятся 3 произведения (2 · 6, 2 · 5, 6 · 5).

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

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

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

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

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

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

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

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