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

1.

Сколько верных неравенств среди перечисленных:

 

100110102 > 25610;

100110102 > 9F16;

100110102 > 2328.

2.

Дан фрагмент таблицы истинности выражения F:

 

x1x2x3x4x5x6x7F
01011101
10110010
11011011

 

Каким выражением может быть F?

 

1) ¬x1 ∧ x2 ∧¬x3 ∧ ¬x4 ∧x5 ∧ x6 ∧ ¬x7

2) ¬x1 ∨ x2 ∨ ¬x3 ∨¬x4 ∨ x5 ∨ x6 ∨ ¬x7

3) ¬x1 ∨ ¬x2 ∨ x3 ∨ x4 ∨ ¬x5 ∨ ¬x6 ∨ x7

4) ¬x1 ∧ ¬x2 ∧ x3 ∧ x4 ∧ ¬x5 ∧ ¬x6 ∧ x7

3.

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

 

ABCDEF
A33618
B35
C31
D651510
E53
F18103

 

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

4.

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

 

Символ «?» (вопросительный знак) означает ровно один произвольный символ.

 

Символ «*» (звёздочка) означает любую последовательность символов произвольной длины, в том числе «*» может задавать и пустую последовательность. В каталоге находится 6 файлов:

 

slon.doc

slon.docx

klon.doc

poklon.doc

lom.doc

lomka.doc

 

Определите, по какой из масок из них будет отобрана указанная группа файлов:

 

slon.doc

klon.doc

poklon.doc

lom.doc

 

1) *lo?.doc?

2) ?lo*.doc

3) *lo?.doc

4) *?lo?*.*?doc?*

5.

По каналу связи передаются сообщения, каждое из которых содержит 16 букв А, 8 букв Б, 4 буквы В и 4 буквы Г (других букв в сообщениях нет). Каждую букву кодируют двоичной последовательностью. При выборе кода учитывались два требования:

а) ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование);

б) общая длина закодированного сообщения должна быть как можно меньше.

Какой код из приведённых ниже следует выбрать для кодирования букв А, Б, В и Г?

 

1) А:0, Б:10, В:110, Г:111

2) А:0, Б:10, В:01, Г:11

3) А:1, Б:01, В:011, Г:001

4) А:00, Б:01, В:10, Г:11

6.

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

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

2. Полученные два числа записываются друг за другом в порядке убывания (без разделителей).

Пример. Исходное число: 3165. Суммы: 3 + 1 = 4; 6 + 5 = 11. Результат: 114.

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

7.

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

 

ABCDE
1404100709
23036010
3= $B3 * B$223005011
41014004012

 

Из ячейки A3 в ячейку С2 была скопирована формула. При копировании адреса ячеек в формуле автоматически изменились. Каким стало числовое значение формулы в ячейке С2?

 

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

8.

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

 

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

DIM N, S AS INTEGER

N = 0

S = 512

WHILE S >= 0

    S = S - 20

    N = N + 1

WEND

PRINT N

var n, s: integer;

begin

    n := 0;

    s := 512;

    while s >= 0 do

    begin

        s := s - 20;

    n := n + 1

    end;

    write(n)

end.

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

#include <iostream>

using namespace std;

int main()

{

    int n, s;

    n = 0;

    s = 512;

    while (s >= 0)

    {

        s = s - 20;

        n = n + 1;

    }

    cout « n « endl;

}

алг

нач

    цел n, s

    n := 0

    s := 512

    нц пока s >= 0

        s := s - 20

        n := n + 1

    кц

    вывод n

кон

Python

n = 0

s = 512

while s >= 0:

    s -= 20

    n += 1

print(n)

 

9.

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

10.

Все 4-буквенные слова, составленные из букв М, А, Р, Т, записаны в алфавитном порядке.

 

Вот начало списка:

1. АААА

2. АААМ

3. АААР

4. АААТ

5. ААМА

……

Запишите слово, которое стоит на 250-м месте от начала списка.

11.

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

 

F(1) = 3;F(2)=3;

F(n) = 5*F(n-1) − 4*F(n−2) при n >2.

 

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

12.

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

По заданным IP-адресу узла и маске определите адрес сети.

IP адрес узла: 217.9.142.131

Маска: 255.255.192.0

При записи ответа выберите из приведенных в таблице чисел четыре элемента IP-адреса и запишите в нужном порядке соответствующие им буквы, без использования точек.

 

ABCDEFGH
091664128142192217

 

Пусть искомый IP-адрес 192.168.128.0, и дана таблица

 

ABCDEFGH
1281682558127017192

 

В этом случае правильный ответ будет записан в виде: HBAF.

13.

При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 9 символов. Из соображений информационной безопасности каждый пароль должен содержать хотя бы 1 десятичную цифру, как прописные, так и строчные латинские буквы (в латинском алфавите 26 букв), а также не менее 1 символа из 6-символьного набора: «&», «#», «$», «*», «!», «@». В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт; это число одно и то же для всех пользователей.

Для хранения сведений о 20 пользователях потребовалось 500 байт. Сколько байт выделено для хранения дополнительных сведений об одном пользователе? В ответе запишите только целое число – количество байт.

Примечание. В латинском алфавите 26 букв.

14.

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

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

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

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

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

Цикл

 

ПОКА условие

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

КОНЕЦ ПОКА

 

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

 

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

 

ЕСЛИ условие

ТО команда1

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

КОНЕЦ ЕСЛИ

 

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

 

В конструкциях ПОКА и ЕСЛИ условие может содержать команды проверки, а также слова И, ИЛИ, НЕ, обозначающие логические операции. Если РОБОТ начнёт движение в сторону находящейся рядом с ним стены, то он разрушится и программа прервётся.

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

 

НАЧАЛО

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

ЕСЛИ снизу свободно

ТО

вниз

КОНЕЦ ЕСЛИ

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

ТО

вправо

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

15.

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

16.

Запись числа N в системе счисления с основанием 6 содержит две цифры, запись этого числа в системе счисления с основанием 5 содержит три цифры, а запись в системе счисления с основанием 11 заканчивается на 1.

Чему равно N?

17.

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

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

 

ЗапросНайдено страниц (в тысячах)
Канада & США277
США & (Канада | Мексика)417
Канада & США & Мексика106

 

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

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

18.

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

 

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

 

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

(М. В. Кузнецова)

19.

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

 

 

БейсикPython

 

FOR i = 1 TO 10

    A(i) = 5*i

NEXT i

FOR i = 1 TO 10

    k = A(i) - 2

    A(10-i+1) = k

NEXT i

 

 

for i in range(1, 11):

    A[i] = 5*i

for i in range(1, 11):

    k = A[i]-2

    A[10-i+1]=k

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

 

for i : = 1 to 10

    do A[i] : = 5*i;

for i : = 1 to 10 do begin

    k:=A[i]-2;

    A[10-i+1]:=k;

end;

 

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

    A[i] : = 5*i

кц

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

    k:=A[i]-2

    A[10-i+1]:=k

кц

 

Си++

 

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

    A[i] = 5*i;

}

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

    k=A[i]-2;

    A[10-i+1]=k;

}

 

 

 

Чему будут равны элементы этого массива?

 

1) 1 6 11 16 21 23 18 13 8 3

2) 3 8 13 18 23 28 33 38 43 48

3) 48 43 38 33 28 23 18 13 8 3

4) 1 6 11 16 21 26 31 36 41 46

20.

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

 

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

DIM X, A, B AS INTEGER

INPUT X

A = 0: B = 0

WHILE X > 0

    A = A + 2

    B = B + (X MOD 10)

    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 + 2;

            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 + 2;

        b = b + (x%10);

        x = x / 10;

    }

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

}

алг

нач

цел x, a, b

ввод x

a:=0; b:=0

нц пока x > 0

    a := a + 2

    b := b+mod(x,10)

    x := div(x,10)

кц

вывод a, нс, b

кон

Python

x = int(input())

a = 0

b = 0

while x > 0:

    a += 2

    b += (x % 10)

    x //= 10

print(a)

print(b)

 

21.

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

 

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

DIM А, В, Т, М, R AS INTEGER

А = -20: В = 20

М = A: R = F (А)

FOR Т = А ТО В

    IF F(T) < R THEN

        M = T

        R = F(T)

    END IF

NEXT T

PRINT M

FUNCTION F(x)

    F = 19 * (16 - x) * (16 - x) + 27

END FUNCTION

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

    Function F (x: integer):integer;

        begin

            F := 19 * (16 - x) * (16 - x) + 27;

        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) i

{

    return 19 * (16 - x) * (16 - x) + 27;

}

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, R, М

а := - 20; Ь := 20

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

нц для t от а до Ь

если F(t) < R

то

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

все

кц

вывод М

кон

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

нач

знач := 19 * (16 - х) * (16 - х) + 27

кон

Python

def f(x):

    return 19 * (16 - x) * (16 - x) + 27

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.

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


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

a = 30

b = 6

a = a / 5 * b

IF a > b THEN

    c = a - 4 * b

ELSE

    c = a + 4 * b

ENDIF

a : = 30;

b : = 6;

a : = a / 5 * b;

if a > b then

    c : = a - 4 * b

else

    c : = a + 4 * b;

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

a = 30

b = 6

a = a / 5 * b

if a > b

    c = a - 4 * b

else

    c = a + 4 * b

a : = 30

b : = 6

a : = a / 5 * b

если a > b

    то c : = a - 4 * b

иначе c : = a + 4 * b

все

Python

a = 30

b = 6

a = a / 5 * b

if a > b:

    c = a - 4 * b

else:

    c = a + 4 * b

 

23.

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

(¬ (x1 ≡ x2) ∨ ¬ (y1 ≡ y2) ) = 1

(¬ (x2 ≡ x3) ∨ ¬ (y2 ≡ y3) ) = 1

(¬ (x3 ≡ x4) ∨ ¬ (y3 ≡ y4) ) = 1

(¬ (x4 ≡ x5) ∨ ¬ (y4 ≡ y5) ) = 1

x5 ≡ y5 = 1

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

24.

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

 

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

DIM N AS LONG

INPUT N

min_digit = 0

WHILE N > 0

    digit = N MOD 10

    IF digit < min_digit THEN

        min_digit = digit

    END IF

    N = N \ 10

WEND

PRINT digit

END

var N: longint;

    digit, min_digit: integer;

begin

    readln(N);

    min_digit := 0;

    while N > 0 do

    begin

        digit := N mod 10;

        if digit < min_digit then

            min_digit := digit;

        N := N div 10;

    end;

    writeln(digit);

end.

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

#include <iostream>

using namespace std;

int main()

{

    long int N;

    int digit, min_digit;

    cin >> N;

    min_digit = 0;

    while (N > 0)

    {

        digit = N % 10;

        if (digit < min_digit)

            min_digit = digit;

        N = N / 10;

    }

    cout « digit « endl;

}

алг

нач

    цел N, digit, min_digit

    ввод N

    min_digit := 0

    нц пока N > 0

        digit := mod(N, 10)

        если digit < min_digit то

            min_digit := digit

        все

        N := div(N, 10)

    кц

    вывод digit

кон

Python

n = int(input())

min_digit = 0

while n > 0:

    digit = n % 10

    if digit < min_digit:

        min_digit = digit

    n //= 10

print(digit)

 

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

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

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

1) выпишите строку, в которой сделана ошибка;

2) укажите, как исправить ошибку, — приведите правильный вариант строки.

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

25.

Дан массив, содержащий 2014 положительных целых чисел. Напишите на одном из языков программирования программу, которая находит в этом массиве количество элементов, значение которых более чем в два раза превосходит значение предшествующего элемента. Например, для массива из 6 элементов, содержащего числа 2, 5, 10, 15, 40, 100, программа должна выдать ответ 3 (условию соответствуют элементы со значениями 5, 40 и 100). Программа должна вывести общее количество подходящих элементов, значения элементов выводить не нужно. Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать часть из описанных переменных.

 

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

N=2014

DIM A(N) AS INTEGER

DIM I, J, K AS INTEGER

FOR I = 1 TO N

INPUT A(I)

NEXT I

END

const

N=2014;

var

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

i, j, k: integer;

begin

for i:=1 to N do

readln(a[i]);

end.

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

#include <iostream>

using namespace std;

#define N 2014

int main(){

int a[N];

int i, j, k;

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

cin >> a[i];

}

алг

нач

цел N=2014

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

цел i, j, k

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

ввод a[i]

кц

кон

Python

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

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

# целочисленные переменные j, k

a = []

n = 2014

for i in range(0, n):

a.append(int(input()))

...

 

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

26.

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

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

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

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

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

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

27.

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

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

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

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

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

Входные данные

В первой строке задаётся N — количество точек в заданном множестве. Каждая из следующих строк содержит два целых числа — координаты очередной точки.

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

3

6 6

-8 8

9 7

Выходные данные

Если искомый треугольник существует, программа должна напечатать одно число: максимально возможную площадь треугольника, удовлетворяющего условиям. Если искомый треугольник не существует, программа должна напечатать сообщение: «Треугольник не существует».

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