1. Сколько единиц в двоичной записи десятичного числа 127?
2. Для таблицы истинности функции F известны значения только некоторых ячеек.
| x1 | x2 | x3 | x4 | x5 | x6 | x7 | F |
|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | |||||
| 0 | 0 | 0 | |||||
| 0 | 1 | 0 |
Каким выражением может быть F?
1) x1 ∧ x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ x6 ∧ ¬x7
2) x1 ∨ ¬x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ x6 ∨ ¬x7
3) ¬x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ x5 ∧ x6 ∧ x7
4) x1 ∨ x2 ∨ ¬ x3 ∨ x4 ∨ x5 ∨ ¬x6 ∨ x7
3. Между населёнными пунктами А, В, С, D, Е, F, Z построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
| A | B | C | D | E | F | Z | |
| A | 4 | 10 | 15 | 34 | |||
| B | 4 | 4 | 6 | ||||
| C | 10 | 4 | 2 | ||||
| D | 15 | 6 | 2 | 3 | 11 | 15 | |
| E | 3 | 8 | 9 | ||||
| F | 11 | 8 | 4 | ||||
| Z | 34 | 15 | 9 | 4 |
Определите длину кратчайшего пути между пунктами А и Z (при условии, что передвигаться можно только по построенным дорогам).
4. Во фрагменте базы данных представлены сведения о родственных отношениях. На основании приведённых данных определите идентификационный номер (ID) родного брата Решко В.А.
|
|
5. Для кодирования букв А, Б, В, Г решили использовать двухразрядные последовательные двоичные числа (от 00 до 11 соответственно). Закодируйте таким образом последовательность символов ГБВА и запишите результат шестнадцатеричным кодом.
6. Цепочка из трёх бусин, помеченных латинскими буквами, формируется по следующему правилу. В конце цепочки стоит одна из бусин W, X, Y, Z. В середине — одна из бусин V, W, Z, которой нет на последнем месте. На первом месте — одна из бусин X, У, Z, не стоящая на втором месте.
Какая из перечисленных цепочек создана по этому правилу?
1) XZZ
2) ZXY
3) YWV
4) YWY
7. В ячейке СЗ электронной таблицы записана формуле =$А$1+В1. Какой вид будет иметь формула, если ячейку СЗ скопировать в ячейку ВЗ?
1) =$A$1+А1
2) =$В$1+ВЗ
3) =$А$1+ВЗ
4) =$B$1+C1
8. Определите, что будет напечатано в результате выполнения программы
var n, s: integer;
begin
n := 4;
s := 0;
while n <= 8 do
begin
s := s + 15;
n := n + 1
end;
write(s)
end.
9. Производится двухканальная (стерео) звукозапись с частотой дискретизации 48 кГц и 24-битным разрешением. Результаты записываются в файл, размер полученного файла — 3 Мбайт; сжатие данных не производилось. Какая из приведённых ниже величин наиболее близка к времени, в течение которого происходила запись?
1) 5 сек.
2) 10 сек.
3) 15 сек.
4) 20 сек.
10. Для передачи аварийных сигналов договорились использовать специальные цветные сигнальные ракеты, запускаемые последовательно. Одна последовательность ракет — один сигнал; в каком порядке идут цвета — существенно. Какое количество различных сигналов можно передать при помощи запуска ровно четырёх таких сигнальных ракет, если в запасе имеются ракеты четырёх различных цветов (ракет каждого вида неограниченное количество, цвет ракет в последовательности может повторяться)?
11. Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(n) = n + 1 при n =< 2;
F(n) = 2 · F(n − 1) + F(n − 2) при n > 2.
Чему равно значение функции F(4)? В ответе запишите только натуральное число.
12. В терминологии сетей TCP/IP маска сети — это двоичное число, меньшее 232; в маске сначала (в старших разрядах) стоят единицы, а затем с некоторого места нули. Маска определяет, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу самого узла в этой сети. Обычно маска записывается по тем же правилам, что и IP-адрес — в виде четырёх байт, причём каждый байт записывается в виде десятичного числа. Адрес сети получается в результате применения поразрядной конъюнкции к заданному IP-адресу узла и маске. Например, если IP-адрес узла равен 231.32.255.131, а маска равна 255.255.240.0, то адрес сети равен 231.32. 240.0.
Для узла с IP-адресом 224.128.112.142 адрес сети равен 224.128.64.0. Чему равен третий слева байт маски? Ответ запишите в виде десятичного числа.
13. В некоторой стране автомобильный номер длиной 10 символов составляют из заглавных букв (используются только 21 различная буква) и десятичных цифр в любом порядке.
Каждый такой номер в компьютерной программе записывается минимально возможным и одинаковым целым количеством байтов (при этом используют посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством битов).
Определите объём памяти, отводимый этой программой для записи 81 номеров. (Ответ дайте в байтах.)
14. Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости:
| вверх | вниз | влево | вправо |
При выполнении этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →.
Четыре команды проверяют истинность условия отсутствия стены у той клетки, где находится РОБОТ:
| сверху свободно | снизу свободно | слева свободно | справа свободно |
Цикл
ПОКА <условие> команда
выполняется, пока условие истинно, иначе происходит переход на следующую строку.
Сколько клеток приведенного лабиринта соответствует требованию, что, выполнив предложенную ниже программу, РОБОТ остановится в той же клетке, с которой он начал движение?
НАЧАЛО
ПОКА <справа свободно> вправо
ПОКА <снизу свободно> вниз
ПОКА <слева свободно> влево
ПОКА <сверху свободно> вверх
КОНЕЦ
15. На рисунке изображена схема дорого, связывающих города A, B, C, D, E, F, G, H, K, L, M. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город M?
16. Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 75 оканчивается на 13.
17. Каким условием нужно воспользоваться для поиска в сети Интернет информации о цветах, растущих на острове Тайвань или Хонсю
1) цветы & (Тайвань | Хонсю)
2) цветы & Тайвань & Хонсю
3) цветы | Тайвань | Хонсю
4) цветы & (остров | Тайвань | Хонсю)
18. На числовой прямой даны два отрезка: P = [10, 35] и Q = [17, 48].
Укажите наибольшую возможную длину отрезка A, для которого формула
A) → ¬(x P)) → ((x A) → (x Q))
19. В программе используется одномерный целочисленный массив A с индексами от 0 до 9. Значения элементов равны 6; 4; 5; 4; 3; 3; 9; 8; 6; 2 соответственно, т.е. A[0] = 6; A[1] = 4 и т.д.
Определите значение переменной c после выполнения следующего фрагмента программы, записанного ниже на разных языках программирования.
| Бейсик | Python |
|---|---|
c = 0
FOR i = 1 TO 9 IF A(i - 1) < A(i) THEN t = A(i) A(i) = A(i - 1) A(i - 1) = t c = c + 1 ENDIF NEXT i |
c = 0
for i in range(1, 10): if A[i - 1] < A[i]: t = A[i] A[i] = A[i - 1] A[i - 1] = t c = c + 1 |
| Алгоритмический язык | Паскаль |
c := 0
нц для i от 1 до 9 если A[i - 1] < A[i] то t := A[i] A[i] := A[i - 1] A[i - 1] := t c := c + 1 все кц |
c := 0;
for i := 1 to 9 do if A[i - 1] < A[i] then begin t := A[i]; A[i] := A[i - 1]; A[i - 1] := t; c := c + 1; end; |
| Си | |
c = 0;
for (i = 1; i <= 9; i++) if (A[i - 1] < A[i]) { t = A[i]; A[i] = A[i - 1]; A[i - 1] = t; c++; } | |
20. Ниже на четырёх языках программирования записан алгоритм. Получив на вход число N, этот алгоритм печатает число q. Укажите наименьшее из таких чисел N, при вводе которого алгоритм напечатает 13.
| Бейсик | Паскаль |
|---|---|
DIM N, q, i AS INTEGER
INPUT N
FOR i = 1 TO N - 1
IF N MOD i = 0 THEN q = i
NEXT i
PRINT q
|
var N, q, i: integer;begin
read(N); for i : = 1 to N - 1 do begin if N mod i = 0 then q : = i end; write(q) end. |
| Си | Алгоритмический язык |
#include<stdio.h>
void main() { int N, q, i; scanf("%d", &N); for (i = 1; i <= N - 1; i++) { if (N%i == 0) q = i; } printf("%d", q); } |
алг
нач цел N, q, i ввод N нц для i от 1 до N - 1 если mod(N, i) = 0 то q : = i все кц вывод q кон |
21. Напишите в ответе число, которое будет напечатано в результате выполнения следующего алгоритма (для вашего удобства алгоритм представлен на четырёх языках).
| Бейсик | Паскаль |
|---|---|
DIM A, B, T, M, R AS INTEGER
A = -11: B = 11 M = A: R = F(А) FOR T = A TO B IF F(T) <= R THEN M = T R = F(T) END IF NEXT T PRINT M+23 FUNCTION F(x) F = (x*x-4)*(x*x-4)+11 END FUNCTION |
var a,b,t,M,R: integer;
Function F(x:integer): integer; begin F := (x*x-4)*(x*x-4)+11 end; begin a := -11; b := 11; 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+23) end. |
| Си | Алгоритмический |
#include <stdio.h>
int F(int x) { return (x*x-4)*(x*x-4)+11; } void main() { int a, b, t, M, R; a = -11; b = 11; M = a; R = F(a); for (t = a; t <= b; t++) { if (F(t) <= R) { M = t; R = F(t); } } printf("%d", M+23); } |
алг
нач цел a, b, t, M, R a := -11; b := 11
M := a; R := F(a)
нц для t от a до bесли F(t) <= R то
M := t; R := F(t)
всекц вывод M + 23 кон алг цел F(цел x) нач знач := (x*x-4)*(x*x-4)+11 кон |
22. У исполнителя Плюсик две команды:
1.прибавь 6,
2.вычти 3.
Первая из них увеличивает число на экране на 6, вторая – уменьшает его на 3. Плюсик умеет производить действия только с положительными числами. Если в ходе вычислений появляется отрицательное число, он выходит из строя и стирает написанное на экране.
Программа для Плюсика – это последовательность команд.
Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 10 команд?
23. A, B и С — целые числа, для которых истинно высказывание
¬ (А = B) ∧ ((A > B)→(B > C)) ∧ ((B > A)→(С > B)).
Чему равно В, если A = 45 и C = 43?
24. Требовалось написать программу, при выполнении которой с клавиатуры считывается натуральное число N, не превосходящее 109, и выводится минимальная цифра этого числа. Программист торопился и написал программу неправильно. (Ниже для Вашего удобства программа представлена на четырёх языках программирования.)
| Бэйсик | Паскаль |
|---|---|
DIM N AS LONG
INPUT N min_digit = 0 WHILE N > 0 digit = N MOD 10 IF digit < min_digit THEN min_digit = digit END IF N = N \ 10 WEND PRINT digit END |
var N: longint;
digit, min_digit: integer; begin readln(N); min_digit := 0; while N > 0 do begin digit := N mod 10; if digit < min_digit then min_digit := digit; N := N div 10; end; writeln(digit); end. |
| Си | Алгоритмический язык |
#include <stdio.h>
int main() { long int N; int digit, min_digit; scanf(H%ld", &N); min_digit = 0; while (N > 0) { digit = N % 10; if (digit < min_digit) min_digit = digit; N = N / 10; } printf("%d", digit); } |
алг
нач цел N, digit, min_digit ввод N min_digit := 0 нц пока N > 0 digit := mod(N, 10) если digit < min_digit то min_digit := digit все N := div(N, 10) кц вывод digit кон |
Последовательно выполните следующее.
1. Напишите, что выведет эта программа при вводе числа 862.
2. Найдите все ошибки в этой программе (их может быть одна или несколько). Для каждой ошибки:
1) выпишите строку, в которой сделана ошибка;
2) укажите, как исправить ошибку, — приведите правильный вариант строки.
Обратите внимание, что требуется найти ошибки в имеющейся программе, а не написать свою, возможно, использующую другой алгоритм решения. Исправление ошибки должно затрагивать только строку, в которой находится ошибка.
25. Дан целочисленный массив из 20 элементов. Элементы массива могут принимать целые значения от –1000 до 1000 включительно. Опишите на естественном языке или на одном из языков программирования алгоритм, позволяющий найти и вывести минимальное значение среди положительных элементов массива, кратных 8. Если в исходном массиве нет элемента, значение которого положительно и делится на 8, то вывести сообщение «Не найдено». Исходные данные объявлены так, как показано ниже на примерах для некоторых языков программирования и естественного языка. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать некоторые из описанных переменных.
| Бейсик | Паскаль |
|---|---|
N = 20
DIM A(N) AS INTEGER DIM I, J, MIN AS INTEGER FOR I = 1 TO N INPUT A(I) NEXT I ... END |
const
N = 20;
vara: 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 20 void main() { int a[N]; int i, j, min; for (i = 0; i>N; i++) scanf("% d", &a[i]); ... } |
алг
нач цел N = 20 целтаб a[1:N] цел i, j, min нц для i от 1 до N ввод a[i] кц ... кон |
| Eстественный язык | |
| Объявляем массив A из 20 элементов.Объявляем целочисленные переменные I, J, MIN. В цикле от 1 до 20 вводим элементы массива A с 1-го по 20-й. ... | |
В качестве ответа Вам необходимо привести фрагмент программы (или описание алгоритма на естественном языке), который должен находиться на месте многоточия. Вы можете записать решение также на другом языке программирования (укажите название и используемую версию языка программирования, например Free Pascal 2.4) или в виде блок-схемы. В этом случае Вы должны использовать те же самые исходные данные и переменные, какие были предложены в условии (например, в образце, записанном на естественном языке).
26. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или два камня или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 17 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее 39. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 39 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 38.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Выполните следующие задания. Во всех случаях обосновывайте свой ответ.
1. а) Укажите все такие значения числа S, при которых Петя может выиграть в один ход. Обоснуйте, что найдены все нужные значения S, и укажите выигрывающий ход для каждого указанного значения S.
б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.
2. Укажите два таких значения S, при которых у Пети есть выигрышная стратегия, причём (а) Петя не может выиграть за один ход и (б) Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Для каждого указанного значения S опишите выигрышную стратегию Пети.
3. Укажите значение S, при котором:
— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и
— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Для указанного значения S опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход, в узлах — количество камней в куче.
27. В физической лаборатории проводится долговременный эксперимент по изучению гравитационного поля Земли. По каналу связи каждую минуту в лабораторию передаётся положительное целое число – текущее показание прибора «Сигма 2015». Количество передаваемых чисел в серии известно и не превышает 10 000. Все числа не превышают 1000. Временем, в течение которого происходит передача, можно пренебречь.
Необходимо вычислить «бета-значение» серии показаний прибора – минимальное чётное произведение двух показаний, между моментами передачи которых прошло не менее 6 минут. Если получить такое произведение не удаётся, ответ считается равным –1.
Вам предлагается два задания, связанных с этой задачей: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору. Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Если решение одного из заданий не представлено, то считается, что оценка за это задание – 0 баллов. Задание Б является усложнённым вариантом задания А, оно содержит дополнительные требования к программе.
А. Напишите на любом языке программирования программу для решения поставленной задачи, в которой входные данные будут запоминаться в массиве, после чего будут проверены все возможные пары элементов. Перед программой укажите версию языка программирования.
ОБЯЗАТЕЛЬНО укажите, что программа является решением ЗАДАНИЯ А.
Максимальная оценка за выполнение задания А – 2 балла.
Б. Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик).
Программа считается эффективной по времени, если время работы
программы пропорционально количеству полученных показаний прибора N, т.е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.
Перед программой укажите версию языка программирования и кратко опишите использованный алгоритм.
ОБЯЗАТЕЛЬНО укажите, что программа является решением ЗАДАНИЯ Б.
Максимальная оценка за правильную программу, эффективную по времени и по памяти, – 4 балла.
Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, – 3 балла. НАПОМИНАЕМ! Не забудьте указать, к какому заданию относится каждая из представленных Вами программ.
Входные данные представлены следующим образом. В первой строке задаётся число N – общее количество показаний прибора. Гарантируется, что N > 6. В каждой из следующих N строк задаётся одно положительное целое число – очередное показание прибора.
Пример входных данных:
11
12
45
5
3
17
23
21
20
19
18
17
Программа должна вывести одно число – описанное в условии произведение либо –1, если получить такое произведение не удаётся.
Пример выходных данных для приведённого выше примера входных данных:
54
Комментариев нет:
Отправить комментарий