VK's Weekly test Informatics Variant 13 by Eugene Jobs

Source  180226 Информатика - Пробный вариант №13.pdf

 

Решение задачи 23 Демо версии ЕГЭ Информатика 2017 Методом отображений vs Метод битовых масок vs Информатик БУ Видео

Задача 23 Демо версии ЕГЭ Информатика 2017 хорошо известна  ролик
Информатика БУ  https://www.youtube.com/watch?v=uQtANwb_-Qs
Информатик БУ не использует дистрибутивность импликации по
отношению к конъюнкции, что влечет за собой меньшую прозрачность в получении результата.

   Строим диаграмму  генерации матрицы на основании уравнения
                         (x1 => (x2^y1)) ^ (y1 => y2) =1

******************************

  Метод битовых масок
******************************

В силу дистрибутивности импликации по отношению к конъюнкции

(x1 => (x2^y1))^(y1 => y2) =1  <=> (x1=>x2)^(x1=>y1)^(y1=>y2) =1
(x2 => (x3^y2))^(y2 => y3) =1  <=> (x2=>x3)^(x2=>y2)^(y2=>y3) =1
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 

и так для каждого уравнения
Получаем эквивалентную и хорошо известную систему

(x1 => x2)^(x2 => x3)^ . . . . . ^(x5 => x6) = 1
(y1 => y2)^(y2 => y3)^ . . . . . ^(y5 => y6) = 1
(x1 => y1)^(x2 => y2)^ . . . . . ^(x5 => y5)^(x6 => y6) = 1

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

x1 x2 x3 x4 x5 x6 

-------------------
1  1   1  1  1  1   1
0  1   1  1  1  1   2
0  0   1  1  1  1   3     Число конкатенаций 
0  0   0  1  1  1   4     каждого кортежа {x} строка номер j
0  0   0  0  1  1   5     c кортежами {y} ( с 1-го по j - ый)
0  0   0  0  0  1   6
0  0   0  0  0  0   7  Total = 1+2+3+ . . . .+7 = 28

y1 y2 y3 y4  y5 y6 

-------------------
1  1   1  1  1  1
0  1   1  1  1  1
0  0   1  1  1  1
0  0   0  1  1  1
0  0   0  0  1  1   x4=>y4 = False
0  0   0  0  0  1
0  0   0  0  0  0

Решение одной системы уравнений в булевских переменных Методом отображений вместо битовых масок ВК 09.02.18

     Конвертируем в эквивалетную систему

     (x1=>x2)^(y1=>y2) =1
     (x2=>x3)^(y2=>y3) =1
     . . . . . . . . .
     (x5=>x6)^(y5=>y6) =1
     x1=>y1 =1
  
    и применим метод отображений

  

Решение задач №13 и 14 из "Сколько различных решений имеет система уравнений.pdf" с помощью битовых масок versus Метод Отображений

   Источник 1Сколько различных решений имеет система уравнений.pdf

   13)  Запишем эквивалентную систему

          (x4 => x3) => (x2=>x1) =1
          (x6 => x5) => (x4=>x3) =1
          (x8 => x7) => (x6=>x5) =1
          (x10 => x9) => (x8=>x7) =1


         z1 = x2 =>x1
         z2 = x4 =>x3
         z3 = x6 =>x5
         z4 = x8 => x7
         z5 = x10 => x9


         z2 => z1 =1
         z3 => z2 =1
         z4 => z3 =1
         z5 => z4 =1


         z5  z4 z3 z2 z1
        ============
         1    1   1   1   1          3^5
         0    1   1   1   1          3^4
         0    0   1   1   1          3^3
         0    0   0   1   1          3^2
         0    0   0   0   1          3^1
         0    0   0   0   0          3^0


       Результат   (3^6 - 1) /2  =364

       14)

          (x3 => x4) => (x1=>x2) =1
          (x5 => x6) => (x3=>x4) =1
          (x7 => x8) => (x5=>x6) =1
          (x9 => x10) => (x7=>x8) =1
          (x1=>x2) => (x9 => x10) =1

         z1 = x1 =>x2
         z2 = x3 =>x4
         z3 = x5 =>x6
         z4 = x7 => x8
         z5 = x10 => x9


         z2 => z1 =1
         z3 => z2 =1
         z4 => z3 =1
         z5 => z4 =1
         z1 => z5 =1

        z5 z4 z3 z2 z1
       ===========
        1   1   1   1  1                3^5
        0   0   0   0  0                3^0

       Результат   243 + 1 = 244
         

       Метод отображений для задачи 14

 
   Сравни с https://www.youtube.com/watch?v=KNpJsN3smQg

Системный подход к решению задачи 18 (ДЕЛ(х,А)) ЕГЭ Информатика 2018

Наиболее сложный случай , когда уравнение сводится к импликации :-
    D(X,A)^D(X,S) => D(X,N) =1
Тогда A(min) есть  произведение простых делителей Q(j) числа N, начиная с наименьшего, которые не являются делителями S с учетом их кратности для N. Если Q есть общий делитель кратности N1 для N и кратности  N2
N2 для S то cмотри детали
http://egekp.unoforum.pro/?1-4-0-00000169-000-0-0-1515330726

Notice1
======
Допустим N и S содержат общий простой  делитель Q причем 
N в степени N1, а  S  в степени N2 и  N1 > N2.
Пусть А содержит Q в степени N3.  Пусть Х произвольное натуральное, делящееся на А и Q^N2. Импликация выше означает, что если  Х 
делится A и на Q^N2, то Х делится на Q^N1. 
Если N2 < N1, то в этом случае N3 (должно быть) >= N1. Чтобы минимизировать А необходимо положить  N3=N1

   138)

        D(A) => (¬D(28) v D(42)) = 1
        ¬D(A) v ¬D(28) v D(42) = 1
       D(A)^D(28) => D(42) = 1

        28 = 7*2*2
        42 = 7*2*3

     A(min) = 3
      
   139)

      (D(A)^D(21) => D(18)

      18 = 2*3^2
      21 = 3*7
 
  Per Notice1

    A(min) =18


  140)
          ((D(A) ^ ¬D(36)) => ¬D(12) = 1
          ¬D(A) v D(36) v ¬D(12) = 1
          ¬((D(A)^D(12)) v D(36) =`1
          D(A)^D(12) => D(36) = 1

 
  Per Notice1

           12 = 2^2*3
           36 = 2^2*3^2

  A(min) = 9


141)
        (D(A) ^ ¬D(50)) => ( ¬D(18) v D(50)) =1
        ¬D(A) v D(50) v ¬D(18) = 1
        ¬(D(A) v D(18)) v D(50) = 1
        D(A)^D(18)  => D (50) = 1

       18=2*3^2
       50=2*5^2
       5 имеет кратность 2

  A(min) = 25

  

   144)

     (D(A) ^ D(24) ^ ¬D(16)) => ¬D(A) = 1

    ¬D(A) v ¬D(24) v D(16) = 1

     (D(A)^D(24)) => D(16) = 1

        24 = 3*2^3

        16 = 2^4

    Per Notice1

      

     A(min) = 16

   145)

     (D(34) ^ ¬D(51)) => (¬D(A) v D(51)) = 1
     ¬D(34) v D(51) v ¬D(A) v D(51) = 1
    ¬((D(A)^D(34)) v D(51) = 1
    D(A)^D(34) => D(51) =1

    17 - общий делитель

     34 =17*2
     51 =17*3

   A(min) =3

146)

  ((D(15)^¬D(21)) =>(¬D(A) v ¬D(15)) =1
  ¬D(15) v D(21) v ¬D(A) v ¬D(15) =1
  ¬((D(15)^D(A)) v D(21) = 1
 D(15)^D(A) => D(21) = 1

    15=3*5
    21=3*7

 A(min) = 7

  131)

  (D(A)^D(12)) => (D(42) v ¬D(12)) = 1
  ¬D(A) v ¬D(12) v D(42) v ¬D(12) = 1
  ¬(D(A)^D(12)) v D(42) = 1
 D(A)^D(12) => D(42) = 1

 12 = 2^2*3
 42 = 2*3*7

 В этом случае N2(=2) > N1(=1) - нет проблемы

 A(min) = 7

*****************************************************************************
Можно ли доверять сайту https://bingoschool.ru/ege/informatics/
*****************************************************************************

Рассмотрим пример 8 из https://bingoschool.ru/ege/informatics/tasks/18/     и предложенное решение 

     (D(X,A)^¬D(X,100)) => (¬D(X,18) v D(X,100) ) = 1

     Решение

     ¬D(Х,A) v D(Х,100) v ¬D(Х,18) v D(Х,100) = 1
     ¬((D(Х,A)^D(Х,18)) v D(Х,100) = 1
     D(Х,A)^D(Х,18) => D(Х,100) =1
    
        18 = 2*3^2
        100 = 2^2*5^2

    Таким образом А = 100
    Контр-пример   к 50  есть 450
     
      
  
References
1. http://информатика23.рф/
2. http://egekp.unoforum.pro/?1-4-0-00000169-000-0-0-1515330726

Решение задачи №10 и 11 из "Сколько различных решений имеет система уравнений.pdf" Методом Отображений

Источник   1Сколько различных решений имеет система уравнений.pdf

Задача 11

   Преобразуем систему к эквивалентной

     (x2=>x1)^(y2=>y1) =1
     (x2=>x3)^(y2=>y3) =1
     (x4=>x3)^(y4=>y3) =1
     (x4=>x5)^(y4=>y5) =1
             x1^y1 =1
    

  Задача 10

 

      (x1 v x2)^(y1 v y2) =1
      (x2 v x3)^(y2 v y3) =1
      (x3 v x4)^(y3 v y4) =1
      (x4 v x5)^(y4 v y5) =1
              x1 v y1 =0

    

Векторная алгебра в R^3 и что такое векторное произведение в контексте задач типа 14 ЕГЭ Математика 2018

    Что такое вектоное произдение ?

    Решаем в несколько строк , выбрав удобную систему координат

   

Последняя выкладка

              

Следующий пример

   Решение

  

Следующий пример