Поляков ЕГЭ информатика 2015

Скачать сборник  К. Ю. Полякова по единому государственному экзамену по информатике можно на этой странице.

Читать этот сборник онлайн ниже:

Простейшие случаи

Задача 1. Найти число решений уравнения 1

(xx = x2)-(x2 = x3)-…-(x4 = x5) = 1.

Решение. Все “сомножители”2 имеют форму xf=xi+1, они должны быть равны 1. Это значит, что любые два соседних бита должны быть равны. Существует всего две таких цепочки:

000000, 111111.

Ответ: два решения.

Задача 2. Найти число решений уравнения (xx = x2)-(x2 = x3)-…-(x4 = x5) = 1.

Решение. Все “сомножители” имеют форму (Xi=xi+1), они должны быть равны 1. Это значит, что каждые два соседних бита должны быть различны, то есть нули и единицы в битовой цепочке чередуются. Существует всего две таких цепочки: 101010, 010101.

Ответ: два решения.

Задача 3. Найти число решений уравнения

Решение. Подобно рассмотренным выше задачам, все импликации (хх^х2), …, (х5-»х6) должны быть истинны. Импликация a ^ b ложна только при a = 1 и b = 0. Иными словами, если a = 1, то и b = 1. Поэтому, если битовый вектор X = x1 x2… x3 — решение данного уравнения, и в нем встретилась единица, то правее нее будут только единицы (сочетание “10” запрещено!). С другой стороны, если вектор удовлетворяет приведенному условию, он будет решением уравнения. Таким образом, уравнение имеет семь решений:

000000, 000001, 000011, 000111,

001111, 011111, 111111.

Каждое решение определяется тем, в какой позиции первый раз встречается единица: на 1-м, 2-м, …, 6-м месте или вообще не встречается.

Ответ: семь решений.

Задача 4. Найти число решений уравнения ((x1 + x2)^x3)-(( x2 + x3)^x4b..<( x4 + x5)^x6) = 1.

Решение. Все сомножители имеют форму (Xj’+x^) ^ xi+2, они должны быть равны 1, то есть недопустима импликация 1 ^ 0. Поскольку левая часть импликации — это логическая сумма двух соседних битов, а правая — следующий за ними бит, можно сделать вывод: слева от каждого нулевого бита (начиная с третьего) должны обязательно стоять два нуля. Этому условию удовлетворяют цепочки вида “все нули, потом — все единицы”: 111111, 011111, 001111, 000111,

000011, 000001, 000000.

Решение — битовый вектор

Пусть задана некоторая система логических (часто говорят — булевых) уравнений от переменных x-, x2, xn вида

F1( xi; x2,…, xN) = 1

FM(xl> x2’—>xN) = 1

Слово “логических” означает, что переменные x1tx2,…,xN — логические, то есть принимают значения 0 или 1, и выражения F1,…FM, зависящие от этих переменных, — тоже логические (множество их возможных значений — {0, 1}). Решением этой системы называется такой вектор значений X = x1x2…xN, при котором все уравнения обращаются в тождества. Поскольку все переменные, входящие в решение X, логические (0 или 1), все решение можно рассматривать как цепочку нулей и единиц длиной N. Такие цепочки называют битовыми цепочками, или битовыми векторами.

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

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

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

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

1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд
Загрузка...