Информатика. Вариант 11

0

Часть 1.

Ответами к заданиям 1–23 являются число или последовательность цифр. Запишите ответ справа от номера задания без пробелов, запятых и других дополнительных символов.

1. Сколько единиц в двоичной записи шестнадцатеричного числа E1A016?
2. Между населёнными пунктами А, Б, В, Г, Д, Е и К построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

634 2 0 - Информатика. Вариант 11

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

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

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

634 3 0 - Информатика. Вариант 11

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

Пример. Если бы функция была задана выражением ¬x \/ y, зависящим от двух переменных: x и y, и был приведён фрагмент её таблицы истинности, содержащий все наборы аргументов, при которых функция F истинна.

634 3 1 - Информатика. Вариант 11

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

4. Ниже представлены две таблицы из базы данных. Каждая строка таблицы 2 содержит информацию о ребёнке и об одном из его родителей. Информация представлена значением поля ID в соответствующей строке таблицы 1. Определите на основании приведённых данных суммарное число дочерей и внучек Коренных А.С.
Таблица 1
ID Фамилия_И.О. Пол
1171 Шемко Н.А. Ж
2242 Шемко И.М. М
2251 Шемко М.И. М
2262 Шемко М.М. М
3342 Галиани А.И. Ж
3351 Галиани В.С. Ж
3371 Галиани С.С. М
4442 Коренных А.С. М
4451 Коренных Л.А. М
4462 Воевода О.С. М
4482 Воевода М.О. М
5542 Бой А.М. Ж
7751 Медечко М.А. Ж
Таблица 2
ID_родителя ID_ребенка
1171 3371
2242 2251
2242 3342
2251 2262
2251 5542
3342 3351
3342 4462
3371 3351
3371 4462
4442 2251
4442 3342
7751 2262
7751 5542
5. По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В используются такие кодовые слова: А – 0; Б – 110; В – 100.

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

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

6. У исполнителя Аккорд-4 две команды, которым присвоены номера:

1. вычти 1

2. умножь на 4

Выполняя первую из них, Аккорд-4 вычитает из числа на экране 1, а выполняя вторую, умножает это число на 4.

Запишите порядок команд в программе, которая содержит не более пяти команд и преобразует число 5 в число 62. Если таких программ более одной, то запишите любую из них.

В ответе указывайте лишь номера команд. Так, для программы

умножь на 4

вычти 1

вычти 1

нужно написать: 211. Эта программа преобразует, например, число 7 в число 26.

7. Дан фрагмент электронной таблицы.
A B C
1 4 10
2 =(C1–5)/(4*A1) =1/(C1+1) =3/(2*C1+B1)

634 7 0 - Информатика. Вариант 11

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

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

Бейсик

DIM N, S AS INTEGER
N = 0
S = 0
WHILE S <= 251
    S = S + 25
N = N + 1
WEND
PRINT N

Python

n = 0
s = 0
while s <= 251:
s = s + 25
n = n + 1
print(n)

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

алг
нач
цел n, s
n := 0
s := 0
     нц пока s <= 251
     s := s + 25
     n := n + 1
     кц
     вывод n
кон

Паскаль

var n, s: integer;
begin
     n := 0;
s := 0;
while s <= 251 do
begin
s := s + 25;
n := n + 1
end;
write(n)
end.

Си

#include<stdio.h>
void main()
{
int n, s;
     n = 0;
     s = 0;
while (s <= 251)
     {
s = s + 25;
     n = n + 1;
     }
     printf("%d", n);
}
9. Какой минимальный объём памяти (в Кбайт) нужно зарезервировать, чтобы можно было сохранить любое растровое изображение размером 320×640 пикселей при условии, что в изображении могут использоваться 256 различных цветов? В ответе запишите только целое число, единицу измерения писать не нужно.
10. Некоторый алфавит содержит три различные буквы. Сколько пятибуквенных слов можно составить из букв данного алфавита (буквы в слове могут повторяться)?
11. Ниже на пяти языках программирования записан рекурсивный алгоритм F.

Бейсик

SUB F(n)
IF n > 0 THEN
PRINT "*"
        F(n - 1)
F(n \ 3)
END IF
END SUB

Python

def F(n):
     if n > 0:
         print("*")
         F(n - 1)
F(n // 3)

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

алг F(цел n)
нач
    если n > 0 то
        вывод "*"
F(n - 1)
F(div(n, 3))
    все
кон

Паскаль

procedure F(n: integer);
begin
if n > 0 then
begin
writeln('*');
F(n - 1);
F(n div 3)
end
end

Си

void F(int n)
{
if (n > 0)
{
printf("*");
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-адресом 115.181.92.48 адрес сети равен 115.181.80.0. Чему равно значение третьего слева байта маски? Ответ запишите в виде десятичного числа.

13. При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 9 символов и содержащий только символы из 26-символьного набора прописных латинских букв. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт; это число одно и то же для всех пользователей. Для хранения сведений о 20 пользователях потребовалось 400 байт. Сколько байт выделено для хранения дополнительных сведений об одном пользователе? В ответе запишите только целое число – количество байт.
14. Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости, включает в себя 4 команды-приказа и 4 команды проверки условия. Команды-приказы:
вверх | вниз | влево | вправо

При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ^, вниз v, влево . Если РОБОТ начнёт движение в сторону находящейся рядом с ним стены, то он разрушится, и программа прервётся. Другие 4 команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ:

сверху свободно | снизу свободно | слева свободно | справа свободно
Цикл
    ПОКА условие
        последовательность команд
    КОНЕЦ ЦИКЛА
выполняется, пока условие истинно.
В конструкции
    ЕСЛИ условие
        ТО команда1
        ИНАЧЕ команда2
КОНЕЦ ЕСЛИ

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

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

НАЧАЛО
ПОКА слева свободно ИЛИ сверху свободно
    ЕСЛИ сверху свободно
        ТО вверх
        ИНАЧЕ влево
    КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

634 14 0 - Информатика. Вариант 11

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

Сколько существует различных путей из города А в город Л?

634 15 0 - Информатика. Вариант 11

16. Сколько единиц содержится в двоичной записи значения выражения: 42013 + 22012 – 16?
17. В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «634 17 0 - Информатика. Вариант 11», а для обозначения логической операции «И» – символ «&». В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.
Запрос Найдено страниц (в тысячах)
Мадрид & Берлин 245
Мадрид & Берлин & Париж 120
Мадрид & Париж 235

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

Мадрид & (Берлин 634 17 0 - Информатика. Вариант 11 Париж)

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

18. На числовой прямой даны два отрезка: P = [20, 50] и Q = [30,65]. Отрезок A таков, что формула

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

истинна при любом значении переменной x.

Какова наименьшая возможная длина отрезка A?

19. В программе используется одномерный целочисленный массив A с индексами от 0 до 9. Значения элементов равны 8, 4, 3, 0, 7, 2, 1, 5, 9, 6 соответственно, т.е. A[0] = 8, A[1] = 4 и т.д. Определите значение переменной s после выполнения следующего фрагмента программы (записанного ниже на разных языках программирования).

Бейсик

s = 0
FOR j = 0 TO 9
     IF A(j) <=4 THEN
s = j
ENDIF
NEXT j

Python

s = 0
for j in range(10):
     if A[j] <4:
s = j

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

s := 0
нц для j от 0 до 9
    если A[j] <= 4 то
s := j
    все
кц

Паскаль

s := 0;
for j := 0 to 9 do
if A[j] <= 4 then
s := j;

Си

s = 0;
for (j = 0; j <= 9; j++)
if (A[j] <= 4)
s = j;
20. Ниже на пяти языках программирования записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа: a и b. Укажите наибольшее из таких чисел x, при вводе которых алгоритм печатает сначала 2, а потом 9.

Бейсик

DIM X, A, B AS INTEGER
INPUT X
A = 0: B = 0
WHILE X > 0
A = A+1
B = B+(X MOD 10)
X = X \ 10
WEND
PRINT A
PRINT B

Python

x = int(input())
a = 0
b = 0
while x > 0:
a = a + 1
b = b + (x % 10)
x = x // 10
print (a)
print (b)

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

алг
нач
    цел x, a, b
    ввод x
a := 0; b := 0
    нц пока x>0
a := a+1
b := b+mod(x,10)
x := div(x,10)
    кц
    вывод a, нс, b
кон

Паскаль

var x, a, b: integer;
begin
readln(x);
a := 0; b := 0;
while x>0 do
begin
a := a+1;
b := b+(x mod 10);
x := x div 10
end;
writeln(a); write(b)
end.

Си

#include<stdio.h>
void main()
{
int x, a, b;
scanf("%d", &x);
a = 0; b = 0;
while (x>0) {
a = a+1;
b = b+(x%10);
x = x/10;
}
printf("%d\n%d", a, b);
}
21.Напишите в ответе число, которое будет напечатано в результате выполнения следующего алгоритма (для Вашего удобства алгоритм представлен на пяти языках программирования).

Бейсик

DIM A, B, T, M, R AS INTEGER
A = 5: B = 35
M = A: R = F(A)
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 = 3*(x-1)*(x-1)+37
END FUNCTION

Python

def F(x):
return 3*(x-1)*(x-1)+37

a = 5
b = 35
M = a
R = F(a)
for t in range(a, b+1):
if F(t) > R:
M = t
R = F(t)
print (M)

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

алг
нач
    цел a, b, t, M, R
a := 5; b := 35
M := a; R := F(a)
    нц для t от a до b
        если F(t) > R
            то
M := t; R := F(t)
        все
    кц
    вывод M
кон

алг цел F(цел x)
нач
    знач := 3*(x-1)*(x-1)+37
кон

Паскаль

var a,b,t,M,R :integer;
Function F(x:integer):integer;
begin
F := 3*(x-1)*(x-1)+37
end;

    begin
a := 5; b := 35;
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<stdio.h>
int F(int x)
{
return 3*(x-1)*(x-1)+37;
}

void main()
{
int a, b, t, M, R;
a = 5; b = 35;
M = a; R = F(a);
for (t = a; t <= b; t++) {
if (F(t) > R) {
M = t; R = F(t);
}
}
printf("%d", M);
}
22. Исполнитель Вычитатель преобразует число, которое записано на экране. У исполнителя

Вычитатель две команды, которым присвоены номера:

1. Вычти 2

2. Вычти 5

Первая из них уменьшает число на экране на 2, вторая уменьшает его на 5.

Программа для Вычитателя – это последовательность команд.

Сколько есть программ, которые число 22 преобразуют в число 2?

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

(x1 → x2) /\ (x2 → x3) /\ (x3 → x4) /\ (x4 → x5) /\ (x5 → x6) = 1

(y1 → y2) /\ (y2 → y3) /\ (y3 → y4) /\ (y4 → y5) /\ (y5 → y6) = 1

(¬x1 \/ y1) /\ (¬x2 \/ y2) /\ (¬x3 \/ y3) /\ (¬ x4 \/ y4) /\ (¬x5 \/ y5) /\ (¬x6 \/ y6) = 1

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

Часть 2.

Запишите сначала номер задания (24, 27 и т. д.), затем полное решение. Ответы записывайте чётко и разборчиво.

24. На обработку поступает последовательность из четырёх неотрицательных целых чисел (некоторые числа могут быть одинаковыми). Нужно написать программу, которая выводит на экран количество чётных чисел в исходной последовательности и максимальное чётное число. Если чётных чисел нет, требуется на экран вывести «NO». Известно, что вводимые числа не превышают 1000. Программист написал программу неправильно. Ниже эта написанная им программа для Вашего удобства приведена на пяти языках программирования.

Бейсик

CONST n = 4
count = 0
maximum = 1000
FOR I = 1 TO n
INPUT x
IF x mod 2 = 0 THEN
count = count + 1
IF x > maximum THEN
maximum = I
END IF
END IF
NEXT I
IF count > 0 THEN
PRINT count
PRINT maximum
ELSE
PRINT "NO"
END IF

Python

n = 4
count = 0
maximum = 1000
for i in range (1, n+1):
x = int(input())
if x % 2 == 0:
count += 1
if x > maximum:
maximum = i
if count > 0:
print (count)
print (maximum)
else:
print ("NO")

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

алг
нач
    цел n = 4
    цел i, x
    цел maximum, count
count := 0
maximum := 1000
    нц для i от 1 до n
        ввод x
        если mod(x, 2) = 0 то
count := count + 1
            если x > maximum то
maximum := i
            все
        все
    кц
    если count > 0 то
        вывод count, нс
        вывод maximum
    иначе
        вывод "NO"
    все
кон

Паскаль

const n = 4;
var i, x: integer;
var maximum, count: integer;
begin
count :0;
maximum :1000;
for i :1 to n do
begin
read(x);
if x mod 2 = 0 then
begin
count := count + 1;
             if x > maximum then
maximum := i
end
end;
if count > 0 then
begin
writeln(count);
writeln(maximum)
end
else
writeln('NO')
end.

Си

#include <stdio.h>
#define n 4

void main(void)
{
int i, x;
int maximum, count;
count = 0;
maximum = 1000;
for (i = 1; i <= n; i++)
{
scanf("%d",&x);
         if (x % 2 == 0)
{
count++;
if (x > maximum)
maximum = i;
         }
}
     if (count > 0)
{
printf("%d\n", count);
     printf("%d\n", maximum);
}
else
printf("NO\n");
}

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

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

2 9 4 3

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

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

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

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

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

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

Примечание: 0 – чётное число.

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

Например, для массива из пяти элементов: 16 2 14 91 21 – ответ: 2. Исходные данные объявлены так, как показано ниже на примерах для некоторых языков программирования и естественного языка. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать некоторые из описанных переменных.

Бейсик

CONST N = 50
DIM A (1 TO N) AS INTEGER
DIM I, J, K, AS INTEGER

FOR I = 1 TO N
INPUT A(I)
NEXT I
...

END

Python

//допускается также использовать
//две целочисленные переменные j и k
a = []
n = 50
for i in range(0, n):
a.append(int(input()))
...

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

алг
нач
    цел N = 50
    целтаб a[1:N]
    цел i, j, k
    нц для i от 1 до N
        ввод a[i]
    кц
...

кон

Паскаль

const
N = 50;
var
a: array [1..N] of integer;
i, j, k: integer;
begin
for i := 1 to N do
readln(a[i]);
...

end.

Си

#include <stdio.h>
#define N 50
int main() {
int a[N];
int i, j, k;
for (i = 0; i<N; i++)
scanf("%d", &a[i]);
...

return 0;
}

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

Объявляем массив A из 50 элементов.
Объявляем целочисленные переменные I, J, K.
В цикле от 1 до 50 вводим элементы массива
A с 1-го по 50-й.
…

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

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

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

В начальный момент в куче было S камней; 1 ≤ S ≤ 27.

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

Выполните следующие задания. Во всех случаях обосновывайте свой ответ.

Задание 1

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

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

Задание 2

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

– Петя не может выиграть за один ход;

– Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

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

Задание 3

Укажите значение S, при котором одновременно выполняются два условия:

– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Для указанного значения S опишите выигрышную стратегию Вани.

Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы). На рисунке на рёбрах дерева указывайте, кто делает ход; в узлах – количество камней в позиции.

27. По каналу связи передаётся последовательность положительных целых чисел, все числа не превышают 1000. Количество чисел известно, но может быть очень велико. Затем передаётся контрольное значение последовательности – наименьшее число R, удовлетворяющее следующимусловиям:

1) R является произведением двух различных переданных элементов последовательности («различные» означает, что не рассматриваются квадраты переданных чисел, произведения различных элементов последовательности, равных по величине, допускаются);

2) R кратно 6.

Если такого числа R нет, то контрольное значение полагается равным 0.

В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены.

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

Программа должна напечатать отчёт по следующей форме:

Вычисленное контрольное значение: …<br />Контроль пройден (или – Контроль не пройден)

Перед текстом программы кратко опишите используемый Вами алгоритм решения.

На вход программе в первой строке подаётся количество чисел N; в программе можно считать, что 2 ≤ N ≤ 10 000. В каждой из последующих N строк записано одно натуральное число, не превышающее 1000.

В последней строке записано контрольное значение – натуральное число, не превышающее 1 000 000.

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

6

30

6

5

3

4

300

12

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

Вычисленное контрольное значение: 12

Контроль пройден

Оставьте ответ

Ваш электронный адрес не будет опубликован.