Some issues related with Unified State Examination in Informatics in Russian Federation

Friday, February 9, 2018

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

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

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

    и применим метод отображений

Friday, January 19, 2018

Решение задач №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

Monday, January 15, 2018

Системный подход к решению задачи 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

Wednesday, January 3, 2018

Решение задачи №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

Wednesday, December 27, 2017

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

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

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

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

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

Решение

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

Wednesday, November 22, 2017

The hidden presence of CIDR (Classless Inter domain routing) in EGE Informatics (example of problem 12 from Trial KIM)

   Answer is obviously 3*8+2 = 26 due to 60 = 00111100 (binary)
   Thus we may place "11" in first two bits of fourth octet of network mask

   What means CIDR - See http://www.zvmpt.ru/IP_NGN/praktika/praktika_8.htm

On the other hand it is easy to see how 162.232.136.0/26 looks

Friday, November 10, 2017

Решение задачи 11 ЕГЭ Информатика Пробник 2 2018 ( inform20171106proba05+otvet.pdf ) 10.11.17

Оригинальный текст из http://bsoh1.tat.rusobr.ru/IKT/EGE/ege2016web/ege11.htm

66) (И. Тощенко) Дан рекурсивный алгоритм:

function F(n: integer): integer;

begin

if n < 5 then

F:= F(n*3) + F(n+3) + F(n+1)

else

F:= n div 2;

end;

Чему будет равно значение, вычисленное алгоритмом при выполнении вызова F(2)?

Source code

[boris@fedora26workstation GCC]$ cat recursEGE11DB.c
#include <stdio.h>
int cnt ;

int F(int n)
{
cnt++ ;
printf("%s%d%s\t","F(",n,")");

switch (cnt) {
case 1:
printf ("\n");
break;
case 4:
printf ("\n"); printf ("\t\t");
break;
case 7:
printf ("\n"); printf ("\t\t\t\t");
break;
case 10:
printf ("\n"); printf ("\t\t\t\t\t");
break;
default:
break;
}

if (n < 5) {
return F(3*n) + F(n+3) + F(n+1);
}
else {
return n / 2 ;
}
}

int main(void)
{
int res,n=2;
res = F(n);
printf("%s%d\n","Result = ",res);
}

*************************
Runtime output
*************************
[boris@fedora26workstation GCC]$ gcc -o recursEGE11DB recursEGE11DB.c
[boris@fedora26workstation GCC]$ strip recursEGE11DB
[boris@fedora26workstation GCC]$ ls -l recursEGE11DB
-rwxrwxr-x. 1 boris boris 6160 Nov 10 20:49 recursEGE11DB
[boris@fedora26workstation GCC]$ file recursEGE11DB
recursEGE11DB: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 2.6.32, BuildID[sha1]=94912d58f183297fd10d3bbd6a944f883046064e, stripped
[boris@fedora26workstation GCC]$ ./recursEGE11DB
F(2)
F(6)    F(5)    F(3)
          F(9)    F(6)    F(4)
               F(12)    F(7)    F(5)
                   Result = 23

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

Краткое пояснение работы алгоритма рекурсии
***************************************************************
F(6) + F(5) + F(3) = 3 + 2 + F(3) =
5 + F(9) + F(6) + F(4) = 5 + 4 + 3 + F(12) + F(7) + F(5) =
12 + 6 +3 + 2 = 23

Ответ : 23

67)(И. Тощенко) Дан рекурсивный алгоритм:

function F(n: integer): integer;
begin
if n < 5 then
    F:= F(n+3) + F(2*n) + F(3*n div 2)
else
    F:= n + 2;
end;
Чему будет равно значение, вычисленное алгоритмом при выполнении вызова F(3)?

F:= F(6)+F(6)+F(4) = 16+F(7)+F(8)+F(6) = 16+9+10+8 = 43

68)(И. Тощенко) Дан рекурсивный алгоритм:
function F(n: integer): integer;
begin
if n < 6 then
    F:= n+F(n+3) * F(2*n)
else
    F:= n*2;
end;
Чему будет равно значение, вычисленное алгоритмом при выполнении вызова F(3)?

F := 3 +F(6)*F(6) = 3+12*12 = 147

64)   (И. Тощенко) Дан рекурсивный алгоритм:
function F(n: integer): integer;
begin
if n >= 3 then
    F:= F(n-3) + F(n-2)*F(n-1)
else
    F:= n;
end;
Чему будет равно значение, вычисленное алгоритмом при выполнении вызова F(7)?

F(7) := F(4)+F(5)*F(6)
F(4) := F(1)+F(2)*F(3)
F(3) := F(0)+F(1)*F(2)
F(2) := 2
F(3) := 0+1*2 =2
F(4) := 1+4 = 5
F(5) := F(2)+F(3)*F(4) = 2+2*5=12
F(6) := F(3)+F(4)*F(5) = 2+5*12=62
F(7) := F(4)+F(5)*F(6) = 5+12*62=749