Консультация 2 Информатика и ИКТ ЕГЭ 2013. В15 Решение систем логических уравнений Сколько различных решений имеет система логических уравнений X1 X2. - презентация

1 Консультация 2 Информатика и ИКТ ЕГЭ 2013

2 В15 Решение систем логических уравнений Сколько различных решений имеет система логических уравнений X1 X2 X3 ¬X4 = 1 X3 X4 X5 ¬X6 = 1 X5 X6 X1 ¬X2 = 1 Где x1, x2, …, x6 – логические переменные

3 В15 Решение систем логических уравнений X1 X2 X3 ¬X4 = 1 X3 X4 X5 ¬X6 = 1 X5 X6 X1 ¬X2 = 1 Решение. a b = ¬ a b¬a ¬ b = ¬(a b) ¬¬a =a

4 В15 Решение систем логических уравнений X1 X2 X3 ¬X4 = 1 X3 X4 X5 ¬X6 = 1 X5 X6 X1 ¬X2 = 1 Решение. a b = ¬ a b¬a ¬ b = ¬(a b) ¬¬a =a X1 X2 = ¬ X1 X2 X3 ¬ X4 = ¬ ¬ X3 ¬ X4 = ¬(¬ X3 X4 )

5 В15 Решение систем логических уравнений X1 X2 X3 ¬X4 = 1 X3 X4 X5 ¬X6 = 1 X5 X6 X1 ¬X2 = 1 Решение. a b = ¬ a b¬a ¬ b = ¬(a b) ¬¬a =a X1 X2 = ¬ X1 X2 X3 ¬ X4 = ¬ ¬ X3 ¬ X4 = ¬(¬ X3 X4 ) Исходная система примет вид ¬ X1 X2 ¬(¬ X3 X4 ) = 1 ¬ X3 X4 ¬(¬ X5 X6 ) = 1 ¬ X5 X6 ¬(¬ X1 X2 ) = 1

6 В15 Решение систем логических уравнений X1 X2 X3 ¬X4 = 1 X3 X4 X5 ¬X6 = 1 X5 X6 X1 ¬X2 = 1 Решение. a b = ¬ a b¬a ¬ b = ¬(a b) ¬¬a =a X1 X2 = ¬ X1 X2 X3 ¬ X4 = ¬ ¬ X3 ¬ X4 = ¬(¬ X3 X4 ) Исходная система примет вид ¬ X1 X2 ¬(¬ X3 X4 ) = 1 ¬ X3 X4 ¬(¬ X5 X6 ) = 1 ¬ X5 X6 ¬(¬ X1 X2 ) = 1

7 В15 Решение систем логических уравнений X1 X2 X3 ¬X4 = 1 X3 X4 X5 ¬X6 = 1 X5 X6 X1 ¬X2 = 1 Решение. a b = ¬ a b¬a ¬ b = ¬(a b) ¬¬a =a X1 X2 = ¬ X1 X2 X3 ¬ X4 = ¬ ¬ X3 ¬ X4 = ¬(¬ X3 X4 ) Исходная система примет вид ¬ X1 X2 ¬(¬ X3 X4 ) = 1 ¬ X3 X4 ¬(¬ X5 X6 ) = 1 ¬ X5 X6 ¬(¬ X1 X2 ) = 1 Введем замены переменных Y1 = ¬ X1 X2 Y2 = ¬ X3 X4 Y3 = ¬ X5 X6

8 В15 Решение систем логических уравнений X1 X2 X3 ¬X4 = 1 X3 X4 X5 ¬X6 = 1 X5 X6 X1 ¬X2 = 1 Решение. Исходная система примет вид ¬ X1 X2 ¬(¬ X3 X4 ) = 1 ¬ X3 X4 ¬(¬ X5 X6 ) = 1 ¬ X5 X6 ¬(¬ X1 X2 ) = 1 Введем замены переменных Y1 = ¬ X1 X2 Y2 = ¬ X3 X4 Y3 = ¬ X5 X6 Получим новую систему Y1 ¬ Y2 = 1 Y2 ¬ Y3 = 1 Y3 ¬ Y1 = 1

9 В15 Решение систем логических уравнений Получим новую систему Y1 ¬ Y2 = 1 Y2 ¬ Y3 = 1 Y3 ¬ Y1 = 1 Находим решение полученной системы

10 В15 Решение систем логических уравнений Получим новую систему Y1 ¬ Y2 = 1 Y2 ¬ Y3 = 1 Y3 ¬ Y1 = 1 Находим решение полученной системы

11 В15 Решение систем логических уравнений Получим новую систему Y1 ¬ Y2 = 1 Y2 ¬ Y3 = 1 Y3 ¬ Y1 = 1 Находим решение полученной системы Получили два решения для системы с Y1, Y2, Y3

12 В15 Решение систем логических уравнений Получим новую систему Y1 ¬ Y2 = 1 Y2 ¬ Y3 = 1 Y3 ¬ Y1 = 1 Находим решение полученной системы Получили два решения для системы с переменными Y1, Y2, Y3 Была сделана заменаY1 = ¬ X1 X2 Построим таблицу истинности для Y1

13 В15 Решение систем логических уравнений Получим новую систему Y1 ¬ Y2 = 1 Y2 ¬ Y3 = 1 Y3 ¬ Y1 = 1 Находим решение полученной системы Построим таблицу истинности для Y1 Аналогичные таблицы истинности можно построить для Y2 и Y3

14 В15 Решение систем логических уравнений Получим новую систему Y1 ¬ Y2 = 1 Y2 ¬ Y3 = 1 Y3 ¬ Y1 = 1 Находим решение полученной системы

15 В15 Решение систем логических уравнений Получим новую систему Y1 ¬ Y2 = 1 Y2 ¬ Y3 = 1 Y3 ¬ Y1 = 1 Находим решение полученной системы Количество решений = = 28 1 решение 3 3 = 27 решений Переменные Y1, Y2, Y3 – независимы

16 Анализ алгоритма В8 Получив на вход число x, этот алгоритм печатает два числа: a и b. Укажите наименьшее из таких чисел x, при вводе которых алгоритм печатает сначала 2, а потом 21 БейсикПаскальCиCи DIM X, A, B, K AS INTEGER INPUT X A=0: B=1 WHILE X > 0 A = A+1 K = X MOD 10 B = B*K X = X \ 10 WEND PRINT A PRINT B var x, a, b, k: integer; begin readln(x); a:=0; b:=1; while x>0 do begin a:=a+1; k:=x mod 10; b:=b*k; x:= x div 10 end; writeln(a); write(b); end. #include void main() { int x, a, b, k; scanf("%d", &x); a=0; b=1; while (x>0) { a = a+1; k = x % 10; b = b*k; x = x/10;} printf("%d\n%d", a, b); } 0) { a = a+1; k = x % 10; b = b*k; x = x/10;} printf("%d\n%d", a, b); }">

17 Анализ алгоритма БейсикПаскальCиCи WHILE X > 0 K= X MOD 10 X = X \ 10 WEND while x>0 do begin ………… k:=x mod 10; x:= x div 10 end; while (x>0) { ………. k=x%10; x= x/10; } Остаток от целочисленного деления – mod, % Целочисленное деление - \, div, /

18 Анализ алгоритма БейсикПаскальCиCи WHILE X > 0 K= X MOD 10 X = X \ 10 WEND while x>0 do begin ………… k:=x mod 10; x:= x div 10 end; while (x>0) { ………. k=x%10; x= x/10; } Остаток от целочисленного деления – mod, % Целочисленное деление - \, div, /

19 Анализ алгоритма БейсикПаскальCиCи WHILE X > 0 K= X MOD 10 X = X \ 10 WEND while x>0 do begin ………… k:=x mod 10; x:= x div 10 end; while (x>0) { ………. k=x%10; x= x/10; } Остаток от целочисленного деления – mod, % Целочисленное деление - \, div, /

20 Анализ алгоритма БейсикПаскальCиCи WHILE X > 0 K= X MOD 10 X = X \ 10 WEND while x>0 do begin ………… k:=x mod 10; x:= x div 10 end; while (x>0) { ………. k=x%10; x= x/10; } Остаток от целочисленного деления – mod, % Целочисленное деление - \, div, /

21 Анализ алгоритма Алгоритм печатает сначала 2, т.е. а = 2 БейсикПаскальCиCи DIM X, A, B,K AS INTEGER INPUT X A=0: B=1 WHILE X > 0 A = A+1 K = X MOD 10 B = B*K X = X \ 10 WEND PRINT A PRINT B var x, a, b,k: integer; begin readln(x); a:=0; b:=1; while x>0 do begin a:=a+1; k:=x mod 10; b:=b*k; x:= x div 10 end; writeln(a); write(b); end. #include void main() { int x, a, b, k; scanf("%d", &x); a=0; b=1; while (x>0) { a = a+1; k = x % 10; b = b*k; x = x/10;} printf("%d\n%d", a, b); } 0) { a = a+1; k = x % 10; b = b*k; x = x/10;} printf("%d\n%d", a, b); }">

22 Анализ алгоритма Алгоритм печатает сначала 2, т.е. а = 2 БейсикПаскальCиCи DIM X, A, B,K AS INTEGER INPUT X A=0: B=1 WHILE X > 0 A = A+1 K = X MOD 10 B = B*K X = X \ 10 WEND PRINT A PRINT B var x, a, b,k: integer; begin readln(x); a:=0; b:=1; while x>0 do begin a:=a+1; k:=x mod 10; b:=b*k; x:= x div 10 end; writeln(a); write(b); end. #include void main() { int x, a, b, k; scanf("%d", &x); a=0; b=1; while (x>0) { a = a+1; k = x % 10; b = b*k; x = x/10;} printf("%d\n%d", a, b); } a = 2 9 < x 0) { a = a+1; k = x % 10; b = b*k; x = x/10;} printf("%d\n%d", a, b); } a = 2 9 < x ">

23 Анализ алгоритма В8 Алгоритм печатает сначала 2, а потом 21, т.е. b= 21 БейсикПаскальCиCи DIM X, A, B,K AS INTEGER INPUT X A=0: B=1 WHILE X > 0 A = A+1 K = X MOD 10 B = B*K X = X \ 10 WEND PRINT A PRINT B var x, a, b,k: integer; begin readln(x); a:=0; b:=1; while x>0 do begin a:=a+1; k:=x mod 10; b:=b*k; x:= x div 10 end; writeln(a); write(b); end. #include void main() { int x, a, b, k; scanf("%d", &x); a=0; b=1; while (x>0) { a = a+1; k = x % 10; b = b*k; x = x/10;} printf("%d\n%d", a, b); } b - произведение цифр числа x 0) { a = a+1; k = x % 10; b = b*k; x = x/10;} printf("%d\n%d", a, b); } b - произведение цифр числа x">

24 Анализ алгоритма В8 Алгоритм печатает сначала 2, а потом 21, т.е. b= 21 БейсикПаскальCиCи DIM X, A, B,K AS INTEGER INPUT X A=0: B=1 WHILE X > 0 A = A+1 K = X MOD 10 B = B*K X = X \ 10 WEND PRINT A PRINT B var x, a, b,k: integer; begin readln(x); a:=0; b:=1; while x>0 do begin a:=a+1; k:=x mod 10; b:=b*k; x:= x div 10 end; writeln(a); write(b); end. #include void main() { int x, a, b, k; scanf("%d", &x); a=0; b=1; while (x>0) { a = a+1; k = x % 10; b = b*k; x = x/10;} printf("%d\n%d", a, b); } b = 21 b = 7*3 0) { a = a+1; k = x % 10; b = b*k; x = x/10;} printf("%d\n%d", a, b); } b = 21 b = 7*3">

25 Анализ алгоритма В8 Алгоритм печатает сначала 2, а потом 21, т.е. b= 21 БейсикПаскальCиCи DIM X, A, B,K AS INTEGER INPUT X A=0: B=1 WHILE X > 0 A = A+1 K = X MOD 10 B = B*K X = X \ 10 WEND PRINT A PRINT B var x, a, b,k: integer; begin readln(x); a:=0; b:=1; while x>0 do begin a:=a+1; k:=x mod 10; b:=b*k; x:= x div 10 end; writeln(a); write(b); end. #include void main() { int x, a, b, k; scanf("%d", &x); a=0; b=1; while (x>0) { a = a+1; k = x % 10; b = b*k; x = x/10;} printf("%d\n%d", a, b); } b = 21 b = 7*3 Следовательно, наименьшее из таких чисел x, при вводе которых алгоритм печатает сначала 2, а потом 21 равно = 37 0) { a = a+1; k = x % 10; b = b*k; x = x/10;} printf("%d\n%d", a, b); } b = 21 b = 7*3 Следовательно, наименьшее из таких чисел x, при вводе которых алгоритм печатает сначала 2, а потом 21 равно = 37">

26 У исполнителя Утроитель две команды, которым присвоены номера: 1. прибавь 1, 2. умножь на 3. Первая из них увеличивает число на экране на 1, вторая – утраивает его. Программа для Утроителя – это последовательность команд. Сколько есть программ, которые число 1 преобразуют в число 17? В13. Анализ результатов алгоритма

27 В прибавь 1, 2. умножь на 3. Решение. Если число N не делится на три, то оно может быть получено только из предыдущего N-1 с помощью команды прибавь 1. Если число N делится на три, то оно может быть получено из предыдущего N-1 с помощью команды прибавь 1 из числа N/3 с помощью команды умножь на 3

28 B13 1. прибавь 1, 2. умножь на 3. Решение. Если число N не делится на три, то оно может быть получено только из предыдущего N-1 с помощью команды прибавь 1. Если число N делится на три, то оно может быть получено из предыдущего N-1 с помощью команды прибавь 1 из числа N/3 с помощью команды умножь на 3

29 B13 1. прибавь 1, 2. умножь на 3. Решение. Если число N не делится на три, то оно может быть получено только из предыдущего N-1 с помощью команды прибавь 1. Если число N делится на три, то оно может быть получено из предыдущего N-1 с помощью команды прибавь 1 из числа N/3 с помощью команды умножь на 3

30 B13 1. прибавь 1, 2. умножь на 3. Решение.

31 B13 1. прибавь 1, 2. умножь на 3. Решение.

32 B13 1. прибавь 1, 2. умножь на 3. Решение.

33 B13 1. прибавь 1, 2. умножь на 3. Решение. Ответ: 9

34 B13 У исполнителя Утроитель три команды, которым присвоены номера: 1.прибавь 1, 2.прибавь 3, 3.умножь на 3. Сколько есть программ, которые число 1 преобразуют в число 10?

35 B13 У исполнителя Утроитель три команды, которым присвоены номера: 1.прибавь 1, 2.прибавь 3, 3.умножь на 3. Сколько есть программ, которые число 1 преобразуют в число 10? Ответ: 33

36 C3. Построение дерева игры по заданному алгоритму, поиск и обоснование выигрышной стратегии Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Количество камней неограниченное. Игра завершается в тот момент, когда количество камней в куче становится не менее 22. Победителем считается игрок, сделавший последний ход. В начальный момент в куче было S камней, 1 S 21. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.

37 C3. Построение дерева игры по заданному алгоритму, поиск и обоснование выигрышной стратегии Выполните следующие задания. Во всех случаях обосновывайте свой ответ. 1. а) Укажите все такие значения числа S, при которых Петя может выиграть в один ход. Обоснуйте, что найдены все нужные значения S, и укажите выигрывающий ход для каждого указанного значения S. б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани. 2. Укажите два таких значения S, при которых у Пети есть выигрышная стратегия, причём – Петя не может выиграть за один ход, и – Петя может выиграть своим вторым ходом, независимо от того, как будет ходить Ваня. Для каждого указанного значения S опишите выигрышную стратегию Пети. 3. Укажите значение S, при котором: – у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и – у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Для указанного значения S опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход, в узлах – количество камней в куче.

38 C3. Построение дерева игры по заданному алгоритму, поиск и обоснование выигрышной стратегии Выполните следующие задания. Во всех случаях обосновывайте свой ответ. 1.а) Укажите все такие значения числа S, при которых Петя может выиграть в один ход. Обоснуйте, что найдены все нужные значения S, и укажите выигрывающий ход для каждого указанного значения S. Решение. По условию задачи возможные ходы+1или*2 Выигрыш количество камней S >=22 Следовательно, выиграть последним ходом +1, если S = 21 *2, если S > =11 Ответ Петя может выиграть первым ходом, если S > =11. Ход - удвоить количество камней в куче. При меньших значениях S за один ход нельзя получить кучу, в которой больше 21 камня.

39 C3. Построение дерева игры по заданному алгоритму, поиск и обоснование выигрышной стратегии Выполните следующие задания. Во всех случаях обосновывайте свой ответ. 1.б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани. Решение. В пункте 1а найдено количество камней, при котором можно выиграть первым ходом. Эта позиция (S>=11) нужна Ване. А для Пети нужно позиция, из которой все возможные ходы ведут к S>=11. Ответ. Ваня может выиграть первым ходом (как бы ни играл Петя), если исходно в куче будет S =10 камней. Тогда после первого хода Пети в куче будет 11 камней или 20 камней. В обоих случаях Ваня удваивает количество камней и выигрывает своим первым ходом.

40 C3. Построение дерева игры по заданному алгоритму, поиск и обоснование выигрышной стратегии 2. Укажите два таких значения S, при которых у Пети есть выигрышная стратегия, причём – Петя не может выиграть за один ход, и – Петя может выиграть своим вторым ходом, независимо от того, как будет ходить Ваня. Решение. Пете нужно перевести игру в позицию S = 10 (пункт 2б). Это можно сделать при S = 9 или S = 5.

41 C3. Построение дерева игры по заданному алгоритму, поиск и обоснование выигрышной стратегии 2. Укажите два таких значения S, при которых у Пети есть выигрышная стратегия, причём – Петя не может выиграть за один ход, и – Петя может выиграть своим вторым ходом, независимо от того, как будет ходить Ваня. Решение. Пете нужно перевести игру в позицию S = 10 (пункт 2б). Это можно сделать при S = 9 или S = 5. Ответ. Возможные значения S: 5 и 9. В этих случаях Петя, очевидно, не может выиграть первым ходом. Однако он может получить кучу из 10 камней. Эта позиция разобрана в п. 1б. В ней игрок, который будет ходить (теперь это Ваня), выиграть не может, а его противник (то есть, Петя) выиграет следующим ходом.

42 C3. Построение дерева игры по заданному алгоритму, поиск и обоснование выигрышной стратегии Выполните следующие задания. Во всех случаях обосновывайте свой ответ. 3. Укажите значение S, при котором: – у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и – у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Решение. Ваня ходит вторым, поэтому необходимо найти такое значение S, при котором оба возможных хода Пети ведут в позиции, приводящую к выигрышу в 1 ход или к выигрышу в 2 хода. Например, позиция S = 8

43 C3. Построение дерева игры по заданному алгоритму, поиск и обоснование выигрышной стратегии 3. Ответ. Возможное значение S= 8. После первого хода Пети в куче будет 9 или 16 камней. Если в куче станет 16 камней, Ваня удвоит количество камней и выиграет первым ходом. Ситуация, когда в куче 9 камней, разобрана в п. 2. В этой ситуации игрок, который будет ходить (теперь это Ваня), выигрывает своим вторым ходом. На рисунке изображено дерево возможных партий при описанной стратегии Вани. Заключительные позиции (в них выигрывает Ваня) обведены кружком. В дереве в каждой позиции, где должен ходить Петя, разобраны все возможные ходы, а для позиций, где должен ходить Ваня, – только ход, соответствующий стратегии, которую выбрал Ваня.