Информатика. Вариант 10
Часть 1.
Ответами к заданиям 1–23 являются число или последовательность цифр. Запишите ответ справа от номера задания без пробелов, запятых и других дополнительных символов.
A | B | C | D | E | F | Z | |
A | 3 | 5 | 15 | ||||
B | 2 | 8 | |||||
C | 2 | 7 | |||||
D | 1 | 5 | 5 | ||||
E | 1 | 4 | |||||
F | 12 | 1 | 9 | ||||
Z |
Укажите длину (в километрах) кратчайшего маршрута из А в Z, который проходит через пять или более населённых пунктов. Пункты А и Z при подсчёте учитывайте. Два раза проходить через один пункт нельзя. В ответе укажите только число.
X | Y | Z | F |
0 | 0 | 1 | 1 |
1 | 1 | 0 | 1 |
0 | 1 | 0 | 1 |
Каким выражением может быть F?
1) (X v Y) ∧ (Z v 0)
2) (X ∧ Y) v (Z v 1)
3) X ∧ Y ∧ -Z
4) X v Y v -Z
Таблица 1 | ||
---|---|---|
ID | Фамилия | Пол |
20 | Лисица А.П. | ж |
76 | Сергеев А.В. | м |
30 | Четогоров Ф.К. | м |
24 | Королек М.В. | м |
54 | Злобкина С.В. | ж |
90 | Окатова Н.М. | ж |
18 | Китова Л.Б. | ж |
44 | Иноварова В.П. | ж |
19 | Катова Б.Д. | ж |
… | … | … |
Таблица 2 | |
---|---|
ID_родителя | ID_ребенка |
19 | 18 |
20 | 54 |
44 | 19 |
54 | 90 |
76 | 54 |
30 | 44 |
24 | 90 |
90 | 18 |
… | … |
1) Иноварова В.П.
2) Злобкина С.В.
3) Лисица А.П.
4) Королёк М.В
1) прибавь 2,
2) умножь на 3.
Первая из них увеличивает число на экране на 2, вторая утраивает его. Запишите порядок команд в программе преобразования числа 1 в число 35, содержащей не более 5 команд, указывая лишь номера команд. (Например, 21211 — это программа
умножь на 3
прибавь 2
умножь на 3
прибавь 2
прибавь 2,
которая преобразует число 1 в число 19.)
(Если таких программ более одной, то запишите любую из них.)
Какое целое число должно быть записано в ячейке С1, чтобы построенная после выполнения вычислений диаграмма по значениям диапазона ячеек А2:С2 соответствовала рисунку?
Известно, что все значения диапазона, по которым построена диаграмма, имеют один и тот же знак.
Компьютер Маши может начать ретрансляцию данных не раньше чем им будут получены первые 1024 Кбайт этих данных. Каков минимально возможный промежуток времени (в секундах) с момента начала скачивания Машей данных до полного их получения Андреем?
В ответе укажите только число, слово «секунд» или букву «с» добавлять не нужно.
Бейсик
DIM k, s, d AS INTEGER
INPUT d
s = 100
к = 1000
WHILE k > 0
s = s - 15
k = k - d
WEND
PRINT s
Паскаль
var k, s, d: integer;
begin
readln(d);
s := 100;
k := 1000;
while k > 0 do
begin
s := s - 15;
k : = k - d;
end;
write (s);
end.
Си
{
int k, s, d;
scanf("%d", &d);
s = 100;
к = 1000;
while (k > 0) {
s = s - 15;
k = k - d;
}
printf("%d", s);
}
Алгоритмический язык
нач
цел k, s, d
ввод d
s := 100
k := 1000
нц пока k > 0
s := s - 15
k := k - d
кц
вывод s
кон
Укажите, каким кодовым словом должна быть закодирована буква Е. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования. Если таких кодов несколько, укажите код с наименьшим числовым значением.
1. ААААА
2. ААААО
3. ААААУ
4. АААОА
Запишите слово, которое стоит под номером 242 от начала списка.
F(1) = 1
F(2) = 1
F(n) = 2F(n — 1) + F(n — 2), при n > 2
Чему равно значение функции F(5)?
В ответе запишите только натуральное число.
По заданным IP-адресу узла и маске определите адрес сети.
IP-адрес узла: 114.16.230.225
Маска: 255.255.252.0
При записи ответа выберите из приведённых в таблице чисел четыре элемента IP-адреса и запишите в нужном порядке соответствующие им буквы, без использования точек.
A | B | C | D | E | F | G | H |
255 | 228 | 0 | 225 | 16 | 114 | 252 | 230 |
Пример.
Пусть искомый IP-aдpec — 192.168.128.0 и дана таблица.
A | B | C | D | E | F | G | H |
128 | 168 | 255 | 8 | 127 | 0 | 17 | 192 |
В этом случае правильный ответ будет записан в виде HBAF.
Под хранение каждого такого пароля на компьютере отводится минимально возможное и одинаковое целое количество байтов, при этом используется посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством битов.
Определите объём памяти (в байтах), который занимает хранение 27 паролей. В ответе укажите только число.
Бейсик
а = 50
b = 100
b = 400 - (10 * а - 5 * b)
IF а > b THEN
с = b + 10 * а
ELSE
с = а + 2 * b
END IF
Паскаль
а := 50;
b := 100;
b := 400 - (10 * а - 5 * b) ;
if а > b then
с := b + 10 * а
else
с := а + 2 * b;
Си
а = 50;
b = 100;
b = 400 - (10 * а - 5 * b); if (а > b)
с = b + 10 * а;
else
с = а + 2 * b;
Алгоритмический язык
а := 50
b := 100
b := 400 - (10 * а - 5 * b)
если а > b
то с := b + 10 * а
иначе с := а + 2 * b
все
В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.
запрос | найдено страниц (в тыс) |
море | курорт | горы | 555 |
море | курорт | 200 |
горы & (море | курорт) | 115 |
Компьютер печатает количество страниц (в тысячах), которое будет найдено по следующему запросу:
Укажите целое число, которое напечатает компьютер.
Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.
Укажите наибольшую возможную длину промежутка А, для которого формула
(x ∈ А) → ((x ∈ P) ~ ¬(x ∈ Q))
тождественно истинна, то есть принимает значение 1 при любом значении переменной х.
Бейсик
s = 1 п = 10
FOR i = 1 ТО 3
s = s * A (i) * A(n - i + l)
NEXT i
Паскаль
s := 1; n := 10;
for i := 1 to 3 do begin
s := s * A[i] * A[n - i + 1]
end;
Си
s = 1; n = 10;
for (i = 1; i <= 3; i++)
s = s * A [i] * A [n - i +1];
Алгоритмический язык
s : = 1
n := 10
нц для i от 1 до 3
s := s * A[i] * A[n - i + 1]
кц
В начале выполнения этого фрагмента в массиве находились однозначные натуральные числа, кратные 3. Какое наименьшее значение может иметь переменная s после выполнения данной программы?
Бейсик
DIM X, L, М AS INTEGER
INPUT X
L = 0: М = 9
WHILE X > 0
L = L + 1
IF M > (X MOD 10) THEN
M = X MOD 10
END IF
X = X \ 10
WEND
PRINT L
PRINT M
Паскаль
var x, L, M: integer; begin
readln(x);
L := 0; M := 9;
while x > 0 do
begin
L := L + 1;
if M > (x mod 10) then
M := x mod 10;
x := x div 10;
end;
writeln(L); write(M);
end.
Си
#include<stdio.h>
void main()
{
int x, L, M; scanf("%d", &x);
L = 0; M = 9;
while (x > 0){
L = L + 1;
if M > x % 10 {
M = x % 10
}
x = x/10;
}
printf("%d\n%d", L, M);
}
Алгоритмический язык
алг
нач
цел х, L, М
ввод X
L := 0; М := 9
нц пока х > 0
L : = L + 1
если М > mcd(x, 10) то
М := mod(x, 10)
все
х := div(x, 10)
кц
вывод L, нс, М
кон
Бейсик
DIM А, В, Т, М, R, Н AS INTEGER
INPUT Н
А = -20: В = 40
М = A: R = F (Н, А)
FOR Т = А ТО В
IF F (Н, Т) < R THEN
М = Т
R = F (Н, Т)
END IF
NEXT Т
PRINT М
FUNCTION F (Н, x)
F = (x - 10) * (x - H)
END FUNCTION
Паскаль
var a, b, t, M, R, H: integer;
function F(H, x: integer): integer;
begin
F := (x - 10) * (x - H) ;
end;
begin
readln(H);
a := -20; b := 40;
M := a; R : = F (H, a) ;
for t := a to b do begin
if (F(H, t) < R) then begin
M := t;
R := F(H, t)
end
end;
write(M)
end.
Си
#include<stdio.h>
int F(int H, int x)
{
return (x - 10) * (x - H);
}
void main()
{
int a, b, t, M, R, H;
scant("%d", &H);
a = -20; b = 40;
M = a; R = F (H, a);
for (t = a; t <= b; t++){
if (F (H, t) < R) {
M = t; R = F (H, t);
}
}
printf("%d", M);
}
Алгоритмический язык
нач
цел a, b, t, R, M, H
ввод H
a := -20; b := 40
M := a; R := F(H, a)
нц для t от а до b
если F(H, t) < R
то
M := t; R := F(H, t)
все
кц
вывод M
кон
алг цел F(цел Н, х)
нач
знач := (х - 10) * (х - Н)
кон
прибавь 1,
умножь на 2.
Первая из них увеличивает число на экране на 1, вторая умножает его на 2. Программа для Увеличителя — это последовательность команд.
Сколько есть программ, которые число 3 преобразуют в число 16?
(¬(x2 ~ x3) v (x4 ~ x5)) v ((x2 ~ x3) → (x4 ~ x5)) = 0
(¬(x6 ~ x7) v (x8 ~ x9)) v ((x6 ~ x7) → (x8 ~ x9)) = 0
(¬(x2 ~ x3) v (x8 ~ x9)) v ((x2 ~ x3) → (x8 ~ x9)) = 0
(¬(x6 ~ x7) v (x4 ~ x5)) v ((x6 ~ x7) → (x4 ~ x5)) = 0
((x10 ~ x1) v x1= 1
В ответе не нужно перечислять все различные наборы значений x1, х2, … x9, х10, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Часть 2.
Запишите сначала номер задания (24, 27 и т. д.), затем полное решение. Ответы записывайте чётко и разборчиво.
Бейсик
DIM N AS LONG
DIM product AS LONG
INPUT N
product = 1
WHILE N > 0
digit = N MOD 10
digit = product * digit
N = N \ 10
WEND
PRINT digit
END
Паскаль
var N, product: longint;
digit: integer;
begin
readln(N);
product := 1;
while N > 0 do
begin
digit := N mod 10;
digit := product * digit;
N := N div 10;
end;
writeln(digit);
end.
Си
#include <stdio.h>
int main()
{
long int N, product;
int digit;
scant("%ld", &N);
product = 1;
while (N > 0)
{
digit = N % 10;
digit = product * digit;
N = N / 10;
}
printf("%d", digit);
}
Алгоритмический язык
алг
нач
цел N, digit, product
ввод N
product := 1
нц пока N > 0
digit := mod(N, 10)
digit := product * digit
N := div(N, 10)
кц
вывод digit
кон
Последовательно выполните следующее.
1. Напишите, что выведет эта программа при вводе числа 325.
2. Найдите все ошибки в этой программе (их может быть одна или несколько). Для каждой ошибки:
1) выпишите строку, в которой сделана ошибка;
2) укажите, как исправить ошибку, — приведите правильный вариант строки.
Обратите внимание, что требуется найти ошибки в имеющейся программе, а не написать свою, возможно, использующую другой алгоритм решения. Исправление ошибки должно затрагивать только строку, в которой находится ошибка.
Содержание верного ответа
Решение использует запись программы на Паскале. Допускается использование программы на трёх других языках программирования.
1. Программа выведет число 3.
2. Первая ошибка. Неверное вычисление произведения в цикле.
Строка с ошибкой:
digit := product * digit;
Исправление:
product := product * digit;
3. Вторая ошибка. Программа выводит значение переменной digit, а не product. Строка с ошибкой:
writeln(digit);
Возможное исправление:
writeln(product);
Исходные данные объявлены так, как показано ниже на примерах для некоторых языков программирования и естественного языка. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать некоторые из описанных переменных.
Бейсик
N = 30
DIM A(N) AS INTEGER
DIM, I, J, MAX AS INTEGER
FOR I = 1 TO N
INPUT A(I)
NEXT I
...
END
Паскаль
const
N = 30;
var
a: array [1..N] of integer;
i, j, max: integer;
begin
for i:= 1 to N do
readln(a[i]);
...
end.
Си
#include <stdio.h>
#define N 30
void main () {
int a[N];
int i, j, max;
for (i = 0; i < N; i++)
scanf ("%d", &a[i]);
...
}
Алгоритмический язык
алг
нац
цел N = 30
целтаб а[1:N]
цел i, j, max
нц для i от 1 до N
ввода a[i]
кц
...
кон
Естественный язык
Объявляем массив А из 30 элементов.
Объявляем целочисленные переменные I, J, MAX.
В цикле от 1 до 30 вводим элементы массива А с 1-го по 30-й.
...
В качестве ответа Вам необходимо привести фрагмент программы (или описание алгоритма на естественном языке), который должен находиться на месте многоточия. Вы можете записать решение также на другом языке программирования (укажите название и используемую версию языка программирования, например Free Pascal 2.4) или в виде блок-схемы. В этом случае Вы должны использовать те же самые исходные данные и переменные, какие были предложены в условии (например, в образце, записанном на естественном языке).
Содержание верного ответа
На языке Паскаль
шах := -1001; for i := 1 to N do
if (a[i] < 0) and ((-1 * a[i]) mod 10 <> 3) and (a[i] > max) then
max := a[i];
if max > -1001 then writeln(max) else writeln('He найдено');
На алгоритмическом языке
max := -1001
нц для i от 1 до N
если a[i] < 0 и mod(-l * a[i], 10) о 3 и a[i] > max
то
max := a[i]
все
кц
если max > -1001
то
вывод max
иначе
вывод "He найдено"
все
На языке Бейсик
МАХ = -1001 FOR I = 1 ТО N
IF, А (I) < 0 AND (-1 * A(I) ) MOD 10 О 3 AND A(I) > MAX THEN
МАХ = А(I)
END IF NEXT I
IF MAX > -1001 THEN
PRINT MAX
ELSE
PRINT "He найдено"
END IF
На языке Си
max = -1001;
for (i = 0; i < N; i++)
if (a[i] < 0 && (-1 * a[i]) % 10 != 3 && a[i] > max)
max = a[i];
if (max > -1001)
printf("%d", max);
else
printf("Не найдено");
Игра завершается в тот момент, когда количество камней в куче становится не менее 35.
Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 35 или больше камней.
В начальный момент в куче было S камней, 1 ≤ S ≤ 34.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Выполните следующие задания. Во всех случаях обосновывайте свой ответ.
Задание 1
а) Укажите все такие значения числа S, при которых Петя может выиграть в один ход. Обоснуйте, что найдены все нужные значения S, и укажите выигрывающий ход для каждого указанного значения S.
б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.
Задание 2
Укажите два таких значения S, при которых у Пети есть выигрышная стратегия, причём (а) Петя не может выиграть за один ход и (б) Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Для каждого указанного значения S опишите выигрышную стратегию Пети.
Задание 3
Укажите значение S, при котором:
— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и
— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Для указанного значения S опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы). На рисунке на рёбрах дерева указывайте, кто делает ход; в узлах — количество камней в куче.
Содержание верного ответа
Задание 1.
а) Петя может выиграть в один ход, если S = 15, … 34. Во всех этих случаях достаточно добавить 20 камней, после чего их количество станет больше 34, и игра закончится.
При значениях S, меньших 15, за один ход нельзя получить кучу, количество камней в которой будет не менее 35.
б) Ваня может выиграть первым ходом (при любой игре Пети), если S = 14. Тогда после первого хода Пети в куче будет 15, 17 или 34 камня. После этого Ваня добавляет 20 камней и выигрывает в один ход.
Задание 2.
При S = 11 или S = 13 у Пети есть выигрышная стратегия, позволяющая ему выиграть своим вторым ходом. В этих случаях Петя не может выиграть первым ходом (см. п. 1а)). Однако он может получить кучу из 14 камней, добавив в кучу один камень (при S = 13) или три камня (при S = 11). После этого хода Петя попадает в ситуацию, разобранную в п. 16) для Вани, то есть у игрока, делающего следующий ход (у Вани), нет хода, сразу приводящего его к выигрышу, а у Пети выигрышный ход «добавить 20 камней» есть независимо от того, какой ход сделал Ваня.
Задание 3.
При S = 10 у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом. После первого хода Пети в куче будет 11, 13 или 30 камней. Если в куче станет 30 камней, то Ваня добавит 20 камней и выиграет своим первым ходом. Если после первого хода Пети в куче оказалось 11 или 13 камней, то Ваня попадает в ситуацию, разобранную в п. 2 для Пети, и у него есть выигрышная стратегия, позволяющая ему выиграть своим вторым ходом.
В таблице представлено дерево возможных партий при описанной выигрышной стратегии Вани. На рисунке это же дерево изображено в графическом виде. Заключительные позиции, в которых выигрывает Ваня, подчёркнуты. Приведены все возможные ходы Пети и ходы, отвечающие выигрышной стратегии Вани.
Вам предлагается написать эффективную, в том числе по используемой памяти, программу, которая будет выводить третье по величине (считая от минимума) значение измерения. Если несколько измерений имеют одинаковые значения, то они учитываются как одно измерение. Если искомого значения не существует (например, когда все значения измерений равны), то нужно вывести символ «#». Следует учитывать, что количество измерений может быть очень велико.
Перед текстом программы кратко опишите используемый Вами алгоритм решения задачи. На вход программе в первой строке подаётся общее количество N значений измерений. В каждой из последующих N строк записано целое число. Гарантируется, что N ≥ 1, то есть всегда имеется хотя бы одно измерение.
Пример входных данных:
5
100
10
100
10
100
Пример выходных данных для приведённого выше примера входных данных:
#
Содержание верного ответа
Программа последовательно читает значения измерений, обновляя при необходимости три наименьших значения. После цикла печатается результат.
Баллы начисляются только за программу, которая решает задачу хотя бы для одного частного случая. Ниже приведёны примеры решения задания на языках Паскаль, Бейсик и алгоритмическом языке. Допускаются решения, записанные на других языках программирования
Пример правильной и эффективной программы на языке Бейсик
DIM N, Min, Next_Min, Next_Next_Min, i, s AS Integer
Min = 1001: Next_Min = 1001: Next_Next_Min = 1001
INPUT N
REM Считываем количество измерений
FOR i = 1 to N
INPUT s
REM Считали очередное значение
IF s < Min THEN
REM обновление всех трёх минимумов
Next_Next_Min = Next_Min: Next_Min = Min: Min = s
ELSE
IF (s < Next_Min) AND (s <> Min) THEN
REM обновление 2-го и 3-го минимума
Next_Next_Min = Next_Min Next_Min = s
ELSE
IF (s < Next_Next_Min) AND (s <> Min) AND (s <> Next_Min) THEN
REM обновление 3-го минимума
Next_Next_Min = s
END IF
END IF
END IF
NEXT i
REM Вывод результата
IF Next_Next_Min < 1001 THEN
PRINT Next_Next_Min
ELSE
PRINT '#'
END IF
Пример правильной и эффективной программы на языке Паскаль
var N, Min, Next_Min, Next_Next_Min, i, s: integer;
begin
Min := 1001; Next_Min := 1001;
Next_Next_Min := 1001;
ReadLn (N); {Считываем количество измерений}
for i := 1 to N do
begin
ReadLn (s); {Считали очередное значение}
if s < Min then
{обновление всех трёх минимумов}
begin
Next_Next_Min := Next_Min;
Next_Min := Min;
Min := s;
end
else if (s < Next_Min) and (s <> Min) then
begin
{обновление 2-го и 3-го минимума}
Next_Next_Min := Next_Min;
Next_Min := s;
end
else if (s < Next_Next_Min) and (s <> Min) and (s <> Next_Min) then
{обновление 3-го минимума}
Next_Next_Min := s;
end; {Вывод результата}
if Next_Next_Min < 1001 then
WriteLn (Next_Next_Min)
else WriteLn (’#’);
end.