Информатика. Вариант 3
Часть 1.
Ответами к заданиям 1–23 являются число или последовательность цифр. Запишите ответ справа от номера задания без пробелов, запятых и других дополнительных символов.
A | B | C | D | E | F | |
A | 5 | 3 | ||||
B | 2 | 4 | ||||
C | 2 | 2 | 1 | |||
D | 5 | 2 | 1 | |||
E | 3 | 1 | 8 | |||
F | 4 | 1 | 8 |
Определите длину кратчайшего пути между пунктами А и F (при условии, что передвигаться можно только по построенным дорогам). В ответе укажите только число.
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | F |
1 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 1 |
1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
Каким выражением может быть F?
1) x1 ∧ x2 ∧ x3 ∧ x4 ∧ x5 ∧ x6 ∧ ¬x7 ∧ ¬x8
2) x1 ∧ x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ x6 ∧ ¬x7 ∧ ¬x8
3) ¬x1 v ¬x2 v x3 v x4 v x5 v ¬x6 v x7 v ¬x8
4) ¬x1 v ¬x2 v ¬x3 v x4 v x5 v x6 v x7 v x8
Символ «?» (вопросительный знак) означает ровно один произвольный символ. Символ «*» (звёздочка) означает любую последовательность символов произвольной длины, в том числе «*» может задавать и пустую последовательность.
В каталоге находятся шесть файлов:
sorry.docx rock.docx or.doc ork.dat port.doc ok.dat
Ниже представлено восемь масок. Сколько из них таких, которым соответствуют ровно четыре файла из данного каталога?
*o?*.d?? | ?o*?.d* | *or*.doc? | ?or??.d* |
*r*.doc* | *o.?d* | *o?*.d?c* | *.* |
1) 1
2) 2
3) 3
4) 4
1. Складываются первая и вторая, затем вторая и третья, а далее третья и четвёртая цифры исходного числа.
2. Полученные три числа записываются друг за другом в порядке возрастания (без разделителей).
Пример. Исходное число: 7531. Суммы: 7 + 5 = 12; 5 + 3 = 8; 3 + 1 = 4. Результат: 4812.
Укажите наибольшее число, в результате обработки которого автомат выдаст число 2512.
A | B | C | D | |
1 | 1 | 3 | 7 | 9 |
2 | 13 | 15 | 19 | |
3 | 23 | 25 | 27 | =$B3*2+C$4 |
4 | 33 | 17 | 11 | 37 |
5 | 21 | 31 | 33 | 41 |
Формулу из ячейки D3 скопировали в ячейку С2 так, что числовое значение ячейки С2 стало отличаться от числового значения ячейки D3. Каково стало числовое значение ячейки С2?
Бейсик
DIM k, s AS INTEGER
s = 0
к = 0
WHILE s <= 2048
s = s + 64
к = к + 1
WEND
PRINT к
Алгоритмический язык
нач
цел k, s
s : = 0
k := 0
нц пока s <= 2048
s := s + 64
k := k + 1
кц
вывод k
KOH
Паскаль
var k, s : integer;
begin
s : = 0 ;
k : = 0;
while s <= 2048 do
begin
s : = s + 64;
k : = k + 1;
end;
write(k);
end.
Си
{
int к, s;
s = 0;
к = 0;
while (s <= 2048) {
s = s + 64;
к = к + 1;
}
printf("%d", k);
}
Укажите, каким кодовым словом должна быть закодирована буква Д. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Бейсик
SUB F(n)
PRINT n
IF n <= 5 THEN
F(n + 2)
F(n + 3)
END IF
END SUB
Алгоритмический язык
алг F(цел n)
нач
вывод n, нс
если n <= 5 то
F(n + 2)
F (n + 3)
все
кон
Паскаль
procedure F(n: integer);
begin
writeln (n);
if n <= 5 then
begin
F(n + 2);
F (n + 3)
end
end
Си
void F(int n)
{
printf("%d\n", n);
if (n <= 5)
{
F(n + 2) ;
F(n + 3) ;
}
}
Чему равна сумма всех чисел, напечатанных на экране при выполнении вызова F(2)?
Например, если IP-адрес узла равен 131.111.255.131, а маска равна 255.255.192.0, то адрес подсети равен 131.111. 192.0.
Для узла с IP-адресом 175.182.179.170 адрес сети равен 175.182.160.0. Чему равен третий слева байт маски? Ответ запишите в виде десятичного числа.
Под хранение каждого такого пароля на компьютере отводится минимально возможное и одинаковое целое количество байтов, при этом используется посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством битов.
Определите объём памяти (в байтах), который занимает хранение 80 паролей. В ответе укажите только число.
Бейсик
INPUT а
b = 30
а = - а - 3 * b
IF а < b THEN
с = b + 45
ELSE
с = b - 50
END IF
Алгоритмический язык
ввод a
b := 30
a : = - a - 3 * b
если a < b
то c := b + 45
иначе c := b - 50
все
Паскаль
readln(a);
b := 30;
a:= - a - 3 * b;
if a < b then
c := b + 45
else
c := b - 50;
Си
scanf("%d", &а);
b = 30;
a= - a - 3 * b;
if (a < b)
c = b + 45;
else
c = b - 50;
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей, ведущих из города А в город М и проходящих через город Г?
111x + 2 — 568 = 1110
Определите значение х. Ответ запишите в десятичной системе счисления.
В таблице приведёны запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.
Запрос | Найдено страниц (в тыс) |
(математика & физика) | информатика | 800 |
математика & физика & информатика | 70 |
информатика | 700 |
Компьютер печатает количество страниц (в тысячах), которое будет найдено по следующему запросу:
Укажите целое число, которое напечатает компьютер.
Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.
Укажите наибольшую возможную длину отрезка А, для которого формула
((х ∈ Р) → (х ∈ Q)) → ¬(х ∈ А)
тождественно истинна, то есть принимает значение 1 при любом значении переменной х.
Бейсик
s = 0
n = 10
FOR i = 0 ТО n - 1
s = s + A (i) +А(i+1)
NEXT i
Алгоритмический язык
s : = 0
n : = 10
нц для i от 0 до n - 1
s := s + A[i] + A[i+1]
кц
Паскаль
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 после выполнения данной программы?
Бейсик
DIM X, L, М AS INTEGER
INPUT X
L = 0: М = 0
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
Алгоритмический язык
алг
нач
цел х, L, М
ввод X
L := 0; М := 0
нц пока х > 0
L := L + 1
если М < mod(х,10) то
М := mod(х,10)
все
х := div(х,10)
кц
вывод L, нс, М
кон
Паскаль
var x, L, M: integer;
begin
readln(x);
L := 0; M := 0;
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 = 0;
while (x > 0) {
L = L + 1;
if M < x % 10 {
M = x % 10
}
x /= 10;
}
printf("%d\n%d", L, M);
}
Бейсик
DIM А, В, Т, М, R AS INTEGER
А = -20: В = 20
М = A: R = F(А)
FOR Т = А ТО В
IF F(Т) < R THEN
М = Т
R = F (Т)
END IF
NEXT Т
PRINT М
FUNCTION F (x)
F = 4 * (x + 2) * (x - 4)
END FUNCTION
Алгоритмический язык
нач
цел a, b, t, М, R
а := -20; b := 20
М := a; R:= F(a)
нц для t от а до b
если F(t) < R то
М := t; R := F(t)
все
кц
вывод М
кон
алг цел F(цел х)
нач
знач := 4*(х + 2)*(х ~ 4)
кон
Паскаль
var a, b, t, M, R: integer;
function F(x: integer): integer;
begin
F := 4 * (x + 2) * (x - 4) ;
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.
Си
int F(int х)
{
return 4 * (х + 2) * (х - 4);
}
void 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) ;
}
}
printf("%d", M);
}
1. прибавь 1,
2. умножь на 3.
Первая из них увеличивает число на экране на 1, вторая умножает его на 3. Программа для Увеличителя — это последовательность команд.
Сколько есть программ, которые число 1 преобразуют в число 17?
((x1 ~ x3) v (x2 ~ x4)) ∧ (¬(x1 ~ x3) v ¬(x2 ~ x4)) = 1
((x2 ~ x4) v (x5 ~ x7)) ∧ (¬(x2 ~ x4) v ¬(x5 ~ x7)) = 1
((x5 ~ x7) v (x6 ~ x8)) ∧ (¬(x5 ~ x7) v ¬(x6 ~ x8)) = 1
((x6 ~ x8) v (x9 ~ x10)) ∧ (¬(x6 ~ x8) v ¬(x9 ~ x10)) = 1
В ответе не нужно перечислять все различные наборы значений x1, х2, … x9, x10, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Часть 2.
Запишите сначала номер задания (24, 27 и т. д.), затем полное решение. Ответы записывайте чётко и разборчиво.
Бейсик
CONST n = 4
count = 0
minimum = 0
FOR 1=1 ТО n
INPUT x
IF x mod 3=0 THEN
count = count + 1
IF x < minimum THEN
minimum. = I
END IF
END IF
NEXT I
IF count > 0 THEN
PRINT count
PRINT minimum
ELSE
PRINT "NO"
END IF
Алгоритмический язык
алг
нач
цел n = 4
цел i, х
цел minimum, count
count := 0
minimum := 0
нц для i от 1 до n
ввод X
если mod(x,3) = 0 то
count := count + 1
если х < minimum то
minimum := i
все
все
кц
если count > 0 TO
вывод count, HC
вывод minimum
иначе
вывод "NO"
все
кон
Паскаль
const n = 4;
var i, x: integer;
var minimum, count: integer;
begin
count := 0;
minimum := 0;
for i := 1 to n do
begin
read(x);
if x mod 3=0 then
begin
count := count + 1;
if x < minimum then
minimum := i
end
end;
if count > 0 then
begin
writeln(count);
writeln(minimum)
end
else
writeln('NO')
end.
Си
linclude <stdio.h>
Idefine n 4
void main(void)
{
int i, x;
int minimum, count;
count = 0;
minimum = 0;
for (i = 1; i <= n; i++)
{
scanf("%d" , &x);
if (x % 3 == 0)
{
count++;
if (х < minimum)
minimum = i;
}
}
if (count > 0)
{
printf("%d\n" , count);
printf("%d\n", minimum);
}
else
printf("NO\n");
}
Последовательно выполните следующее.
1. Напишите, что выведет эта программа при вводе последовательности: 6 9 12 5
2. Приведите пример такой последовательности, содержащей хотя бы одно кратное 3 число, что, несмотря на ошибки, программа печатает правильный ответ.
3. Найдите все ошибки в этой программе (их может быть одна или несколько). Известно, что каждая ошибка затрагивает только одну строку и может быть исправлена без изменения других строк. Для каждой ошибки:
1) выпишите строку, в которой сделана ошибка;
2) укажите, как исправить ошибку, то есть приведите правильный вариант строки. Достаточно указать ошибки и способ их исправления для одного языка программирования.
Обратите внимание, что требуется найти ошибки в имеющейся программе, а не написать свою, возможно, использующую другой алгоритм решения. Исправление ошибки должно затрагивать только строку, в которой находится ошибка.
Примечание: 0 — кратное 3 число.
Содержание верного ответа
Решение использует запись программы на Паскале. Допускается использование программы на трёх других языках программирования.
Программа выведет два числа: 3 и 0.
Пример последовательности, содержащей числа, кратные 3, для которой программа работает правильно: 1 0 3 5.
Замечание для проверяющего. В конце работы программы значение переменной minimum всегда равно 0. Соответственно, программа будет работать верно, если в последовательности есть 0. Выведенное количество кратных 3 чисел будет правильным в любом случае.
В программе есть две ошибки.
Первая ошибка: неверная инициализация minimum.
Строка с ошибкой:
minimum := 0;
Верное исправление:
minimum := 1001;
Вместо 1001 может быть любое целое число, большее 1000, либо MAXINT.
Можно использовать и число 1000, так как при выводе мы проверяем, есть ли в последовательности хотя бы одно кратное 3 число.
Вторая ошибка: неверное присваивание при вычислении минимума.
Строка с ошибкой:
minimum = i;
Верное исправление:
minimum = х;
Исходные данные объявлены так, как показано ниже на примерах для некоторых языков программирования и естественного языка. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать некоторые из описанных переменных.
Бейсик
N = 30
DIM A(N) AS INTEGER
DIM I, J, К AS INTEGER
FOR I = 1 TO N
INPUT A(I)
NEXT I
...
END
Алгоритмический язык
ал г нач
цел N = 30
цел таб а[1:N]
цел i, j, k
нц для i от 1 до N
ввод а[i]
кц
...
кон
Паскаль
const
N = 30;
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 30 void main()
{
int a[N];
int i, j, k;
for (i =0; i < N; i++)
scanf("%d", &a[i]);
...
}
Естественный язык
Объявляем массив А из 30 элементов.
Объявляем целочисленные переменные I, J, К.
В цикле от 1 до 30 вводим элементы массива А с 1-го по 30-й.
...
Содержание верного ответа
На языке Паскаль
к := 0;
for i := 1 to N - 1 do
if ( (a [ i] + a[i + l]) mod 7 = 0) and (a[i] + a[i+l] < 0) then
inc(k);
writeln(k);
На алгоритмическом языке
k : = 0
нц для i от 1 до N - 1
если mod(a[i] + a[i+l],7) = 0 и a[i] + a[i+l] < 0
то
k := k + 1
все
кц
вывод k
На языке Бейсик
K = 0
FOR I = 1 ТО N - 1
IF (A(I) + A(I+1)) MOD 7=0 AND A(I) + A(I+1) < 0 THEN
К = К + 1
END IF
NEXT I
PRINT К
На языке Си
k = 0;
for (i = 0; i < N - 1; i++)
if ((a[i] + a[i+1]) % 7 == 0 && a[i] + a[i+1] < 0)
k++
printf("%d", k);
На естественном языке
Записываем в переменную К начальное значение, равное 0. В цикле от первого элемента до предпоследнего находим остаток от деления суммы текущего и лсдеюущего элементов массива на 7. Если значение данного остатка равно 0 и сумма текущего и следующего элементов массива меньше 0, увеличиваем переменную К на единицу.
После завершения цикла выводим значение переменной К.
Игра завершается в тот момент, когда количество камней в куче становится не менее 29. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 29 или больше камней.
В начальный момент в куче было S камней, 1 ⩽ S ⩽ 28.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Выполните следующие задания. Во всех случаях обосновывайте свой ответ.
Задание 1
а) Укажите все такие значения числа S, при которых Петя может выиграть в один ход. Обоснуйте, что найдены все нужные значения S, и укажите выигрывающий ход для каждого указанного значения S.
б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.
Задание 2
Укажите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
— Петя не может выиграть за один ход;
— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Для каждого указанного значения S опишите выигрышную стратегию Пети.
Задание 3
Укажите хотя бы одно значение S, при котором одновременно выполняются два условия:
— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Для указанного значения S опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы). На рисунке на рёбрах дерева указывайте, кто делает ход; в узлах — количество камней в позиции.
Содержание верного ответа
Задание 1.
а) Петя может выиграть, удвоив количество камней в куче, если S = 15, … 28. При меньших значениях S за один ход нельзя получить кучу, в которой не менее 29 камней.
б) Ваня может выиграть первым ходом (как бы ни играл Петя), если исходно в куче будет S = 14 камней. Тогда после первого хода Пети в куче будет 15, 17 или 28 камней. Во всех случаях Ваня удваивает количество камней и выигрывает в один ход.
Задание 2.
Возможные значения S: 7, 11, 13. В этих случаях Петя, очевидно, не может выиграть первым ходом. Однако он может получить кучу из 14 камней. Эта позиция разобрана в п. 16). В ней игрок, который будет ходить (теперь это Ваня), выиграть не может, а его противник (то есть Петя) следующим ходом выиграет.
Задание 3.
Возможные значения S: 10, 12. Например, для S = 10 после первого хода Пети в куче будет 11, 13 или 20 камней. Если в куче станет 20 камней, Ваня удвоит количество камней и выиграет первым ходом. Ситуация, когда в куче 11 или 13 камней, разобрана в п. 2. В этой ситуации игрок, который будет ходить (теперь это Ваня), выигрывает своим вторым ходом.
В таблице изображено дерево возможных партий при описанной стратегии Вани для первого возможного значения. Для второго возможного значения дерево строится аналогично. Заключительные позиции (в них выигрывает Ваня) подчёркнуты. На рисунке это же дерево изображено в графическом виде (оба способа изображения дерева допустимы)
Необходимо найти в заданной серии показаний датчика минимальное произведение двух показаний, между моментами передачи которых прошло не менее 3 секунд. Значение каждого показания датчика не превышает 1000. Общее количество показаний датчика не превышает 10 000.
Напишите на любом языке программирования программу для решения поставленной задачи. Ваша оценка будет зависеть не только от правильности программы, но и от того, насколько она эффективна.
Программа считается эффективной по времени, если время работы программы пропорционально количеству полученных показаний прибора N, то есть при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайт. Максимальная оценка за правильную программу, эффективную по времени и по памяти, — 4 балла.
Максимальная оценка за правильную программу, эффективную по времени, но не-эффективную по памяти, — 3 балла.
Максимальная оценка за правильную программу, неэффективную ни по времени, ни по памяти, — 2 балла.
Перед программой укажите версию языка и кратко опишите использованный алгоритм. В первой строке задаётся число N — общее количество показаний прибора. Гарантируется, что N > 3. В каждой из следующих N строк задаётся одно неотрицательное вещественное число — очередное показание датчика.
Пример входных данных:
11
12
45
5
4
25
23
21
20
10
12
26
Программа должна вывести одно число — описанное в условии произведение. Пример выходных данных для приведённого выше примера входных данных: 40
Содержание верного ответа
Для построения программы, эффективной по времени, можно определить для каждого элемента входных данных минимальное значение от начала данных до этого элемента включительно. Затем нужно умножать каждый элемент, начиная с четвёртого, на значение этого минимума, взятого на три элемента раньше, и выбрать наименьшее из этих произведений.
Чтобы построить программу, эффективную и по времени, по памяти, заметим, что, поскольку при обработке очередного элемента входных данных используется минимум, найденный на три элемента раньше, достаточно хранить только три последних минимума. Ниже приводится пример программы, реализующей эту идею
\n
const s = 3; {требуемое расстояние между показаниями} var N: integer; a: array[0..s - 1] of real; {хранение показаний прибора} {k-e введенное число записываем в ячейку a[k mod 3]} а_: real; {ввод очередного показания} mn: real; {минимальное введенное число} {не считая 3 последних} m: real; {минимальное значение произведения} i: integer; begin readln(N); { Ввод первых трех чисел} for i := 1 to s do begin readln(a_); a[i mod s] := a_ end; {Ввод остальных значений, поиск минимального произведения} mn := 1001; m := 1000 * 1000 + 1; for i := s + 1 to N do begin readln(a_); if a[i mod s] < mn then mn := a[i mod s]; if a_ * mn < m then m := a_ * mn; a[i mod s] := a_ end; writeln(m) end.