Тренаж по информатике: «разбор полётов» Богомолова О.Б., Усенков Д.Ю.
1. Снова Фано Для кодирования последовательности символов, состоящей из букв К, И, Н, О, используется неравномерный двоичный код, удовлетворяющий условию Фано. При этом для буквы К использован код 0, а для буквы И – код 11. Требуется определить наименьшую возможную суммарную длину всех кодовых слов указанных букв. 1) 8 2) 9 3) 10 4) 11
1. Снова Фано Решение Условие Фано: Закодированное сообщение можно однозначно декодировать с начала, если никакое кодовое слово не является началом другого кодового слова. Для проверки на соответствие кодов условию Фано нужно попарно сравнивать между собой коды по следующим правилам: когда длина обоих сравниваемых кодов совпадает, проверяется равенство этих кодов: если один код совпадает с другим, то такая пара кодов неправильна (не удовлетворяет условию Фано); когда длина сравниваемых кодов различна, более короткий код записывается под более длинным с выравниванием обоих кодов по левому краю: если все знаки более короткого кода совпадают с соответствующими знаками в начале более длинного кода, то такая пара кодов неправильна (не удовлетворяет условию Фано).
1. Снова Фано Решение Будем подбирать коды для буквы Н, перебирая возможные двоичные числа с возрастающей длиной (чтобы получить наименьшую возможную суммарную длину кодов). Код буквы К Код буквы И Предполагаемый код буквы Н Комментарий 0 11 1 1 Нельзя, так как совпадает с началом кода буквы И 00 00 Нельзя – код буквы К совпадает с его началом 01 01 Нельзя – код буквы К совпадает с его началом 10 10 Допустимый код (не совпадает с двузначным кодом буквы И, а код буквы К не совпадает с его началом)
1. Снова Фано Решение Предположим, что первый код найден. Удастся ли найти код для оставшейся буквы О? (Коды, которые не подошли для буквы Н, можно сразу отбросить, так как код буквы О должен удовлетворять тем же требованиям при сравнении с кодами букв К и И.) 000, 001, 010, 011 000, 001, 010, 011 Нельзя – код буквы К совпадает с его началом Код буквы К Код буквы И Код буквы Н Предполагаемый код буквы О Комментарий 0 11 10 11 11 Нельзя – совпадает с кодом буквы И 100, 101 100, 101 Нельзя – код буквы Н совпадает с его началом 110, 111 110, 111 Нельзя – код буквы Н совпадает с его началом Далее с увеличением числа разрядов в предполагаемом коде буквы О будет сохраняться та же тенденция: ни один код не пригоден.
Код буквы К Код буквы И Код буквы Н Предполагаемый код буквы О Комментарий 0 11 100 1. Снова Фано Решение Причина: выбрав для буквы Н код 10, мы «закрыли» возможность дальнейшего расширения нашей кодовой системы. Поэтому вместо кода 10 придется выбрать для буквы Н более длинный код, – например, 100. Повторим попытку поиска кода для буквы О: 101 101 Допустимый код (не совпадает с трехзначным кодом буквы Н, а коды букв К и И не совпадают с его началом)
1. Снова Фано Решение Решение найдено: Суммарная длина этих кодов (в знаках): 1 + 2 + 3 + 3 = 9. К И Н О 0 11 100 101 Ответ: 2).
2. Крупинки истинности Для таблицы истинности функции F известны значения нескольких ячеек: Каким выражением может быть F ? 1) x1 /\ x2 /\ x3 /\ ¬x4 2) x1 \/ x2 \/ x3 \/ ¬x4 3) ¬x1 /\ x2 /\ ¬x3 /\ x4 4) ¬x1 \/ x2 \/ ¬x3 \/ x4 x1 x 2 x3 x4 F 1 0 1 0 1 1 1 0 0 0 1 0
Решение Каждый из предложенных вариантов ответа проверяется на соответствие таблице истинности. Если при указанных в ней значениях переменных хоть в какой-нибудь строке не получается требуемое значение F, то данное значение не подходит. Если для всех строк таблицы истинности и всех имеющихся в ней значений переменных требуемое значение F получается, то считается, что такое логическое выражение может соответствовать таблице и является решением задачи. 2. Крупинки истинности
Решение Для логической операции И «критическим» значением является нуль : если хотя бы одна переменная равна нулю, то всё выражение тоже равно нулю. Для логической операции ИЛИ «критическим» значением является единица : если хотя бы одна переменная равна единице, то всё выражение тоже равно единице. Поэтому для ускорения решения достаточно при проверке вариантов ответа проверять только часть строк таблицы истинности : если логическое выражение составлено из операций И, то прежде всего проверяем строки таблицы истинности, в которых F = 1 : если хоть в одной ячейке, соответствующей «обычной» переменной, записан 0, а в ячейке, соответствующей переменной с НЕ, записана 1, то такой вариант ответа можно отбросить; если логическое выражение составлено из операций ИЛИ, то прежде всего проверяем строки таблицы истинности, в которых F = 0 : если хоть в одной ячейке, соответствующей «обычной» переменной, записана 1, а в ячейке, соответствующей переменной с НЕ, записан 0, то такой вариант ответа можно отбросить. 2. Крупинки истинности
Решение Предполагаемый правильный ответ – выражение ¬x1 /\ x2 /\ ¬x3 /\ x4. Проверяем его для оставшихся строк с F = 0 и убеждаемся, что им оно тоже соответствует (так как x2 = 0 ). Ответ: 3). 2. Крупинки истинности № Выражение Операция Проверяем строки таблицы: Комментарий Вывод 1) x1 /\ x2 /\ x3 /\ ¬ x4 И с F = 1 x 3 = 0 (строка 1) Не годится 2) x1 \/ x2 \/ x3 \/ ¬ x4 ИЛИ с F = 0 x 1 = 1 (строка 3) Не годится 3) ¬ x1 /\ x2 /\ ¬ x3 /\ x4 И с F = 1 всё соответствует 4) ¬ x1 \/ x2 \/ ¬ x3 \/ x4 ИЛИ с F = 0 X 4 = 1 (строка 4) Не годится
3. Сколько единиц? Определите наименьшее пятизначное восьмеричное число, двоичная запись которого содержит 3 единицы. (В ответе записать только само число, без индекса системы счисления.)
Решение Чем правее в двоичном числе записаны единицы, тем это число меньше. Вообще в любой системе счисления в наименьшем числе чем больше цифра, тем правее она должна стоять в записи числа (т.е. попадать в самые младшие разряды). И наоборот, в наибольшем числе самые большие цифры должны быть записаны ближе к левому краю (в старших разрядах). Наименьшее двоичное число из трех единиц равно 111 2. Оно соответствует однозначному восьмеричному числу (7). Нам же нужно пятизначное восьмеричное. Чтобы найти наименьшее пятизначное восьмеричное число, нужно, оставляя как можно больше единиц справа, «отодвигать» только одну единицу влево, записывая после нее нули, пока не получится двоичное число, которое после перевода в восьмеричную систему счисления будет иметь 5 цифр. Такое число будет наименьшим из возможных. 3. Сколько единиц?
Решение Каждой восьмеричной цифре соответствуют три двоичных цифры. Значит, нужно «оттаскивать» единицу влево, пока она только-только не «вылезет» в пятую триаду (будет в ней самым младшим битом): 3. Сколько единиц? 1 7 8 1 1 0 3 8 1 0 1 0 0 0 8 1 1 0 1 0 1 0 0 8 1 0 1 0 1 0 0 8 1 0 0 1 8 10003 8 Ответ: 10003.
4. «Эх, дороги…» Между городами А, Б, В, Г, Д построены дороги, протяжённость которых указана в таблице. Отсутствие числа в ячейке означает, что прямой дороги между соответствующими городами нет. Найти длину кратчайшего пути между пунктами А и Д, проходящего через пункт В, если передвигаться можно только по указанным дорогам. А Б В Г Д А 3 1 2 15 Б 3 4 2 В 1 4 3 Г 2 2 2 Д 15 3 2
Решение Строим по таблице граф дорог: 4. «Эх, дороги…» А Б В Г Д 3 1 2 15 4 2 3 2 Дальше нужно искать все возможные пути из А в Д, отбрасывая те, которые не проходят через город В, подсчитывать их длину и искать путь с минимальным значением его суммарной длины.
Решение Чтобы ускорить решение, можно сразу исключить пути «в обход» города В: 4. «Эх, дороги…» А Б В Г Д 3 1 2 15 4 2 3 2 А Б В Г Д 3 1 4 3 2 Получили совсем простой граф (тем более, что в город Г теперь вообще ни одна дорога из А не идет, так что путь ГД тоже можно исключить).
Решение В этом графе только два возможных пути: АБВД с длиной 3 + 4 + 3 = 10, АВД с длиной 1 + 3 = 4. Кратчайший из них – путь АВД. Его длина равна 4. Ответ: 4. 4. «Эх, дороги…» А Б В Д 3 1 4 3
5. «Однорукий бандит» Автомат получает на вход трёхзначное число. По этому числу формируется новое число по следующим правилам. 1. Складываются первая и вторая, а затем – вторая и третья цифры исходного числа. 2. Полученные два числа записываются друг за другом подряд в порядке возрастания. Пример. Исходное число: 176. Полученные числа: 1+7 = 8, 7+6 = 13. Результат: 813. Найдите наибольшее исходное число, для которого автомат выдаст результат 815.
Решение Определим, как можно «разрезать» результирующее число на два, вычисленных автоматом. Сумма двух десятичных цифр (которые могут быть равны от 0 до 9) может равняться от 0 (0+0) до 18 (9+9). Если пытаться разделить число 815 как 81 и 5, то первое из этих чисел не соответствует этому возможному диапазону значений сумм цифр, а числа записаны не по возрастанию. Поэтому остается только один вариант: число 815 как 8 и 15. 5. «Однорукий бандит»
Решение Посмотрим, какие цифры могут давать такие суммы: 8 = 0+8, 1+7, 2+6, 3+5, 4+4; 15 = 9+6, 8+7. 5. «Однорукий бандит» По условию, одна сумма – это сумма первой и второй цифры исходного числа, а вторая – это сумма второй и третьей цифры. Значит, вторая цифра должна повторяться в обеих суммах. Ищем такие две суммы в обеих «подборках» (для числа 8 и для числа 15). Это пары: 0+8 и 8+7; 1+7 и 8+7; 9+6 и 2+6. Им соответствуют числа (учитывая, что нуль не может быть записан самым первым – тогда он был бы незначащим, а число – двузначным): 780, 178, 871, 962, 269 (везде повторяющаяся цифра стоит в середине). Среди них наибольшее – это число 962. Ответ: 962.
6. «Формула-1» в Excel Дан фрагмент электронной таблицы. Из ячейки C 3 в одну из ячеек столбца D была скопирована формула. После копирования значение этой формулы стало равным 100. В какую ячейку была скопирована формула? В ответе надо записать только номер строки, в которой находится эта ячейка. A B C D 1 5 13 2 6 12 3 7 11 = $B 3* A$4 4 8 10
Решение Сначала определим, как меняется формула при ее копировании в ячейки столбца D (с учетом абсолютной адресации): 6. «Формула-1» в Excel A B C D 1 5 13 2 6 12 3 7 11 4 8 10 = $B 3* A$4 = $B 1* B$4 = $B 2* B$4 = $B 3* B$4 = $B 4* B$4 Остается вычислить произведения и сверить их с требуемым. Впрочем, сразу видно, что 100 – это 10*10, а подходящая формула – только в ячейке D4 ( =$ B 4* B $4 ). Ответ: 4. ВАЖНО! В ответе надо записать только номер строки. Запись ответа в виде « D 4» при автоматической проверке ответов будет признана за ошибку!
7. Оцифровка аудио Выполнена квадро (4-канальная) звукозапись с частотой дискретизации 32 кГц и 16-битным разрешением. В результате получен файл размером 38 Мбайт, причем сжатие данных не производилось. Требуется приблизительно оценить, сколько времени (в минутах) производилась запись. В качестве ответа нужно указать ближайшее к полученному времени записи целое число минут.
Решение количество каналов записи – 4, частота – 32000 колебаний в секунду, разрешение – 16 бит, длительность – неизвестна ( t ); получаемый размер файла равен 38 Мбайт = 38 2 23 бит. Все величины обязательно преобразуются к одним и тем же размерностям. 4 32000 16 t = 38 2 23, откуда t = 155,648 (с). Полученное значение преобразуется в минуты и округляется до ближайшего целого : t = 155,648/60 2,594 3 минуты. Ответ : 3. 7. Оцифровка аудио
8. Parole, parole, parole … Сколько «слов» длины 7 символов, начинающихся с английской буквы, можно составить из букв S, И, R, П, Q ? Каждая буква может входить в «слово» несколько раз, а сами получаемые «слова» не обязательно должны быть осмысленными.
Решение 1) Определяем количество «слов», которые можно составить из указанных букв без учета первой буквы, на которую накладывается особое условие («только английская»), т.е. количество «слов» длиной 6 символов. Сопоставляем каждой букве цифру, например: S = 0, И = 1, R = 2, П = 3, Q = 4. Тем самым задача сводится к следующей: «сколько различных 6-разрядных чисел можно получить в пятеричной системе счисления». Количество таких чисел равно n m, где n – основание системы счисления, а m – количество разрядов. В нашем случае получается 5 6 = 15625 чисел («слов»). 2) Первая буква должна быть только английской. Английских букв у нас три. Для каждой из них возможно 15625 слов. Тогда общее количество слов равно 3 15625 = 46875. Ответ: 46875. 8. Parole, parole, parole …
9. «Эх, раз, еще раз!»… Имеется рекурсивный алгоритм F : procedure F(n: integer): integer; begin if n > 3 then F := F(n-1) + F(n-2) + F(n-3) else F := 2; end; Чему равно значение, вычисленное при вызове этой процедуры в виде F (6)?
Решение Рекурсия – это вызов функции или процедуры «самой из себя». При этом в каждом новом вызове вычисления внутри функции / процедуры производятся уже с соответствующим значением «внутренней» (формальной) переменной. Кроме того, в рекурсивной функции / процедуре обязательно должны быть и «конечные» условия, когда значение переменной определяется однозначно, без новых рекурсивных вызовов. В нашем случае это условие: if n > 3 then … else F := 2; 9. «Эх, раз, еще раз!»…
Решение 1) Самый первый вызов, для которого n = 6 : F (6) = F (6–1) + F (6–2) + F (6–3) = F (5) + F (4) + F (3) 2) Рекурсивный вызов F (5) : F (5) = F (5–1) + F (5–2) + F (5–3) = F (4) + F (3) + F (2) 3) Вызов F (4) : F (4) = F (4–1) + F (4–2) + F (4–3) = F (3) + F (2) + F (1) 4) Значения F (3), F (2) и F (1) – «конечные»: согласно «конечному» условию рекурсии, все они равны 2. 9. «Эх, раз, еще раз!»…
Решение Вычерчиваем схему этих вызовов в виде дерева: 9. «Эх, раз, еще раз!»… F (6) F (6) = F (5) + F (4) + F (3) F (4) + F (3) + F (2) F (3) + F (2) + F (1) 2 F (3) + F (2) + F (1) 2 2 2 2 2 2 2 2
Решение Расписываем схему этих вызовов в виде дерева: 9. «Эх, раз, еще раз!»… F (6) F (6) = F (5) + F (4) + F (3) F (4) + F (3) + F (2) F (3) + F (2) + F (1) 2 F (3) + F (2) + F (1) 2 2 2 2 2 2 2 2 F (6) = F (5) + F (4) + F (3) F (6) = F ( 4 ) + F (3) + F (2) + F ( 4 ) + F (3) F (5) F (6) = F (3) + F (2) + F (1) + F (3) + F (2) + F (3) + F (2) + F (1) + F (3) F (4) F (4) F (5)
Решение Подставляем в запись имеющиеся конечные значения: 9. «Эх, раз, еще раз!»… F (6) = F (3) + F (2) + F (1) + F (3) + F (2) + F (3) + F (2) + F (1) + F (3) F (5) F (5) F (5) 2 2 2 2 2 2 2 2 2 = 18 Ответ: 18.
10. «Призрак Оперы»… а также Firefox, Chrome и прочих В сетях TCP/IP маска сети – это двоичное число, меньшее 2 32 ; в маске сначала (в старших разрядах) записаны единицы, а затем с некоторого бита – нули. Маска определяет, какая часть IP-адреса относится к адресу подсети, а какая – к адресу конкретного компьютера (узла) в этой сети. Маска записывается по тем же правилам, что и IP-адрес, – в виде четырёх десятичных чисел, каждое из которых соответствует одному байту и отделяется от других точкой. Адрес сети получается в результате применения поразрядной конъюнкции к заданному IP-адресу узла и маске. Для узла с IP-адресом 167.57.252.220 адрес сети равен 167.48.0.0. Чему равен второй по счету слева байт маски? Ответ нужно записать в виде десятичного числа.
Решение Первый байт адреса сети совпадает с первым байтом IP-адреса, – значит, первый байт маски равен 11111111 2. Третий и четвертый байты адреса сети нулевые, значит, им соответствуют и нулевые байты маски. Второй по счету байт маски – самый «интересный», он должен содержать как единицы, так и нули. Поэтому в задаче требуется определить не всю маску, а только этот «ключевой» второй байт. 10. «Призрак Оперы»… а также Firefox, Chrome и прочих
Решение 1) Переводим оба «ключевых» числа в двоичную систему счисления: 57 10 = 111001 2, 48 10 = 110000 2. Обязательно дополняем полученные двоичные значения до 8 битов незначащими нулями слева. 57 10 = 00 111001 2, 48 10 = 00 110000 2. 10. «Призрак Оперы»… а также Firefox, Chrome и прочих
Решение 2) Записываем поразрядную конъюнкцию, в которой второй операнд неизвестен: 10. «Призрак Оперы»… а также Firefox, Chrome и прочих & 0 0 1 1 1 0 0 1 0 0 1 1 0 0 0 0 3) Сопоставляем первый операнд и результат: там, где биты в первом числе и в результате оба равны 1, соответствующий бит маски тоже равен 1; там, где бит в первом числе равен 1, а в результате равен 0, соответствующий бит маски равен 0; в маске все биты левее единичных битов тоже должны быть равны 1; все биты правее нулевых битов тоже должны быть равны 0. ? ? ? ? ? ? ? ? 1 1 0 1 1 0 0 0 11110000 2 = 240 10 Ответ: 240.
11. Четыре черненьких чумазеньких чертенка… Исполнитель Чертёжник перемещается по координатной плоскости. Основная команда Чертёжника – сместиться на ( a, b ), где a, b – целые числа. Она перемещает Чертёжника из точки с координатами ( x, y ) в точку с координатами ( x + a, y + b ). Например, из точки с координатами (3, 5) команда сместиться на (–2, 1) переместит Чертёжника в точку (1, 6). Цикл ПОВТОРИ число РАЗ последовательность команд КОНЕЦ ПОВТОРИ означает, что заданная последовательность команд будет выполнена указанное количество раз (значение должно быть натуральным).
11. Четыре черненьких чумазеньких чертенка… Чертёжник выполнял алгоритм, в котором количество повторений и оба смещения в первой из повторяемых команд неизвестны: НАЧАЛО сместиться на (–2, 3) ПОВТОРИ … РАЗ сместиться на (…, …) сместиться на (–2, –1) КОНЕЦ ПОВТОРИ сместиться на (–19, –18) КОНЕЦ При этом, выполнив этот алгоритм, Чертёжник вернулся в исходную точку. Какое наибольшее количество повторений могло быть указано в конструкции « ПОВТОРИ … РАЗ »?
Решение Обозначаем неизвестные значения переменными: k – количество повторений, x и y – неизвестные смещения в первой повторяемой команде. Составляем два отдельных уравнения движения: по координате x и по координате y и рассматриваем их в виде системы из двух уравнений. При этом каждое уравнение приравнивается нулю, так как Чертежник после выполнения всех перемещений вернулся в исходную точку. 1) Перемещение Чертежника по координате x : –2 + k ( x – 2) – 19 = 0. 2) Перемещение Чертежника по координате y : 3 + k ( y – 1) – 18 = 0. 11. Четыре черненьких чумазеньких чертенка…
Решение 3) Объединяем оба уравнения в систему: –2 + k ( x – 2) – 19 = 0, k ( x – 2) = 21, 3 + k ( y – 1) – 18 = 0; k ( y – 1) = 15. 4) На первый взгляд, данная система нерешаема: два уравнения и три неизвестных. Но в обоих случаях слева от знака равенства стоят произведения, один из сомножителей в которых один и тот же ( k ). Разложим числа справа от знаков равенства на простые сомножители (это можно сделать одним-единственным способом): 21 = 3 7 ; 15 = 3 5. В обоих получившихся произведениях тоже повторяется один и тот же сомножитель – 3. Значит, это и есть k. Определив, что k = 3, можно (если это потребуют в условии задачи) вычислить значения x и y. Нам же требуется только значение k. Ответ: 3. 11. Четыре черненьких чумазеньких чертенка…
12. «Эх, дороги» – 2 Дана схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л, М. По каждой дороге можно двигаться только в направлении, указанном стрелкой. Сколько возможно различных путей из города А в город Л ? А Б Ж В Г Д И Е К Л М
Решение Возможен способ решения без построения «дерева путей» (продемонстрирован ученицей 11«А» класса школы №1360 Анастасией Ремизовой). 12. «Эх, дороги» – 2 1) Возле города А записываем единицу. Это «стартовое» значение, поскольку один путь из А в М есть всегда. А Б Ж В Г Д И Е К Л М 1
Решение 2) Смотрим город Б. В этот узел графа входит только одна стрелка, которая идет от узла А со значением 1. Поэтому возле узла Б тоже записываем единицу. 12. «Эх, дороги» – 2 А Б Ж В Г Д И Е К Л М 1 1 3) То же с городами (узлами) В и Г – в них по единственной входящей стрелке «переносится» все та же единица из узла А. 1 1
Решение 4) Смотрим город Д. В него входит две стрелки. Одна идет из узла Б и «несет» оттуда единицу. Вторая аналогичным способом переносит единицу по стрелке из узла В. Итого в узле Д в сумме получаем значение 2 (1+1). 12. «Эх, дороги» – 2 А Б Ж В Г Д И Е К Л М 1 1 5) То же самое получаем для узла Е, куда по соответствующим двум стрелкам «приходят» единицы из узлов В и Г. 1 1 2 2
Решение 6) В узел Ж входят две стрелки. Одна (из узла Б ) «приносит» единицу, вторая (из узла Д ) «приносит» двойку. Итого в сумме получается 3 (1+2). 12. «Эх, дороги» – 2 А Б Ж В Г Д И Е К Л М 1 1 7) Для узла К аналогично – рядом с ним записываем 3 (1 по стрелке из узла Г плюс 2 по стрелке из узла Е ). 1 1 2 2 3 3 8) Для узла И две стрелки «принесут» из узлов Б и Г по 1 каждая, итого в сумме получаем 2. 2
Решение 9) В узел Л входит три стрелки. Первая, из узла Ж, «переносит» в Л тройку. Вторая, из узла К, «переносит» тоже тройку. Третья, из узла И, «переносит» в Л двойку. В сумме для Л получаем значение 8 (3+2+3). 12. «Эх, дороги» – 2 А Б Ж В Г Д И Е К Л М 1 1 1 1 2 2 3 3 2 8
Решение 10) Остается узел М. В него приходит три стрелки. Стрелка из узла Ж «приносит» в М тройку. Стрелка из узла К «приносит» в М тоже тройку. А стрелка из узла Л приносит в М восьмерку. В сумме для М получаем 14 (3+3+8). 12. «Эх, дороги» – 2 А Б Ж В Г Д И Е К Л М 1 1 1 1 2 2 3 3 2 8 14 Ответ: 14.
1 3. «Ищут пожарные, ищет милиция…» В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» – символ «&». В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет. Какое количество страниц (в тысячах) будет найдено по запросу Паскаль & Си & Бейсик ? Считаем, что все запросы выполнялись почти одновременно и набор страниц, содержащих искомые слова, за это время не изменялся. Запрос Кол-во найденных страниц, тыс. Паскаль & ( Си & Бейсик | Кобол ) 350 Паскаль & Кобол 187 Паскаль & Си & Бейсик & Кобол 48
Решение Паскаль & ( Си & Бейсик | Кобол ) 1 3. «Ищут пожарные, ищет милиция…» Паскаль & Си & Бейсик & Кобол раскрытие скобок добавление переменной согласно правилу поглощения Паскаль & Си & Бейсик | Паскаль & Кобол Паскаль & Си & Бейсик & Паскаль & Кобол выделение одинаковых частей выражения: Паскаль & Си & Бейсик и Паскаль & Кобол Паскаль & Си & Бейсик | Паскаль & Кобол Паскаль & Си & Бейсик & Паскаль & Кобол
Решение 1 3. «Ищут пожарные, ищет милиция…» Паскаль & Си & Бейсик | Паскаль & Кобол Паскаль & Си & Бейсик & Паскаль & Кобол замена: A = Паскаль & Си & Бейсик B = Паскаль & Кобол Тогда исходные запросы будут иметь вид: Паскаль & Си & Бейсик | Паскаль & Кобол Паскаль & Кобол ( Паскаль & Си & Бейсик ) & ( Паскаль & Кобол ) Паскаль & Си & Бейсик A | B (350 тыс.стр.), B (187 тыс.стр.), A & B (48 тыс.стр.), A – искомый.
Решение 1 3. «Ищут пожарные, ищет милиция…» Какое количество страниц (в тысячах) будет найдено по запросу A ( + )? Запрос Кол-во найденных страниц, тыс. A | B + + 350 B + 187 A & B 48 A B + + = 350; + = 187; = 48 + 48 + = 350; 48 + = 187 + = 302; = 139 + 139 = 302; = 163, + = 163 + 48 = 211. Следовательно, по запросу Паскаль & Си & Бейсик будет найдено 211 тыс.стр. Ответ: 211.
1 4. Вместо отрезков Элементами множества X являются натуральные числа. Известно, что выражение ( n Î {2,3,6,15,26,30}) → ((( n Î {1,3,6,12,15,35}) /\ ¬( n Î X )) → ¬( n Î {2,6,15,26,30})) истинно (принимает значение 1) при любом значении n. Требуется определить наименьшее возможное значение произведения элементов множества X.
Решение 1) Для упрощения решения заменим предложенные множества чисел буквами: {2,3,6,15,26,30} = A ; {1,3,6,12,15,35} = В. Тогда исходное уравнение можно записать так: ( n Î A ) → (( ( n Î B ) /\ ¬( n Î X )) → ¬( n Î A ) ) = 1 1 4. Вместо отрезков 2) Заменим утверждения о принадлежности n какому-либо множеству логическими переменными: ( n Î A ) = a ; ( n Î B ) = b ; ( n Î X ) = x. Получим выражение в виде: a → (( b /\ ¬ x ) → ¬ a ) = 1
Решение 3) Упрощаем полученное выражение и заменяем операцию следования на «ИЛИ» по правилу A → B = ¬ A B : a → (¬( b /\ ¬ x ) ¬ a ) = 1; ¬ a (¬( b /\ ¬ x ) ¬ a ) = 1. Применим операцию отрицания к содержимому скобок ( b /\ ¬ x ): ¬ a ( ¬ b x ) ¬ a ) = 1. Теперь все операции равноценны и скобки можно убрать: ¬ a ¬ b x ¬ a = 1. Повторяющийся аргумент ¬ a можно «поглотить»: ¬ a ¬ b x = 1. 1 4. Вместо отрезков
Решение 4) Вернемся к исходной записи переменных – аргументов, учитывая, что операция «НЕ» в данном случае означает непринадлежность тому или иному множеству: ( n A ) ( n B ) ( n Î X ) = 1 или ( n {2,3,6,15,26,30}) ( n {1,3,6,12,15,35}) ( n Î X ) = 1. 1 4. Вместо отрезков Пусть n = 1. Используется логическая операция ИЛИ, значит, для получения результата «ИСТИНА» достаточно истинности хотя бы одного из аргументов. Принадлежит ли число 1 первому множеству ({2,3,6,15,26,30})? Нет. Значит, условие ( n {2,3,6,15,26,30}) истинно. Этого достаточно для получения общего результата «ИСТИНА», поэтому значения всех остальных аргументов нам безразличны. Пусть n = 2. Это число принадлежит первому множеству {2,3,6,15,26,30}, значит, соответствующее условие ложно. C мотрим второй аргумент: ( n {1,3,6,12,15,35}). Этому множеству число 2 не принадлежит, значит, данное условие истинно, и этого нам достаточно. Пусть n = 3. Это число принадлежит и первому множеству ({2,3,6,15,26,30}), и второму ({1,3,6,12,15,35}). Следовательно, ложны и первое, и второе условия. В этом случае истинность результата может обеспечить только истинность третьего условия – ( n X ). Чтобы это условие было истинным, надо включить в состав множества X число 3. Выявлена следующая закономерность: если натуральное число n не входит хотя бы в одно из двух заданных нам множеств, то этого достаточно; если же n имеется в обоих заданных множествах, то это число n требуется включить в искомое множество X.
Решение 6) Теперь легко, сравнивая между собой элементы первого и второго множества, выписать всё множество X : {2, 3, 6, 15, 26, 30} {1, 3, 6, 12, 15, 35} X = { } 1 4. Вместо отрезков 3 3 3, 6 6 6, 15 15 15 7) Вычисляем произведение элементов множества X : 3 6 15 = 270. Ответ: 270.
1 5. Еще одна сумма элементов массива В программе описан одномерный целочисленный массив. Ниже представлен фрагмент программы, обрабатывающей этот массив: s:=0; n:=8; for i:=0 to n-4 do begin s:=s+A[i]-A[i+3] end; До выполнения этого фрагмента в массиве находились четырехзначные нечетные натуральные числа. Какое наименьшее значение может иметь переменная s после выполнения данной программы?
Решение 1) Расписываем вычисление суммы в виде одной строки, помня, что значение i меняется в цикле от 0 до 6 (т.е. до 10 – 4 ): s = 0 + A [0] – A [3] + A [1] – A [4] + A [2] – A [5] + A [3] – A [6] + + A [4] – A [7] + A [5] – A [8] + A [6] – A [9]. 1 5. Еще одна сумма элементов массива 2) Сокращаем одинаковые переменные (элементы массива), записанные со знаками «плюс» и «минус»: s = 0 + A [0] – A [3] + A [1] – A [4] + A [2] – A [5] + A [3] – A [6] + + A [4] – A [7] + A [5] – A [8] + A [6] – A [9]. Получаем : s = A [0] + A [1] + A [2] – A [7] – A [8] – A [9].
Решение 3) Получаемая сумма (разность) должна, по условию, иметь наименьшее значение. А элементы массива – это четырехзначные нечетные натуральные числа, т.е. числа в диапазоне от 1001 до 9999. Следовательно, элементы массива, которые записаны в выражении со знаком «плюс», должны быть наименьшими из возможных, а элементы массива со знаком «минус» должны быть наибольшими из возможных. Значит, нужно выбрать их следующими: A [0] = A [1] = A [2] = 1001, A [7] = A [8] = A [9] = 9999. 1 5. Еще одна сумма элементов массива 4) Вычисляем значение s при этих значениях элементов массива: s = 1001 + 1001 + 1001 – 9999 – 9999 – 9999 = 3 (1001 – 9999) = –26994. Ответ: –26994.
16. И снова числа Получив на вход число x, программа печатает два числа a и b. Определите наименьшее из чисел, при вводе которого алгоритм печатает сначала 2, а потом 357. var x, a, b: integer; begin readln(x); a := 0; b := 0; while x > 0 do begin a := a+1; b := b+(x mod 1000); x := x div 1000; end; writeln(a); write(b); end.
Решение 1) Проанализировав алгоритм, видим, что переменная a – это счетчик проходов цикла. В переменной b накапливается сумма… чего? Раньше в такой задаче имелись операторы b := b+(x mod 10); x := x div 10; и это означало вычисление суммы цифр. Теперь вместо константы 10 записана константа 1000, а значит, из числа выделяются сразу тройки цифр. 16. И снова числа 2) Поскольку в качестве значения переменной a выводится число 2, цикл выполнялся 2 раза. Следовательно, исходное число могло состоять из 4, 5 или 6 цифр, – только тогда мы получаем из него две триады цифр, одна из которых (левая) возможно, неполная. Поскольку требуется, чтобы число было наименьшим, левая «триада» должна состоять из одной цифры.
Решение 3) Обозначим неизвестные цифры исходного числа как a, b, с и d. Тогда первый проход цикла отделит цифры bcd, т.е. число 100 b + 10 с + d. Второй проход цикла добавит к сумме однозначное число (цифру) a. 16. И снова числа 4) Какой может быть эта единственная цифра a, чтобы число было наименьшим? Очевидно, a = 1. Тогда, зная, что итоговая сумма равна 357, сразу получаем, что bcd = 356. А всё первоначальное число x тогда равно 1356. Ответ: 1356.
17. Опять логика Сколько существует различных наборов значений логических переменных a 1, a 2,..., a 5, b 1, b 2,..., b 5, c 1, c 2,..., c 6, которые удовлетворяют перечисленным уравнениям? ( a 1 → a 2) /\ ( a 2 → a 3) /\ ( a 3 → a 4) /\ ( a 4 → a 5) = 1 ( b 1 → b 2) /\ ( b 2 → b 3) /\ ( b 3 → b 4) /\ ( b 4 → b 5) = 1 ( c 1 → c 2) /\ ( c 2 → c 3) /\ ( c 3 → c 4) /\ ( c 4 → c 5) = 1 a 1 /\ b 2 /\ c 3 = 0. В качестве ответа нужно указать количество таких наборов переменных.
Решение 1) Анализируем первое уравнение: ( a 1 → a 2) /\ ( a 2 → a 3) /\ ( a 3 → a 4) /\ ( a 4 → a 5) = 1. Составляем таблицу возможных значений переменных a 1, a 2,..., a 5, учитывая, что при логической операции «И» результат 1 обеспечивается только истинными значениями всех ее аргументов и что операция следования истинна в трех случаях: 1 → 1, 0 → 1 и 0 → 0. 17. Опять логика a 1 a 2 a 3 a 4 a 5 1 0 1 1 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0
Решение 2) Второе и третье уравнения полностью аналогичны первому, только имена переменных другие. Поэтому таблицы значений переменных будут такими же. 17. Опять логика b 1 b 2 b 3 b 4 b 5 c 1 c 2 c 3 c 4 c 5 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
Решение 3) Анализируем четвертое уравнение – «ключевое» : a 1 /\ b 2 /\ c 3 = 0. Строим для него таблицу истинности: 17. Опять логика a 1 b 2 c 3 Результат 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 Из нее нам требуются все строки, кроме последней.
Решение 4) Подсчитываем количества значений переменных, соответствующие таблице истинности четвертого уравнения. 17. Опять логика a 1 a 2 a 3 a 4 a 5 b 1 b 2 b 3 b 4 b 5 c 1 c 2 c 3 c 4 c 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 a 1 b 2 c 3 Кол-во наборов переменных 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 Итого: a 1 0 5 нулей 1 единица 5 b 2 0 4 нуля 2 единицы 4 c 3 0 3 нуля 3 единицы 3 = 60 5 4 3 = 60 5 2 3 = 30 5 2 3 = 30 1 4 3 = 12 1 4 3 = 12 1 2 3 = 6 60 + 60 + 30 + 30 + 12 + 12 + 6 = 210 Ответ: 210. a 1 b 2 c 3 Результат 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1
