1, Д1, 3, 4, 5, 6, 7, Д7, Д7, Д7, 8, 11, 12, Д12, Д12, 13, 15, 16, Д17, 23, Д23, Д24 C1, Д25 C2, Д25 C2, Д26 C3, Д27, Д27 C4
Между населёнными пунктами A, B, C, D, E, F, G построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице значает, что прямой дороги между пунктами нет.
| A | B | C | D | E | F | G | |
| A | 5 | 12 | 25 | ||||
| B | 5 | 8 | |||||
| C | 2 | 4 | 5 | 10 | |||
| D | 12 | 8 | 2 | ||||
| E | 4 | 5 | |||||
| F | 5 | 5 | |||||
| G | 25 | 10 | 5 | 5 |
Определите длину кратчайшего пути между пунктами A и G (при условии, что передвигаться можно только по построенным дорогам).
Сколько единиц в двоичной записи десятичного числа 519?
Ниже представлены две таблицы из базы данных. Каждая строка таблицы 2 содержит информацию о ребёнке и об одном из его родителей. Информация представлена значением поля ID в соответствующей строке таблицы 1. Определите на основании приведённых данных ID дяди Леоненко В. С.
Пояснение: дядей считается брат отца или матери.
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код:
А — 0; Б — 100; В — 1010; Г — 111; Д — 110. Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. Коды остальных букв меняться не должны. Каким из указанных способов это можно сделать?
1) для буквы В — 101
2) это невозможно
3) для буквы В — 010
4) для буквы Б — 10
Автомат получает на вход четырёхзначное число. По этому числу строится новое число по следующим правилам.
1. Складываются первая и вторая, а также третья и четвёртая цифры исходного числа.
2. Полученные два числа записываются друг за другом в порядке убывания (без разделителей).
Пример. Исходное число: 3165. Суммы: 3 + 1 = 4; 6 + 5 = 11. Результат: 114.
Укажите наименьшее число, в результате обработки которого, автомат выдаст число 1311.
Запишите число, которое будет напечатано в результате выполнения программы. Для Вашего удобства программа представлена на пяти языках программирования.
| Бейсик | Python |
|---|---|
DIM S, N AS INTEGER S = 33 N = 1 WHILE S > 0 S = S – 7 N = N * 3 WEND PRINT(N)
| s = 33 n = 1 while s > 0: s = s - 7 n = n * 3 print(n)
|
| Паскаль | Алгоритмический язык |
var s, n: integer; begin s := 33; n := 1; while s > 0 do begin s := s – 7; n := n * 3 end; writeln(n) end.
| нач цел s, n s := 33 n := 1 нц пока s > 0 s := s – 7 n := n * 3 кц вывод n кон |
| Си++ | |
#include <iostream> using namespace std; int main(void) { int s, n; s = 33; n = 1; while (s > 0) { s = s – 7; n = n * 3; } cout << n << endl; }
| |
Документ объёмом 40 Мбайт можно передать с одного компьютера на другой двумя способами.
А. Сжать архиватором, передать архив по каналу связи, распаковать.
Б. Передать по каналу связи без использования архиватора.
Какой способ быстрее и насколько, если:
· средняя скорость передачи данных по каналу связи составляет 223 бит
в секунду;
· объём сжатого архиватором документа равен 90% исходного;
· время, требуемое на сжатие документа, — 16 секунд, на распаковку — 2 секунды?
В ответе напишите букву А, если быстрее способ А, или Б, если быстрее способ Б. Сразу после буквы напишите число, обозначающее, на сколько секунд один способ быстрее другого.
Так, например, если способ Б быстрее способа А на 23 секунды, в ответе нужно написать Б23. Единицы измерения «секунд», «сек.», «с» к ответу добавлять не нужно.
Для групповых операций с файлами используются маски имён файлов. Маска представляет собой последовательность букв, цифр и прочих допустимых в именах файлов символов, в которых также могут встречаться следующие символы.
Символ «?» (вопросительный знак) означает ровно один произвольный символ.
Символ «*» (звёздочка) означает любую последовательность символов произвольной длины, в том числе «*» может задавать и пустую последовательность.
В каталоге находится 7 файлов:
carga.mp3
cascad.mpeg
cassa.mp3
cassandra.mp4
castrol.mp4
picasa.map
picasa.mp4
Определите, по какой из перечисленных масок из этих 7 файлов будет отобрана указанная группа файлов:
cascad.mpeg
cassa.mp3
cassandra.mp4
picasa.mp4
1) *cas*a*.mp*
2) *ca*a*.mp*
3) *cas*.mp*
4) *cas*a*.mp?
Коле нужно с помощью электронных таблиц построить таблицу квадратов двузначных чисел от 20 до 59.
Для этого сначала в диапазоне В1:К1 он записал числа от 0 до 9, и в диапазоне А2:А5 он записал числа от 2 до 5. Затем в ячейку В5 записал формулу квадрата двузначного числа (А5 — число десятков; В1 — число единиц), после чего скопировал её во все ячейки диапазона B2:К5. В итоге получил таблицу квадратов двузначных чисел. На рисунке ниже представлен фрагмент этой таблицы.
| A | B | C | D | E | |
| 1 | 0 | 1 | 2 | 3 | |
| 2 | 2 | 400 | 441 | 484 | 529 |
| 3 | 3 | 900 | 961 | 1024 | 1089 |
| 4 | 4 | 1600 | 1681 | 1764 | 1849 |
| 5 | 5 | 2500 | 2601 | 2704 | 2809 |
В ячейке B5 была записана одна из следующих формул:
1) =(B1+10*A5)^2
2) =($B1+10*$A5)^2
3) =(B$1+10*$A5)^2
4) =($B1+10*A$5)^2
Укажите в ответе номер формулы, которая была записана в ячейке B5 Примечание. Знак $ используется для обозначения абсолютной адресации.
Дан фрагмент электронной таблицы.
| A | B | C | |
| 1 | 4 | 6 | |
| 2 | = (A1 − 2)/(B1 − 1) | = C1*B1/(4*A1 + 4) | = C1/(A1 − 2) |
Какое целое число должно быть записано в ячейке A1, чтобы диаграмма, построенная по значениям ячеек диапазона A2:С2, соответствовала рисунку? Известно, что все значения ячеек из рассматриваемого диапазона неотрицательны.
Все 4-буквенные слова, составленные из букв К, Л, Р, Т, записаны в алфавитном порядке и пронумерованы.
Вот начало списка:
1. КККК
2. КККЛ
3. КККР
4. КККТ
……
Запишите слово, которое стоит под номером 67.
При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 15 символов и содержащий только символы Ш, К, О, Л, А (таким образом, используется 5 различных символов). Каждый такой пароль в компьютерной системе записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством бит). Укажите объём памяти в байтах, отводимый этой системой для записи 30 паролей. В ответе запишите только число, слово «байт» писать не нужно.
Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду сместиться на (a, b), где a, b – целые числа. Эта команда перемещает Чертёжника из точки с координатами (x, y) в точку с координатами
Цикл
ПОВТОРИ число РАЗ
последовательность команд
КОНЕЦ ПОВТОРИ
означает, что последовательность команд будет выполнена указанное число раз (число должно быть натуральным).
Чертёжнику был дан для исполнения следующий алгоритм (буквами n, a, b обозначены неизвестные числа, при этом n > 1):
НАЧАЛО
сместиться на (–3, –3)
ПОВТОРИ n РАЗ
сместиться на (a, b)
сместиться на (27, 12)
КОНЕЦ ПОВТОРИ
сместиться на (–22, –7)
КОНЕЦ
Укажите наименьшее возможное значение числа n, для которого найдутся такие значения чисел a и b, что после выполнения программы Чертёжник возвратится в исходную точку.
Александра заполняла таблицу истинности для выражения F. Она успела заполнить лишь небольшой фрагмент таблицы:
| x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | F |
|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 0 | ||||||
| 1 | 0 | 1 | ||||||
| 1 | 1 | 1 |
Каким из приведённых ниже выражений может быть F?
1) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ x6 ∧ ¬x7 ∧ ¬x8
2) x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ ¬x8
3) ¬x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ x5 ∧ ¬x6 ∧ x7 ∧ x8
4) x1 ∨ ¬x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ ¬x8
В терминологии сетей TCP/IP маской сети называется 32-разрядная двоичная (то есть состоящая из нулей и единиц) последовательность. Маска определяет, какая часть IP-адреса узла сети относится к адресу сети, а какая — к адресу самого узла в этой сети. Обычно маска записывается по тем же правилам, что и IP-адрес. Адрес сети получается в результате применения поразрядной конъюнкции к заданному IP-адресу узла и маске. По заданным IP-адресу узла и маске определите адрес сети.
IP-адрес узла: 217.8.244.3
Маска: 255.255.252.0
При записи ответа выберите из приведённых в таблице чисел четыре элемента IP-адреса сети и запишите в нужном порядке соответствующие им буквы без использования точек.
| A | B | C | D | E | F | G | H |
| 0 | 3 | 8 | 217 | 224 | 244 | 252 | 255 |
Пример. Пусть искомый IP-адрес: 192.168.128.0, и дана таблица:
| A | B | C | D | E | F | G | H |
| 128 | 168 | 255 | 8 | 127 | 0 | 17 | 192 |
В этом случае правильный ответ будет записан в виде: HBAF.
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л?
На числовой прямой даны два отрезка: P = [37; 60] и Q = [40; 77]. Укажите наименьшую возможную длину такого отрезка A, что формула
(x ∈ P) → (((x ∈ Q) ∧ ¬(x ∈ A)) → ¬(x ∈ P))
истинна при любом значении переменной х, т. е. принимает значение 1 при любом значении переменной х.
Ниже на пяти языках программирования записан рекурсивный алгоритм F.
| Бейсик | Python |
|---|---|
SUB F(n) PRINT n IF n < 5 THEN F(n + 1) F(n + 3) END IF END SUB
| def F(n): print(n) if n < 5: F(n + 1) F(n + 3)
|
| Паскаль | Алгоритмический язык |
procedure F(n: integer); begin writeln(n); if n < 5 then begin F(n + 1); F(n + 3) end end
| алг F(цел n) нач вывод n, нс если n < 5 то F(n + 1) F(n + 3) все кон |
| С++ | |
void F(int n) { cout << n << endl; if (n < 5) { F(n + 1); F(n + 3); } }
| |
Чему равна сумма всех чисел, напечатанных на экране при выполнении вызова F(1)?
В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для обозначения логической операции «И» — символ «&». В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.
| Запрос | Найдено страниц (в сотнях тысяч) |
|---|---|
| Ухо | 35 |
| Подкова | 25 |
| Наковальня | 40 |
| Ухо | Подкова | Наковальня | 70 |
| Ухо & Наковальня | 10 |
| Ухо & Подкова | 0 |
Какое количество страниц (в сотнях тысяч) будет найдено по запросу Подкова & Наковальня?
Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.
Исполнитель Май4 преобразует число, записанное на экране. У исполнителя три команды, которым присвоены номера:
1. Прибавь 1
2. Прибавь 2
3. Прибавь 4
Первая из них увеличивает число на экране на 1, вторая увеличивает это число на 2, а третья — на 4. Программа для исполнителя Май4 — это последовательность команд. Сколько есть программ, которые число 21 преобразуют в число 30?
Сколько существует различных наборов значений логических переменных x1, x2, … x8, y1, y2, … y8, которые удовлетворяют всем перечисленным ниже условиям?
(x1 ∨ x2) ∧ ((x1 ∧ x2) → x3) ∧ (¬x1 ∨ y1) = 1
(x2 ∨ x3) ∧ ((x2 ∧ x3) → x4) ∧ (¬x2 ∨ y2) = 1
…
(x6 ∨ x7) ∧ ((x6 ∧ x7) → x8) ∧ (¬x6 ∨ y6) = 1
(x7 ∨ x8) ∧ (¬x7 ∨ y7) = 1
(¬x8 ∨ y8) = 1
В ответе не нужно перечислять все различные наборы значений переменных x1, x2, … x8, y1, y2, … y8, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
На обработку поступает последовательность из четырёх неотрицательных целых чисел (некоторые числа могут быть одинаковыми). Нужно написать программу, которая выводит на экран количество нечётных чисел в исходной последовательности и максимальное нечётное число. Если нечётных чисел нет, требуется на экран вывести «NO». Известно, что вводимые числа не превышают 1000. Программист написал программу неправильно. Ниже эта программа для Вашего удобства приведена на пяти языках программирования.
| Бейсик | Python |
|---|---|
CONST n = 4 count = 0 maximum = 999 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
| n = 4 count = 0 maximum = 999 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")
|
| Паскаль | Алгоритмический язык |
const n = 4; var i, x: integer; var maximum, count: integer; begin count := 0; maximum := 999; 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.
| алг нач цел n = 4 цел i, x цел maximum, count count := 0 maximum := 999 нц для i от 1 до n ввод x если mod(x, 2) <> 0 то count := count + 1 если x > maximum то maximum := i все все кц если count > 0 то вывод count, нс вывод maximum иначе вывод "NO" все кон |
| Си++ | |
#include <iostream> using namespace std; int main(void) { const int n = 4; int i, x, maximum, count; count = 0; maximum = 999; for (i = 1; i <= n; i++) { cin >> x; if (x % 2 != 0) { count++; if (x > maximum) maximum = i; } } if (count > 0) { cout << count << endl; cout << maximum << endl; } else cout << "NO\n"; }
| |
Последовательно выполните следующее.
1. Напишите, что выведет эта программа при вводе последовательности: 2 9 4 3
2. Приведите пример такой последовательности, содержащей хотя бы одно нечётное число, что, несмотря на ошибки, программа печатает правильный ответ.
3. Найдите все ошибки в этой программе (их может быть одна или несколько). Известно, что каждая ошибка затрагивает только одну строку и может быть исправлена без изменения других строк. Для каждой ошибки:
1) выпишите строку, в которой сделана ошибка;
2) укажите, как исправить ошибку, т. е приведите правильный вариант строки.
Достаточно указать ошибки и способ их исправления для одного языка программирования. Обратите внимание, что требуется найти ошибки в имеющейся программе, а не написать свою, возможно, использующую другой алгоритм решения. Исправление ошибки должно затрагивать только строку, в которой находится ошибка.
В программе используется одномерный целочисленный массив A с индексами от 0 до 9. Значения элементов равны
| Бейсик | Python |
|---|---|
c = 0 FOR i = 1 TO 9 IF A(i - 1) < A(i) THEN c = c + 1 t = A(i) A(i) = A(i - 1) A(i - 1) = t ENDIF NEXT i
| c = 0 for i in range(1, 10): if A[i - 1] < A[i]: c = c + 1 t = A[i] A[i] = A[i - 1] A[i - 1] = t
|
| Паскаль | Алгоритмический язык |
c := 0; for i := 1 to 9 do if A[i - 1] < A[i] then begin c := c + 1; t := A[i]; A[i] := A[i - 1]; A[i - 1] := t end;
| c := 0 нц для i от 1 до 9 если A[i - 1] < A[i] то c := с + 1 t := A[i] A[i] := A[i - 1] A[i - 1] := t все кц |
| Си | |
#include c = 0; for (i = 1; i <= 9; i++) if (A[i - 1] < A[i]) { c++; t = A[i]; A[i] = A[i - 1]; A[i - 1] = t; }
| |
Дан целочисленный массив из 20 элементов. Элементы массива могут принимать целые значения от –10 000 до 10 000 включительно. Опишите на естественном языке или на одном из языков программирования алгоритм, позволяющий найти и вывести количество пар элементов массива, сумма которых нечётна и положительна. Под парой подразумевается два подряд идущих элемента массива. Исходные данные объявлены так, как показано ниже на примерах для некоторых языков программирования и естественного языка. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать некоторые из описанных переменных.
| Бейсик | Python |
|---|---|
N = 20 DIM A(N) AS INTEGER DIM I, J, K AS INTEGER FOR I = 1 TO N INPUT A(I) NEXT I ... END
| N = 20 i = None j = None k = None a = [int(input()) for i in range(N)] ...
|
| Паскаль | Алгоритмический язык |
const N = 20; var a: array [1..N] of integer; i, j, k: integer; begin for i := 1 to N do readln(a[i]); ... end.
| алг нач цел N = 20 цел таб a[1:N] цел i, j, k нц для i от 1 до N ввод a[i] кц ... кон |
| Си++ | Естественный язык |
#include <iostream> using namespace std; int main(void) { const int N = 20; int a[N]; int i, j, k; for (i = 0; i < N; i++) cin >> a[i]; ... }
| Объявляем массив A из 20 элементов. Объявляем целочисленные переменные I, J, K. В цикле от 1 до 20 вводим элементы массива A с 1-го по 20-й. ... |
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или три камня или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 18 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 35. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу, в которой будет 35 или больше камней. В начальный момент в куче было S камней; 1 ≤ S ≤ 34. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Выполните следующие задания. Во всех случаях обосновывайте свой ответ.
Задание 1
а) Укажите все такие значения числа S, при которых Петя может выиграть в один ход. Обоснуйте, что найдены все нужные значения S, и укажите выигрывающие ходы.
б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.
Задание 2
Укажите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Для каждого указанного значения S опишите выигрышную стратегию Пети.
Задание 3
Укажите значение S, при котором одновременно выполняются два условия:
− у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
− у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Для указанного значения S опишите выигрышную стратегию Вани.
Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы). На рисунке на рёбрах дерева указывайте, кто делает ход; в узлах — количество камней в позиции.
Производилась двухканальная (стерео) звукозапись с частотой дискретизации 64 кГц и 24-битным разрешением. В результате был получен файл размером 120 Мбайт, сжатие данных не производилось. Определите приблизительно, сколько времени (в минутах) производилась запись. В качестве ответа укажите ближайшее к времени записи целое число, кратное 5.
На спутнике «Фотон» установлен прибор, предназначенный для измерения энергии космических лучей. Каждую минуту прибор передаёт по каналу связи неотрицательное вещественное число — количество энергии, полученной за последнюю минуту, измеренное в условных единицах. Временем, в течение которого происходит передача, можно пренебречь. Необходимо найти в заданной серии показаний прибора минимальное произведение двух показаний, между моментами передачи которых прошло не менее 6 минут. Количество энергии, получаемое прибором за минуту, не превышает 1000 условных единиц. Общее количество показаний прибора в серии не превышает 10 000. Напишите на любом языке программирования программу для решения поставленной задачи.
Вам предлагаются два задания, связанные с этой задачей: задание А и задание Б. Вы можете решать оба задания А и Б или одно из них по своему выбору.
Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Если решение одного из заданий не представлено, то считается, что оценка за это задание составляет 0 баллов.
Задание Б является усложненным вариантом задания А, оно содержит дополнительные требования к программе. Перед программой укажите версию языка программирования.
А. Напишите на любом языке программирования программу для решения поставленной задачи, в которой входные данные будут запоминаться в массиве, после чего будут проверены все возможные пары элементов.
Обязательно укажите, что программа является решением задания А.
Максимальная оценка за выполнение задания А – 2 балла.
Б. Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик).
Программа считается эффективной по времени, если время работы программы пропорционально количеству элементов последовательности N, т.е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Обязательно укажите, что программа является решением задания Б.
Перед программой укажите версию языка и кратко опишите использованный алгоритм. В первой строке задаётся число N — общее количество показаний прибора. Гарантируется, что N > 6. В каждой из следующих N строк задаётся одно неотрицательное вещественное число — очередное показание прибора.
Пример входных данных:
11
12
45.3
5.5
4
25
23
21
20
10
12
26
Программа должна вывести одно число — описанное в условии произведение.
Пример выходных данных для приведённого выше примера входных данных:
48