Информатика. Вариант 7
Часть 1.
Ответами к заданиям 1–23 являются число или последовательность цифр. Запишите ответ справа от номера задания без пробелов, запятых и других дополнительных символов.
A | B | C | D | E | F | |
A | 6 | 3 | ||||
B | 1 | 1 | ||||
C | 6 | 1 | 2 | 5 | 5 | |
D | 3 | 2 | 4 | |||
E | 5 | 4 | ||||
F | 1 | 5 |
Определите длину кратчайшего пути между пунктами А и F (при условии, что передвигаться можно только по построенным дорогам). В ответе укажите только число.
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | F |
1 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 1 |
1 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
1 | 0 | 1 | 0 | 0 | 1 | 1 | 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)
Символ «?» (вопросительный знак) означает ровно один произвольный символ. Символ «*» (звёздочка) означает любую последовательность символов произвольной длины, в том числе «*» может задавать и пустую последовательность.
В каталоге находятся шесть файлов:
pig.doc tiger.doc dog.dll haghog.dat goat.docx dig.dat
Ниже представлено восемь масок. Сколько из них таких, которым соответствуют ровно пять файлов из данного каталога?
*g?*.*d* | *g*.??? | *g*.* | ??g*.*d |
*?g*.*d?? | ??g*.??* | ?og*.d*? | *?*?g*.*?* |
1. Складываются первая и вторая, затем вторая и третья, а далее третья и четвёртая цифры исходного числа.
2. Полученные три числа записываются друг за другом в порядке убывания (без разделителей).
Пример. Исходное число: 7531. Суммы: 7 + 5 = 12; 5 + 3 = 8; 3 + 1 = 4. Результат: 1284.
Укажите наименьшее число, в результате обработки которого автомат выдаст число 1262.
A | B | C | D | |
1 | 1 | 3 | 7 | 9 |
2 | 13 | 15 | 19 | |
3 | 23 | 24 | 27 | =B$3*2+$C4 |
4 | 33 | 17 | 11 | 37 |
5 | 21 | 31 | 33 | 41 |
Формулу из ячейки D3 скопировали в ячейку С2 так, что числовое значение ячейки С2 стало отличаться от числового значения ячейки D3. Каково стало числовое значение ячейки С2?
Компьютер Тани может начать ретрансляцию данных, не раньше чем им будут получены первые 512 Кбайт этих данных. Каков минимально возможный промежуток времени (в секундах) с момента начала скачивания Таней данных до полного их получения Сергеем?
В ответе укажите только число, слово «секунд» или букву «с» добавлять не нужно.
Бейсик
DIM k, s AS INTEGER
s = 1024
k = 0
WHILE s < 2000
s = s + 32
к = к + 1
WEND
PRINT к
Паскаль
var k, s : integer;
begin
s := 1024;
k := 0;
while s < 2000 do
begin
s : = s + 32;
k := k + 1;
end;
write(k);
end.
Си
{
int к, s;
s = 1024;
k = 0;
while (s < 2000) {
s = s + 32;
k = k + 1;
}
printf("%d", k);
}
Алгоритмический язык
нач
цел k, s
s := 1024
k := 0
нц пока s < 2000
s := s + 32
k := k + 1
кц
вывод k
кон
Укажите, каким кодовым словом должна быть закодирована буква Е. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования. Если таких кодов несколько, укажите код с наименьшим числовым значением.
F(1) = 1
F(2) = 1
F(n) = F(n-1) + F(n-2), при n > 2
Чему равно значение функции F(7)?
В ответе запишите только натуральное число.
Например, если IP-адрес узла равен 207.123.255.131, а маска равна 255.240.0.0, то адрес подсети равен 207.112.0.0.
По заданным IP-адресу узла и маске определите второй слева байт адреса сети. IP-адрес узла: 14.8.192.131. Маска: 255.255.192.0. Ответ запишите в виде десятичного числа.
Под хранение каждого такого пароля на компьютере отводится минимально возможное и одинаковое целое количество байтов, при этом используется посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством битов.
Определите объём памяти (в байтах), который занимает хранение 25 паролей. В ответе укажите только число.
Бейсик
INPUT а
b = 15
а = b - 5 * а
IF а * b < 0 THEN
с = b + 4
ELSE
с = 3 * b
END IF
Паскаль
readln(а);
b := 15;
а : = b - 5 * а;
if а * b < 0 then
с : = b + 4
else
с := 3 * b;
Си
scanf("%d", &a);
b = 15;
a = b - 5 * a;
if (a * b < 0)
c = b + 4;
else
c = 3 * b;
Алгоритмический язык
ввод а
b := 15
a := b - 5 * a
если a * b < 0
то c := b + 4
иначе c := 3 * b
все
3322x + 1 — 3122x + 2 + 8910 = 0
Определите значение х. Ответ запишите в десятичной системе счисления.
В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.
Запрос | Найдено страниц (в тыс) |
(олимпиада & задание) | информатика | 850 |
олимпиада & задание & информатика | 50 |
информатика | 600 |
Компьютер печатает количество страниц (в тысячах), которое будет найдено по следующему запросу:
олимпиада & задание
Укажите целое число, которое напечатает компьютер.
Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.
Укажите наибольшую возможную длину промежутка А, для которого формула ((x ∈ P) → (x ∈ Q)) ∧ (x ∈ A)
тождественно ложна, то есть принимает значение 0 при любом значении переменной х.
Бейсик
s = 0 n — 10
FOR 1 = 0 ТО n - 1
s = s + 2 * A(i) + A(i+1)
NEXT i
Паскаль
s : = 0;
n := 10;
for i := 0 to n - 1 do begin
s := s + 2 * A[i] + A[i+1]
end;
Си
s = 0;
n = 10;
for (i = 0; i <= n - 1; i++)
s = s + 2 * A [i] + A [i +1];
Алгоритмический язык
s : = 0
n := 10
нц для i от 0 до n - 1
s := s + 2 * A[i] + A[i +1]
кц
В начале выполнения этого фрагмента в массиве находились двухзначные нечётные натуральные числа. Какое наименьшее значение может иметь переменная s после выполнения данной программы?
Бейсик
DIM X, L, M AS INTEGER
INPUT X
L = 0: M = 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
если М > mod(х,10) то
М := mod (х,10)
все
х := div(х,10)
кц
вывод L, нс, М
кон
Бейсик
DIM А, В, Т, М, R AS INTEGER
А = -20: В - 20
М = A: R = F (А)
FOR Т = А ТО В
IF F(Т) < R THEN
М = Т
R = F (Т)
END IF
NEXT Т
PRINT М
FUNCTION F (x)
F = -3 * (x + 2) * (x - 6)
END FUNCTION
Паскаль
var a, b, t, M, R: integer;
function F(x: integer): integer;
begin
F := -3 * (x + 2) * (x - 6);
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 -3 * (х + 2) * (х - 6);
}
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) ;
}
Алгоритмический язык
нач
цел а, b, t, М, R
а := -20; b := 20
М := a; R := F(a)
нц для t от а до b
если F(t) < R то
М := t; R := F(t)
все
кц
вывод М
кон
алг цел F(цел х)
нач
знач := -3 * (х + 2) * (х - 6)
кон
1. прибавь 2,
2. прибавь 5.
Первая из них увеличивает число на экране на 2, вторая увеличивает его на 5. Программа для Увеличителя — это последовательность команд.
Сколько есть программ, которые число 1 преобразуют в число 21?
((x1 ~ x2) v (x3 ~ x4)) ∧ (¬((x1 ~ x2) → (x3 ~ x4))) = 1
((x5 ~ x6) v (x7 ~ x8)) ∧ (¬((x5 ~ x6) → (x7 ~ x8))) = 1
((x1 ~ x2) v (x7 ~ x8)) ∧ (¬((x1 ~ x2) → (x7 ~ x8))) = 1
((x6 ~ x8) v (x3 ~ x4)) ∧ (¬((x5 ~ x6) → (x3 ~ x4))) = 1
x9 ~ x10 = 1
В ответе не нужно перечислять все различные наборы значений x1, х2, … x9, х10, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Часть 2.
Запишите сначала номер задания (24, 27 и т. д.), затем полное решение. Ответы записывайте чётко и разборчиво.
Бейсик
DIM N AS LONG
INPUT N
max digit = 9
WHILE N > 0
digit = N MOD 10
IF digit > max digit THEN
digit = max digit
END IF
N = N \ 10
WEND
PRINT max_digit
END
Паскаль
var N: longint;
digit, max digit: integer;
begin
readln(N);
max digit := 9;
while N > 0 do
begin
digit := N mod 10;
if digit > max digit then
digit := max digit;
N := N div 10;
end;
writeln(max digit);
end.
Си
#include <stdio.h>
int main()
{
long int N;
int digit, max digit;
scant("%ld", &N);
max digit = 9;
while (N > 0)
{
digit = N % 10;
if (digit > max digit)
digit = max digit;
N = N / 10;
}
printf(M%d", max digit);
}
Алгоритмический язык
алг
нач
цел N, digit, max digit
ввод N
max digit := 9
нц пока N > 0
digit := mod(N, 10)
если digit > max digit to
digit := max digit
все
N := div(N, 10)
кц
вывод max_digit
кон
Последовательно выполните следующее.
1. Напишите, что выведет эта программа при вводе числа 384.
2. Найдите все ошибки в этой программе (их может быть одна или несколько). Для каждой ошибки:
1) выпишите строку, в которой сделана ошибка;
2) укажите, как исправить ошибку, — приведите правильный вариант строки. Обратите внимание, что требуется найти ошибки в имеющейся программе, а не написать свою, возможно, использующую другой алгоритм решения. Исправление ошибки должно затрагивать только строку, в которой находится ошибка.
Содержание верного ответа
Решение использует запись программы на Паскале. Допускается использование программы на трёх других языках программирования.
Программа выведет число 9.
Первая ошибка. Неверная инициализация переменной в строке
max digit = 9;
Возможный вариант исправления:
max digit = 1;
Вторая ошибка. Неверное присваивание
digit := max digit
при поиске максимума.Строка с ошибкой:
digit := max digit;
В этой строке необходимо поменять местами переменные, то есть исправить её на
max digit := digit;
Бейсик
N = 30
DIM A(N) AS INTEGER
DIM I, J, MIN 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, min: 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, min;
for (i = 0; i < N; i++)
scanf("%d", &a[i]);
...
}
Алгоритмический язык
алг
нач
цел N = 30
целтаб а[1:N]
цел i, j, min
нц для i от 1 до N
ввод a[i]
кц
...
кон
Естественный язык
Объявляем массив А из 30 элементов.
Объявляем целочисленные переменные I, J, MIN.
В цикле от 1 до 30 вводим элементы массива А с 1-го по 30-й.
В качестве ответа Вам необходимо привести фрагмент программы (или описание алгоритма на естественном языке), который должен находиться на месте многоточия. Вы можете записать решение также на другом языке программирования (укажите название и используемую версию языка программирования, например Free Pascal 2.4) или в виде блок-схемы. В этом случае Вы должны использовать те же самые исходные данные и переменные, какие были предложены в условии (например, в образце, записанном на естественном языке).
Содержание верного ответа
На языке Паскаль
min := 1001;
for i := 1 to N do
if (a[i] > 0) and (a[i] mod 10 = 5) and (a[i] < min) then
min := a[i];
if min < 1001 then writeln(min) else writeln('He найдено');
На алгоритмическом языке
min := 1001 нц для i от 1 до N
если а[i] > 0 и mod(a[i], 10) = 5 и a[i] < min
то
min := а [i]
все
кц
если min < 1001
то
вывод min
иначе
вывод "Не найдено"
все
На языке Бейсик
MIN = 1001 FOR 1=1 ТО N
IF А(I) > 0 AND А(I) MOD 10 = 5 AND А(I) < MIN THEN
MIN = A(I)
END IF
NEXT I
IF MIN < 1001 THEN
PRINT MIN
ELSE
PRINT "He найдено"
END IF
На языке Си
min = 1001;
for (i = 0; i < N; i++)
if (a[i] > 0 && a[i] % 10 == 5 && a[i] < min)
min = a[i];
if (min < 1001)
printf("%d", min);
else
printf("Не найдено");
Игра завершается в тот момент, когда количество камней в куче становится не менее 33. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 33 или больше камней.
В начальный момент в куче было S камней, 1 ⩽ S ⩽ 32.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Выполните следующие задания. Во всех случаях обосновывайте свой ответ.
Задание 1
а) Укажите все такие значения числа S, при которых Петя может выиграть в один ход. Обоснуйте, что найдены все нужные значения S, и укажите выигрывающий ход для каждого указанного значения S.
б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.
Задание 2
Укажите два таких значения S, при которых у Пети есть выигрышная стратегия, причём (а) Петя не может выиграть за один ход и (б) Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Для каждого указанного значения S опишите выигрышную стратегию Пети.
Задание 3
Укажите значение S, при котором:
— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и
— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Для указанного значения S опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы). На рисунке на рёбрах дерева указывайте, кто делает ход; в узлах — количество камней в куче.
Содержание верного ответа
Задание 1.
а) Петя может выиграть в один ход, если S = 11, … 32. Во всех этих случаях достаточно утроить количество камней, после чего их количество станет не менее 33, и игра закончится.
При значениях S, меньших 11, за один ход нельзя получить кучу, количество камней в которой будет не менее 33.
б) Ваня может выиграть первым ходом (при любой игре Пети), если S = 10. Тогда после первого хода Пети в куче будет 11, 12 или 30 камней. После этого Ваня утраивает количество камней и выигрывает в один ход.
Задание 2.
При S = 8 или S = 9 у Пети есть выигрышная стратегия, позволяющая ему выиграть своим вторым ходом. В этих случаях Петя не может выиграть первым ходом (см. п. 1а)). Однако он может получить кучу из 10 камней, добавив в кучу два камня (при S = 8) или один камень (при S = 9). После этого хода Петя попадает в ситуацию, разобранную в п. 16) для Вани, то есть у игрока, делающего следующий ход (у Вани), нет хода, сразу приводящего его к выигрышу, а у Пети выигрышный ход «утроить количество камней» есть независимо от того, какой ход сделал Ваня.
Задание 3.
При S = 7 у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом. После первого хода Пети в куче будет 8, 9 или 21 камень. Если в куче станет 21 камень, то Ваня утроит количество камней и выиграет своим первым ходом. Если после первого хода Пети в куче оказалось 8 или 9 камней, то Ваня попадает в ситуацию, разобранную в п. 2 для Пети, и у него есть выигрышная стратегия, позволяющая ему выиграть своим вторым ходом.
В таблице представлено дерево возможных партий при описанной выигрышной стратегии Вани. На рисунке это же дерево изображено в графическом виде. Заключительные позиции, в которых выигрывает Ваня, подчёркнуты. Приведены все возможные ходы Пети и ходы, отвечающие выигрышной стратегии Вани.
В серии обязательно присутствует хотя бы одна частица с отрицательным зарядом. При обработке результатов в каждой серии эксперимента отбирается основноемножество значений зарядов. Это такое непустое подмножество значений зарядов частиц (в него могут войти как заряд одной частицы, так и заряды всех частиц серии), для которого произведение значений зарядов является минимальным среди всех возможных подмножеств. При нахождении произведения знак числа учитывается. Если есть несколько таких множеств, то берётся то, которое содержит наибольшее количество элементов.
Вам предлагается написать эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например Borland Pascal 7.0), которая будет обрабатывать результаты эксперимента, находя основное множество.
Перед текстом программы кратко опишите используемый Вами алгоритм решения задачи.На вход программе в первой строке подаётся количество частиц N. В каждой из последующих N строк записано одно целое число, по абсолютной величине не превышающее 109. Все N чисел различны.
<!—QuoteBegin—>
<!—QuoteEBegin—>Пример входных данных:
4
323
0
2
-999
<!—QuoteEnd—>
<!—QuoteEEnd—>Программа должна вывести в порядке возрастания номера частиц, заряды которых принадлежат основному множеству данной серии.
Нумерация частиц ведётся с единицы.
Пример выходных данных для приведённого выше примера входных данных: 1 3 4.
Содержание верного ответа
Основное множество состоит из всех значений зарядов, кроме 0, если он встречается, и кроме минимального по модулю отрицательного заряда, если отрицательных зарядов чётное число.Программа читает все входные данные один раз, не запоминая все входные данные в массиве, размер которого равен N. Во время чтения данных запоминается номер О, если он встретится (по условию все значения различны, поэтому 0 встречается не больше одного раза), подсчитывается количество отрицательных значений и ищется минимальное по модулю отрицательное значение.После окончания ввода распечатываются все номера, кроме номера 0 и номера минимального по модулю отрицательного значения, но только в случае, если их чётное число.
Ниже приведёны примеры решения задания на языках Паскаль и Бейсик. Допускаются решения, записанные на других языках программирования
\nПример правильной и эффективной программы на языке Паскаль
var n, i, j, k, с, min, a: longint; begin readln(n); min := -1000000001; k := 0; j : = 0; c : = 0 ; for i := 1 to n do begin readln(a); if a = 0 then j := i; if a < 0 then begin с : = с + 1 ; if a > min then begin min := a; k : = i; end end end; for i := 1 to n do if (i <> j) and ((c mod 2 <> 0) or (i <> k)) then write(i, ' ');end.
Пример правильной и эффективной программы на языке Бейсик
INPUT п min = 0 k = 0 j = 0 с = 0FOR i = 1 ТО n INPUT а IF а = 0 THEN j = i IF а < 0 THEN с = с + 1 IF (min = 0) OR (a > min) THEN min = a k = i END IF END IF NEXT iFOR i = 1 TO n IF (i <> j) AND ((c MOD 2 <> 0) OR (i <> k)) THEN PRINT i NEXT i END