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

1.

Сколько единиц в двоичной записи восьмеричного числа 20768?

2.

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

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

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

 

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

 

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

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

 

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

 

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

3.

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

 

 

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

4.

В фрагменте базы данных представлены сведения о родственных отношениях. На основании приведённых данных определите ID дедушки Корзуна П. А.

 

Таблица 1
IDФамилия_И.О.Пол
1072Онищенко А.Б.Ж
1028Онищенко Б.Ф.М
1099Онищенко И.Б.М
1178Онищенко П.ИМ
1156Онищенко Т.И.Ж
1065Корзун А.И.Ж
1131Корзун А.П.М
1061Корзун Л.Г.М
1217Корзун П.А.М
1202Зельдович М.А.Ж
1027Витюк Д.К.Ж
1040Лемешко В.А.Ж
1046Месяц К.Г.М
1187Лукина Р.Г.Ж
1093Фокус П.А.Ж
1110Друк Г.Р.Ж

Таблица 2
ID_РодителяID_Ребенка
10271072
10271099
10281072
10281099
10721040
10721202
10721217
10991156
10991178
11101156
11101178
11311040
11311202
11311217
11871061
11871093

5.

Для кодирования букв О, Ч, Б, А, К решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Закодируйте последовательность букв КАБАЧОК таким способом и результат запишите шестнадцатеричным кодом.

6.

Исполнитель КАЛЬКУЛЯТОР имеет только две команды, которым присвоены номера:

 

1. прибавь 1

2. умножь на 2

 

Выполняя команду номер 1, КАЛЬКУЛЯТОР прибавляет к числу на экране 1, а выполняя

команду номер 2, умножает число на экране на 2. Укажите минимальное число команд, которое должен выполнить исполнитель, чтобы получить из числа 19 число 629.

7.

Дан фрагмент электронной таблицы. Из ячейки B2 в одну из ячеек диапазона A1:A4 была скопирована формула. При копировании адреса ячеек в формуле автоматически изменились, и числовое значение в этой ячейке стало равным 8. В какую ячейку была скопирована формула? В ответе укажите только одно число — номер строки, в которой расположена ячейка.

 

ABCDE
14321
2= D$3 + $C2432
36543
47654

 

Примечание. Знак $ обозначает абсолютную адресацию.

8.

Определите значение переменной c после выполнения следующего фрагмента программы (записанного ниже на разных языках программирования). Ответ запишите в виде целого числа.

 

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

a = 20

b = 15

b = 3 * b - a

IF a > b THEN

c = 2 * a + b

ELSE

c = 2 * a - b

END IF

a := 20;

b := 15;

b := 3 * b - a;

if a > b then

c := 2 * a + b

else

c := 2 * a - b;

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

a = 20;

b = 15;

b = 3 * b - a;

if (a > b)

c = 2 * a + b;

else

c = 2 * a - b;

a := 20

b := 15

b := 3 * b - a

если a > b

то c := 2 * a + b

иначе c := 2 * a - b

все

Python

a = 20

b = 15

b = 3 * b - a

if a > b:

    c = 2 * a + b

else:

    c = 2 * a - b

 

9.

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

10.

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

11.

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

 

БейсикPython

SUB F(n)

    PRINT n

    IF n > 1 THEN

        F(n - 1)

        F(n - 3)

    END IF

END SUB

def F(n):

    print(n)

    if n > 1:

        F(n - 1)

        F(n - 3)

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

procedure F(n: integer);

    begin

        writeln(n);

        if n > 1 then

            begin

                F(n - 1);

                F(n - 3)

            end

    end

алг F(цел n)

нач

вывод n, нс

если n > 1 то

    F(n - 1)

    F(n - 3)

все

кон

C++

void F(int n)

{

    cout << n;

    if (n > 1)

    {

        F(n - 1);

        F(n - 3);

    }

}

 

Чему равна сумма всех чисел, напечатанных на экране при выполнении вызова F(6)?

12.

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

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

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

13.

При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 10 символов. Для построения идентификатора используют только прописные латинские буквы (26 букв). В базе данных для хранения каждого пароля отведено одинаковое минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым минимально возможным количеством бит. Кроме пароля для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено одинаковое целое количество байт на каждого пользователя. Для хранения информации о 15 пользователях потребовалось 300 байт. Сколько байт выделено для хранения дополнительных сведений об одном пользователе? В ответе запишите только целое число — количество байт.

14.

Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости, включает в себя 4 команды-приказа и 4 команды проверки условия. Команды-приказы: вверх, вниз, влево, вправо. При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →. Если РОБОТ начнёт движение в сторону находящейся рядом с ним стены, то он разрушится, и программа прервётся.

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

Цикл

ПОКА условие

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

КОНЕЦ ПОКА

 

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

 

В конструкции

ЕСЛИ условие

ТО команда1

ИНАЧЕ команда2

КОНЕЦ ЕСЛИ

 

выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

 

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

 

НАЧАЛО

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

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

вниз

КОНЕЦ ПОКА

ЕСЛИ справа свободно

ТО

вправо

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

15.

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

 

16.

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

17.

В таблице приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета:

 

ЗапросКоличество страниц
(тыс.)
пирожное | выпечка14200
пирожное9700
пирожное & выпечка5100

 

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

выпечка

18.

Сколько существует целых значений числа A, при которых формула

 

((x < 5) → (x2 < A)) /\ ((y2A) → (y ≤ 5))

 

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

19.

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

 

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

s = 0

n = 10

FOR i = 0 TO n-1

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

NEXT i

s:=0;

n:=10;

for i:=0 to n-1 do begin

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

end;

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

s = 0;

n=10;

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

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

}

s:=0

n:=10

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

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

кц

Python

s = 0

n = 10

for i in range(0, n):

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

 

 

В начале выполнения этого фрагмента в массиве находились числа 15, 10, 5, 0, 5, 10, 15, 10, 5, 0, 5, т. е. A[0]=15, A[1]=10 и т. д. Чему будет равно значение переменной s после выполнения данной программы?

20.

Ниже на четырёх языках записан алгоритм. Получив на вход число , этот алгоритм печатает два числа: и . Укажите наименьшее из таких чисел , при вводе которых алгоритм печатает сначала 2, а потом 3. Допускается диапазон значений для величин целого типа: от −231 до 231 — 1.

 

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

DIM X, А, В, С AS INTEGER

INPUT X

А = 0: В = 0

WHILE X > 0

    С = X MOD 2

    IF C = 0 THEN

        A = A + 1

    ELSE

        B = B + 1

    END IF

    X = X \ 10

WEND

PRINT А

PRINT В

var x, a, b, c: integer;

begin

    readln(x);

    a := 0; b := 0;

    while x>0 do

        begin

            с := x mod 2;

            if c = 0 then

                a := a + 1

            else

                b := b + 1

            x := x div 10

        end;

    writeln(a); write(b);

end.

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

#include <iostream>

using namespace std;

int main()

{

    int x, a, b, c;

    cin >> x;

    a = 0;

    b = 0;

    while (x > 0) {

        с = x % 2;

        if (c == 0) a = a + 1;

        else b = b + 1;

        x = x / 10;

    }

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

}

алг

нач

цел х, а, b, с

ввод X

а := 0; b := 0

нц пока х>0

    с := mod(х, 2)

    если с = 0

        то a := a + 1

    иначе b := b + 1

все

х := div(х, 10)

кц

вывод а, не, b

кон

Python

x = int(input())

a = 0

b = 0

while x > 0:

    с = x % 2

    if c == 0:

        a += 1

    else:

        b += 1

    x //= 10

print(a)

print(b)

 

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*x - 8*x + 10

END FUNCTION

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

    Function F(x:integer): integer;

        begin

            F := x*x - 8*x + 10

        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*x - 8*x + 10;

}

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*x - 8*x + 10

кон

Python

def f(x):

    return x*x - 8*x + 10

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, вторая удваивает его. Программа для Удвоителя — это последовательность команд. Сколько есть программ, которые число 3 преобразуют в число 22?

23.

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

 

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

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

x1 → y1 = 1

 

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

24.

Дано натуральное число N (N ≤ 109). Необходимо найти и вывести наибольшую нечётную цифру в десятичной записи N или вывести сообщение «NO», если таких цифр нет.

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

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

 

 

БейсикPython

DIM N, D, M, T AS INTEGER

INPUT N

T = 0

M = T

WHILE N > 1

    D = N MOD 10

    IF D MOD 2 = 1 OR D > M THEN

        M = D

    END IF

    N = N \ 10

WEND

IF M = T THEN

    PRINT "NO"

ELSE

    PRINT M

END IF

END

N = int(input())

t = 0

m = t

while N > 1:

    d = N % 10

    if d%2 == 1 or d > m:

        m = d

    N = N // 10

if m == t:

    print("NO")

else:

    print(m)

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

var N, d, m, t: integer;

begin

    read(N);

    t := 0;

    m := t;

    while N > 1 do begin

        d := N mod 10;

        if (d mod 2 = 1) or (d>m)

            m := d;

        N := N div 10

    end;

    if m = t

        then writeln('NO')

        else writeln(m)

end.

алг

нач

    цел N, d, m, t

    ввод N

     t := 0

     m := t

     нц пока N > 1

        d := mod(N,10)

        если mod(d,2)=1 или d>m то

            m := d

        все

        N := div(N,10)

     кц

     если m = t

        то вывод "NO"

        иначе вывод m

    все

кон

С++

#include <iostream>

using namespace std;

int main(){

    int N, d, m, t;

    cin >> N;

    t = 0;

    m = t;

    while (N > 1) {

        d = N % 10;

        if (d % 2 == 1 || d > m)

            m = d;

        N = N / 10;

    }

    if (m == t)

        cout << "NO";

    else

        cout << m;

    return 0;

}

 

 

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

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

2. Какое наменьшее число может стать результатом работы этой программы? Приведите пример числа N, при вводе которого программа выведет такой ответ.

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

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

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

25.

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

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

 

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

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.

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

Игра завершается в тот момент, когда количество камней в куче становится не менее 20. Если при этом в куче оказалось не более 30 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. Например, если в куче было 17 камней и Паша удвоит количество камней в куче, то игра закончится, и победителем будет Валя. В начальный момент в куче было S камней, 1 ≤ S ≤ 19.

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

 

Выполните следующие задания.

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

б) У кого из игроков есть выигрышная стратегия при S = 18, 17, 16? Опишите выигрышные стратегии для этих случаев.

2. У кого из игроков есть выигрышная стратегия при S = 9, 8? Опишите соответствующие выигрышные стратегии.

3. У кого из игроков есть выигрышная стратегия при S = 7? Постройте дерево всех партий, возможных при этой выигрышной стратегии (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход; в узлах — количество камней в позиции.

27.

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

 

6

1

2

1

1

5

2

 

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

 

1 3

2 2

5 1