Отправляет email-рассылки с помощью сервиса Sendsay

RFpro.ru: Консультации по информатике

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 293 RSS
←   Декабрь 2017   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


За последние 60 дней ни разу не выходила


Сайт рассылки: http://rusfaq.ru/issues/8/19/228
Открыта: 17-04-2009

Автор
Калашников О.А.

Статистика

293 подписчиков
0 за неделю
←   Все выпуски   →

RFpro.ru: Консультации по информатике


РАССЫЛКИ ПОРТАЛА RFPRO.RU

Лучшие эксперты в разделе

Коцюрбенко Алексей aka Жерар
Статус: Мастер-Эксперт
Рейтинг: 674
∙ повысить рейтинг » 		CradleA
Статус: Профессионал
Рейтинг: 207
∙ повысить рейтинг » 		mklokov
Статус: 6-й класс
Рейтинг: 42
∙ повысить рейтинг »

∙ Информатика

Номер выпуска:328
Дата выхода:20.12.2017, 16:15
Администратор рассылки:Андреенков Владимир (Академик)
Подписчиков / экспертов:23 / 23
Вопросов / ответов:1 / 1

Консультация # 192087: Здравствуйте! У меня возникли сложности с двумя задачами, прикрепленными в файле. Я видел решение этих задач в консультациях 191925 и 191927, но я не понял их, так как ни разу не решал задачи такого типа. Поэтому ,пожалуйста, распишите решения подробно. ...

Консультация # 192087:

Здравствуйте! У меня возникли сложности с двумя задачами, прикрепленными в файле. Я видел решение этих задач в консультациях 191925 и 191927, но я не понял их, так как ни разу не решал задачи такого типа. Поэтому ,пожалуйста, распишите решения подробно.

Дата отправки: 10.12.2017, 15:58
Вопрос задал: Валерий (Посетитель)
Всего ответов: 1
Страница онлайн-консультации »

Консультирует Коцюрбенко Алексей aka Жерар (Мастер-Эксперт):

Здравствуйте, Валерий!

Рассмотрим задачу №191925.

1. В первом условии имеем функцию (x1→x2)⊕(x3→x4) четырёх переменных (x1, x2, x3 и x4). Необходимо определить, при каких значениях этих переменных функция равна 1. Для этого составим таблицу значений функции для всех наборов переменных:

(для облегчения расчётов внесём в неё также значения промежуточных выражений x1→x2 и x3→x4).
Из таблицы видно, что функция принимает единичное значение на наборах 0010, 0110, 1000, 1001, 1011 и 1110. Поскольку функция не зависит от остальных переменных (x5 ... x10), то каждый из этих наборов представляет собой на самом деле несколько наборов. Например, 0010, это наборы 0010000000, 0010000001, 0010000010,... 0010111110, 0010111111 - всего 64 набора, в которых переменные x5...x10 принимают все возможные значения.
Для облегчения работы (чтобы не писать слишком много) используют сокращённую запись, в которой вместо двух наборов, отличающихся только значением одной переменной (0 или 1), используют один, в котором эта переменная имеет значение x (означающее "0 или 1"). То есть, вместо 0010000000 и 0010000001 можно записать 001000000x, вместо 001000000x и 001000001x пишем 00100000xx и т.д. Соответственно, те шесть наборов, на которых наша функция принимает значение 1, запишутся как 0010xxxxxx, 0110xxxxxx, 1000xxxxxx, 1001xxxxxx, 1011xxxxxx и 1110xxxxxx. Если же объединить первый и второй наборы (они отличаются только значен ием переменной x2), а также третий и четвёртый (отличающиеся значением переменной x4), то решение примет вид 0x10xxxxxx, 100xxxxxxx, 1011xxxxxx и 1110xxxxxx.
Определить количество наборов при такой форме записи решения очень просто: каждый компонент записи задаёт 2k наборов, где k - число значений x в этом компоненте. То есть в данном случае 0x10xxxxxx и 100xxxxxxx задают по 27 = 128 наборов, а 1011xxxxxx и 1110xxxxxx - по 26 = 64, а всего 128 + 128 + 64 + 64 = 384 набора.

2. Если бы рассмотренное условие было единственным, это и было бы решением задачи. Но необходимо учесть и остальные. Поэтому рассмотрим условие 2.
В общем случае следовало бы повторить для него все те же действия, что и для первого условия (составить таблицу значений функции, определить наборы, на которых она равна 1 и записать и х в сокращённой форме). Но в данном случае мы видим, что соответствующая функция (x3→x4)⊕(x5→x6) отличается от предыдущей только используемыми переменными (x3, x4, x5 и x6 вместо x1, x2, x3 и x4 соответственно, то есть номера переменных отличаются на 2). Следовательно, множество наборов переменных, удовлетворяющих этому условию, можно получить путём сдвига всех значений из предыдущего решения (0x10xxxxxx, 100xxxxxxx, 1011xxxxxx и 1110xxxxxx) вправо на 2: xx0x10xxxx, xx100xxxxx, xx1011xxxx и xx1110xxxx - также 384 набора.

3. Таким образом, имеется множество наборов, удовлетворяющих первому условию, и аналогичное множество наборов, удовлетворяющих второму условию. Множество наборов, удовлетворяющих обоим у словиям, является, очевидно, пересечением этих двух множеств. Можно было бы записать все 384 набора переменных из первого решения и все 384 из второго, а затем найти общие, но это очень долго и неудобно. Гораздо быстрее и проще выполнить операцию пересечения непосредственно над сокращёнными записями. Определим, по каким правилам она будет выполняться.
Пусть у нас имеется функция одной переменной x, тогда множеством наборов переменных, на которых она принимает некоторое значение, может быть либо {0}, либо {1}, либо {0,1} (в используемой сокращённой форме записи им соответствуют 0, 1 и x). Пересечения этих множеств определяются по стандартным правилам: {0}∩{0} = {0}∩{0,1} = 0, {1}∩{1} = {1}∩{0,1} = 1, {0,1}∩{0,1} = {0,1}, {0}∩{1} = ∅ (пустое множество). Таким образом, операцию "пересечения" над значениями 0, 1 и x можно задать таблицей:

(знак "-" означает, что пересечения нет). В случае нескольких переменных операция "пересечения" выполняется "поразрядно" - над каждой из переменных.
Теперь найдём пересечение двух наборов: {0x10xxxxxx, 100xxxxxxx, 1011xxxxxx, 1110xxxxxx}∩{xx0x10xxxx, xx100xxxxx, xx1011xxxx, xx1110xxxx} = {0x10xxxxxx∩xx0x10xxxx, 0x10xxxxxx∩xx100xxxxx, 0x10xxxxxx∩xx1011xxxx, 0x10xxxxxx∩xx1110xxxx, 100xxxxxxx∩xx0x10xxxx, 100xxxxxxx∩xx100xxxxx, 100xxxxxxx∩xx1011xxxx, 100xxxxxxx∩xx1110xxxx, 1011xxxxxx∩xx0x10xxxx, 1011xxxxxx∩xx100xxxxx, 1011xxxxxx∩xx1011xxxx, 1011xxxxxx∩xx1110xxxx, 1110xxxxxx∩xx0x10xxxx, 1110xxxxxx∩xx100xxxxx, 1110xxxxxx∩xx1011xxxx, 1110xxxxxx∩xx1110xxxx} = {∅, 0x100xxxxx, 0x1011xxxx, ∅, 100x10xxxx, ∅, ∅, ∅, ∅, ∅, ∅, 1 01110xxxx, ∅, 11100xxxxx, 111011xxxx, ∅} = {0x100xxxxx, 0x1011xxxx, 100x10xxxx, 101110xxxx, 11100xxxxx, 111011xxxx} - это решение задаёт 64+32+32+16+32+16=192 набора.

4. Точно также функция (x5→x6)⊕(x7→x8) из третьего условия отличается лишь используемыми переменными (x5, x6, x7 и x8 вместо x3, x4, x5 и x6 соответственно). Поэтому множество наборов переменных, удовлетворяющих третьему условию, запишется как xxxx0x10xx, xxxx100xxx, xxxx1011xx и xxxx1110xx. Найдём его пересечение с уже найденным множеством: {0x100xxxxx, 0x1011xxxx, 100x10xxxx, 101110xxxx, 11100xxxxx, 111011xxxx}∩{xxxx0x10xx, xxxx100xxx, xxxx1011xx, xxxx1110xx} = {0x100xxxxx∩xxxx0x10xx, 0x100xxxxx∩xxxx100xxx, 0x100xxxxx∩xxxx1 011xx, 0x100xxxxx∩xxxx1110xx, 0x1011xxxx∩xxxx0x10xx, 0x1011xxxx∩xxxx100xxx, 0x1011xxxx∩xxxx1011xx, 0x1011xxxx∩xxxx1110xx, 100x10xxxx∩xxxx0x10xx, 100x10xxxx∩xxxx100xxx, 100x10xxxx∩xxxx1011xx, 100x10xxxx∩xxxx1110xx, 101110xxxx∩xxxx0x10xx, 101110xxxx∩xxxx100xxx, 101110xxxx∩xxxx1011xx, 101110xxxx∩xxxx1110xx, 11100xxxxx∩xxxx0x10xx, 11100xxxxx∩xxxx100xxx, 11100xxxxx∩xxxx1011xx, 11100xxxxx∩xxxx1110xx, 111011xxxx∩xxxx0x10xx, 111011xxxx∩xxxx100xxx, 111011xxxx∩xxxx1011xx, 111011xxxx∩xxxx1110xx} = {0x100x10xx, ∅, ∅, ∅, ∅, ∅, ∅, 0x101110xx, ∅, 100x100xxx, 100x1011xx, ∅, ∅, 1011100xxx, 10111011xx, ∅, 11100x10xx, ∅, ∅, ∅, ∅, ∅, ∅, 11101110xx} = {0x100x10xx, 0x101110xx, 100x100xxx, 100x1011xx, 1011100xxx, 10111011xx, 11100x10xx, 11101110xx} - это решение задаёт 16+8+1 6+8+8+4+8+4=72 набора.

5. Наконец, последнему условию будет удовлетворять множество наборов переменных xxxxxx0x10, xxxxxx100x, xxxxxx1011 и xxxxxx1110. Его пересечение с уже найденным множеством {0x100x10xx, 0x101110xx, 100x100xxx, 100x1011xx, 1011100xxx, 10111011xx, 11100x10xx, 11101110xx}∩{xxxxxx0x10, xxxxxx100x, xxxxxx1011, xxxxxx1110} = {0x100x10xx∩xxxxxx0x10, 0x100x10xx∩xxxxxx100x, 0x100x10xx∩xxxxxx1011, 0x100x10xx∩xxxxxx1110, 0x101110xx∩xxxxxx0x10, 0x101110xx∩xxxxxx100x, 0x101110xx∩xxxxxx1011, 0x101110xx∩xxxxxx1110, 100x100xxx∩xxxxxx0x10, 100x100xxx∩xxxxxx100x, 100x100xxx∩xxxxxx1011, 100x100xxx∩xxxxxx1110, 100x1011xx∩xxxxxx0x10, 100x1011xx∩xxxxxx100x, 100x1011xx∩xxxxxx1011, 100x1011xx∩xxxxxx1110, 1011100xxx∩xxxxxx0x10, 1011100xxx∩xxxxxx100x, 1011100xxx∩xxxxxx1011, 1011100xxx∩xxxxxx1110, 10111011xx∩xxxx xx0x10, 10111011xx∩xxxxxx100x, 10111011xx∩xxxxxx1011, 10111011xx∩xxxxxx1110, 11100x10xx∩xxxxxx0x10, 11100x10xx∩xxxxxx100x, 11100x10xx∩xxxxxx1011, 11100x10xx∩xxxxxx1110, 11101110xx∩xxxxxx0x10, 11101110xx∩xxxxxx100x, 11101110xx∩xxxxxx1011, 11101110xx∩xxxxxx1110} = {∅, 0x100x100x, 0x100x1011, ∅, ∅, 0x1011100x, 0x10111011, ∅, 100x100x10, ∅, ∅, ∅, ∅, ∅, ∅, 100x101110, 1011100x10, ∅, ∅, ∅, ∅, ∅, ∅, 1011101110, ∅, 11100x100x, 11100x1011, ∅, ∅, 111011100x, 1110111011, ∅} = {0x100x100x, 0x100x1011, 0x1011100x, 0x10111011, 100x100x10, 100x101110, 1011100x10, 1011101110, 11100x100x, 11100x1011, 111011100x, 1110111011} даёт решение задачи - 8+4+4+2+4+2+2+1+4+2+2+1=36 наборов.

Задача №191927 решается аналогично (единственное замечание - переменные следует расположить в следующем порядке: x1, y1, x2, y2, x3, y3, x4, y4, x5, y5, x6, y6).

Консультировал: Коцюрбенко Алексей aka Жерар (Мастер-Эксперт)
Дата отправки: 20.12.2017, 05:37
Рейтинг ответа:

НЕ одобряю 0 одобряю!

Оценить выпуск | Задать вопрос экспертам

главная страница  |  стать участником  |  получить консультацию
техническая поддержка

Дорогой читатель!
Команда портала RFPRO.RU благодарит Вас за то, что Вы пользуетесь нашими услугами. Вы только что прочли очередной выпуск рассылки. Мы старались. Пожалуйста, оцените его. Если совет помог Вам, если Вам понравился ответ, Вы можете поблагодарить автора - для этого в каждом ответе есть специальные ссылки. Вы можете оставить отзыв о работе портале. Нам очень важно знать Ваше мнение. Вы можете поближе познакомиться с жизнью портала, посетив наш форум, почитав журнал, который издают наши эксперты. Если у Вас есть желание помочь людям, поделиться своими знаниями, Вы можете зарегистрироваться экспертом. Заходите - у нас интересно!
МЫ РАБОТАЕМ ДЛЯ ВАС!
В избранное