Если коротко, то битовые маски наиболее гибкий инструмент
для решения систем уравнений в булевых переменных
в сравнении с методом, предложенным на нескольких известных сайтах
runet'a. Не буду скрывать, следующее видео :-
https://www.youtube.com/watch?v=MDL5Mym5Aac
прозводит сильное впечатление в сравнении с некоторыми роликами
на YouTube по той же задаче. Таже техника эффектно применена здесь :-
https://www.youtube.com/watch?v=uQtANwb_-Qs
https://www.youtube.com/watch?v=MDL5Mym5Aac
задача 23 демо версии ЕГЭ 2017. Битовые маски для (x} и {y}
конкатенируются следуя логике конкретного случая.
In meantime mister "BU" seems to be the best IT trainer on the Net,
either he wants it to happen or doesn't. He deserves words "Thank you Sir"
uncountable number of times.
******************************************************************************
Рассмотрим пример на сайте Константина Полякова
Вариант 9 задача 23 (№ 476) с печально известным номером 23
******************************************************************************
Найти количество решений системы
{x1,...,x9,y1,....,y9}
((x1 ≡ y1) → (x2 ≡ y2)) ∧ (x1 → x2) ∧ (y1 → y2) = 1
((x2 ≡ y2) → (x3 ≡ y3)) ∧ (x2 → x3) ∧ (y2 → y3) = 1
...
((x8 ≡ y8) → (x9 ≡ y9)) ∧ (x8 → x9) ∧ (y8 → y9) = 1
********************************
Начнем с системы вида :-
********************************
(x1 → x2) ∧ (y1 → y2) = 1
(x2 → x3) ∧ (y2 → y3) = 1
...
(x8 → x9) ∧ (y8 → y9) = 1
Решения этой системы описываются хорошо известными масками -
x1 x2 x3 x4 x5 x6 x7 x8 x9
----------------------------------------
1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1
0 0 1 1 1 1 1 1 1
0 0 0 1 1 1 1 1 1
0 0 0 0 1 1 1 1 1
0 0 0 0 0 1 1 1 1
0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0
y1 y2 y3 y4 y5 y6 y7 y8 y9
-----------------------------------------
1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1
0 0 1 1 1 1 1 1 1
0 0 0 1 1 1 1 1 1
0 0 0 0 1 1 1 1 1
0 0 0 0 0 1 1 1 1
0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0
Будем называть первую матрицу X,a вторую Y
Для j от 2 до 9 рассмотрим конкатенации
"X" ->"Y" и "Y" -> "X"
Мы получим 2*(10-j) кортежей, делающих следуюшую имликацию
ложной ((x[j-1] ≡ y[j-1])) → (x[j] ≡ y[j])
**************************************
Например, при j=3 получаем
**************************************
Таким образом при j=3 имеем 2*7 = 14 кортежей где x2≡y2 is True
и x3≡y3 is False. Тогда (x2 ≡ y2) → (x3 ≡ y3) есть 1 -> 0 ,
что ложно по определению
****************************************************************************
Это означает, для каждого j из набора [2.3.4,...,9]
2*(10 - j) кортежей должно быть удалено из множества решений усеченной
системы системы уравнений. В духе ЕГЭ пишем на паскале
s:= 0 ;
for j:=2 to 9 do
begin
s:= s + (10-j) ;
end ;
s= 2*s ;
writeln (s) ;
72
Таким образом, ответ 10*10 - 72 = 28
Метод отображений для той же задачи
https://www.youtube.com/watch?v=2n0qJ4VSaAQ
x9y9 даст 28
для решения систем уравнений в булевых переменных
в сравнении с методом, предложенным на нескольких известных сайтах
runet'a. Не буду скрывать, следующее видео :-
https://www.youtube.com/watch?v=MDL5Mym5Aac
прозводит сильное впечатление в сравнении с некоторыми роликами
на YouTube по той же задаче. Таже техника эффектно применена здесь :-
https://www.youtube.com/watch?v=uQtANwb_-Qs
https://www.youtube.com/watch?v=MDL5Mym5Aac
задача 23 демо версии ЕГЭ 2017. Битовые маски для (x} и {y}
конкатенируются следуя логике конкретного случая.
In meantime mister "BU" seems to be the best IT trainer on the Net,
either he wants it to happen or doesn't. He deserves words "Thank you Sir"
uncountable number of times.
******************************************************************************
Рассмотрим пример на сайте Константина Полякова
Вариант 9 задача 23 (№ 476) с печально известным номером 23
******************************************************************************
Найти количество решений системы
{x1,...,x9,y1,....,y9}
((x1 ≡ y1) → (x2 ≡ y2)) ∧ (x1 → x2) ∧ (y1 → y2) = 1
((x2 ≡ y2) → (x3 ≡ y3)) ∧ (x2 → x3) ∧ (y2 → y3) = 1
...
((x8 ≡ y8) → (x9 ≡ y9)) ∧ (x8 → x9) ∧ (y8 → y9) = 1
********************************
Начнем с системы вида :-
********************************
(x1 → x2) ∧ (y1 → y2) = 1
(x2 → x3) ∧ (y2 → y3) = 1
...
(x8 → x9) ∧ (y8 → y9) = 1
Решения этой системы описываются хорошо известными масками -
x1 x2 x3 x4 x5 x6 x7 x8 x9
----------------------------------------
1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1
0 0 1 1 1 1 1 1 1
0 0 0 1 1 1 1 1 1
0 0 0 0 1 1 1 1 1
0 0 0 0 0 1 1 1 1
0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0
y1 y2 y3 y4 y5 y6 y7 y8 y9
-----------------------------------------
1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1
0 0 1 1 1 1 1 1 1
0 0 0 1 1 1 1 1 1
0 0 0 0 1 1 1 1 1
0 0 0 0 0 1 1 1 1
0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0
Будем называть первую матрицу X,a вторую Y
Для j от 2 до 9 рассмотрим конкатенации
"X" ->"Y" и "Y" -> "X"
Первая :- X Y --------------------------- ------------------------------ | | | | --------------------------- ------------------------------ j | | | --------------------------- ------------------------------ . . . . | j+1 | --------------------------- ------------------------------ j+2 | ------------------------------ | . . . . . | --------------------------- ------------------------------ 10 | 10 | --------------------------- ------------------------------ Запись {j} из X с записями {j+1,j+2,. . . 10} из Y и вторые конкатенации из Y в X :- Y X --------------------------- ------------------------------ | | | | --------------------------- ------------------------------ j | | | --------------------------- ------------------------------ . . . . | j+1 | --------------------------- ------------------------------ j+2 | ------------------------------ | . . . . . | --------------------------- ------------------------------ 10 | 10 | --------------------------- ------------------------------Запись { j } из Y с записями {j+1,j+2,. . . 10} из X
Мы получим 2*(10-j) кортежей, делающих следуюшую имликацию
ложной ((x[j-1] ≡ y[j-1])) → (x[j] ≡ y[j])
**************************************
Например, при j=3 получаем
**************************************
x1 x2 x3 x4 x5 x6 x7 x8 x9 ---------------------------------------- 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 => 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 y1 y2 y3 y4 y5 y6 y7 y8 y9 ----------------------------------------- 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 <= 0 0 0 0 1 1 1 1 1 <= 0 0 0 0 0 1 1 1 1 <= 0 0 0 0 0 0 1 1 1 <= 0 0 0 0 0 0 0 1 1 <= 0 0 0 0 0 0 0 0 1 <= 0 0 0 0 0 0 0 0 0 <= Vice Versa множество :- y1 y2 y3 y4 y5 y6 y7 y8 y9 ----------------------------------------- 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 => 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 x1 x2 x3 x 4 x5 x6 x7 x8 x9 ---------------------------------------- 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 <= 0 0 0 0 1 1 1 1 1 <= 0 0 0 0 0 1 1 1 1 <= 0 0 0 0 0 0 1 1 1 <= 0 0 0 0 0 0 0 1 1 <= 0 0 0 0 0 0 0 0 1 <= 0 0 0 0 0 0 0 0 0 <=****************************************************************************
Таким образом при j=3 имеем 2*7 = 14 кортежей где x2≡y2 is True
и x3≡y3 is False. Тогда (x2 ≡ y2) → (x3 ≡ y3) есть 1 -> 0 ,
что ложно по определению
****************************************************************************
Это означает, для каждого j из набора [2.3.4,...,9]
2*(10 - j) кортежей должно быть удалено из множества решений усеченной
системы системы уравнений. В духе ЕГЭ пишем на паскале
s:= 0 ;
for j:=2 to 9 do
begin
s:= s + (10-j) ;
end ;
s= 2*s ;
writeln (s) ;
72
Таким образом, ответ 10*10 - 72 = 28
Метод отображений для той же задачи
https://www.youtube.com/watch?v=2n0qJ4VSaAQ
x9y9 даст 28
******************************************************************** Рассмотрим 11 из https://inf-ege.sdamgia.ru/test?theme=264
*******************************************************************
(¬(x1 ≡ y1) → ¬(x2 ≡ y2))∧(x1 → x2)∧(y1 → y2) = 1 (¬(x2 ≡ y2) → ¬(x3 ≡ y3))∧(x2 → x3)∧(y2 → y3) = 1 ... (¬(x8 ≡ y8) → ¬(x9 ≡ y9))∧(x8 → x9)∧(y8 → y9) = 1 где ¬ есть логическое отрицание ******************************** Начнем с системы вида :- ******************************** (x1 → x2)∧(y1 → y2) = 1 (x2 → x3)∧(y2 → y3) = 1 ... (x8 → x9)∧(y8 → y9) = 1 Решения этой системы описываются хорошо известными масками - x1 x2 x3 x4 x5 x6 x 7 x8 x9 ---------------------------------------- 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 ==> 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 y1 y2 y3 y4 y5 y6 y7 y8 y9 ----------------------------------------- 1 1 1 1 1 1 1 1 1 <== 0 1 1 1 1 1 1 1 1 <== 0 0 1 1 1 1 1 1 1 <== 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 Будем называть первую матрицу X,a вторую Y Первая строка из Х конкатенирутся с первой строкой из Y ¬(x1 ≡ y1) is False (0) => ¬(x1 ≡ y1) → ¬(x2 ≡ y2) is True Вторая строка из Х конкатенирутся с первой,второй строками из Y ¬(x2 ≡ y2) is False (0) => ¬(x2 ≡ y2) → ¬(x3 ≡ y3) is True Третья строка из Х конкатенирутся первой,второй,третьей строками из Y ¬(x3 ≡ y3) is False (0) => ¬(x3 ≡ y3) → ¬(x4 ≡ y4) is True . . . . . Восьмая строка из Х конкатенирутся с первой,второй,третьей,...,восьмой строками из Y ¬(x8 ≡ y8) is False (0) => ¬(x8 ≡ y8) → ¬(x9 ≡ y9) is True Всего решений 1+2+3+4+5+6+7+8 = (8*9)/2 = 56/2 = 28
No comments:
Post a Comment