Рабочая программа для подготовки к ЕГЭ по информатике

Следовательно, существует 6 целых чисел, для которых это неравенство выполнится (43, 44, 45, 46, 47, 48).

Ответ: 6

Логическая функция F задаётся выражением ¬x \/ y \/ (¬z /\ w).
На рисунке приведён фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F ложна.
Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных w, x, y, z.

В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала – буква, соответствующая первому столбцу; затем – буква, соответствующая второму столбцу, и т.д.) Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Пример. Если бы функция была задана выражением ¬x \/ y, зависящим от двух переменных: x и y, и был приведён фрагмент её таблицы истинности, содержащий все наборы аргументов, при которых функция F истинна.

Тогда первому столбцу соответствовала бы переменная y, а второму столбцу – переменная x. В ответе следовало бы написать: yx.

Ответ: ________

¬x \/ y \/ (¬z /\ w)

Дизъюнкция (логическое сложение) истинна тогда и только тогда, когда истинно хотя бы одно высказывание.

Следовательно, для того чтобы вся функция была ложна, переменной х должен соответствовать тот столбец, в котором стоит значение 1 (так как, ¬x превращает 1 в 0), а переменной y столбец со значениями 0.

Таким образом:
— переменной x соответствует столбец с переменной 1,
— переменной y соответствует столбец с переменной 4.

Конъюнкция (логическое умножение) истинна тогда и только тогда, когда истинны все высказывания (ложна — если ложно хотя бы одно высказывание).
Конъюнкция ¬z /\ w в нашем выражении будет истинна только если z=0, w=1.

Посмотрим на вторую строчку таблицы, где переменная 2 равна 1, а переменная 3 равна 0.

Так как ¬z /\ w должна равняться 0, то z = 1 и w = 0 (в противном случае произведение будет равно 1)

Таким образом:
— переменной z соответствует столбец с переменной 2 (2 столбец),
— переменной w соответствует столбец с переменной 3 (3 столбец).

Ответ: xzw

На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова протяжённость дороги из пункта А в пункт Г. В ответе запишите целое число – так, как оно указано в таблице.

Ответ: ________

Для решения этой задачи — достаточно найти в таблице, где пункт А и где пункт Г.

Строке П3 должна соответствовать вершина из которой выходит 3 дуги.

Такой вершиной является А.

П3 — А

Строке П4 должна соответствовать вершина из которой выходит 2 дуги.

Такой вершиной является Д.

П4 — Д

Один путь из пункта Д ведет в пункт А (11).

Второй путь ведет в пункт Г (5).

Теперь становится очевидным, что П5 — это пункт Г.

П5 — Г

В задании требуется определить длину дороги из пункта А в пункт Г.

По таблице определяем что путь из А в Г равен 6.

Ответ: 6

Ниже представлены два фрагмента таблиц из базы данных о жителях микрорайона. Каждая строка таблицы 2 содержит информацию о ребёнке и об одном из его родителей. Информация представлена значением поля ID в соответствующей строке таблицы 1. Определите на основании приведённых данных, у скольких детей на момент их рождения матерям было больше 22 полных лет. При вычислении ответа учитывайте только информацию из приведённых фрагментов таблиц.

Ответ: ________

По ID ребенка определяем его год рождения, ID — родителей их пол и их возраст.

Ребенок ID_23 — 1968 г.р.
Родитель ID_22 — пол М — не подходит
Родитель ID_42 — пол Ж — 1941 г.р. — подходит

Определяем возраст матери на момент рождения ребенка. Для этого из года рождения ребенка вычитаем год рождения матери.

1968 — 1941 = 27 лет — подходит (1)

Аналогично поступаем с остальными данными таблицы.

Ребенок ID_24 — 1993 г.р.
Родитель ID_23 — пол М — не подходит
Родитель ID_73 — пол Ж — 1967 г.р. — подходит

1993 — 1967 = 26 лет — подходит (2)

Ребенок ID_32 — 1960 г.р.
Родитель ID_22 — пол М — не подходит
Родитель ID_42 — пол Ж — 1941 г.р. — подходит

1960 — 1941 = 19 лет — не подходит

Ребенок ID_33 — 1987 г.р.
Родитель ID_32 — пол Ж — 1960 г.р. — подходит
Родитель ID_35 — пол М

1987 — 1960 = 27 лет — подходит (3)

Ребенок ID_35 — 1965 г.р.
Родитель ID_15 — пол Ж — 1944 г.р. — подходит

1965 — 1944 = 21 год — не подходит

Ребенок ID_44 — 1990 г.р.
Родитель ID_32 — пол Ж — 1960 г.р. — подходит
Родитель ID_35 — пол М

1990 — 1960 = 30 лет — подходит (4)

Ребенок ID_52 — 1995 г.р.
Родитель ID_23 — пол М
Родитель ID_73 — пол Ж — 1967 г.р. — подходит

1995 — 1967 = 28 лет — подходит (5)

Следовательно у 5 детей на момент их рождения матерям было больше 22 полных лет

Ответ: 5

По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У. Для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые слова.

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

Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Ответ: ________

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

0 — не подходит, так как А, Е, И начинаются с 0.
1 — не подходит, так как буквы К, Л, Р, С, Т, У начинаются с 1.
01 — не подходит из-за Е и К.
10 — не подходит из-за Р, Т и У.
11 — не подходит из-за К, Л, С.
000 — не подходит из-за А.
001 — не подходит из-за А.
101 — не подходит из-за Р и Т.
110 — не подходит из-за Л.
111 — не подходит из-за К.
1000 — не подходит из-за У.
1001 — не подходит из-за У.
1100 — подходит для использования.

Следовательно, кратчайшее кодовое слово для буквы Б — 1100.

Ответ: 1100

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число Rследующим образом.

1) Строится двоичная запись числа N.
2) К этой записи дописываются справа ещё два разряда по следующему правилу:

а) складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на 2.

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите минимальное число R, которое превышает число 83 и может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.

Ответ: ________

Операция над числом выполняется два раза, значит к числу N добавляется два разряда.

Для начала, определим, что может быть окончанием числа R, то есть разберем вот эти последние два разряда.

Если изначально сумма разрядов число не четное,

— например 10101, то сначала оно будет преобразовано в 101011 (добавили 1), т.к. сумма разрядов равна 3,
— затем в 1010110 (добавили 0), т.к. сумма разрядов равна 4.

Если число разрядов не четное,

— например 10001, то сначала оно будет преобразовано в 110000 (добавили 0), т.к. сумма разрядов равна 2,
— затем в 1100000 (добавили 0), т.к. сумма разрядов не изменилась.

Таким образом, делаем вывод, что окончанием числа может быть либо 10 (если сумма разрядов исходного числа N нечетное), либо 00 (если сумма разрядов исходного числа N четная), других вариантов нет.

Теперь рассмотрим число 83.

83₁₀ = 1010011₂

При этом 1010011 — это число R, а исходное число N на два разряда меньше, то есть 10100.

Если мы выполним алгоритм для этого числа N (10100), то у нас получится 1010000, это число меньше 83.

Поэтому берем N на единицу больше, то есть 10101.

— 10101 — сумма разрядов нечетная, добавляем 1 в конец и получаем 101011
— 110011 — сумма разрядов четная, добавляем 0 в конец и получаем 1010110

То есть наименьшее число R 83 — это 1010110 в двоичной или 86 в десятичной.

Ответ: 86

Дан фрагмент электронной таблицы. Из ячейки B3 в ячейку A4 была скопирована формула. При копировании адреса ячеек в формуле автоматически изменились. Каким стало числовое значение формулы в ячейке A4?

Примечание: знак $ обозначает абсолютную адресацию.

Ответ: ________

При копировании все абсолютные ссылки (ссылки со знаком $, который обозначает абсолютную адресацию) не меняются.

Наша формула =$C2+D$3 в ячейке B3 содержит две смешанные ссылки.

— в первой $С2 — адрес столбца С не меняется при копировании
— во второй D$3 — не меняется адрес строки 3 при копировании

Наша формулу =$C2+D$3 скопировали из ячейки B3 в ячейку A4.

— сместилась на один столбец влево (уменьшилась на один столбец)
— сместилась на одну строку вниз (увеличилась на одну строку)

Следовательно после копирования формула =$C2+D$3, примет вид =$C3+С$3.

Вычисление этого выражения (=$C3+С$3) дает следующий результат: 300 + 300 = 600.

Ответ: 600

Запишите число,которое будет напечатано в результате выполнения следующей программы. Для Вашего удобства программа представлена на пяти языках программирования.

Ответ: ________

Нужно определить значение переменной n в результате выполнения программы.

Что мы имеем:

1) Начальное значение переменной s=260, переменной n=0.
2) Цикл в программе будет выполняться пока выполняется условие s0.
3) После окончания цикла выводится значение переменной n.
4) С каждым шагом цикла s уменьшается на 15
s := s — 15
n увеличивается на 2
n := n + 2
5) Цикл закончится, как только s станет меньше или равно 0 (пока выполняется условие s0).
6) Таким образом цикл выполнится 18 раз
для s = 
260
245
230
215
200
185
170
155
140
125
110
95
80
65
50
35
20
5
7) Следовательно к начальному значению n=0 прибавиться 18*2=36 — это и есть наш ответ.

Ответ: 36

Автоматическая фотокамера производит растровые изображения размером 640×480 пикселей. При этом объём файла с изображением не может превышать 320 Кбайт, упаковка данных не производится. Какое максимальное количество цветов можно использовать в палитре?

Ответ: ________

Объём растрового изображения находится как произведение количества пикселей в изображении на объём памяти i, необходимый для хранения цвета одного пиксела

В нашем случае

640 · 480 · i ≤ 320 · 1024 · 8 бит

i ≤ 320 · 1024 · 8/(640 · 480),

i ≤ 8.53333

так как бит может быть только целым числом, то получаем

i = 8 (в нашей задаче сказано, что объём файла с изображением не может превышать 320 Кбайт, следовательно, округлять вверх мы не можем! Полученное значение i округляем вниз до 8 бит!)

Далее находим N — максимальное количество цветов в палитре

Для этого используем формулу N = 2ⁱ

N = 2⁸ = 256

Значит, в изображении можно использовать не более 256 цветов.

Ответ: 256

Все 4-буквенные слова, составленные из букв Д, Е, К, О, Р, записаны в алфавитном порядке и пронумерованы, начиная с 1.

Ниже приведено начало списка.

1. ДДДД
2. ДДДЕ
3. ДДДК
4. ДДДО
5. ДДДР
6. ДДЕД
…

Под каким номером в списке идёт первое слово, которое начинается с буквы K?

Ответ: ________

Заменим буквы Д, Е, К, О, Р на цифры

Д — 0
Е — 1
К — 2
О — 3
Р — 4

Перепишем наш список

1. ДДДД
2. ДДДЕ
3. ДДДК
4. ДДДО
5. ДДДР
6. ДДЕД

заменив буквы на цифры

1. 0000
2. 0001
3. 0002
4. 0003
5. 0004
6. 0010
…

Полученная запись — это числа, записанные в пятеричной системе счисления в порядке возрастания.

Переведем первое слово, начинающееся с К в пятеричную систему

КДДД — 2000

2000 переведём его в десятичную систему счисления

2000₅ = 2 · 5³ + 0 · 5² + 0 · 5¹ + 0 · 5⁰ = 250₁₀

Не забываем, что порядковый номер числа всегда на единицу больше самого числа (есть слово номер 1, записывающееся как 0 (0000)), а это значит, что числу — 250, соответствует порядковый номер — 251.

Ответ: 251

Ниже на пяти языках программирования записан рекурсивный алгоритм F.

Запишите подряд без пробелов и разделителей все числа, которые будут напечатаны на экране при выполнении вызова F(9). Числа должны быть записаны в том же порядке, в котором они выводятся на экран.

Ответ: ________

procedure F(n: integer);
begin
if n 0 then
begin
write(n);
F(n — 3);
F(n div 3)
end
end;

После каждого вызова на экран выводится значение параметра функции, если будет выполнено условие n2.

Запишем все вызовы в виде дерева.

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

Теперь перепишем по порядку все выводимые на экран числа: 9631231

Ответ: 9631231

В терминологии сетей TCP/IP маской сети называется двоичное число, определяющее, какая часть IP-адреса узла сети относится к адресу сети, а какая – к адресу самого узла в этой сети. Обычно маска записывается по тем же правилам, что и IP-адрес, – в виде четырёх байтов, причём каждый байт записывается в виде десятичного числа. При этом в маске сначала (в старших разрядах) стоят единицы, а затем с некоторого разряда – нули. Адрес сети получается в результате применения поразрядной конъюнкции к заданному IP-адресу узла и маске.

Например, если IP-адрес узла равен 231.32.255.131, а маска равна 255.255.240.0, то адрес сети равен 231.32.240.0.

Для узла с IP-адресом 57.179.208.27 адрес сети равен 57.179.192.0. Каково наибольшее возможное количество единиц в разрядах маски?

Ответ: ________

Адрес подсети получается в результате поразрядной конъюнкции (перемножение двоичных разрядов) между IP-адресом и маской. В маске сначала идут все единицы, которые выделяют часть IP-адреса, которая соответствует адресу подсети, а затем – все нули, которые соответствуют части, в которой записан адрес компьютера.

В нашем случае, первые два байта IP-адреса (57.179.) совпадают с адресом сети (57.179.), следовательно, маска сети для этих двух байт состоит только из единиц (11111111.11111111.).

Четвёртый байт IP-адреса отличен от нуля (27), но при этом четвёртый байт адреса сети равен нулю (0), значит, нужно положить четвёртый байт маски равным нулю (11111111.11111111.хххххх.00000000).

Рассмотрим третий байт IP-адреса и адреса сети в двоичной системе счисления:

208₁₀ = 1101 0000₂
192₁₀ = 1100 0000₂

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

Получаем, что третий слева байт маски равен 1110 0000.

Маска сети 11111111.11111111.1110000

Теперь посчитаем единицы: 8 + 8 + 3 = 19

Ответ: 19

При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 10 символов. В качестве символов используют прописные буквы латинского алфавита, т.е. 26 различных символов. В базе данных для хранения каждого пароля отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит.

Определите объём памяти (в байтах), необходимый для хранения данных о 50 пользователях. В ответе запишите только целое число – количество байт.

Ответ: ________

По условию задания, в пароле могут быть использовано 26 символов латинского алфавита.

Используем формулу N = 2ⁱ

26 = 2ⁱ

Поскольку 2^4 5, то для записи каждого из 26 символов необходимо 5 бит.

Для хранения всех 10 символов номера нужно 10 · 5 = 50 бит, но т. к. для записи используется целое число байт, то берём ближайшее не меньшее значение, кратное восьми.

56 = 7 · 8 бит (7 байт).

Для хранения всех сведений о 50 пользователях используется

50 · 7 = 350 байт, то есть для хранения данных о 50 пользователях необходимо выделить 350 байт.

Ответ: 350

Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду сместиться на (a, b), где a, b – целые числа. Эта команда перемещает Чертёжника из точки с координатами (x, y) в точку с координатами (x + a, y + b).
Например, если Чертёжник находится в точке с координатами (4, 2), то команда сместиться на (2, −3) переместит Чертёжника в точку (6, −1).

Цикл
ПОВТОРИ число РАЗ
последовательность команд 
КОНЕЦ ПОВТОРИ

означает, что последовательность команд будет выполнена указанное число раз (число должно быть натуральным).

Чертёжнику был дан для исполнения следующий алгоритм (число повторений и величины смещения в первой из повторяемых команд неизвестны):

НАЧАЛО
сместиться на (4, 6)
ПОВТОРИ … РАЗ
сместиться на (.., …)
сместиться на (4, -6)
КОНЕЦ ПОВТОРИ
сместиться на (-28, -22)
КОНЕЦ

В результате выполнения этого алгоритма Чертёжник возвращается в исходную точку. Какое наибольшее число повторений могло быть указано в конструкции «ПОВТОРИ … РАЗ»?

Ответ: ________

После выполнения команд сместиться на (4, 6) и сместиться на (–28, −22) Чертёжник окажется в точке с координатами (−24, −16).

После выполнения цикла Чертёжник переместится на n · (a + 4, b − 6).

От нас требуется, чтобы после выполнения программы Четрёжник вернулся в исходную точку.

Мы имеем два уравнения:

n · (a + 4) = 24
n · (b − 4) = 16

Переменные a, b и n должны быть целыми, причём n  1.
Следовательно, числа 24 и 16 должны быть кратны n.

Наибольшее, подходящее n равно 8.

Ответ: 8

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

Ответ: ________

Для начала определяем количество путей из города А в город Ж

Около каждого города будем записывать количество маршрутов из города А

В город Б ведет 1 маршрут

В город Д ведет 1 маршрут

В город Г ведут 2 маршрута из А и Д

В город В ведут 4 маршрута: 1 из А, 1 из Б и 2 из Г

В город Е ведёт 1 маршрут из Б

В город З ведут 1 маршрут из Д

В город Ж ведут 10 маршрутов: 1 из Е, 1 из Б, 4 из В, 2 из Г, 1 из Д и 1 из З

Теперь будем определять пути из пункта Ж в пункт М, зная что попасть из пункта А в пункт Ж можно 10 способами.

Попасть в пункт И через пункт Ж можно только 10 способами

В пункт К ведут 10 маршрутов из И

В пункт Л ведут 10 маршрутов из И

В город М ведут 20 маршрутов: 10 маршрутов из К, 10 маршрутов из Л.

Ответ: 20

Значение арифметического выражения: 49¹⁰ + 7³⁰ − 49 – записали в системе счисления с основанием 7. Сколько цифр «6» содержится в этой записи?

Ответ: ________

Приведем наше арифметическое выражение к следующему виду:

49¹⁰ + 7³⁰ − 49,
7³⁰ + 7²⁰ − 7².

Зная, что число 7ⁿ записывается в системе счисления с основанием 7, как единица и n нулей, а выражение 7ⁿ-7^k записывается в системе счисления с основанием 7, как n-k шестерок и kнулей, найдем количество цифр «6» в этой записи.

7³⁰ — дает нам в системе счисления с основанием 7 — одну 1 и 30 нулей.
выражение 7²⁰ − 7² — дает нам 20-2=18 — шестерок и 2 нуля.

Следовательно, выражение 7²⁰ − 7², содержит 18 шестерок.

Ответ: 18

В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для обозначения логической операции «И» – символ «&».
В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.

Какое количество страниц (в сотнях тысяч) будет найдено по запросу Бабочка & Гусеница?
Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.

Ответ: ________

Что мы имеем:

Бабочка (Б) — 22
Гусеница (Г) — 40
Трактор (T) — 24
Т | Б | Г — 66
Т & Г — 12
Т & Б — 0
Б & Г — Х

Представим нашу задачу в виде кругов Эйлера

Теперь все становится ясно

Х = T + Б + Г − (Т | Б | Г) − (Т & Г) = 24 + 40 + 22 − 66 − 12 = 8

Ответ: 8

Для какого наибольшего целого числа А формула

((x ≤ 9) → (x⋅x ≤ A)) ⋀ ((y⋅y ≤ A) → (y ≤ 9))

тождественно истинна, то есть принимает значение 1 при любых целых неотрицательных x и y?

Ответ: ________

Разделим наше выражение на 2 части:

((x ≤ 9) → (x⋅x ≤ A)) = B
((y⋅y ≤ A) → (y ≤ 9)) = C

получаем

B ⋀ C

Главное действие в исходном выражении — это коньюнкция. Конъюнкция истинна, когда все операнды истинны. Т.е. в задаче обе части B и C должны быть истинными.

Рассмотрим часть B:

если в выражении (x ≤ 9), х  9, то часть В будет истинна независимо от А. Значит значение числа А влияет на решение только при выполнении условия:

x ≤ 9

теперь для того чтобы в части В, выражение было истинным, надо чтобы (x⋅x ≤ A) было истинным:

x⋅x ≤ A

(импликация 1 → 1 = 1)

таким образом получаем:

x ≤ 9
x² ≤ A

при любых x

Но нам нам необходимо найти наибольшее возможное А, поэтому надо ограничить его значения сверху, а данная часть выражения ограничивает только снизу:

возьмем наименьшее натуральное: x = 1, тогда A ≥ 1

Рассмотрим часть С:

если выражение (y ≤ 9) действительно истинно (т.е. y ≤ 9), то часть С будет истинна независимо от А. Значит значение числа А влияет на решение только при выполнении условия:

y  9

теперь для того чтобы в части C, выражение было истинным, надо чтобы (y⋅y ≤ A) было ложным:

y⋅y  A

(импликация 0 → 0 = 1)

таким образом получаем:

y 9
y²  A

при любых y

данная часть выражения ограничивает значения А сверху:

возьмем наименьшее возможное по условию натуральное: y = 10, тогда A А меньшее 100 — это А = 99

Ответ: 99

В программе используется одномерный целочисленный массив A с индексами от 0 до 9. Значения элементов равны 3, 0, 4, 6, 5, 1, 8, 2, 9, 7 соответственно, т.е. A[0] = 3, A[1] = 0 и т.д.
Определите значение переменной c после выполнения следующего фрагмента этой программы (записанного ниже на разных языках программирования).

Ответ: ________

Разберем задачу по циклам

1) i = 1
A[i-1]=A[0]=3
A[i]=A[1]=0
Условие A[i-1] A[i] выполняется (3 0)
Следовательно:
с = 0 + 1 = 1
элементы массива А[0] и A[1] меняются местами
A[0]=0
A[1]=3

2) i = 2
A[i-1]=A[1]=3
A[i]=A[2]=4
Условие A[i-1] A[i] не выполняется (3 не может быть больше 4)

3) i = 3
A[i-1]=A[2]=4
A[i]=A[3]=6
Условие A[i-1] A[i] не выполняется (4 не может быть больше 6)

4) i = 4
A[i-1]=A[3]=6
A[i]=A[4]=5
Условие A[i-1] A[i] выполняется (6 5)
Следовательно:
с = 1 + 1 = 2
элементы массива А[3] и A[4] меняются местами
A[3]=5
A[4]=6

5) i = 5
A[i-1]=A[4]=6
A[i]=A[5]=1
Условие A[i-1] A[i] выполняется (6 1)
Следовательно:
с = 2 + 1 = 3
элементы массива А[4] и A[5] меняются местами
A[4]=1
A[5]=6

6) i = 6
A[i-1]=A[5]=6
A[i]=A[6]=8
Условие A[i-1] A[i] не выполняется (6 не может быть больше 8)

7) i = 7
A[i-1]=A[6]=8
A[i]=A[7]=2
Условие A[i-1] A[i] выполняется (8 2)
Следовательно:
с = 3 + 1 = 4
элементы массива А[6] и A[7] меняются местами
A[6]=2
A[7]=8

8) i = 8
A[i-1]=A[7]=8
A[i]=A[8]=9
Условие A[i-1] A[i] не выполняется (8 не может быть больше 9)

9) i = 9
A[i-1]=A[8]=9
A[i]=A[9]=7
Условие A[i-1] A[i] выполняется (9 7)
Следовательно:
с = 4 + 1 = 5
элементы массива А[8] и A[9] меняются местами
A[8]=7
A[9]=9

Значение переменной c после выполнения фрагмента этой программы равно 5

Ответ: 5

Ниже на пяти языках программирования записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа: L и M. Укажите наименьшее число x, при вводе которого алгоритм печатает сначала 5, а потом 7.

Ответ: ________

Проанализируем работу программы. Для этого в качестве х возьмем произвольное двоичное число. Например 25.

1) while x0 do — пока х0 выполняем тело цикла (250)
M := M + 1 увеличиваем М на 1 (0 + 1 = 1)
x mod 2 0 при делении 25 на 2 получаем остаток 1, условие выполняется
L := L + 1 увеличиваем L на 1 (0 + 1 = 1)
x := x div 2 целочисленное деление нашего числа x = 25 на 2 (25/2 = 12)

2) while x0 do — пока х0 выполняем тело цикла (120)
M := M + 1 увеличиваем М на 1 (1 + 1 = 2)
x mod 2 0 при делении 12 на 2 остатка нет, условие не выполняется
L остается прежним (1)
x := x div 2 целочисленное деление нашего числа x = 12 на 2 (12/2 = 6)

3) while x0 do — пока х0 выполняем тело цикла (60)
M := M + 1 увеличиваем М на 1 (2 + 1 = 3)
x mod 2 0 при делении 6 на 2 остатка нет, условие не выполняется
L остается прежним (1)
x := x div 2 целочисленное деление нашего числа x = 6 на 2 (6/2 = 3)

4) while x0 do — пока х0 выполняем тело цикла (30)
M := M + 1 увеличиваем М на 1 (3 + 1 = 4)
x mod 2 0 при делении 3 на 2 получаем остаток 1, условие выполняется
L := L + 1 увеличиваем L на 1 (1 + 1 = 2)
x := x div 2 целочисленное деление нашего числа x = 3 на 2 (3/2 = 1)

5) while x0 do — пока х0 выполняем тело цикла (10)
M := M + 1 увеличиваем М на 1 (4 + 1 = 5)
x mod 2 0 при делении 1 на 2 получаем остаток 1, условие выполняется
L := L + 1 увеличиваем L на 1 (2 + 1 = 3)
x := x div 2 целочисленное деление нашего числа x = 25 на 2 (1/2 = 0)

условие while x0 больше не выполняеется

L = 3
M = 5

Данный алгоритм печатает на выходе количество единиц в двоичной записи числа х и количество всех цифр в этой записи. (25₁₀ = 11001₂)

Получается, что по условию задачи, нужно найти наименьшее семизначное двоичное число х, в записи которого присутствует пять единиц (L = 5, M=7). Это число 1001111₂ = 79₁₀.

Ответ: 79

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

Ответ: ________

Программа выведет на экран сумму R+M, их значения зависят от функции F(х) — если результат функции ≤ R, то R и M будут изменены (R станет равным результату функции, а M — аргументу).

Функция F вычисляется по формуле 2*(x*x-1)*(x*x-1)+27 или 2x⁴ — 4x² + 29

Найдем минимумальное значение функции 2x⁴ — 4x² + 29 для х от -20 до 20

Чем больше по модулю значение х, тем больше будет результат функции (кроме |х|=1)

F(-1) = 2-4+29 = 27 — минимум

F(0) = 29

F(1) = 2-4+29 = 27 — минимум

Т.к. в цикле идет проверка F(t) ≤ R, то выбираем второй минимум: F(1)=27

Вывод:
после выполнения цикла М=1, R=27. Следовательно, M+R=28

Ответ: 28

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

1. Прибавить 1
2. Прибавить 2
3. Умножить на 3

Первая из них увеличивает число на экране на 1, вторая увеличивает его на 2, третья умножает на 3.
Программа для исполнителя М17 – это последовательность команд.
Сколько существует таких программ, которые преобразуют исходное число 2 в число 12 и при этом траектория вычислений программы содержит числа 8 и 10? Траектория должна содержать оба указанных числа.
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 24, 26.

Ответ: ________

Искомое количество программ будет равно произведению количества программ, которые получают из числа 2 число 8, на количество программ, получающих из числа 8 число 10, и на количество программ, получающих из числа 10 число 12.

Эту задачу удобно решать с конца.

Число 12 из числа 10 можно получить двумя способами (10+1+1; 10+2).

Число 10 из числа 8 можно получить двумя способами (8+1+1; 8+2).

Остается узнать количество способов получения числа 8 из числа 2. Начнем свои рассуждения с числа 3, т.к. двойка это начальное число. Тройку можно получить только одним способом – прибавив 1. Четверку получим двумя способами – прибавив единицу к тройке или добавив двойку к двойке и т. д.

Запишем эти рассуждения в следующем виде:

R(2) = 1
R(3) = R(2) = 1
R(4) = R(3) + R(2) = 2
R(5) = R(4) + R(3) = 2 + 1 = 3
R(6) = R(5) + R(4) + R(2) = 3 + 2 + 1 = 6
R(7) = R(6) + R(5) = 6 + 3 = 9
R(8) = R(7) + R(6) = 9 + 6 = 15

Таким образом, количество программ, удовлетворяющих условию задачи равно

R(2) * R(8) * R(10) * R(12) = 1 * 15 * 2 * 2 = 60.

Ответ: 60

Сколько существует различных наборов значений логических переменных x₁, x₂, …x₇, y₁, y₂, …y₇, которые удовлетворяют всем перечисленным ниже условиям?

(¬x₁ ∨ y₁) → (¬x₂ ∧ y₂) = 1
(¬x₂ ∨ y₂) → (¬x₃ ∧ y₃) = 1
…
(¬x₆ ∨ y₆) → (¬x₇ ∧ y₇) = 1

В ответе не нужно перечислять все различные наборы значений переменных x₁, x₂, …x₇, y₁, y₂, …y₇, при которых выполнена данная система равенств.
В качестве ответа Вам нужно указать количество таких наборов.

Ответ: ________

Рассмотрим 1-е уравнение и построим для него таблицу истинности:

(¬x₁ ∨ y₁) → (¬x₂ ∧ y₂) = 1

Итого 7 решений дает одно первое уравнение. Столько же решений будет и у отдельно взятого второго уравнения:

Теперь добавим ко второй таблице истинности x₁ и y₁ (переменные, которые присутствуют в первом уравнении):

Вывод: второе уравнение увеличивает количество наборов на 3, следовательно, каждое следующее уравнение, тоже будет увеличивать количество наборов на 3.

Итого: 7 + 5 ⋅ 3 = 22

Ответ: 22

На обработку поступает натуральное число, не превышающее 109. Нужно написать программу, которая выводит на экран максимальную цифру числа, кратную 5. Если в числе нет цифр, кратных 5, требуется на экран вывести «NO». Программист написал программу неправильно. Ниже эта программа д ля Вашего удобства приведена на пяти языках программирования.

Напоминание: 0 делится на любое натуральное число.

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

1. Напишите, что выведет эта программа при вводе числа 132.
2. Приведите пример такого трёхзначного числа, при вводе которого программа выдаёт верный ответ.
3. Найдите все ошибки в этой программе (их может быть одна или
несколько). Известно, что каждая ошибка затрагивает только одну строку
и может быть исправлена без изменения других строк. Для каждой ошибки:
1) выпишите строку, в которой сделана ошибка;
2) укажите, как исправить ошибку, т.е. приведите правильный вариант строки.

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

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

1. Программа выведет число 2.

2. Программа выдаёт правильный ответ, например, для числа 135.

Замечание. Программа работает неправильно из-за неверной начальной инициализации и неверной проверки отсутствия цифр, кратных 5. Соответственно, программа будет выдавать верный ответ, если вводимое число содержит хотя бы одну цифру, кратную 5, и наибольшая цифра числа, кратная 5, не равна 0 и не меньше младшей (крайней правой) цифры числа (или просто стоит последней).

3. В программе есть две ошибки.

Первая ошибка. Неверная инициализация ответа (переменная maxDigit).

Строка с ошибкой:
maxDigit := N mod 10;

Верное исправление:
maxDigit := -1;

Вместо -1 может быть использовано любое число, меньшее 0.

Вторая ошибка. Неверная проверка отсутствия цифр, кратных 5.

Строка с ошибкой:
ifmaxDigit = 0 then

Верное исправление:
ifmaxDigit = -1 then

Вместо -1 может быть другое число, меньшее 0, которое было положено в maxDigit при исправлении первой ошибки, или проверка, что maxDigit

Ответ: 22