Готовимся к ЕГЭ

ВАРИАНТ 1

1. Определите количество натуральных чисел, удовлетворяющих неравенству: 110011102 < x < DE16.
2. Логическая функция F задаётся выражением   x ∧ (y ∧ z ∨ z ∧ w  ∨ y ∧ ¬w). На рисунке приведён фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F истинна. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w.

В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы.

3. На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину кратчайшего пути между пунктами В и Д. Передвигаться можно только по указанным дорогам.

4. В каталоге находятся файлы со следующими именами:

chifera.dat

chifera.doc

ferrum.doc

deLafer.doc

oferta.doc

tokoferol.docx

Определите, по какой из масок будет выбрано ровно два файла:

1)  *fer?*.d*    2)  ?*fer*.doc        3) *?fer*?.doс*      4) ?*fer?*.doc

5. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 1, для буквы Б – кодовое слово 001. Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?
6. Автомат получает на вход трёхзначное число. По этому числу строится новое число по следующим правилам.

1. Перемножаются первая и вторая, а также вторая и третья цифры.

2. Полученные два числа записываются друг за другом в порядке неубывания без разделителей.

Пример. Исходное число: 631. Произведение: 6*3 = 18; 3*1 = 3. Результат: 318. Укажите наибольшее число, при обработке которого автомат выдаёт результат 621.

7. Дан фрагмент электронной таблицы:

Найдите минимальное натуральное число, которое должно быть записано в ячейке A1, чтобы построенная после выполнения вычислений диаграмма по значениям диапазона ячеек A2:D2 соответствовала рисунку? Известно, что все значения диапазона, по которым построена диаграмма – целые положительные числа.

8. Сколько различных значений числа d можно ввести, чтобы после выполнения программы было напечатано 171?

var n, s, d: integer;

begin

  readln(d);

  n := 27;

  s := 12;

  while s <= 2019 do begin

    s := s + d;

    n := n + 16

  end;

  write(n)

end.

9. После преобразования растрового 256-цветного графического файла в 4-цветный формат его размер уменьшился на 18 Кбайт. Каков был размер исходного файла в Кбайтах?
10. Вася составляет 6-буквенные слова, в которых есть только буквы Ж, И, Р, А, Ф, причём в каждом слове используется буква А , но не более 4-х раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?
11. Дан рекурсивный алгоритм:

procedure F(n: integer);

begin

  writeln(n);

  if n > 1 then begin

   writeln(n);

   F(n-1);

   F(n-4)

 end

end;

Найдите сумму чисел, которые будут выведены при вызове F(7).

12. Для узла с IP-адресом 241.185.253.57 адрес сети равен 241.185.252.0. Найдите наименьшее возможное количество нулей в двоичной записи маски подсети.
13. Для регистрации на сайте необходимо продумать пароль, состоящий из 10 символов. Он должен содержать хотя бы 3 цифры, а также строчные или заглавные буквы латинского алфавита (алфавит содержит 26 букв). В базе данных для хранения сведения о каждом пользователе отведено одинаковое и минимальное возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственного пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт одинаковое для каждого пользователя. Для хранения сведений о 30 пользователях потребовалось 870 байт. Сколько байт выделено для хранения дополнительных сведений об одном пользователе. В ответе запишите только целое число – количество байт.
14. Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.

заменить (v, w)

нашлось (v)

Дана программа для исполнителя Редактор:

НАЧАЛО

ПОКА нашлось (9999) ИЛИ нашлось (333)

  ЕСЛИ нашлось (9999)

    ТО заменить (9999, 3)

    ИНАЧЕ заменить (333, 99)

  КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 194 идущих подряд цифр 3? В ответе запишите полученную строку.

15. На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М, проходящих через город Е?

16. Значение арифметического выражения: 97 + 38 – 1 записали в системе счисления с основанием 3. Какая из цифр чаще всего встречается в полученном числе? В ответе укажите, сколько таких цифр в этой записи.
17. В таблице приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета:

Сколько страниц (в тысячах) будет найдено по запросу

Напряженность | Поле | Пшеница?

18. Определите наибольшее натуральное число A, такое что выражение

(x & 10 ≠ 0) ∨ (x & 39 = 0) ∧ (x & 149 = 0) ∨ (x & А = 0)

тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной x)?

19. Ниже представлен фрагмент программы, обрабатывающей одномерный целочисленный массив с индексами от 0 до 10. Известно, что в начале выполнения этого фрагмента в массиве находилась возрастающая последовательность чисел, то есть A[0] < A[1] < … < A[10]. Какое наибольшее значение может иметь переменная s после выполнения данной программы?

s := 27;

n := 10;

for i:=0 to n-1 do begin

  s:=s+A[i]-A[i+1]+2

end;

20. Ниже приведён алгоритм. Укажите наименьшее из таких чисел , при вводе которых алгоритм печатает сначала 3, а потом 2.

var x, a, b, i, c: integer;

begin

  readln(x);

  a:= 0; b:= 0; i:=0;

  while x > 0 do begin

    i:= i + 1;

    c:= x mod 10;

    if i mod 2  = 0 then a:= a + c

    else b:= b + c;

    x:= x div 10;

  end;

  writeln(a);

  writeln(b);

end.

21. Напишите в ответе наибольшее значение входной переменной k, при котором программа выдаёт тот же ответ, что и при входном значении k = 30.

var k, i : longint;

function f(n: longint): longint;

begin

  f := n * n * n;

end;

function g(n: longint): longint;

begin

  g := 3*n + 6;

end;

begin

  readln(k);

  i := 1;

  while f(i) < g(k) do

    i := i+1;

  writeln(i)

end.

22. Исполнитель Июнь16 преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:

1. Прибавить 1

2. Прибавить 2

3. Умножить на 2

Сколько существует программ, для которых при исходном числе 2 результатом является число 12 и при этом траектория вычислений не содержит число 10?

23. Сколько различных решений имеет система логических уравнений

(x1 → (x2 ∨ y1)) ∧ (y1 → y2) = 1

(x2 → (x3 ∨ y2)) ∧ (y2 → y3) = 1

...

 (x8 → (x9 ∨ y8)) ∧ (y8 → y9) = 1

x9 → y9 = 1

где x1,x2,…,x9  и y1,y2,…,y9, – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

24. Дано целое положительное число N, не превосходящее 1000. Необходимо определить, является ли это число степенью числа 7. То есть требуется определить, существует ли такое целое число К, что 7K =N, и вывести это число либо сообщение, что такого числа не существует. Для решения этой задачи ученик написал программу, но, к сожалению, его программа оказалась неверной.

var n, k: integer;

begin

  read(n);

  k := 0;

  while n mod 7 = 0 do begin

    k := k + n div 7;

    n := n div 7;

  end;

  if n <= 7 then

    writeln(k)

  else

    writeln('He существует')

end.

Последовательно выполните следующее.

1. Напишите, что выведет эта программа при вводе числа 49.

2. Приведите пример числа, при вводе которого приведённая программа напечатает то, что требуется.

3. Найдите в программе все ошибки (их может быть одна или несколько). Для каждой ошибки выпишите строку, в которой она допущена, и приведите эту же строку в исправленном виде.

25. Дан массив, содержащий 2014 целых чисел в диапазоне от -10000 до 10000. Напишите на одном из языков программирования программу, которая находит в этом массиве количество пар соседних элементов массива, произведение которых нечётно, а сумма – положительна. Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать часть из описанных.

26. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может

а) добавить в кучу один камень или

б) увеличить количество камней в куче в два раза.

Игра завершается в тот момент, когда количество камней в куче становится не менее 24. Если при этом в куче оказалось не более 38 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. Например, если в куче был 21 камень и Петя удвоит количество камней в куче, то игра закончится и победителем будет Ваня. В начальный момент в куче было S камней, 1

Задание 1. а) При каких значениях числа S Петя может выиграть в один ход? Укажите все такие значения и соответствующие ходы Пети.

б) У кого из игроков есть выигрышная стратегия при S = 22, 21, 20? Опишите выигрышные стратегии для этих случаев.

Задание 2. У кого из игроков есть выигрышная стратегия при S = 11, 10? Опишите соответствующие выигрышные стратегии.

Задание 3. У кого из игроков есть выигрышная стратегия при S = 9? Постройте дерево всех партий, возможных при этой выигрышной стратегии (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход; в узлах – количество камней в позиции.

27. По каналу связи передастся последовательность слов в алфавите {А, Е, Р}. Длина каждого слова не превосходит 10 букв, слова могут не быть осмысленными словами русского языка. Каждое слово передается в виде целого числа, полученного следующим образом.

1. Сначала слово колируется с помощью неравномерного двоичного кода с кодовыми словами: Е – 0; Р – 10; А – 11.
2. К полученной двоичной последовательности справа приписывается цифра 1.
3. Полученная двоичная цепочка переворачивается, то есть, из цепочки 01010111 получается 11101010.
4. Искомое число N вычисляется в результате перевода двоичной цепочки, полученной на предыдущем шаге, в десятичную систему.

Например, символьная последовательность ААЕЕР будет преобразована в 11110010, затем (добавляем единицу в конец) – в 111100101, а затем – в число: 1 + 2 + 4 + 8 + 64 + 256 = 335. Отметим, что 335 = 1010011112.

Напишите программу, которая, получив на вход натуральное число, декодирует переданное сообщение и определяет, сколько раз в исходном слове встречаются гласные буквы. Считается, что входное число может быть представлено в виде значения целого типа в используемом языке программирования.

Пример входных данных:

5483

Пример выходных данных:

АЕРАЕРР

4

Примечание. В этом примере: исходное слово: АЕРАЕРР. Кодовая двоичная последовательность: 110101101010, после добавления 1 справа получим: 1101011010101.

ВАРИАНТ 2

1. Определите количество натуральных чисел, удовлетворяющих неравенству: 111100002 < x < FA16.
2. Логическая функция F задаётся выражением   x ∧ (z ∧ ¬w ∨ y ∧ ¬w  ∨ y ∧ ¬z). На рисунке приведён фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F истинна. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w.

В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы.

3. На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину кратчайшего пути между пунктами Е и Л. Передвигаться можно только по указанным дорогам.

4. В каталоге находятся файлы со следующими именами:

chifera.dat

chifera.doc

ferrum.doc

deLafer.doc

oferta.doc

tokoferol.docx

Определите, по какой из масок будет выбрано ровно три файла:

1)  *fer?*.d*    2)  ?*fer*?.doc*        3) *?fer*?.doс      4) ?*fer?*.docx

5. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д  решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 01, для буквы Б – кодовое слово 10. Какова наименьшая возможная суммарная длина всех пяти кодовых слов?
6. Автомат получает на вход пятизначное число. По этому числу строится новое число по следующим правилам.

1. Складываются отдельно первая, третья и пятая цифры, а также вторая и четвёртая цифры.

2. Полученные два числа записываются друг за другом в порядке неубывания без разделителей.

Пример. Исходное число: 63 179. Суммы: 6 + 1 + 9 = 16; 3 + 7 = 10. Результат: 1016.

Укажите наименьшее число, при обработке которого автомат выдаёт результат 621.

7. Дан фрагмент электронной таблицы:

Найдите минимальное натуральное число, которое должно быть записано в ячейке A1, чтобы построенная после выполнения вычислений диаграмма по значениям диапазона ячеек A1:D2 соответствовала рисунку? Известно, что все значения диапазона A2:D2, по которым построена диаграмма – целые положительные числа.

8. Сколько различных значений числа d можно ввести, чтобы после выполнения программы было напечатано 246?

var n, s, d: integer;

begin

  readln(d);

  n := 8;

  s := 6;

  while s <= 1800 do begin

    s := s + d;

    n := n + 7

  end;

  write(n)

end.

9. После преобразования растрового графического файла его объем уменьшился в 1,5 раза. Сколько цветов было в палитре первоначально, если после преобразования было получено растровое изображение того же разрешения в 16-цветной палитре?
10. Вася составляет 5-буквенные слова, в которых есть только буквы С, И, Р, О, П, причём в каждом слове обязательно есть одна буква 0 , при этом стоять она может только после согласной. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?
11. Дан рекурсивный алгоритм:

procedure F(n: integer);

begin

  writeln(n);

  if n > 1 then begin

   writeln(n);

   F(n-2);

   F(n-3)

 end

end;

Найдите сумму чисел, которые будут выведены при вызове F(6).

12. Для узла с IP-адресом  204.108.112.142 адрес сети равен 204.108.64.0. Найдите наибольшее возможное количество нулей в двоичной записи маски подсети.
13. Для регистрации на сайте необходимо продумать пароль, состоящий из 9 символов. Он должен содержать хотя бы 1 цифру, строчные или заглавные буквы латинского алфавита (алфавит содержит 26 букв) и хотя бы 1 символ из перечисленных: «.», «$», «#», «@», «%», «&». В базе данных для хранения сведения о каждом пользователе отведено одинаковое и минимальное возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственного пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт одинаковое для каждого пользователя. Для хранения сведений о двадцати пользователях потребовалось 500 байт. Сколько байт выделено для хранения дополнительных сведений об одном пользователе. В ответе запишите только целое число – количество байт.
14. Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.

заменить (v, w)

нашлось (v)

Дана программа для исполнителя Редактор:

НАЧАЛО

ПОКА нашлось (9999) ИЛИ нашлось (333)

  ЕСЛИ нашлось (9999)

    ТО заменить (9999, 3)

    ИНАЧЕ заменить (333, 99)

  КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 207 идущих подряд цифр 9? В ответе запишите полученную строку.

15. На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М, проходящих через город Г?

16. Значение арифметического выражения: 97 + 38 –5 записали в системе счисления с основанием 3. Какая из цифр реже всего встречается в полученном числе? В ответе укажите, сколько таких цифр в этой записи.
17. В таблице приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета:

Сколько страниц (в тысячах) будет найдено по запросу

Бабочка & Гусеница?

18. Определите наименьшее натуральное число A, такое что выражение

(x & 10 ≠ 0) ∨ (x & 39 = 0) ∧ (x & 149 = 0) ∨ (x & А = 0)

тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной x)?

19. Ниже представлен фрагмент программы, обрабатывающей одномерный целочисленный массив с индексами от 0 до 10. Известно, что в начале выполнения этого фрагмента в массиве находилась возрастающая последовательность чисел, то есть A[0] < A[1] < … < A[10]. Какое наименьшее значение может иметь переменная s после выполнения данной программы?

s := 32;

n := 10;

for i:=0 to n-1 do begin

  s:=s+A[i+1]-A[i]+1

end;

20. Ниже приведён алгоритм. Укажите наименьшее из таких чисел , при вводе которых алгоритм печатает сначала 4, а потом 5.

var x, b, i: integer;

begin

  readln(x);

  b:= 0; i:=0;

  while x > 0 do begin

    if i mod 2  > 0 then b:= b + x mod 10;

    x:= x div 10;

    i:= i + 1;

  end;

  writeln(i);

  writeln(b);

end.

21. Напишите в ответе наименьшее значение входной переменной k, при котором программа выдаёт тот же ответ, что и при входном значении k = 18.

var k, i : longint;

function f(n: longint): longint;

begin

  f := n * n;

end;

function g(n: longint): longint;

begin

  g := 2*n + 5;

end;

begin

  readln(k);

  i := 1;

  while f(i) < g(k) do

    i := i+1;

  writeln(i)

end.

22. Исполнитель Июнь16 преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:

1. Прибавить 1

2. Прибавить 2

3. Умножить на 3

Сколько существует программ, для которых при исходном числе 2 результатом является число 16 и при этом траектория вычислений не содержит число 14?

23. Сколько различных решений имеет система логических уравнений

(¬x1 ∨ ¬y1) ∧ ((x1 ∨ y1) → (x2 ∨ y2)) = 1

(¬x2 ∨ ¬y2) ∧ ((x2 ∨ y2) → (x3 ∨ y3)) = 1

...

(¬x5 ∨ ¬y5) ∧ ((x5 ∨ y5) → (x6 ∨ y6)) = 1

(¬x6 ∨ ¬y6) = 1

где x1,x2,…,x6  и y1,y2,…,y6, – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

24. Дано целое положительное число N, не превосходящее 1000. Необходимо определить, является ли это число степенью числа 4. То есть требуется определить, существует ли такое целое число К, что 4K =N, и вывести это число либо сообщение, что такого числа не существует. Для решения этой задачи ученик написал программу, но, к сожалению, его программа оказалась неверной.

var n, k: integer;

begin

  read(n);

  k := 0;

  while n mod 4 = 0 do begin

    k := k + n div 4;

    n := n div 4;

  end;

  if k = 1 then

    writeln(k)

  else

    writeln('He существует')

end.

Последовательно выполните следующее.

1. Напишите, что выведет эта программа при вводе числа 16.

2. Приведите пример числа, при вводе которого приведённая программа напечатает то, что требуется.

3. Найдите в программе все ошибки (их может быть одна или несколько). Для каждой ошибки выпишите строку, в которой она допущена, и приведите эту же строку в исправленном виде.

25. Дан целочисленный массив из 20 элементов. Элементы массива могут принимать целые значения от –10 000 до 10 000 включительно. Опишите на одном из языков программирования алгоритм, позволяющий найти и вывести количество пар элементов массива, в которых сумма элементов делится на 2, но не делится на 4. В данной задаче под парой подразумеваются два соседних элемента массива.

26. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может

а) добавить в кучу один камень или

б) увеличить количество камней в куче в два раза.

Игра завершается в тот момент, когда количество камней в куче становится не менее 28. Если при этом в куче оказалось не более 46 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. В начальный момент в куче было S камней, 1 ≤ S ≤ 27.

Задание 1. а) При каких значениях числа S Петя может выиграть в один ход? Укажите все такие значения и соответствующие ходы Пети.

б) У кого из игроков есть выигрышная стратегия при S = 24, 25, 26? Опишите выигрышные стратегии для этих случаев.

Задание 2. У кого из игроков есть выигрышная стратегия при S = 10, 11? Опишите соответствующие выигрышные стратегии.

Задание 3. У кого из игроков есть выигрышная стратегия при S = 8? Постройте дерево всех партий, возможных при этой выигрышной стратегии (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход; в узлах – количество камней в позиции.

27. По каналу связи передаются положительные целые числа, не превышающие 1000 – результаты измерений, полученных в ходе эксперимента (количество измерений N известно заранее, гарантируется, что 2 < N ≤ 10000). После окончания эксперимента передаётся контрольное значение – наибольшее число R, удовлетворяющее следующим условиям.

1. R – сумма двух различных переданных элементов последовательности («различные» означает, что нельзя просто удваивать переданные числа, суммы различных, но равных по величине элементов допускаются).

2. R кратно 3.

3. Если в последовательности нет двух чисел, сумма которых кратна 3, контрольное значение считается равным 1.

В результате помех при передаче как сами числа, так и контрольное значение

могут быть искажены.

Напишите эффективную, в том числе по используемой памяти, программу, которая будет проверять правильность контрольного значения. Программа должна напечатать отчёт по следующей форме:

Вычисленное контрольное значение: …

Контроль пройден (или Контроль не пройден)

Задача А (2 балла). Напишите на любом языке программирования программу для решения поставленной задачи, в которой входные данные будут запоминаться

в массиве, после чего будут проверены все возможные пары элементов.

Задача Б (4 балла). Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих

характеристик).

На вход программе в первой строке подаётся количество чисел N (2 < N ≤ 10000). В каждой из последующих N строк записано одно натуральное число, не превышающее 1000. В последней строке записано контрольное значение.

Пример входных данных:

6

100

8

33

145

19

84

153

Пример выходных данных для приведённого выше примера входных данных:

Вычисленное контрольное значение: 153

Контроль пройден

ВАРИАНТ 3

1. Определите количество натуральных чисел, удовлетворяющих неравенству: 111001012 < x < FC16.
2. Логическая функция F задаётся выражением   x ∧ (y ∧ z ∨ y ∧ ¬w ∨  ¬z ∧ ¬w). На рисунке приведён фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F истинна. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w.

В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы.

3. На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину кратчайшего маршрута между пунктами Б и Г. Передвигаться можно только по указанным дорогам.

4. В каталоге находятся файлы со следующими именами:

primera.dat

primera.doc

merchant.doc

k-mer.doc

omerta.doc

Tamerlan.docx

Определите, по какой из масок будет выбрано ровно три файла:

1)  *mer?*.d*    2)  *mer*?.doc*        3) ?*mer?*.doc      4) *?mer*?.doc*

5. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д  решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0, для буквы Б – кодовое слово 101. Какова наименьшая возможная суммарная длина всех пяти кодовых слов?
6. Автомат получает на вход пятизначное число. По этому числу строится новое число по следующим правилам.

1. Складываются отдельно первая, третья и пятая цифры, а также вторая и четвёртая цифры.

2. Полученные два числа записываются друг за другом в порядке неубывания без разделителей.

Пример. Исходное число: 63 179. Суммы: 6 + 1 + 9 = 16; 3 + 7 = 10. Результат: 1016.

Укажите наименьшее число, при обработке которого автомат выдаёт результат 723.

7. Дан фрагмент электронной таблицы:

Найдите минимальное натуральное число, которое должно быть записано в ячейке A1, чтобы построенная после выполнения вычислений диаграмма по значениям диапазона ячеек A2:D2 соответствовала рисунку? Известно, что все значения диапазона A2:D2, по которым построена диаграмма – целые положительные числа.

8. Сколько различных значений числа d можно ввести, чтобы после выполнения программы было напечатано 196?

var n, s, d: integer;

begin

  readln(d);

  n := 7;

  s := 35;

  while s <= 2570 do begin

    s := s + d;

    n := n + 9

  end;

  write(n)

end.

9. После преобразования растрового графического файла его объем уменьшился в 2 раза. Сколько цветов было в палитре первоначально, если после преобразования было получено растровое изображение того же разрешения в 16-цветной палитре?
10. Вася составляет 6-буквенные слова, в которых есть только буквы П, И, Р, О, Г, причём в каждом слове есть одна буква Р , при этом после неё обязательно стоит гласная буква. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?
11. Дан рекурсивный алгоритм:

procedure F(n: integer);

begin

  writeln(n);

  if n > 1 then begin

   writeln(n);

   F(n-1);

   F(n-3)

 end

end;

Найдите сумму чисел, которые будут выведены при вызове F(5).

12. Для узла с IP-адресом 111.91.200.28 адрес сети равен 111.91.192.0. Найдите наименьшее возможное количество нулей в двоичной записи маски подсети.
13. При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 11 символов. Из соображений информационной безопасности каждый пароль должен содержать хотя бы 2 десятичных цифры, как прописные, так и строчные латинские буквы, а также не менее 2-х символов из 6-символьного набора: «&», «#», «$», «*», «!», «@». В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт; это число одно и то же для всех пользователей. Для хранения сведений о 30 пользователях потребовалось 900 байт. Сколько байт выделено для хранения дополнительных сведений об одном пользователе? В ответе запишите только целое число – количество байт.
14. Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.

заменить (v, w)

нашлось (v)

Дана программа для исполнителя Редактор:

НАЧАЛО

ПОКА нашлось (9999) ИЛИ нашлось (333)

  ЕСЛИ нашлось (9999)

    ТО заменить (9999, 3)

    ИНАЧЕ заменить (333, 99)

  КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 207 идущих подряд цифр 3? В ответе запишите полученную строку.

15. На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М, не проходящих через город Г?

16. Значение арифметического выражения: 95 + 37 –14 записали в системе счисления с основанием 3. Какая из цифр реже всего встречается в этой записи? В ответе укажите, сколько таких цифр в записи.
17. В таблице приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета:

Сколько страниц (в тысячах) будет найдено по запросу

Слон | Ладья | Хобот?

18. Определите наименьшее натуральное число A, такое что выражение

(x & 51 ≠ 0) → (x & А ≠ 0) ∨  ¬ ((x & 11 ≠ 0) ∨  (x & А ≠ 0))

тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной x)?

19. Ниже представлен фрагмент программы, обрабатывающей одномерный целочисленный массив с индексами от 0 до 10. Известно, что в начале выполнения этого фрагмента в массиве находилась возрастающая последовательность чисел, то есть A[0] < A[1] < … < A[10]. Какое наибольшее значение может иметь переменная s после выполнения данной программы?

s := 15;

n := 10;

for i:=0 to n-1 do begin

  s:=s+A[i]-A[i+1]+3

end;

20. Ниже приведён алгоритм. Укажите наименьшее из таких чисел , при вводе которых алгоритм печатает сначала 3, а потом 2.

var x, a, b, i, c: integer;

begin

  readln(x);

  a:= 0; b:= 0; i:=0; c:=0;

  while x > 0 do begin

    i:= i + 1;

    if i mod 2  = 0 then a:= a + c

    else b:= b + c;

    c:= x mod 10;

    x:= x div 10;

  end;

  writeln(a);

  writeln(b);

end.

21.         Напишите в ответе наибольшее значение входной переменной k, при котором программа выдаёт тот же ответ, что и при входном значении k = 45.

var k, i : longint;

function f(n: longint): longint;

begin

  f := n * n;

end;

function g(n: longint): longint;

begin

  g := 3*n + 2;

end;

begin

  readln(k);

  i := 1;

  while f(i) < g(k) do

    i := i+1;

  writeln(i)

end.

22. Исполнитель Июнь16 преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:

1. Прибавить 1

2. Прибавить 2

3. Умножить на 3

Сколько существует программ, для которых при исходном числе 2 результатом является число 13 и при этом траектория вычислений содержит число 10?

23. Сколько различных решений имеет система логических уравнений

(¬x1 ∨ ¬y1) ∧ ((x1 ∨ y1) → (x2 ∨ y2)) = 1

(¬x2 ∨ ¬y2) ∧ ((x2 ∨ y2) → (x3 ∨ y3)) = 1

...

(¬x6 ∨ ¬y6) ∧ ((x6 ∨ y6) → (x7 ∨ y7)) = 1

(¬x7 ∨ ¬y7) = 1

где x1,x2,…,x7  и y1,y2,…,y7, – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

24. Дано целое положительное число N, не превосходящее 1000. Необходимо определить, является ли это число степенью числа 3. То есть требуется определить, существует ли такое целое число K, что 3K = N, и вывести это число либо сообщение, что такого числа не существует. Для решения этой задачи ученик написал программу, но, к сожалению, его программа оказалась неверной.

var n, k: integer;

begin

  read(n);

  k := 0;

  while k mod 3 = 0 do begin

    k := k + 1;

    n := n div 3

  end;

  if n > 0 then

    writeln(k)

  else

    writeln('Не существует')

end.

Последовательно выполните следующее.

1. Напишите, что выведет эта программа при вводе числа 9.

2. Приведите пример числа, при вводе которого приведённая программа напечатает то, что требуется.

3. Найдите в программе все ошибки (их может быть одна или несколько). Для каждой ошибки выпишите строку, в которой она допущена, и приведите эту же строку в исправленном виде.

25. Дан целочисленный массив из 40 элементов. Элементы массива могут принимать целые значения от –100 до 100 включительно. Опишите на естественном языке или на одном из языков программирования алгоритм, позволяющий найти и вывести количество пар элементов массива, произведение которых положительно, а сумма кратна 7. Под парой подразумевается два подряд идущих элемента массива.

26. Два игрока, Паша и Валя, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 20. Если при этом в куче оказалось не более 30 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. Например, если в куче было 17 камней и Паша удвоит количество камней в куче, то игра закончится, и победителем будет Валя. В начальный момент в куче было S камней, 1 ≤ S ≤ 19.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.

Выполните следующие задания.

1. а) При каких значениях числа S Паша может выиграть в один ход? Укажите все такие значения и соответствующие ходы Паши.

б) У кого из игроков есть выигрышная стратегия при S = 18, 17, 16? Опишите выигрышные стратегии для этих случаев.

2. У кого из игроков есть выигрышная стратегия при S = 9, 8? Опишите соответствующие выигрышные стратегии.

3. У кого из игроков есть выигрышная стратегия при S = 7? Постройте дерево всех партий, возможных при этой выигрышной стратегии (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход; в узлах – количество камней в позиции.

27. По каналу связи передаются положительные целые числа, не превышающие 1000, – результаты измерений, полученных в ходе эксперимента (количество измерений известно заранее). После окончания эксперимента передаётся контрольное значение – наибольшее число R, удовлетворяющее следующим условиям:

1) R – сумма двух различных переданных элементов последовательности («различные» означает, что нельзя просто удваивать переданные числа, суммы различных, но равных по величине элементов допускаются);

2) R – нечётное число.

Если чисел, соответствующих приведённым условиям, нет, считается, что R = –1.

В результате помех при передаче как сами числа, так и контрольное значение

могут быть искажены.

Напишите эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например, Free Pascal 2.6.4), которая будет проверять правильность контрольного значения.

Программа должна напечатать отчёт по следующей форме:

Вычисленное контрольное значение:…

Контроль пройден (или – контроль не пройден)

Если удовлетворяющее условию контрольное значение определить невозможно

(то есть при R = –1), то выводится только фраза «Контроль не пройден».

Перед текстом программы кратко опишите используемый Вами алгоритм решения.

На вход программе в первой строке подаётся количество чисел N. В каждой из последующих N строк записано одно натуральное число, не превышающее 1000. В последней строке записано контрольное значение.

Пример входных данных:

6

100

8

33

45

19

90

145

Пример выходных данных для приведенного выше примера входных данных:

Вычисленное контрольное значение: 145

Контроль пройден.

Полезные сайты для подготовки к ГИА