Вторым важным способом решения задач является решение задачи с конца. Предположим (хотя это и не всегда верно), что для обоих игроков одни и те же позиции являются выигрышными.
Вернёмся к примеру 9.
Для нахождения выигрышной стратегии рассмотрим общую задачу. Считаем, что начальная позиция является параметром, и будем искать выигрышную стратегию при старте с этой позиции. Будем обозначать знаком «`-`» позиции, в которых при правильной игре участник, начинающий играть из данной позиции, выиграет, и знаком «`+`» отметим позиции, ведущие к поражению[1].
Если игра начинается в поле `"h"8`, первый игрок уже проиграл – это позиция «`+`» (рис. 1).
Далее, если игра стартует с полей `"h"1-"h"7` или `"a"8-"g"8`, то начинающий игрок может за один ход достичь поля `"h"8` и выиграть. Это позиция «`-`» (рис. 2).
Рассмотрим ладью, стоящую в поле `"g"7`. У первого игрока есть только два хода – `"g"8` и `"h"7`. Но в обеих этих позициях стоит «`-`». Следовательно, второй игрок, стартующий из этих позиций, выиграет. Как бы ни ходил первый игрок, он проиграет. Это снова позиция «`+`».
Далее, рассмотрим группы полей `"g"1-"g"6` и `"a"7-"f"7` (рис. 3). Стартуя из этих полей, первый игрок может за один ход попасть в поле `"g"7`, которое помечено знаком «`+`». Любой ход второго игрока из `"g"7` ведёт к его проигрышу.
Продолжая таким образом заполнять шахматную доску, мы видим, что знаки «`+`» размещаются на диагонали `"a"1-"h"8` (рис. 4). В поле a1 стоит знак «`+`», поэтому первый игрок потерпит поражение.
Зафиксируем общие правила расстановки знаков «`+`» и «`-`»:
1) знаком «`-`» обозначаются позиции, в которых при правильной игре участник, стартующий из данной позиции, выиграет, и знаком «`+`» отмечаются позиции, ведущие к поражению;
2) знак «`-`» ставится в позиции, из которой можно за один ход прийти в позицию со знаком «`+`»;
3) знак «`+`» ставится в выигрышных позициях, а также в тех позициях, из которых все возможные ходы ведут только в позиции, уже отмеченные знаком «`-`»[2].
Таким образом, сначала нужно расставить знаки «`+`» в выигрышных позициях. На втором этапе нужно отметить знаком «`-`» те позиции, которые отделяет от выигрышных один ход. На третьем этапе следует просмотреть все позиции и найти «тупиковые», ведущие к положениям, обозначенным знаком «`-`». На игровом поле обязательно будет хотя бы одна такая позиция[3]. Второй и третий этапы необходимо поочередно повторять до тех пор, пока начальная позиция не будет помечена знаком «`+`» или «`-`», что и даст ответ на вопрос, кто выиграет при правильной игре.
Как же должен действовать побеждающий участник игры? Он должен стремиться ходить в позиции, отмеченные знаком «`+`». При этом после очередного хода соперника он опять окажется в позиции со знаком «`-`», так как по определению знака «`+`» все возможные ходы из этой позиции ведут только в позиции со знаком «`-`». Таким образом, стратегия выигрывающего игрока формулируется просто: делать ход в позиции, обозначенные знаком «`+`». По определению знака «`-`» из этой позиции существует хотя бы один ход в позицию, отмеченную знаком «`+`», поэтому такой ход у выигрывающего игрока всегда будет в наличии.
Отметим следующий факт. Если известно, что игра длится не более чем `n` ходов при любых действиях первого и второго игроков, то начальная позиция обязательно будет помечена не более чем за `n` повторений шагов `2` и `3`. Это является идеей доказательства основной теоремы из § 2 в частном случае игр, в которых ничейных позиций нет, и каждая позиция является выигрышной для одного из игроков.
Два игрока играют в следующую игру. Перед ними лежат две кучи камней, в первой – три камня, а во второй – два камня. У каждого игрока имеется неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в три раза число камней в какой-либо куче, или добавляет один камень в любую кучу. Выигрывает тот игрок, после хода которого, в двух кучах станет не менее `16` камней. Кто выиграет при правильной игре: игрок, сделавший первый ход, или игрок, сделавший второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
Попробуем изобразить позиции графически. Рассмотрим таблицу, в которой количество камней в первой куче будет соответствовать номеру столбца, а количество камней во второй куче – номеру строки. Чёрным цветом выделена позиция `(2, 3)`, с которой должна начинаться игра в условии:
1. Выигрышные позиции – точки с координатами `x`, `y`, где `x + y ≥ 16`. Данные точки обозначим знаком «`+`» в таблице ниже[4].
2. Далее, ставим знак «`-`» в позиции, которые отделяет от выигрышных один ход.
По условию, можно либо увеличить одну из кучек в три раза, либо добавить камень в одну из куч, т. е. мы должны поставить знак «`-`» в позицию `(x, y)`, если верно одно из условий: `x+y+1≥16`; `x+3y≥16`; `y+3x≥16`.
3. После чего, ставим знак «`+`» в те позиции, из которых все ходы ведут только в позиции, обозначенные знаком «`-`». Таковыми будут позиции `(0, 5)`, `(5, 0)` и `(4, 3)`, `(3, 4)`.
4. Знак «`-`» ставим в те позиции, стартуя из которых можно за один ход дойти до одной из позиций, отмеченных знаков «`+`» (поставленных на этапе 3).
Стартуя из позиций `(4, 0)`, `(0, 4)`, `(3, 3)`, `(2, 4)`, `(4, 2)`, можно попасть в позиции, обозначенные знаком «`+`», увеличив количество камней в одной из кучек на единицу. Из позиций `(1, 4)` и `(4, 1)` можно прийти в позиции со знаком «`+`», увеличив в три раза количество камней в меньшей куче.
5. Знак «`+`» ставим в те позиции, из которых все ходы ведут только в позиции, обозначенные знаком «`-`». На этот раз таковыми будут позиции `(2, 3)` и `(3, 2)`.
В позиции `(2, 3)` был поставлен знак «`+`», а это значит, что победит второй игрок.
При оформлении задачи необходимо указать выигрывающего игрока, записать его стратегию и показать, что этот игрок победит при любых ответах соперника. Если имеется таблица позиций, то стратегия выигрывающего игрока формулируется простым правилом: делать ходы в позиции, отмеченные знаком «`+`». Но эту стратегию рекомендуется записать в явном виде. Таблицу позиций же, наоборот, при оформлении работы можно не рисовать (она уже сделала свое дело: помогла определить победителя и найти его стратегию).
Покажем, что второй игрок может выиграть при произвольных ответах первого игрока.
Рассмотрим все возможные начальные ходы первого игрока и укажем правильные ответы соперника:
а) если первый игрок в три раза увеличивает число камней в одной из куч, то второй игрок должен увеличить количество камней в этой же куче также в три раза. Тогда в обеих кучах будет как минимум 2*3*3+3=21 камень. Второй игрок побеждает. Рассмотрение этого случая закончено;
б) если первый игрок из позиции (2, 3) делает ход (2, 4) или (3, 3), то второй игрок должен пойти в позицию (3, 4) (именно она в нашем случае обозначена знаком «+»). Теперь первый игрок делает второй ход (заметим, этот ход не может быть выигрышным). Возможны три варианта:
- первый игрок увеличивает в три раза количество камней в одной из куч. Тогда второй игрок повторяет это действие с оставшейся кучкой камней, получает в сумме 21 камень и выигрывает,
- первый игрок добавляет один камень в первую кучу – позиция (4, 4). Тогда второй игрок увеличивает количество камней в одной из куч в три раза, получает в сумме 16 камней и выигрывает,
- первый игрок добавляет один камень во вторую кучу – позиция (3, 5). Тогда второй игрок увеличивает количество камней во второй куче в три раза, получает в сумме 18 камней и выигрывает.
Таким образом, второй игрок побеждает при любых ходах своего соперника.
Обратите внимание, что стратегию второго игрока можно придумать, не основываясь на таблице позиций. Важно помнить: если вы пропустите или не разберёте хотя бы один ход соперника (проигрывающего игрока), это может быть чревато тем, что данная стратегия может оказаться в корне неверной. Также нужно внимательно отнестись к расстановке знаков «`+`» и «`-`» в таблице позиций: один неверно поставленный знак может изменить ответ. Лучше не торопиться и расставить только те знаки, в которых вы уверены на данный момент. И не существенно, если вы не поставите никакого знака в данной позиции на определенном этапе (например, по правилам его необходимо поставить, но вы этого не заметили). Главное – не поставить неверного знака.
[1] «`+`»-позиции иногда называют `"P"`-позициями, а «`-`»-позиции – `"N"`-позициями по первым буквам английских слов «Previous» (предыдущий) и «Nеxt» (следующий), указывающими, какой из игроков выиграет при старте из этой позиции – игрок, который пришёл в эту позицию последним ходом, или игрок, совершающий следующий ход из этой позиции.
[2] Недопустимо, чтобы из этой позиции один ход вёл в позицию, обозначенную знаком «`+`», а другой – вёл в позицию, ещё не обозначенную ни одним из знаков.
[3] Хотя убедиться в этом непросто, мы предлагаем читателю самостоятельно подумать, почему это верно.
[4] Хотя таблица должна быть бесконечной (количество камней может быть сколь угодно большим), достаточно нарисовать таблицу `17` x `17` – случаи, когда в одной из куч более `16` камней, нас не интересуют, так как все эти позиции являются выигрышными.
Данный способ является разновидностью анализа с конца и заключается в том, что мы будем анализировать в знаках «`+`» и «`-`» не все позиции, а только те, в которые можно прийти из начальной позиции. Для этого мы нарисуем дерево ходов из начальной позиции. Разберём этот метод на примере 10.
Первоначальная позиция - `(2,3)`. За один ход из этой позиции можно прийти в позиции: `(3,3)`; `(2,4)`; `(6,3)`; `(2,9)`, добавляя один камень в одну из куч или умножая количество камней в куче на три.
Наша цель, в конечном счёте, во все эти позиции поставить знаки «`+`» и «`-`». Чтобы поставить знак «`+`», нужно быть уверенным, что все ходы из этой позиции ведут в «`-`»; для того, чтобы поставить знак «`-`», нужно, чтобы хотя бы один ход из этой позиции вел к «`+`».
Выше приведённое означает, что если из позиции за один ход можно прийти в позицию с количеством камней, не меньшим `16` (что по условию задачи равносильно выигрышу), это - позиция, выигрышная для первого игрока, т. е. позиция «`-`». В связи с этим знаки «`-`» можно поставить в позициях `(6,3)` и `(2,9)`, умножая количество камней в большей куче на `3`, мы получим `6^(**)3+3=21` и `2+9^(**)3=29` камней соответственно, и выиграем.
Мы не сможем такого утверждать для позиций `(3,3)` и `(2,4)`, поэтому отразим в дереве все позиции, в которые мы можем прийти из них ещё за один ход. Две из полученных после двух ходов позиций повторяются (это позиция `(3,4)`). Можно не делать дубликат позиции `(3,4)`, а провести к ней пути как из позиции `(2,4)`, так и из позиции `(3,3)`. А можно - оставить как есть, что в данном случае мы и сделаем.
Обозначим знаком «`-`» позиции, из которых можно дойти за один ход до выигрышных. Из оставшихся позиций продолжаем дерево дальше позициями, в которые можно попасть за три хода
Из всех полученных позиций можно за один ход дойти до выигрышных. Поэтому, в них можно поставить «`-`» и далее дерево ходов не продолжать. Теперь, посмотрим на позиции `(3,4)` и `(4,3)`. Все ходы в этих позициях ведут в позиции со знаком «`-`», т. е. в позиции, проигрышные для пришедшего в них игрока (и выигрышные для начинающего с них игрока). Поэтому, начинающий из такой позиции при правильной игре проиграет - это позиции «`+`».
После этого, отметим знаком «`-`» позиции `(3,3)` и `(2,4)` уровнем выше как позиции, из которых существует хотя бы один ход в позицию, отмеченную знаком «`+`». И, наконец, позицию `(2,3)` отметим знаком «`+`» как позицию, все ходы из которой ведут в позиции со знаком «`-`».
Таким образом, в позиции `(2,3)` стоит знак «`+`»[1], а это означает, что в данной игре выиграет второй игрок. Его стратегия формулируется тем же правилом, что и ранее: делать ходы в позиции, отмеченные знаком «`+`». Стратегия выигрывающего игрока в явном виде («образец оформления примера») уже была описана ранее. Аналогично анализу с конца обратим внимание, что важно построить дерево позиций до конца - пропуск любой, даже самой маленькой, ветви может существенно поменять всю расстановку знаков в вершинах дерева существенно поменять всю расстановку знаков в вершинах дерева и даже привести к тому, что победит другой игрок. Причём последнее не является редкостью.
Отдельно отметим, что хотя «анализ с конца» и «дерево игры» являются различными вариациями одной и той же идеи, в некоторых случаях быстрее действовать одним методом, а в некоторых - другим. Так, если в игре легко отобразить схематично всё множество позиций (например, на клетчатом листе), с другой стороны, количество ходов до выигрыша может быть довольно большим (см. пример 9), гораздо легче действовать методом «анализ с конца». В примере 10 решения обоими методами примерно идентичны по трудозатратам.
Однако, если известно, что игра всегда заканчивается за малое количество ходов - логичнее нарисовать дерево игры. Более того, если множество позиций сложно или невозможно каким-либо образом изобразить схематически (например, если не две кучи камней, а три кучи) - «анализ с конца» вообще малоприменим – нужно рисовать дерево игры или вообще решать задачу методом «удачный ход».
[1] Поскольку данное дерево игры заполнялось знаками по тем же правилам, что и таблица позиций, знаки «`+`» и «`-`» в позициях, отмеченных на дереве и в таблице позиций ранее, должны совпадать.
Данный параграф появился в связи с тем, что с 2015 года в ЕГЭ в задаче по теме теории игр требуется не только указать стратегию выигравшего, но и провести более подробный анализ, нарисовав дерево игры (о чём прямо сказано в условии) и ответив на дополнительные вопросы вида «из каких позиций выиграет первый игрок, причем ровно за два хода» или «какое максимальное количество ходов потребуется для выигрыша». Условие такой задачи в реальном ЕГЭ будет, скорее всего, очень длинным и занимать до страницы; однако этого не нужно бояться.
Два игрока играют в следующую игру. Перед игроками лежит куча из `S` камней, игроки по очереди могут за ход провести над кучей следующую операцию: добавить `1` или `4` камня в кучу или, если количество камней в куче чётно, увеличить количество камней в куче в `1,5` раза. Выигрывает игрок, после чьего хода в куче будет не менее `31` камня.
Укажите все значения `S`, при которых в правильной игре
А) Первый игрок может выиграть первым ходом.
Б) Второй игрок может выиграть первым ходом.
В) Первый игрок может выиграть вторым ходом, при этом он не может выиграть своим первым ходом.
Г) Найдите хотя бы одно значение `S`, при котором в правильной игре выигрывает второй игрок, при этом он не может выиграть своим первых ходом.
Нарисуем клеточную прямую и отметим знаком «`+`» выигрышные позиции в конце игры - позиции с количеством камней не менее `31`. Далее отметим знаками «`-`» позиции, из которых до указанных можно дойти за `1` ход: это позиция (`30`), из которой можно выиграть ходом «добавить `1` камень», позиции `(30)`, `(29)`, `(28)`, `(27)` из которых выиграть ходом «прибавление `4` камня» и позиции `(22)`, `(24)`, `(26)`, `(28)`, `(30)`, из которых можно выиграть за ход «увеличить кучу с чётным количеством камней в `1,5` раза»[1]. Из некоторых позиций, как видно выше, существует сразу несколько выигрышных ходов, однако это неважно: должен существовать хотя бы один. Чтобы отличать эти отмеченные позиции от всех других, добавим ещё цифру «`1`» к позиции для удобства, получив «`-1`».
Найдя позиции, которые подпадают под условие пункта А), перейдём к пункту Б). Нас интересует не просто дальнейшая расстановка плюсов и минусов в позициях, а ещё и количество ходов до выигрыша. Фраза «второй игрок выиграет первым ходом» означает, что из данных позиций не должно быть ходов ни в какие другие позиции, кроме как в позиции, отмеченные знаком «`-1`», т. е. позиции, из которых второй игрок сможет выиграть за один ход. Такие позиции лучше перебрать следующим образом:
Сначала отметим все пустые позиции знаком «?», из которых существует хотя бы один ход до позиций, уже отмеченных знаком «`-1`». Ходом «добавить один камень» можно за ход попасть в указанное множество из позиций `(25)`, `(23)`, `(21)`; ходом «добавить `4` камня» за ход можно попасть из позиций `(25)`, `(23)`, `(20)`, `(18)`, и ходом «увеличить в `1,5` раза» - из позиций `(16)`, `(18)`, `(20)`.
Теперь для каждой из отмеченных «?» позиций проверим условие, что все допустимые ходы идут в нарисованное множество минусовых позиций.
`(16)`, `(18)`, `(20)` - ход «`+1`» противоречит условию выше;
`(21)` - ход «`+4`» противоречит условию выше;
`(23)`, `(25)` - подходят. Таким образом `(23)`, `(25)` - являются позициями, в которых второй игрок выиграет за один ход. В этих позициях будет стоять знак «`+`» как в позициях, откуда все ходы идут в позиции со знаком «`-1`».
Теперь, перейдём к пункту В). Перед этим сотрём все знаки «?», поскольку в позициях, отличных от `(23)` и `(25)` нам неизвестно, существует ли хотя бы один ход, ведущий в минусовую позицию.
Первый игрок выиграет вторым ходом тогда и только тогда, когда не может выиграть за ход, но может прийти в позицию, из которой он, как второй игрок, выиграет первым ходом. Эти позиции уже найдены - это позиции `(23)` и `(25)`. Таким образом, нас интересуют все позиции, из которых можно за ход дойти до `(23)` и `(25)`. Это позиции `(19)`, `(21)`, `(22)`, `(24)`. Однако из позиций `(22)` и `(24)` в данный момент уже отмечены знаком «`-`», то есть из них можно выиграть за ход, а нас интересуют в данном пункте позиции, где за ход выиграть нельзя. Таким образом, в пункте В). Ответ - позиции `(19)` и `(21)`.
Наконец, в пункте Г) нас интересуют позиции, в которых выиграет второй игрок, т. е. позиции «`+`». Отметим отличие пункта Г) от пункта Б). В пункте Г) нас интересуют позиции, в которых второй игрок выиграет и он не сможет выиграть первым ходом, как бы не ходил его соперник. В пункте Б) же нас интересуют позиции, в которых второй игрок сможет, наоборот, выиграть первым ходом как бы не ходил его соперник. Позиции «`+`», где в зависимости от хода первого игрока второй сможет выиграть как первым своим ходом, так и не первым, нас не интересуют ни в пункте Б), ни в пункте Г).
Для решения пункта Г) просто продолжим заполнять согласно правилам таблицу позиций.
Нас интересует позиция, в которой выиграет второй игрок, то есть позиция «`+`». С другой стороны, нас интересует позиция, из которой второй игрок не сможет выиграть своим первым ходом. Это означает, что первый игрок всеми своими ходами должен ходить в минусовые позиции, но ни одним своим ходом не сможет походить в позиции «`-1`», из которых существует выигрышный ход. Этим свойством будет обладать, например, позиция `(15)` - возможные ходы из неё будут вести в позиции `(16) ` и `(19)`, отмеченные знаком «`-`», а не «`-1`». Это будет наибольшей позицией, обладающей таким свойством - из позиций `(18)` и `(20)`, выигрышных для второго игрока, существует ход первого игрока «`1,5x`», приводящий к позициям `(27)` и `(30)`. Из этих позиций можно выиграть за ход.
А) `(22), (24), (26), (27), (28), (29), (30)`;
Б) `(23), (25)`;
В) `(19), (21)`
Г) Например, `(15)`.
Два игрока играют в следующую игру. Перед игроками лежит две кучи: в первой куче `5` камней, во второй куче - `S` камней. Игроки по очереди могут за ход провести над одной из куч следующую операцию: добавить `2` камня в кучу или, если количество камней в куче чётно, увеличить количество камней в куче в `2,5` раза. Выиграет игрок, после чьего хода суммарное количество камней в обеих кучах будет не менее `39`.
Укажите все значения `S`, при которых в правильной игре
А) Первый игрок может выиграть первым ходом
Б) Второй игрок может выиграть первым ходом.
В) Первый игрок может выиграть вторым ходом, но не может выиграть первым ходом.
Данный пример очень похож по условию на пример 11, однако здесь возникает проблема в том, что количество куч - две, хоть и задано, что изначально в первой куче `5` камней. Если рассматривать двумерную таблицу позиций, это приведёт к побочному анализу многих позиций, в которых количество камней в первой куче отлично от пяти (в примере 11 таких «лишних» позиций не было). Построение дерева игры также не приведёт к быстрому результату, т. к. начальная позиция неизвестна, и такие деревья нужно будет рисовать при каждом `S`.
В связи с этим проведём предварительный анализ игры, не пользуясь ни таблицей позиций, ни деревом игры.
А) Первый игрок выиграет за ход. Первый игрок не может увеличить количество камней в кучке из `5` камней в `1,5` раза. Следовательно, его возможные ходы – это либо добавление камней к одной из куч, либо увеличение количества камней в второй куче в `2,5` раза. В первом случае суммарное количество камней до увеличения должно равняться `37` или `38` (т. е. во второй куче `32` или `33` камня). Во втором случае: пусть `x` – количество камней во второй куче. Тогда `x` - чётно и `2,5x+5>=40`, откуда `x>=14`. Следовательно, возможное количество камней во второй куче, при котором первый игрок победит за ход - `14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 33` (больше `33` нельзя, т. к. изначальное суммарное количество камней должно быть меньше `39`, чтобы игра имела смысл).
Б) Второй игрок выиграет за ход. Это должны быть позиции, при которых первый игрок не сможет выиграть за ход, а второй игрок – сможет выиграть за ход после любого хода первого игрока. Рассмотрим все возможные ходы первого игрока:
– первый игрок увеличивает количество камней в куче с `S` камнями на `2` (этот ход второй игрок может применить в любой ситуации). Тогда второй выиграет, если после этого `S` станет равно `14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 33` (см. предыдущий пункт, количество камней в первой куче не менялось), т. е. изначально `S` могло быть равно `12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 31`.
Из этих вариантов числа камней `S` только варианты `12,31` соответствуют тому, что первый игрок не может выиграть своим первым ходом. Будем далее рассматривать только `S=12`, `S=31` и проверим оставшиеся возможные ходы первого игрока.
Проверим `S=12:`
– первый игрок увеличивает количество камней в куче с `S` камнями в `2,5` раза, получив `30` камней во второй куче. В таком случае второй игрок сможет выиграть за ход, также увеличив количество камней в этой куче в `2,5` раза.
– первый игрок увеличивает количество камней в куче с `5` камнями в `2,5` раза: невозможный ход.
– первый игрок увеличивает количество камней в первой куче на `2`. Таким образом, в первой куче - `7` камней, во второй - `12`. Однако в данном случае второй игрок не сможет выиграть - ни один из его ходов не приводит к ситуации, когда суммарное количество камней после его хода не менее `39`.
`S=12` не подходит. Проверим `S=31:`
– первый игрок увеличивает количество камней в куче с `S` камнями в `2,5` раза: невозможный ход.
– первый игрок увеличивает количество камней в куче с `5` камнями в `2,5` раза: невозможный ход.
– первый игрок увеличивает количество камней в куче с `5` камнями на `2`. Тогда второй игрок также увеличит количество камней в одной из куч на `2`, получит суммарное количество камней - `39`, и победит!
`S=31` подходит.
В) Первый игрок выиграет вторым ходом. После своего хода он должен прийти в позицию, из которой он (будучи «вторым» игроком), сможет выиграть за ход (т. е. в позицию, соответствующую п. Б).
Если после хода первого игрока количество камней в первой куче останется равным `5`, то мы придём в ситуацию предыдущего пункта (после хода первого игрока, если они поменяются ролями, первому игроку, находящемуся в роли второго игрока, нужно выиграть за оставшийся ход). Ответ пункта Б) гласит, что после хода первого игрока количество камней во второй куче должно стать `31`. Единственная возможная ситуация - `29` камней.
Заметим, что при начальном количестве в `5` камней для первой кучи и `29` камней во второй куче единственно возможные ходы - добавления по `2` камня к одной из куч. При этом никогда чётного количества камней в какой-либо из куч не получится, и применить ход «увеличить в `2,5` раза» также будет невозможно. Поэтому при любых ходах как первого, так и второго игрока, через три хода суммарное количество камней станет `29+5+2+2+2=40`, поэтому игра закончится за три хода победой первого игрока (своим вторым ходом).
Второй случай - если первый игрок в правильной игре своим ходом поменяет количество камней в куче единственно возможным ходом «`+2` камня», при этом после хода первого игрока получится `7` камней в первой куче и `S` - во второй. После этого мы должны для начала полностью повторить анализ, по образцу предыдущего пункта. Рассмотрим следующий ход второго игрока:
– второй игрок увеличивает количество камней в куче с `S` камнями на `2`. Тогда первый выиграет, если после этого `S` станет равно `14, 16, 18, 20, 22, 24, 26, 28, 30, 31 ` `(2,5x+7>=39)`, т. е. изначально `S` могло быть равно `12, 14, 16, 18, 20, 22, 24, 26, 28, 29`.
Из этих вариантов числа камней `S` только варианты `12, 29` соответствуют тому, что второй игрок не может выиграть своим первым ходом. Вариант `S=29` уже был рассмотрен ранее - он подходит. Рассмотрим `S=12` и оставшиеся возможные ходы второго игрока.
– второй игрок увеличивает количество камней в куче с `12` камнями в `2,5` раза. При этом он получит `30` камней во второй куче, и `37` - суммарно в обеих кучах. Любой ход первого игрока приведёт к выигрышу.
– первый игрок увеличивает количество камней в первой куче в `2,5` раза: невозможный ход, т. к. `7` - нечётное число.
– первый игрок увеличивает количество камней в первой куче на `2`. Таким образом, в первой куче - `9` камней, во второй - `12`. В данном случае первый игрок сможет выиграть за ход, увеличив количество камней во второй куче, `12`, в `2,5` раза: `9+30 = 39` камней, ровно столько, сколько и требуется для победы. Любой другой ход первого игрока приведёт к тому, что после этого его соперник увеличит в `2,5` раза кучу из `12` или `14` камней и победит, т. о., этот ход не является ходом первого игрока при правильной игре (см. замечание после данной задачи).
Итак, `S=12` будет подходить под условие «первый игрок всегда выиграет вторым ходом», если первым ходом первый игрок увеличит количество камней в первой куче с `5` до `7`. Заметим, что все остальные ходы первого игрока `(12->14; 12->30)` приведут к тому, что второй игрок увеличит количество камней во второй куче в `2,5` раза и выиграет с суммарным количеством камней `40` и `80`. Следовательно, такие ходы первого игрока не могут быть ходами в правильной игре.
А) `S=14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 33`;
Б) `S=31`;
В) `S=12,29`.
[1] Если в условии явно просят объяснить, откуда возникают вышеуказанные позиции и почему других таких позиций нет (это встречено автором в демоверсии ЕГЭ 2015), желательно выписать возникающие неравенства и их решить. Иначе в случае сильно строгой проверки можно недосчитаться первичных баллов на пустом месте. Так, в случае хода «умножить кучу с чётных количеством камней на 1,5» нужна система условий, состоящая из 1) неравенства (невыигрышная априори); 2) неравенства (можно дойти за 1 ход до выигрышной) и 3) чётно.
Алгебра логики является частью активно развивающейся сегодня науки – дискретной математики. Дискретная математика – это тот раз-дел математики, где не используется понятие непрерывности.
1) Состоящий из отдельных частей.
2) Изменяющийся между несколькими стабильными состояниями.
3) Существующий лишь в отдельных точках.
Для того, чтобы лучше понять этот термин, рассмотрим следующий пример. Мы знаем, что график некоторой функции (например, `y=x^2`) является непрерывной линией (параболой), если аргумент функции принимает все значения из множества действительных чисел. А теперь представим, что `x` может принимать только значения из множества целых чисел. В этом случае график будет представлять собой бесконечное количество отдельных точек, располагающихся на координатной плоскости в определённом порядке. В расположении точек будет угадываться парабола, но непрерывной линии мы не увидим. Вместо неё мы увидим дискретную структуру.
В прошлом задании мы говорили о представлении чисел в компьютере, и знаем, что каждое число представляется в виде определённой последовательности значений битов. В каждом бите может храниться ноль или единица. То есть, по сути, представление чисел (в будущем мы увидим, что не только чисел, а вообще любых данных) в компьютере является дискретной структурой. Поэтому, изучение дискретных структур – важная часть информатики. В этом задании мы будем изучать наиболее простую дискретную структуру, которая называется высказыванием.
Высказывание – это повествовательное предложение, в отношении которого можно судить о его истинности либо ложности.
Например, предложение: «Я – твой друг» является высказыванием, а предложение: «Положи это сюда!» высказыванием не является, поскольку не является повествовательным предложением.
Истинность или ложность каждого высказывания зависит от трактовки его содержания. Например, высказывание: «Город Москва – столица России» является истинным, а высказывание: «Город Санкт-Петербург стоит на реке Лене» является ложным.
Высказывание называется простым, если никакая его часть сама по себе не является высказыванием.
Высказывание: «Эта шляпа – красная» является простым, в то время как высказывание: «Если прямая пересекает одну из двух параллельных прямых, то она пересекает и вторую» является примером сложного высказывания, которое, по сути, состоит из трёх простых: «две прямые параллельны», «прямая пересекает одну из двух прямых», «прямая пересекает другую прямую». В сложном высказывании простые высказывания соединяются при помощи логических связок. В рассмотренном выше примере логической связкой является союз «если то».
Алгебра логики изучает структуру сложных логических высказываний и способы установления их истинности при помощи алгебраических методов. Причём, конкретное содержание высказываний предметом изучения алгебры логики не является, и, соответственно, интересовать нас в дальнейшем не будет.
В прошлом задании при изучении основ программирования мы столкнулись с понятиями констант и переменных. Константа – это некоторое конкретное значение, а переменная – это объект, который может менять свои значения и которому можно присваивать различные значения. Этими же понятиями пользуется и алгебра логики, чтобы абстрагироваться от конкретных содержаний высказываний. Будем считать, что любое простое высказывание – это есть константа. И введём понятие переменной в алгебре логики.
Переменной в алгебре логики называется объект, имеющий уникальное имя, и значением которого может являться любое простое высказывание.
В отличие от языков программирования в алгебре логики нет ограничений при именовании переменных. Переменные могут иметь абсолютно любые имена, но чаще всего их обозначают заглавными или строчными латинскими буквами (`A, B, C, x, y, z, s`), либо последовательностью, состоящей из заглавной или строчной латинской буквы и целого числа (`A1, A2, A4, A10000000`). Ещё одно отличие от языков программирования заключается в том, что после присвоения переменной высказывания можно говорить об её истинности либо ложности. То есть существует два понятия «значение логической переменной». С одной стороны – это конкретное высказывание, а с другой стороны – это истина, либо ложь.
Логическим выражением называется объект, состоящий из логических переменных и логических операций и имеющий значение истина, либо ложь. Процесс построения логического выражения по сложному высказыванию называется формализацией высказывания.
В процессе формализации нужно сделать следующие действия: выделить из сложного высказывания простые и превратить их в логические переменные. Затем каждая логическая связка превращается в логическую операцию. В описанных действиях остаётся два непонятных момента. Первый – что такое логическая операция, и второй – каким образом логические связки превращаются в логические операции. Будем последовательно отвечать на эти вопросы.
Для того чтобы определить операцию, необходимо указать количество операндов (объектов, над которыми выполняется операция) их тип и результат выполнения операции. Логические операции чаще всего имеют два операнда, как и математические. Однако мы также будем изучать операции, которые имеют всего один операнд. Независимо от количества операнды должны быть логического типа, то есть иметь значение истина, либо ложь. Результатом логической операции также является логическое значение – истина или ложь. Для того чтобы немного сократить запись, условимся в дальнейшем логическое значение «истина» обозначать единичкой `(1)`, а логическое значение – «ложь» – нулём `(0)`.
Очевидно, что если у операции два операнда, и значением каждого является `0` или `1`, то существует всего четыре набора значений операндов `(00, 01, 10, 11)`. Для каждого из наборов необходимо определить значение логической операции. Удобно это представлять в виде таблицы. Таблицы соответствия значений логических операций набору значений операндов называются таблицами истинности.
Сейчас мы познакомимся с шестью основными логическими операциями. Каждая из них имеет несколько названий и обозначений.
|
Названия операции |
Возможные обозначения |
|
Отрицание, инверсия. |
`-, ~|, not` |
|
Конъюнкция, логическое умножение, операция И, операция AND. |
`&, ^^, *,` по аналогии с алгебраическим умножением может никак не обозначаться
|
|
Дизъюнкция, нестрогая дизъюнкция, логическое сложение, операция ИЛИ, операция OR. |
`|``, vv, +` |
|
Строгая дизъюнкция, разделительная дизъюнкция, исключающее ИЛИ, сложение по модулю `2`. |
`o+, Delta` |
|
Эквивалентность, эквиваленция, равенство, равнозначность. |
`iff, -=` |
|
Импликация, следование, следствие |
`=>, ->` |
Теперь для того чтобы строго определить эти логические операции, нам нужно для каждой из них выписать таблицу истинности. Все перечисленные операции кроме отрицания имеют два операнда. Знак операции в выражениях пишется между операндами (как в алгебре чисел). Операция отрицания имеет один операнд и в выражениях записывается либо в виде черты над операндом, либо в виде символа «приставка» слева от операнда.
Для того, чтобы не путаться и гарантированно перебрать все возможные комбинации значений операндов, принято записывать их в лексикографическом порядке (условно считается, что «ложь» `<` «истина»).
Таблица истинности для конъюнкции
|
Первый операнд |
Второй операнд |
Значение операции |
|
`0` |
`0` |
`bb0` |
|
`0` |
`1` |
`bb0` |
|
`1` |
`0` |
`bb0` |
|
`1` |
`1` |
`bb1` |
Таблица истинности для дизъюнкции
|
Первый операнд |
Второй операнд |
Значение операции |
|
`0` |
`0` |
`bb0` |
|
`0` |
`1` |
`bb1` |
|
`1` |
`0` |
`bb1` |
|
`1` |
`1` |
`bb1` |
Таблица истинности для строгой дизъюнкции
|
Первый операнд |
Второй операнд |
Значение операции |
|
`0` |
`0` |
`bb0` |
|
`0` |
`1` |
`bb1` |
|
`1` |
`0` |
`bb1` |
|
`1` |
`1` |
`bb0` |
Таблица истинности для эквивалентности
|
Первый операнд |
Второй операнд |
Значение операции |
|
`0` |
`0` |
`bb1` |
|
`0` |
`1` |
`bb0` |
|
`1` |
`0` |
`bb0` |
|
`1` |
`1` |
`bb1` |
Таблица истинности для импликации
|
Первый операнд |
Второй операнд |
Значение операции |
|
`0` |
`0` |
`bb1` |
|
`0` |
`1` |
`bb1` |
|
`1` |
`0` |
`bb0` |
|
`1` |
`1` |
`bb1` |
Таблица истинности для отрицания
|
Значение операнда |
Значение операции |
|
`0` |
`bb1` |
|
`1` |
`bb0` |
Теперь осталось лишь установить соответствие между логическими операциями и логическими связками в русском языке.
|
Логическая операция |
Логические связки в русском языке |
|
Отрицание |
Неверно что… |
|
Конъюнкция |
и, а, но, а также, при этом, одновременно с этим, хотя |
|
Дизъюнкция |
Или |
|
Строгая дизъюнкция |
или, либо |
|
Эквивалентность |
Тогда и только тогда когда, необходимо и достаточно чтобы |
|
Импликация |
если то, необходимо чтобы, достаточно чтобы |
Обратите внимание, что союз ИЛИ может означать, как строгую, так и нестрогую дизъюнкцию. Его интерпретация зависит от содержания (!!!) высказывания.
Рассмотрим высказывание: «Мы идём в кино в субботу или в воскресение». Здесь два простых высказывания: «Мы идём в кино в субботу» и «Мы идём в кино в воскресение». Между ними стоит союз ИЛИ, который можно интерпретировать двояко. В данном случае очевидно, что мы можем пойти в кино и в субботу, и в воскресение, поэтому дизъюнкция будет нестрогая. Возьмём две логические переменные – `p` и `q` и присвоим им простые высказывания. Тогда исходное высказывание в формализованном виде будет выглядеть, как `bb(pvvq)`.
Рассмотрим высказывание: «Я сейчас на севере Москвы или на юго-западе Москвы». Здесь тоже два простых высказывания, которые связаны союзом ИЛИ. Но в этом случае союз ИЛИ интерпретируется, как строгая дизъюнкция, поскольку нельзя одновременно находиться в двух местах. Таким образом, если снова взять логические переменные `p` и `q`, то получится следующая логическая формула: `bb(p"o+q)`.
Рассмотрим высказывание: «Для того чтобы четырёхугольник был квадратом, необходимо, чтобы все его стороны были равны». Здесь два простых высказывания: «Четырёхугольник является квадратом» и «Все стороны четырёхугольника равны». Присвоим их соответственно логическим переменным `p` и `q`. Логическая связка «необходимо, чтобы» - это импликация. Весь вопрос в том, что из чего следует. (Какая запись правильная: `bbp -> bbq` или `bbq ->bbp`?) Импликация ложна только в единственном случае: когда левый операнд имеет значение «истина», а правый – «ложь». Рассмотрим все возможные значения операндов и проанализируем, какая из ситуаций невозможна.
1) `p` и `q` ложны. Это значит, что четырёхугольник не является квадратом и его стороны не равны. Это возможная ситуация.
2) `p` – ложно, `q` – истинно. Это значит, что четырёхугольник не является квадратом, но стороны у него равны. Это возможно (ромб).
3) `p` – истинно, `q` – истинно. Это значит, что четырёхугольник является квадратом и стороны у него равны. Это возможная ситуация.
4) `p` – истинно, `q` – ложно. Это значит, что четырёхугольник является квадратом, но стороны у него не равны. Это невозможная ситуация.
Анализ ситуаций показывает, что левым операндом импликации должна быть переменная `p`. Таким образом, в формализованном виде исходное высказывание выглядит как `bb(p -> q)`.
Очень часто вместо «присвоим логическим переменным эти высказывания» говорят «обозначим высказывания следующим образом». В дальнейшем мы тоже будем использовать этот речевой оборот.
Итак, мы познакомились с понятием логического выражения и увидели, каким образом его строить по высказыванию на русском языке. Следующий шаг – изучение преобразований логических выражений.
Логические выражения, зависящие от одних и тех же логических переменных, называются равносильными, если на любом наборе значений переменных они принимают одинаковое значение (`0` или `1`). В дальнейшем для обозначения равносильности логических выражений мы будем использовать знак равенства.<
это некоторые стандартные преобразования логических выражений, при которых сохраняется равносильность. Начнём с самых простых законов:
1) Законы поглощения констант
x `vv` 0 = x, x & 1 = x;
2) Законы поглощения переменных
x `vv` 1 = 1, x & 0 = 0;
3) Законы идемпотентности
x & x = х, x `vv` x = х;
4) Закон двойного отрицания
$$ \stackrel{=}{\mathrm{x}}$$ = x;
5) Закон противоречия
x & $$ \stackrel{-}{\mathrm{x}}$$ = 0;
6) Закон исключённого третьего
x `vv` $$ \stackrel{-}{\mathrm{x}}$$ = 1;
Приведённые законы ещё называют аксиомами алгебры логики. Истинность этих и всех последующих законов легко можно установить, построив таблицу истинности для левого и правого логического выражения.
Переходим к группе законов, которые практически аналогичны законам алгебры чисел.
7) Законы коммутативности
x & y = y & x,
x `vv` y = y `vv` x;
Здесь стоит сделать замечание, что помимо конъюнкции и дизъюнкции свойством коммутативности также обладают эквивалентность и строгая дизъюнкция. Импликация – единственная из изучаемых операций, которая имеет два операнда и не обладает свойством коммутативности.
8) Законы ассоциативности
(x & y) & z = x & (y & z),
(x`vv`y) `vv` z = x `vv` (y `vv` z);
9) Законы дистрибутивности
x & (y `vv` z) = (x & y) `vv` (x & z),
x `vv` (y & z) = (x `vv` y) & (x `vv` z);
Первый из законов дистрибутивности аналогичен закону дистрибутивности в алгебре чисел, если конъюнкцию считать умножением, а дизъюнкцию – сложением. Второй же закон дистрибутивности отличается от алгебры чисел, поэтому рекомендуется обратить на него особое внимание и в дальнейшем использовать при решении задач на упрощение выражений.
Кроме аксиом и алгебраических свойств операций ещё существуют особые законы алгебры логики.
10) Законы де Моргана
$$\style{font-family:'Courier New'}{\overline{\mathrm x\&\mathrm y}=\overline{\mathrm x}\vee\overline{\mathrm y},}$$
$$\style{font-family:'Courier New'}{\overline{\mathrm x\vee\mathrm y}=\overline{\mathrm x}\;\&\;\overline{\mathrm y};}$$
11) Загоны поглощения (не путать с аксиомами поглощения переменных нулём или единицей)
x `vv` (x & y) = x;
x & (x `vv` y) = x.
Рассмотрим пример доказательства первого закона де Моргана при помощи построения таблицы истинности.
|
`x` |
`Y` |
`x&y` |
`bar(x&y)` |
`barx` | `bary` |
`barx vv bary` |
|
`0` |
`0` |
`0` |
`1` |
`1` |
`1` |
`1` |
|
`0` |
`1` |
`0` |
`1` |
`1` |
`0` |
`1` |
|
`1` |
`0` |
`0` |
`1` |
`0` |
`1` |
`1` |
|
`1` |
`1` |
`1` |
`0` |
`0` |
`0` |
`0` |
Так как результирующие столбцы совпали, то выражения, стоящие в левой и правой частях закона, равносильны.
В алгебре при решении задач на упрощение выражений большой популярностью пользовалась операция вынесения общего множителя за скобки. В алгебре логики эта операция также является легитимной, благодаря законам дистрибутивности и закону поглощения константы `1`. Продемонстрируем этот приём на простом примере: докажем первый закон поглощения, не используя таблицу истинности.
Наше начальное выражение: x `vv` (x & y). Выносим `x` за скобки и получаем следующее выражение:
x &(1 `vv` y). Используем закон поглощения переменной константой `1` и получаем следующее выражение: x & 1. И теперь используем закон поглощения константы и получаем просто x.
В заключение, следует сказать несколько слов об операции импликации. Как уже отмечалось выше, импликация не обладает свойством коммутативности. Её операнды неравноправны, поэтому каждый из них имеет уникальное название. Левый операнд импликации называется посылкой, а правый – следствием. Из таблицы истинности импликации следует, что она истинна, когда истинно следствие, либо ложна посылка. Единственный случай, когда импликация ложна – это случай истинной посылки и ложного следствия. Таким образом, мы подошли к последнему закону алгебры логики, который бывает полезен при упрощении выражений.
12) Закон преобразования импликации
`"x" -> "y" = bar("x") vv "y"`
Необходимо ещё отметить, что в сложных логических выражениях у операций есть порядок приоритетов.
1) Отрицание
2) Конъюнкция
3) Дизъюнкция, строгая дизъюнкция, эквивалентность
4) Импликация
С помощью тождественных преобразований максимально упростить следующее логическое выражение:
`bar C vv` (`A` & `С`) `vv` (`bar(A vv C vv bar(B)`)
Максимально упростить, это значит довести выражение до такого вида, когда невозможно применить ни один из законов алгебры логики, которые сокращают длину выражения.
Для того, чтобы не запутаться, можно использовать общую стратегию упрощения логических выражений.
1) Избавиться от операций импликации.
2) Продвинуть отрицание вглубь выражения. То есть применять законы де Моргана, и закон двойного отрицания пока знак отрицания не будет стоять только над переменными (но не над операциями).
После пункта 2 наступает относительная свобода действий. Можно использовать тождества поглощения или раскрывать скобки.
В нашей задаче операция импликации отсутствует, поэтому первый пункт мы пропускаем. Переходим к пункту 2. Применяем два раза второй закон де Моргана (для дизъюнкции) и закон двойного отрицания к правой скобке и получаем следующее логическое выражение:
`bar C vv ` (`A` & `C`) `vv` (`bar A` & `bar C` & `B`)
Если теперь внимательно посмотреть на выражение, то очевидно, что к первому и третьему слагаемому можно применить первый закон поглощения, так как отрицание переменной `C` является первым слагаемым и входит в третье в качестве множителя.
Поскольку дизъюнкцию ещё называют логическим сложением, её операнды называют слагаемыми, аналогично конъюнкция – это логическое умножение, и её операнды называют множителями.
После применения первого закона поглощения получается следующее логическое выражение:
`bar C` `vv` (`A` & `C`)
Применим второй (нестандартный для алгебры) закон дистрибутивности. Получаем:
(`bar C vv A`) & (`bar C vv C`)
Ко второй скобке применяем закон исключённого третьего, превращаем её в единицу, а затем применяем закон поглощения константы `1` и в итоге получаем выражение: `bar C vv A`, которое упростить уже нельзя.
Для лучшего понимания, рекомендуется выписать исходное логическое выражение, последовательно применить к нему все описанные действия и сравнить свой результат с приведённым в конце решения задачи.
Обратите внимание, что исходное логическое выражение зависело от трёх переменных (`A, B, C`) , в то время как упрощённое в итоге зависит от двух логических переменных (`A` и `C`). При этом выражения всё равно остаются равносильными! Это происходит потому, что в процессе упрощения применялись законы поглощения. Аналогичный результат мог бы получиться, если в процессе упрощения выражения используются законы поглощения переменных константами. Исчезновение переменной при упрощении означает, что в исходном выражении она является несущественной.
Укажите значения переменных `K`, `L`, `M`, `N`, при которых логическое выражение `(L vv M) ^^ (¬ K -> M) ^^ ¬ N ^^ ¬ M` истинно.
Будем следовать стратегии, описанной в предыдущем примере. Первым делом избавляемся от операции импликации. Получаем следующее выражение:
`(L vv M) ^^ ( K vv M) ^^ ¬ N ^^ ¬ M`
Отрицание вглубь продвигать не надо. Теперь раскроем скобки. Для упрощения условимся операцию конъюнкции никак не обозначать (по аналогии с алгеброй чисел).
`(LK vv LM vv MK vv M) ( ¬ N) ( ¬ M)`
В первой скобке можно применить тождество поглощения, и «съесть» второе и третье слагаемое, которые содержат M в качестве множителя. Получается такое выражение:
`(LK vv M) ( ¬ N) ( ¬ M)`
Выполнив оставшиеся операции умножения, получим следующий результат:
` LK¬ N¬ M`
Получили одну конъюнкцию. Следовательно, существует всего один набор значений переменных, при котором получится значение «1»: `L=1`, `K=1`, `N=0`, `M=0`.
Сколько решений имеет уравнение:
`(((K¬L¬N) (¬L -> M))` \/ `((¬K` \/ `L` \/ `N) (¬L¬M))) (K`\/`N)=1`
Исходное выражение достаточно сложное, поэтому будем его упрощать. Первым делом избавимся от импликаций, получим:
`(((K¬L¬N) (L`\/ `M))` \/ `((¬K` \/ `L` \/ `N) (¬L¬M))) (K`\/`N) = 1`
Теперь раскроем скобки. Для упрощения условимся не записывать слагаемые, куда одновременно входят некоторая переменная и её отрицание (они всё равно равны нулю):
`(K¬L¬NM` \/ `¬K¬L¬M` \/ `N¬L¬M) (K`\/`N) = 1`
Продолжаем раскрытие скобок. Получаем:
`K¬L¬NM` \/ `¬K¬L¬MN` \/ `KN¬L¬M` \/ `N¬L¬M = 1`
Ко второму, третьему и четвёртому слагаемому можно применить тождество поглощения. В итоге получится:
`K¬L¬NM` \/ `N¬L¬M = 1`
На этом упрощение закончено, теперь будем анализировать. Дизъюнкция равна единице, если хотя бы одно из слагаемых равно единице. Первое слагаемое равно единице на единственном наборе переменных: (`K=1`, `L=0`, `N=0`, `M=1`). Второе слагаемое равно единице на двух наборах: (`N=1`, `L=0`, `M=0`, `K` – любое (или `0` или `1`)). Соответственно, уравнение имеет три различных решения.
В нарушении правил обмена валюты подозреваются четыре работника банка - Антипов (`A`), Борисов (`B`), Цветков (`C`) и Дмитриев (`D`). Известно, что:
1) Если `А` нарушил, то и `В` нарушил правила обмена валюты.
2) Если `B` нарушил, то и `C` нарушил или `A` не нарушал.
3) Если `D` не нарушил, то `A` нарушил, а `C` не нарушал.
4) Если `D` нарушил, то и `A` нарушил.
Кто из подозреваемых нарушил правила обмена валюты?
Чтобы решить эту задачу, необходимо провести процесс формализации условия, сформировать единое логическое выражение и провести его упрощение. Выделим из условия четыре простых высказывания: «`A` нарушил правила», «`B` нарушил правила», «`C` нарушил правила», и «`D` нарушил правила». Обозначим их соответственно буквами `A`, `B`, `C`, `D`. Тогда высказывания из условия формализуются следующим образом (конъюнкция не обозначается никак):
1) `A -> B`;
2) `B -> C` \/ `¬A`;
3) `¬D -> A¬ C`;
4) `D -> A`.
Нам известно, что выполняются все 4 высказывания, следовательно, нужно объединить их знаками конъюнкции и найти наборы, при которых получившееся общее высказывание будет истинным. Эти наборы и покажут нам, какие возможны ситуации (правила обмена нарушил тот, у кого переменная в итоговом наборе имеет значение «1»).
Итак, строим логическое выражение:
`(A -> B)( B -> C` \/ `¬A)( ¬D -> A¬C)( D -> A)`.
Теперь будем его упрощать. По алгоритму первым делом избавляемся от операции импликации. Получаем следующее выражение:
`(¬A` \/ `B)( ¬B` \/ `C` \/ `¬A)( D` \/ `A¬C)( ¬D` \/ `A)`.
Раскрываем скобки. Первую перемножаем со второй, а третью с четвёртой.
`(¬A¬B` \/ `¬AC` \/ `¬A` \/ `BC` \/ `B¬A) ( DA` \/ `A¬C¬D` \/ `A¬C)`.
Напомним, что слагаемые, равные нулю по причине того, что в них входит сразу и переменная и её отрицание, мы не записываем. В первой скобке теперь можно применить тождество поглощения, и «съесть» все слагаемые, имеющие в своём составе `A` с отрицанием. Во второй скобке можно также применить тождество поглощения, и «съесть» второе слагаемое. В итоге получаем:
`( ¬A` \/ `BC ) ( DA` \/ `A¬C)`.
При раскрытии оставшихся скобок три из четырёх слагаемых окажутся равными нулю, а последнее будет выглядеть следующим образом: `ABCD`. Из этого следует, что все четверо работников банка нарушили правило обмена валюты. (Только в этой ситуации предположения из условия задачи одновременно выполняются).
Правила обмена валюты нарушили все.
Известно, что обе надписи на дверях либо истинны, либо ложны одновременно. Надпись на первой двери – "Клад за другой дверью", на второй двери – "Клада за этой дверью нет, а за другой – есть". Где находится клад?
По сути нас интересуют два простых высказывания: «Клад есть за первой дверью» и «Клад есть за второй дверью». Обозначим первое из них буквой `A`, а второе буквой `B`. Тогда изначальные предположения формализуются следующим образом:
1) `B`;
2) `¬BA`.
В этой задаче в отличие от предыдущей у нас две возможные ситуации относительно комбинирования начальных предположений – они либо оба истинны, либо оба ложны. Предположим, что они оба истинны, тогда при их перемножении получится тождественный ноль, что означает невозможность данной ситуации.
Предположим, что оба высказывания ложны, тогда необходимо перед перемножением на каждое из них «навесить» отрицание (рассматривать истинность противоположных высказываний) В итоге получится следующее логическое выражение:
`¬B ¬(¬BA)`.
Упрощаем его по алгоритму: отрицание продвигаем вглубь, применяя тождество Де Моргана. Получаем:
`¬B (B` \/ `¬A)`.
Раскроем скобки. Первое слагаемое сокращается, а второе выглядит следующим образом: `¬B¬A`.
Полученный результат означает, что условия задачи выполняются, только в случае, когда оба высказывания ложны, а это означает, что клада нет ни за одной дверью. Не повезло нам `J`.
Клада нет ни за одной дверью.
В заключение приведём общую схему решения текстовых логических задач, которую мы уже применяли на практике при разборе примеров.
1) Выделить из условия задачи элементарные (простые) высказывания и обозначить их буквами.
2) Записать условие задачи на языке алгебры логики, соединив простые высказывания в сложные с помощью логических операций.
3) Составить единое логическое выражение для всех требований задачи (возможно не одно).
4) Используя законы алгебры логики попытаться упростить полученное выражение и вычислить все его значения либо построить таблицу истинности для рассматриваемого выражения (Таблицу можно строить, если в выражении не более трёх логических переменных).
5) Выбрать решение — набор значений простых высказываний, при котором построенное логическое выражение является истинным;
6) Проверить, удовлетворяет ли полученное решение условию задачи.
Среди задач алгебры логики часто встречаются задачи на определение количества решений систем логических уравнений. Рассмотрим примеры некоторых их них.
Найдите количество решений системы уравнений:
`(x2-=x1)+x2&x3+ not x2& not x3=1`
`(x3-=x1)+x3&x4+ not x3& not x4=1`
`…`
`(x9-=x1)+x9 & x10+ not x9 & not x10=1`
`(x10 -= x1)=0`
где `x1 … x10` - неизвестные логические величины
Упростим исходные уравнения, заметив, что, `(x2&x3+ not x2& notx3=(x2-=x3)`. Исходную систему запишем в виде:
`(x2-=x1)+(x2-=x3)=1`
`(x3-=x1)+(x3-=x4)=1`
`…`
`(x9-=x1)+(x9-=x10)=1`
`(x10&x1)=0`
В первом уравнении используются три переменных `x1`, `x2` и `x3`. Значения `x1` и `x2` могут быть выбраны произвольно четырьмя способами:
|
`bb(x1)` |
`bb(x2)` |
`bb(x3)` |
|
`0` |
`0` |
`0` |
|
`0` |
`0` |
`1` |
|
`0` |
`1` |
`1` |
|
`1` |
`0` |
`0` |
|
`1` |
`1` |
`0` |
|
`1` |
`1` |
`1` |
Если `x2=x1`, то значение `x3` может быть любое (эти строки выделены серым цветом), а при `x2!=x1` получаем только один вариант: `x3=x2`.
Таким образом, при подключении первого уравнения число решений увеличивается на количество строк в таблице, для которых значения `x1` и `x2` (последней рассмотренной переменной) равны. В данном случае таких строк две, получаем 6 решений. Более того, в новой таблице снова осталось всего две строки (верхняя и нижняя), где `x3=x1`. Как следует из второго уравнения, именно эти (и только эти) строки на следующем шаге “раздваиваются”, дают по два решения. Таким образом, при подключении к системе очередного уравнения число решений увеличивается на `2`. Для двух уравнений получим 8 решений, для трёх - 10, а для восьми - 20 решений.
Остается учесть последнее (особое) уравнение, `(x10-=x1)=0`. Это означает, что `x10!=1`. Из анализа таблицы видно, что есть всего две строки (верхняя и нижняя), где первая и последняя переменные равны. Поэтому из полученных 20 решений нужно отбросить эти два, не удовлетворяющие последнему уравнению. В итоге исходная система имеет 18 решений.
Найдите количество решений системы уравнений:
`not x1+x2=1`
`not x2+x3=1`
`…`
`not x9+x10=1`
где `x1 … x10` - неизвестные логические величины
`(not x1 + x2)&( not x2 + x3) &…&(not x9 + x10)=1`
однако это не упрощает решения.
Можно заметить, что первое уравнение зависит только от `x1` и `x2`, а каждое новое уравнение добавляет по одной новой переменной. Поэтому можно решать систему последовательно с помощью построения таблицы. Первое уравнение, `not x1+x2=1`, обращается в истинное равенство в трех случаях:
| `bb(x1)` | `bb(x2)` |
| `0` | `0` |
| `0` | `1` |
| `1` | `1` |
Подключив второе уравнение, `not x2+x3=1`, заметим, что допустимые значения `x3` зависят от ранее выбранного значения `x2`: если `x2=0`, то `x3` может принимать любое значение (`0` или `1`), а если `x2=1`, то `x3=1`. Соответствующая таблица выглядят так:
|
`bb(x1)` |
`bb(x2)` |
`bb(x3)` |
|
`0` |
`0` |
`0` |
|
`1` |
||
|
`0` |
`1` |
`1` |
|
`1` |
`1` |
`1` |
Легко заметить, что при добавлении очередного уравнения верхняя строка таблицы дает два решения (они выделены серы м цветом), а остальные строки - по одному. Поэтому количество решений увеличивается на `1`. Таким образом, система из трёх уравнений имеет 5 решений, из четырех - 6, а исходная система из девяти уравнений - 11 решений.
11 решений.
Заметим, что часто перед решением больших систем логических уравнений сначала удобно упростить исходную систему с помощью законов алгебры логики, а также воспользоваться заменой переменных, если это возможно.
Подобно предыдущему заданию, теперь мы вновь перейдём к изучению программирования и применим полученные знания по алгебре логики на практике.
В прошлом задании мы работали с числовыми типами переменных и учили арифметику, теперь познакомимся с логическим типом переменных, который называется Boolean. Переменные этого типа имеют всего два значения – true и false (соответственно, «истина» и «ложь»). Подобно числовым переменным им можно присваивать значения при помощи оператора присваивания. При этом необходимо строго соблюдать правило совместимости типов. То есть логическим переменным нельзя присваивать числовые значения, а числовым – логические.
В языке Паскаль помимо арифметических операций ещё существует `6` операций сравнения: больше» `(>)`, «больше или равно» `(> =)`, «меньше» `(<)`, «меньше или равно» `(< =)`, «равно» `(=)`, и «не равно» `(<>)`. Операция «не равно» записывается, как последовательность знаков «меньше» и «больше». Результатом каждой из этих операций является логическое значение true или false. Например, операция `5 > 2` выдаст значение true, а операция `x<>3` выдаст значение true, если переменная `X` имеет любое значение, кроме `3`. Сравнивать можно не только числа (причём как целые, так и вещественные), но и логические значения. При этом считается, что значение true больше, чем значение false. При сравнении обязательно соблюдать правило совместимости типов, то есть можно сравнивать числа между собой (причём в отличие от оператора присваивания, здесь никаких ограничений нет). Можно сравнивать между собой логические значения. Но нельзя сравнивать логическое значение с числом любого типа.
Помимо операций сравнения, в паскале существуют четыре логические операции, абсолютно аналогичные операциям алгебры логики.
1) Операция AND (в алгебре логики – «конъюнкция»)
2) Операция OR (в алгебре логики – «дизъюнкция»)
3) Операция XOR (в алгебре логики – «строгая дизъюнкция»)
4) Операция NOT (в алгебре логики – «отрицание»)
Все операнды этих операций должны быть логического типа, а никак не числового. Причём, операции AND, OR и XOR имеют по `2` операнда, а операция NOT – один операнд, который записывается справа от названия операции (аналогично обозначению операции NOT при помощи `¬` в алгебре логики)
Теперь у нас есть достаточно много операций и нужно расставить их по приоритету выполнения. В Паскале есть четыре приоритета операций:
1) Операция not;
2) Операции группы умножения: *, /, div, mod, and;
3) Операции группы сложения: +, – , or, xor;
4) Операции группы сравнения: >, <, <=, >=, =, <>.
Операции одного приоритета выполняются слева направо. Операции в круглых скобках имеют более высокий приоритет, чем вне скобок.
Теперь рассмотрим несколько примеров задач на использование логического типа.
Записать на Паскале логическое выражение истинное при выполнении указанного условия и ложное в противном случае. Результат вычисления данного выражения присвоить переменной F.
Числовая переменная X имеет значение на отрезке [–1,1].
F:=abs(X)<=1;
Числовая переменная X имеет значение на отрезке [2,7].
F:=(X>=2)and(X<=7).
Обратите внимание на скобки. Они обязательны, поскольку операции сравнения имеют более низкий приоритет, чем операция and.
Числовая переменная X имеет значение на одном из 2 отрезков: [–10, 3] или [10, 20].
F:=(X>=-10)and(X<=3)or(X>=10)and(X<=20).
Логические переменные A и B имеют различные значения.
F:=A<>B.
По крайней мере 2 из логических переменных A, B и C имеют значение true.
F:=A and B or A and C or B and C.
:
1.1 Алгоритмическая конструкция «Цикл»
Зачастую в задаче нужно повторять одни и те же действия много раз. Рассмотрим следующий пример: вывести на экран квадраты чисел от `1` до `100`.
Очевидно, что для решения этой задачи нам придётся `100` раз выполнять команду вывода соответствующего числа на экран. Писать `100` операторов вывода как-то не хочется (слишком трудоёмко), поэтому будем знакомиться с алгоритмической конструкцией, которая называется «цикл».
называется повторение фрагмента алгоритма несколько раз с возвратом в более раннюю точку исполнения алгоритма. Повторяемый при этом фрагмент алгоритма называется телом цикла.
Очевидно, что если возврат в более раннюю точку алгоритма происходит абсолютно всегда, то алгоритм никогда не доходит до своего завершения (выполняется бесконечно долго). Для предотвращения бесконечного повторения нужно поставить точку ветвления: в одной из веток будет возврат, а в другой - выход из цикла и дальнейшее продвижение по алгоритму.
В зависимости от положения точки ветвления выделяются циклы с предусловием (точка ветвления располагается перед телом цикла) и с постусловием (точка ветвления располагается после тела цикла).
1.2. Оператор while
В языке программирования есть несколько операторов цикла, реализующих как конструкцию с предусловием, так и конструкцию с постусловием. Познакомимся с ними.
Первый оператор цикла называется While и реализует алгоритмическую конструкцию с предусловием. В общем виде он записывается следующим образом:
while условие do оператор
Слова while и do являются служебными зарезервированными словами языка. Под условием (аналогично оператору if) понимается выражение, результат вычисления которого имеет тип boolean. Работает этот оператор следующим образом. Сначала вычисляется условие. Если в результате получилось true, то мы заходим в цикл, то есть выполняем тело цикла и возвращаемся вновь к вычислению условия. Если же получилось false, то происходит переход к следующему оператору в программы, и входа в цикл не будет. Фактически оператор while является многократным применением оператора if с пустой веткой else. Аналогично оператору if, тело цикла должно состоять из `1` оператора. Если нужно исполнить несколько, то следует использовать операторные скобки (begin end).
Возможна ситуация, когда цикл будет выполняться бесконечное количество раз (зациклится). Например, while 2*2=4 do… Что написать после do, совершенно не важно, важно, что оно будет выполняться, пока 2*2=4, а это всегда так, и никогда не изменится. Значит, чтобы избегать зацикливания, параметры условия должны быть переменными, например while x*x=4 do … Хотя это тоже не гарантирует отсутствие зацикливания. Поэтому при написании программ нужно всегда внимательно следить за тем, какие условия мы пишем в операторе цикла, чтобы не случилось ситуации зацикливания.
Также обратите внимание, что поскольку условие проверяется до входа в цикл, возможна ситуация, что при первой же проверке получится значение false и, соответственно, в цикл мы вообще не зайдём.
1.3. Примеры задач
Рассмотрим несколько примеров задач на оператор цикла.
Дано целое число, не меньшее `2`. Выведите его наименьший натуральный делитель, отличный от `1`.
Для решения этой задачи нам необходимо перебирать натуральные числа, начиная с двух и проверять каждое из них, не является ли оно делителем исходного числа. Процесс завершается, когда делитель найден. Очевидно, что процесс завершится всегда, поскольку в худшем случае число разделится само на себя. Приведём код программы.
var i,n:integer;
begin
readln(n);
i:=2;
while n mod i <> 0 do
i:=i+1;
end;
writeln (i);
end.
В первый день спортсмен пробежал `x` километров, а затем он каждый день увеличивал пробег на `10%` от предыдущего значения. По данному числу `y` определите номер дня, на который пробег спортсмена составит не менее `y` километров. Программа получает на вход действительные числа `x` и `y`. Программа должна вывести одно натуральное число.
В этой задаче нам нужно реализовать постепенное увеличение пробега. То есть, на каждом шаге цикла мы будем сохранять значение пробега в соответствующий день в одной переменной, а номер этого дня – в другой. Завершение, когда значение первой переменной станет не меньшим чем `y`. Приведём код программы. Все переменные, отвечающие за километры, имеют тип real (из условия).
var x,y:real; i:integer;
begin
readln(x,y);
i:=1;
while x<y do begin
x:=x/100*10+x;
i:=i+1;
end;
writeln(i);
end.
Дано натуральное число `N`. Вычислите его сумму цифр.
Для решения этой задачи на каждом шаге цикла нужно изменять наше число: при помощи операции mod можно выделить последнюю цифру из числа и прибавить её к сумме, а затем её надо выбросить из числа при помощи операции div. Делить нужно, естественно, на `10`. Критерий завершения – когда число станет равным нулю, ибо это будет означать, что мы уже рассмотрели все цифры и поделили на `10` однозначное число (по свойствам операции целочисленного деления известно, что при делении меньшего числа на большее получается ноль). Приведём код программы.
var a,n,s:integer;
begin
readln(n);
s:=0;
while n>0 do begin
a:=n mod 10;
s:=s+a;
n:=n div 10;
end;
writeln(s);
end.
Ввести целое число `n`. Вывести `"YES"`, если оно простое, и `"NO"`, если оно составное.
Эта задача демонстрирует сразу две важные вещи. Во-первых, как проверять делимость целых чисел, а во-вторых, технику флажков. Флажком называется переменная, которая имеет некоторое начальное значение и меняет его, если происходит определённое событие. Как правило, флажок имеет тип boolean.
В нашей задаче мы будем перебирать числа от `2` до квадратного корня из `n` и проверять, делится ли `n` на каждое из них. Изначально предположим, что `n` - простое, и присвоим флажку значение true, но если `n` поделится на какое-нибудь число, это будет значить, что оно составное, и, соответственно, флажок «упадёт» на значение false. Проверять на делимость нужно, сравнивая остаток от деления с нулём.
var n,i:integer;
f:boolean;
begin
readln(n);
f:=true;
for i:=2 to round(sqrt(n)) do
if n mod i = 0 then f:=false else;
if f=true
then writeln('YES')
else writeln('NO');
end.
1.4 Оператор repeat
Теперь познакомимся с другим оператором цикла, который реализует алгоритмическую конструкцию цикла с постусловием. Рассмотрим его синтаксис.
repeat
Оператор 1;
Оператор 2;
….
Оператор N
until условие
Все операторы, написанные между repeat и until, являются телом цикла. Это выгодно отличает оператор repeat от других циклов - составной оператор здесь не требуется, а операторными скобками можно считать слова repeat и until. Работает этот оператор по следующему алгоритму:
1) выполняется тело цикла;
2) вычисляется значение условия. Если получилось true, то выход из цикла и переход к следующему оператору программы, в противном случае переход к пункту 1.
Отличительная особенность оператора цикла repeat заключается в том, что тело всегда выполняется, по крайней мере, один раз. Это нужно учитывать в задачах при выборе оператора цикла. Аналогично оператору while, цикл repeat может зациклиться, правда в случае, когда условие никогда не принимает значение true, например, repeat…until 2*2=5.
Этот оператор цикла реализует следующую идею: «Повторять некоторую последовательность команд `N` раз, где `N` известно до начала повторения». Познакомимся с синтаксисом этого оператора.
for имя переменной := начальное значение to конечное значение do оператор
В этой конструкции переменная, стоящая после слова for, называется параметром или счётчиком цикла, а оператор, стоящий после слова do, называется телом цикла. Начальное и конечное значения, по сути, являются константами или выражениями одного типа со счётчиком. Алгоритм выполнения цикла for следующий:
1) вычисляются начальное и конечное значения;
2) счётчику цикла присваивается начальное значение;
3) значение счётчика сравнивается с конечным. Если оно больше ко-нечного, то выполнение цикла завершается и начинает выполняться следующий оператор программы, в противном случае переход к пункту 4;
4) выполняется тело цикла;
5) значение счётчика увеличивается на `1`;
6) переход к пункту 3.
В качестве примера рассмотрим решение задачи, поставленной в самом начале. В качестве счётчика будем использовать переменную i.
var i:integer;
begin
for i:=1 to 100 do write(i*i,' ');
end.
Согласитесь, что решение фактически в одну строчку выглядит гораздо приятнее, чем в `100` строк (если не пользоваться оператором цикла).
Необходимо сделать несколько замечаний по поводу цикла for.
1) Типы счётчика начального и конечного значений должны совпадать, при этом в настоящий момент из известных нам типов можно использовать только integer и boolean. Вещественный тип использовать нельзя.
2) Начальное и конечное значения вычисляются один раз до начала цикла (и после не перевычисляются). Рассмотрим пример.
i:=1; for i:=i to i do writeln('HI');
Этот оператор цикла выполнится всего один раз, а не бесконечно много.
3) В теле цикла значение счётчика изменять нельзя. Так прописано в стандарте языка Pascal, и это требование поддерживается в системах семейства Delphi и PascalABC. Однако в системах семейства Borland Pascal значение счётчика изменять можно, что может приводить к непредсказуемым последствиям (поэтому будем считать, что независимо от системы значение счётчика изменять нельзя).
4) После завершения цикла значение счётчика не определено, то есть нельзя считать, что оно равно конечному значению или больше на единицу и пользоваться этим в дальнейшем алгоритме.
5) Тело цикла по грамматике должно состоять только из `1` оператора. Если же там по алгоритму должно быть несколько, нужно использовать составной оператор. В этом смысле оператор for солидарен с операторами if и while.
6) Можно слово to заменить на слово downto. В этом случае значение счётчика после каждого выполнения тела цикла будет уменьшаться на `1`, а выход из цикла произойдёт, когда значение счётчика окажется меньше, чем конечное.
Выполнение любого оператора цикла можно завершить досрочно, если использовать процедуру break. На данном этапе она особенно актуальна, если надо досрочно прервать цикл for. Выполнение этой процедуры передаст управление на оператор, который следует за прерываемым оператором цикла.
Проиллюстрируем её работу следующим примером:
вводится натуральное число `x` `(2 <= x <= 30000)`. Выведите наименьший делитель числа `x`, отличный от `1`.
Мы уже разбирали алгоритм решения этой задачи выше. Продемонстрируем его с использованием цикла for.
var a,i: integer;
begin
readln(a);
for i := 2 to a do
if a mod i = 0 then
begin
writeln(i);
break;
end;
end.
В данном классе формулировка всех задач начинается со слов: «Вводится последовательность чего-нибудь…». Для простоты будем считать, что чисел - с ними мы умеем работать, но в общем случае это необязательно так. Далее нам нужно оценить какое-то свойство данной последовательности. Например, сколько в ней нулей, является ли она возрастающей (каждое следующее число больше предыдущего) и т. д. Причём, для оценки данного свойства, сохранение всей последовательности в памяти не требуется.
Общий алгоритм решения задач этого класса таков: мы считываем очередной элемент последовательности, обрабатываем его так, как поставлено в задаче, и после про него забываем. Для реализации данного алгоритма нам придётся поместить оператор ввода внутрь цикла.
Рассмотрим стандартные шаблоны решения задач данного класса:
Количество элементов в последовательности известно заранее (`N`).
readln(N);
for j:=1 to N do begin
read(a);
{Содержательна обработка}
end;
Обращаем внимание, что внутрь оператора цикла обязательно помещается оператор read, а не readln. Дело в том, что, как правило, числа будут вводиться в строчку и оператор ввода будет на каждом шаге забирать из буфера по `1` числу. Оператор readln при этом ещё удаляет из буфера всё лишнее до конца строки, поэтому числа прочитаны не будут. Количество элементов последовательности, как правило, задаётся отдельным числом в первой строке, поэтому его логичнее читать оператором readln.
Рассмотрим примеры задач данного класса.
Вводится натуральное число `N`, а затем `N` натуральных чисел, сумму которых необходимо вычислить.
var i,N,a,s:integer;
begin
readln(N);
s:=0;
for i:=1 to N do begin
read(a);
s:=s+a;
end;
writeln(s)
end.
Вводится натуральное число `N`, а затем `N` целых чисел. Выведите `"YES"`, если среди введенных чисел есть хотя бы один ноль, или `"NO"` в противном случае.
var n,i,k,a,s:integer;
begin
s:=0;
readln(n);
for i:=1 to n do begin
read(a);
if a=0 then k:=k+1;
end;
if k<>0
then writeln('YES')
else writeln('NO')
end.
Теперь рассмотрим второй тип задач из класса «Обработка последовательностей», когда количество элементов неизвестно заранее, но известен признак конца.
Признак конца - это служебный элемент, который в саму последовательность не входит. При обработке числовых последовательностей чаще всего признаком конца является ноль (но может быть и любое другое число). Наиболее распространённая ошибка - обработать признак конца как содержательный элемент (например, при расчёте среднего арифметического элементов последовательности). Поэтому порядок действий должен быть таким:
1) Считывание
2) Проверка на признак конца
3) Содержательная обработка
За 3 пунктом алгоритм замыкается в цикл. Выход из цикла - на втором пункте, в случае положительного ответа. Соответственно, шаблон алгоритма должен отражать данную логику действий.
read(a);
while a<>0 do begin
{содержательная обработка};
read(a)
end;
В теле цикла оператор ввода ставится последним, чтобы следующим действием за вводом было вычисление условия цикла (то есть, проверка на признак конца).
Программа получает на вход последовательность целых неотрицательных чисел. Ноль - признак конца. Вывести количество членов последовательности (не считая завершающего числа `0`).
var a,k:integer;
begin
read(a);
k:=0;
while a<>0 do begin
k:=k+1;
read(a);
end;
writeln(k);
end.
Вводится последовательность целых чисел. Ноль - признак конца. Вывести, сколько элементов данной последовательности больше (строго) предыдущего элемента.
При решении этой задачи нам нужно будет сохранять в отдельную переменную значение предыдущего числа перед вводом нового. Приведём код программы.
var a,pr,k:integer;
begin
read(a);
pr:=a;
k:=0;
while a<>0 do begin
if (a > pr) then k:=k+1;
pr:=a;
read(a);
end;
writeln(k);
end.
Вводится последовательность натуральных чисел. Ноль - признак конца. Вывести значение максимального элемента.
Это очень важная эталонная задача, которую обязательно надо уметь решать. Для поиска максимума применяется следующая стратегия. Нужно каждый элемент сравнить с текущим значением максимума и, если элемент оказался больше, то обновить текущее значение максимума. Рассмотрим код программы.
var a,m:integer;
begin
read(a);
m:=a;
while a<>0 do begin
if (a > m) then m:=a;
read(a);
end;
writeln(m);
end.
При решении этой задачи ещё остался вопрос корректной инициализации. В общем случае есть два способа.
Первый вариант - в качестве начального значения максимума брать «минус бесконечность» (для минимума - плюс бесконечность). Под «минус бесконечностью» в данном случае понимается некое число, которое гарантированно меньше чем любой элемент, который может нам встретиться. Инициализация бесконечностью допустима, если мы заранее знаем диапазон элементов последовательности. Это её недостаток, зато она пишется в один оператор присваивания.
Второй вариант - в качестве начального значения брать первый подходящий элемент последовательности. В случае глобального максимума берётся просто первый элемент последовательности. Сложнее в ситуации, когда первый элемент может оказаться неподходящим.
Найти максимальный чётный элемент последовательности в предположении, что он существует.
var a,m:integer;
begin
read(a);
while (a<>0)and(a mod 2 <> 0) do read(a);
m:=a;
while a<>0 do begin
if (a mod 2 = 0)and(a>m) then m:=a;
read(a);
end;
writeln(m);
end.
1.1 Алгоритмическая конструкция «Цикл»
Зачастую в задаче нужно повторять одни и те же действия много раз. Рассмотрим следующий пример: вывести на экран квадраты чисел от `1` до `100`.
Очевидно, что для решения этой задачи нам придётся `100` раз выполнять команду вывода соответствующего числа на экран. Писать `100` операторов вывода как-то не хочется (слишком трудоёмко), поэтому будем знакомиться с алгоритмической конструкцией, которая называется «цикл».
называется повторение фрагмента алгоритма несколько раз с возвратом в более раннюю точку исполнения алгоритма. Повторяемый при этом фрагмент алгоритма называется телом цикла.
Очевидно, что если возврат в более раннюю точку алгоритма происходит абсолютно всегда, то алгоритм никогда не доходит до своего завершения (выполняется бесконечно долго). Для предотвращения бесконечного повторения нужно поставить точку ветвления: в одной из веток будет возврат, а в другой - выход из цикла и дальнейшее продвижение по алгоритму.
В зависимости от положения точки ветвления выделяются циклы с предусловием (точка ветвления располагается перед телом цикла) и с постусловием (точка ветвления располагается после тела цикла).
1.2. Оператор while
В языке программирования есть несколько операторов цикла, реализующих как конструкцию с предусловием, так и конструкцию с постусловием. Познакомимся с ними.
Первый оператор цикла называется While и реализует алгоритмическую конструкцию с предусловием. В общем виде он записывается следующим образом:
while условие do оператор
Слова while и do являются служебными зарезервированными словами языка. Под условием (аналогично оператору if) понимается выражение, результат вычисления которого имеет тип boolean. Работает этот оператор следующим образом. Сначала вычисляется условие. Если в результате получилось true, то мы заходим в цикл, то есть выполняем тело цикла и возвращаемся вновь к вычислению условия. Если же получилось false, то происходит переход к следующему оператору в программы, и входа в цикл не будет. Фактически оператор while является многократным применением оператора if с пустой веткой else. Аналогично оператору if, тело цикла должно состоять из `1` оператора. Если нужно исполнить несколько, то следует использовать операторные скобки (begin end).
Возможна ситуация, когда цикл будет выполняться бесконечное количество раз (зациклится). Например, while 2*2=4 do… Что написать после do, совершенно не важно, важно, что оно будет выполняться, пока 2*2=4, а это всегда так, и никогда не изменится. Значит, чтобы избегать зацикливания, параметры условия должны быть переменными, например while x*x=4 do … Хотя это тоже не гарантирует отсутствие зацикливания. Поэтому при написании программ нужно всегда внимательно следить за тем, какие условия мы пишем в операторе цикла, чтобы не случилось ситуации зацикливания.
Также обратите внимание, что поскольку условие проверяется до входа в цикл, возможна ситуация, что при первой же проверке получится значение false и, соответственно, в цикл мы вообще не зайдём.
1.3. Примеры задач
Рассмотрим несколько примеров задач на оператор цикла.
Дано целое число, не меньшее `2`. Выведите его наименьший натуральный делитель, отличный от `1`.
Для решения этой задачи нам необходимо перебирать натуральные числа, начиная с двух и проверять каждое из них, не является ли оно делителем исходного числа. Процесс завершается, когда делитель найден. Очевидно, что процесс завершится всегда, поскольку в худшем случае число разделится само на себя. Приведём код программы.
var i,n:integer;
begin
readln(n);
i:=2;
while n mod i <> 0 do
i:=i+1;
end;
writeln (i);
end.
В первый день спортсмен пробежал `x` километров, а затем он каждый день увеличивал пробег на `10%` от предыдущего значения. По данному числу `y` определите номер дня, на который пробег спортсмена составит не менее `y` километров. Программа получает на вход действительные числа `x` и `y`. Программа должна вывести одно натуральное число.
В этой задаче нам нужно реализовать постепенное увеличение пробега. То есть, на каждом шаге цикла мы будем сохранять значение пробега в соответствующий день в одной переменной, а номер этого дня – в другой. Завершение, когда значение первой переменной станет не меньшим чем `y`. Приведём код программы. Все переменные, отвечающие за километры, имеют тип real (из условия).
var x,y:real; i:integer;
begin
readln(x,y);
i:=1;
while x<y do begin
x:=x/100*10+x;
i:=i+1;
end;
writeln(i);
end.
Дано натуральное число `N`. Вычислите его сумму цифр.
Для решения этой задачи на каждом шаге цикла нужно изменять наше число: при помощи операции mod можно выделить последнюю цифру из числа и прибавить её к сумме, а затем её надо выбросить из числа при помощи операции div. Делить нужно, естественно, на `10`. Критерий завершения – когда число станет равным нулю, ибо это будет означать, что мы уже рассмотрели все цифры и поделили на `10` однозначное число (по свойствам операции целочисленного деления известно, что при делении меньшего числа на большее получается ноль). Приведём код программы.
var a,n,s:integer;
begin
readln(n);
s:=0;
while n>0 do begin
a:=n mod 10;
s:=s+a;
n:=n div 10;
end;
writeln(s);
end.
Ввести целое число `n`. Вывести `"YES"`, если оно простое, и `"NO"`, если оно составное.
Эта задача демонстрирует сразу две важные вещи. Во-первых, как проверять делимость целых чисел, а во-вторых, технику флажков. Флажком называется переменная, которая имеет некоторое начальное значение и меняет его, если происходит определённое событие. Как правило, флажок имеет тип boolean.
В нашей задаче мы будем перебирать числа от `2` до квадратного корня из `n` и проверять, делится ли `n` на каждое из них. Изначально предположим, что `n` - простое, и присвоим флажку значение true, но если `n` поделится на какое-нибудь число, это будет значить, что оно составное, и, соответственно, флажок «упадёт» на значение false. Проверять на делимость нужно, сравнивая остаток от деления с нулём.
var n,i:integer;
f:boolean;
begin
readln(n);
f:=true;
for i:=2 to round(sqrt(n)) do
if n mod i = 0 then f:=false else;
if f=true
then writeln('YES')
else writeln('NO');
end.
1.4 Оператор repeat
Теперь познакомимся с другим оператором цикла, который реализует алгоритмическую конструкцию цикла с постусловием. Рассмотрим его синтаксис.
repeat
Оператор 1;
Оператор 2;
….
Оператор N
until условие
Все операторы, написанные между repeat и until, являются телом цикла. Это выгодно отличает оператор repeat от других циклов - составной оператор здесь не требуется, а операторными скобками можно считать слова repeat и until. Работает этот оператор по следующему алгоритму:
1) выполняется тело цикла;
2) вычисляется значение условия. Если получилось true, то выход из цикла и переход к следующему оператору программы, в противном случае переход к пункту 1.
Отличительная особенность оператора цикла repeat заключается в том, что тело всегда выполняется, по крайней мере, один раз. Это нужно учитывать в задачах при выборе оператора цикла. Аналогично оператору while, цикл repeat может зациклиться, правда в случае, когда условие никогда не принимает значение true, например, repeat…until 2*2=5.
Этот оператор цикла реализует следующую идею: «Повторять некоторую последовательность команд `N` раз, где `N` известно до начала повторения». Познакомимся с синтаксисом этого оператора.
for имя переменной := начальное значение to конечное значение do оператор
В этой конструкции переменная, стоящая после слова for, называется параметром или счётчиком цикла, а оператор, стоящий после слова do, называется телом цикла. Начальное и конечное значения, по сути, являются константами или выражениями одного типа со счётчиком. Алгоритм выполнения цикла for следующий:
1) вычисляются начальное и конечное значения;
2) счётчику цикла присваивается начальное значение;
3) значение счётчика сравнивается с конечным. Если оно больше ко-нечного, то выполнение цикла завершается и начинает выполняться следующий оператор программы, в противном случае переход к пункту 4;
4) выполняется тело цикла;
5) значение счётчика увеличивается на `1`;
6) переход к пункту 3.
В качестве примера рассмотрим решение задачи, поставленной в самом начале. В качестве счётчика будем использовать переменную i.
var i:integer;
begin
for i:=1 to 100 do write(i*i,' ');
end.
Согласитесь, что решение фактически в одну строчку выглядит гораздо приятнее, чем в `100` строк (если не пользоваться оператором цикла).
Необходимо сделать несколько замечаний по поводу цикла for.
1) Типы счётчика начального и конечного значений должны совпадать, при этом в настоящий момент из известных нам типов можно использовать только integer и boolean. Вещественный тип использовать нельзя.
2) Начальное и конечное значения вычисляются один раз до начала цикла (и после не перевычисляются). Рассмотрим пример.
i:=1; for i:=i to i do writeln('HI');
Этот оператор цикла выполнится всего один раз, а не бесконечно много.
3) В теле цикла значение счётчика изменять нельзя. Так прописано в стандарте языка Pascal, и это требование поддерживается в системах семейства Delphi и PascalABC. Однако в системах семейства Borland Pascal значение счётчика изменять можно, что может приводить к непредсказуемым последствиям (поэтому будем считать, что независимо от системы значение счётчика изменять нельзя).
4) После завершения цикла значение счётчика не определено, то есть нельзя считать, что оно равно конечному значению или больше на единицу и пользоваться этим в дальнейшем алгоритме.
5) Тело цикла по грамматике должно состоять только из `1` оператора. Если же там по алгоритму должно быть несколько, нужно использовать составной оператор. В этом смысле оператор for солидарен с операторами if и while.
6) Можно слово to заменить на слово downto. В этом случае значение счётчика после каждого выполнения тела цикла будет уменьшаться на `1`, а выход из цикла произойдёт, когда значение счётчика окажется меньше, чем конечное.
Выполнение любого оператора цикла можно завершить досрочно, если использовать процедуру break. На данном этапе она особенно актуальна, если надо досрочно прервать цикл for. Выполнение этой процедуры передаст управление на оператор, который следует за прерываемым оператором цикла.
Проиллюстрируем её работу следующим примером:
вводится натуральное число `x` `(2 <= x <= 30000)`. Выведите наименьший делитель числа `x`, отличный от `1`.
Мы уже разбирали алгоритм решения этой задачи выше. Продемонстрируем его с использованием цикла for.
var a,i: integer;
begin
readln(a);
for i := 2 to a do
if a mod i = 0 then
begin
writeln(i);
break;
end;
end.
В данном классе формулировка всех задач начинается со слов: «Вводится последовательность чего-нибудь…». Для простоты будем считать, что чисел - с ними мы умеем работать, но в общем случае это необязательно так. Далее нам нужно оценить какое-то свойство данной последовательности. Например, сколько в ней нулей, является ли она возрастающей (каждое следующее число больше предыдущего) и т. д. Причём, для оценки данного свойства, сохранение всей последовательности в памяти не требуется.
Общий алгоритм решения задач этого класса таков: мы считываем очередной элемент последовательности, обрабатываем его так, как поставлено в задаче, и после про него забываем. Для реализации данного алгоритма нам придётся поместить оператор ввода внутрь цикла.
Рассмотрим стандартные шаблоны решения задач данного класса:
Количество элементов в последовательности известно заранее (`N`).
readln(N);
for j:=1 to N do begin
read(a);
{Содержательна обработка}
end;
Обращаем внимание, что внутрь оператора цикла обязательно помещается оператор read, а не readln. Дело в том, что, как правило, числа будут вводиться в строчку и оператор ввода будет на каждом шаге забирать из буфера по `1` числу. Оператор readln при этом ещё удаляет из буфера всё лишнее до конца строки, поэтому числа прочитаны не будут. Количество элементов последовательности, как правило, задаётся отдельным числом в первой строке, поэтому его логичнее читать оператором readln.
Рассмотрим примеры задач данного класса.
Вводится натуральное число `N`, а затем `N` натуральных чисел, сумму которых необходимо вычислить.
var i,N,a,s:integer;
begin
readln(N);
s:=0;
for i:=1 to N do begin
read(a);
s:=s+a;
end;
writeln(s)
end.
Вводится натуральное число `N`, а затем `N` целых чисел. Выведите `"YES"`, если среди введенных чисел есть хотя бы один ноль, или `"NO"` в противном случае.
var n,i,k,a,s:integer;
begin
s:=0;
readln(n);
for i:=1 to n do begin
read(a);
if a=0 then k:=k+1;
end;
if k<>0
then writeln('YES')
else writeln('NO')
end.
Теперь рассмотрим второй тип задач из класса «Обработка последовательностей», когда количество элементов неизвестно заранее, но известен признак конца.
Признак конца - это служебный элемент, который в саму последовательность не входит. При обработке числовых последовательностей чаще всего признаком конца является ноль (но может быть и любое другое число). Наиболее распространённая ошибка - обработать признак конца как содержательный элемент (например, при расчёте среднего арифметического элементов последовательности). Поэтому порядок действий должен быть таким:
1) Считывание
2) Проверка на признак конца
3) Содержательная обработка
За 3 пунктом алгоритм замыкается в цикл. Выход из цикла - на втором пункте, в случае положительного ответа. Соответственно, шаблон алгоритма должен отражать данную логику действий.
read(a);
while a<>0 do begin
{содержательная обработка};
read(a)
end;
В теле цикла оператор ввода ставится последним, чтобы следующим действием за вводом было вычисление условия цикла (то есть, проверка на признак конца).
Программа получает на вход последовательность целых неотрицательных чисел. Ноль - признак конца. Вывести количество членов последовательности (не считая завершающего числа `0`).
var a,k:integer;
begin
read(a);
k:=0;
while a<>0 do begin
k:=k+1;
read(a);
end;
writeln(k);
end.
Вводится последовательность целых чисел. Ноль - признак конца. Вывести, сколько элементов данной последовательности больше (строго) предыдущего элемента.
При решении этой задачи нам нужно будет сохранять в отдельную переменную значение предыдущего числа перед вводом нового. Приведём код программы.
var a,pr,k:integer;
begin
read(a);
pr:=a;
k:=0;
while a<>0 do begin
if (a > pr) then k:=k+1;
pr:=a;
read(a);
end;
writeln(k);
end.
Вводится последовательность натуральных чисел. Ноль - признак конца. Вывести значение максимального элемента.
Это очень важная эталонная задача, которую обязательно надо уметь решать. Для поиска максимума применяется следующая стратегия. Нужно каждый элемент сравнить с текущим значением максимума и, если элемент оказался больше, то обновить текущее значение максимума. Рассмотрим код программы.
var a,m:integer;
begin
read(a);
m:=a;
while a<>0 do begin
if (a > m) then m:=a;
read(a);
end;
writeln(m);
end.
При решении этой задачи ещё остался вопрос корректной инициализации. В общем случае есть два способа.
Первый вариант - в качестве начального значения максимума брать «минус бесконечность» (для минимума - плюс бесконечность). Под «минус бесконечностью» в данном случае понимается некое число, которое гарантированно меньше чем любой элемент, который может нам встретиться. Инициализация бесконечностью допустима, если мы заранее знаем диапазон элементов последовательности. Это её недостаток, зато она пишется в один оператор присваивания.
Второй вариант - в качестве начального значения брать первый подходящий элемент последовательности. В случае глобального максимума берётся просто первый элемент последовательности. Сложнее в ситуации, когда первый элемент может оказаться неподходящим.
Найти максимальный чётный элемент последовательности в предположении, что он существует.
var a,m:integer;
begin
read(a);
while (a<>0)and(a mod 2 <> 0) do read(a);
m:=a;
while a<>0 do begin
if (a mod 2 = 0)and(a>m) then m:=a;
read(a);
end;
writeln(m);
end.
называется процесс, в котором участвуют две или более стороны, ведущие борьбу за реализацию своих интересов.
Согласно этому определению, довольно много жизненных ситуаций можно считать играми - для этого требуется лишь борьба двух или более лиц и какие-либо интересы, за которые эти лица ведут борьбу. Шахматы, домино, прыжки в высоту - всё это игры. Стремление занять свободное место в автобусе, соперничество мировых держав в ядерной сфере, беседа сотрудника ГИБДД с нарушителем, поход семейной пары в торговый центр - и это тоже игры. Так, в случае стремления занять свободное место в пустом автобусе в этом процессе участвуют не менее двух человек, которые ведут борьбу за свободные места (свои интересы), причём довольно часто количество свободных мест намного меньше количества участвующих в этой игре человек, поэтому в этой игре есть выигравшие и проигравшие. В этом случае интересы (занять свободное место) у игроков совпадают. Однако в случае игры «поход семейной пары в торговый центр» интересы часто строго противоположные: жене хочется совершить как можно больше покупок; мужу - потратить как можно меньше денег на эти покупки.
Изучение такого широкого класса игр математическими методам бессмысленно – в каждой игре есть свои мало-формализуемые особенности, а процесс принятия решений игроками может опираться не только на какие-то математические принципы, в него могут вписываться другие особенности человека, например, уровень интеллекта и характер.
Для решения спора Петя и Вася обращаются к компьютеру за случайным натуральным числом. Если выданное число - чётное, спор выигрывает Петя, если нечетное - спор выигрывает Вася. Является ли описанная процедура игрой?
Данная процедура тоже является игрой - два игрока ведут борьбу за свои интересы (выиграть спор), и то, как это они делают - неважно. Фактически, игроки с помощью компьютера реализовали подкидывание монетки.
Для решения спора Петя и Вася пишут цифры по очереди на доске слева направо, начинает Петя. Если после десяти ходов полученное `10`-значное число не делится на девять, в споре побеждает Петя, а если делится – Вася. Докажите, что Вася может выиграть спор.
Второй игрок (Вася) может дополнять число, написанное первым игроком, до девяти. Если ход Пети - «`9`», то ход Васи - «`0`» и т. п. После десяти ходов получим `10`-значное число, сумма цифр которого равна `9^(**)5=45`, и полученное число будет делиться на девять. Таким образом, второй игрок (Вася) сможет выиграть при любых ходах первого игрока (Пети).
Такие игры, в которых как играть - известно одному или обоим игрокам, уже представляют интерес для формализации и изучения. Одним из самых узких классов таких игр является класс математических игр. Этому классу и посвящено данное задание.
Будем называть игру математической, если для неё выполнены следующие условия:
Условие 1. В игре участвуют два игрока.
Условие 2. Игра заканчиваются выигрышем одного из участников. Это автоматически означает проигрыш соперника. Иногда в математических играх допускают ничью.
Условие 3. В игре участники ходят по очереди и помнят все предыдущие ходы.
Условие 4. Игра характеризуется позицией, которая зависит только от ходов игроков.
Вернёмся к примеру 1. Эта игра не будет являться математической, поскольку не будет удовлетворять только условию 4: мы не сможем определить позицию игры, которая будет зависеть только от хода самих игроков, поскольку игроки обращаются к компьютеру.
Также в математических играх по той же причине не может быть случайных карточных раскладов, игральных кубиков, подкидываний монеток. Попробуем же тогда реализовать игру из этого примера, которая является фактическим подкидыванием монетки игроками, без помощи, как монетки, так и компьютера.
Для решения спора Петя и Вася пишут на листочках по натуральному числу. Если сумма написанных чисел - чётная, спор выигрывает Петя, если нечетная - спор выигрывает Вася. Является ли описанная процедура математической игрой?
Здесь уже не выполняется условие 3, которое гласило, что игроки должны ходить по очереди и помнить все предыдущие ходы.
Сделаем небольшую модификацию условий игры, чтобы игра стала математической и посмотрим, какая игра из этого получится. Чтобы условие 3 поочередности выполнялось, сначала должен походить первый игрок, написать своё число на бумажке и показать это число всем, включая второго игрока. Кто из двух игроков будет первым, они между собой должны договориться сами. И тогда уже второй игрок, зная число, которое написал первый, должен написать своё число, затем эти два числа будут сложены и сумма проверена на чётность.
Однако, если второй игрок обладает хоть каким-либо интеллектом, он может подобрать своё число, чтобы сумма была выигрышной для него чётности. Суть «подкидывания монетки» от этого полностью теряется, т. к. данная игра находится под полным контролем второго игрока.
Два человека встречаются и обмениваются закрытыми сумками, понимая, что одна из них содержит деньги, другая - товар. Каждый игрок может уважать сделку и положить в сумку то, о чём договорились, либо обмануть партнёра, дав пустую сумку. Является ли эта игра математической?
Во-первых, эта игра не удовлетворяет условию 2: в условии не определено, какой игрок выигрывает в каком случае, а какой автоматически при этом проигрывает. Во-вторых, игроки ходят одновременно, а не по очереди, что нарушает условие 3. Поэтому данная игра не является математической.
Заметим, что условие 2 можно выполнить, считая, что в случае если один игрок обманул другого, обманувший игрок выиграл, а обманутый проиграл, в остальных случаях (оба игрока честные или оба обманщики) зафиксировать ничью. Однако условие 3, как и в предыдущем примере, уже нельзя выполнить без существенного изменения самой игры.
Итак, в математической игре имеются два игрока, которые ходят поочередно. Участник, который начинает игру, обычно называется первым игроком, его соперник – вторым. Имеется конечное или бесконечное множество позиций. В каждой позиции для обоих игроков указаны допустимые ходы – разрешённые переходы в другие позиции. Некоторые позиции объявляются выигрышными для какого-то игрока, что автоматически означает, что эти позиции являются проигрышными для соперника. Очень часто выигрышными объявляются те и только те позиции, из которых соперник не может сделать ход, т. е. выигрывает тот игрок, которому удаётся своим последним ходом достичь позиции, в которой у соперника нет допустимых ходов.
Есть две кучи по семь камней в каждой. За ход разрешается взять любое количество камней, но только из одной кучи. Проигрывает тот, кто не сможет сделать ход. Как можно определить позиции в данной игре, и какие позиции будут выигрышными?
Позицией в данной игре являются два числа `(x, y):` `x` – количество камней в первой куче, `y` – количество камней во второй куче. Игрок выигрывает, если противник не может сделать ход, т. е. перед ходом противника камней в обеих кучах не останется. Таким образом, позиция `(0, 0)` является выигрышной для того из игроков, который попал туда своим последним ходом.
Особенно отметим следующее.
Во-первых, в играх могут быть ничьи. Это значит, что некоторые позиции для обоих игроков объявляются ничейными. Игроку целесообразно добиваться ничьей только тогда, когда он не может гарантированно достичь выигрышной позиции.
Во-вторых, оба игрока не обязательно должны преследовать одинаковые цели (например, чтобы противник не смог сделать ход). Так, например, в примере 2 один из игроков стремится к тому, чтобы полученное число не делилось на девять, а второй стремится к обратному.
Поэтому позиция должна ещё характеризоваться номером игрока (либо того, который пришел в эту позицию, либо того, который делает ход из этой позиции в зависимости от ситуации). Так, если в примере 7 добавить номер игрока, который делает ход, то теперь позиция в этой задаче будет выражаться тремя числами `(x,y,n)`, где `n` – номер игрока, который делает ход, имея в начале $$ x$$ камней в первой куче, а $$ y$$ – во второй.
Позиция `(0,0,1)` будет проигрышной для первого игрока (он не может сделать ход) и выигрышной для второго, позиция `(0,0,2)` – наоборот.
Однако в играх, в которых игроки преследуют одинаковые цели и возможные ходы у обоих игроков одинаковы, как например, в примере 5, можно номер игрока из позиции опустить. В этом задании мы будем рассматривать только такие игры.
В точке 0 оси координат находится фишка. За ход игрок обязан подвинуть фишку на единицу влево или вправо. Выиграет тот игрок, после хода которого координата фишки превысит десять. Как определить позиции в данной игре? Какие позиции следует объявить выигрышными? Какие позиции следует объявить ничейными?
Позицией является целое число `(x):` положение фишки на оси. При этом все позиции с `x > 10` будут проигрышными для первого игрока, т. е., выигрышными для второго. Стартуя из позиции `(10)`, первый игрок может одним ходом передвинуть фишку в позицию `(11)` и выиграть. Если же игра начинается из позиции `(x)`, `[x < 10]`, то ни первый, ни второй игрок не могут гарантированно рассчитывать на победу, так как любой игрок в данной игре может не позволить своему противнику достичь выигрышной позиции, просто двигая каждый раз своим ходом фишку влево. Поэтому, стартуя из позиции `(x)`, `[x < 10]`, игра может закончиться выигрышем одного из игроков, если и только если соперник ошибётся. Но что следует считать исходом игры при старте, например, из начала координат (как в условии примера)? Можно было бы, например, считать, что исход игры при старте из начала координат просто не определён. Но мы потребуем выполнения более жёсткого условия.
Условие 5. При старте из любой допустимой позиции, как бы ни играли соперники, через конечное (возможно, очень большое) число ходов обязательно достигается либо выигрышная, либо ничейная позиция.
Иначе говоря, независимо от того, как играют оба игрока, через конечное число ходов игра должна закончиться выигрышем одного из соперников или ничьей.
Так, в примере 5 условие 5 выполняется, поскольку количество камней с каждым ходом уменьшается, а значит, когда-нибудь камней не останется, и один из игроков выиграет.
Для того, чтобы игра из примера 6 удовлетворяла условию 5, нужно кроме уже заданных выигрышных позиций `(x)`, `[x > 9]` объявить все позиции `(x)`, `[x < 10]` ничейными[1].
Чтобы избежать игр с бесконечным количеством ходов, мы можем, например, запретить игрокам ходы, приводящие к полному повторению ранее встречавшихся позиций. Или, наоборот, в таком случае объявлять ничью. Так, в шахматах троекратное повторение одной и той же позиции на доске является поводом для объявления ничьей (в случае, если это будет замечено одним из игроков).
[1] Таким образом, в примере 6 при старте из любой точки кроме точки `(10)` игроки не сделают ни одного хода, и немедленно будет объявлен результат.
Вернёмся к примеру 5 и зададимся вопросом: кто выиграет?
В общем случае может выиграть любой из игроков – для этого его сопернику достаточно «подыграть». Однако второй игрок может выиграть при любых ходах первого игрока. Для этого ему нужно брать то же количество камней, которое брал первый игрок предыдущим ходом, но из другой кучи. После хода второго игрока количество камней в обеих кучах будет равным. Далее. Первый игрок возьмёт несколько камней в одной из кучек, тогда после его хода количество камней в кучках станет неодинаковым, а значит, второй игрок сможет уравнять количество камней в кучах и передать ход сопернику. Второй игрок всегда сможет сделать свой ход, а поскольку камней становится все меньше и меньше, наступит момент, когда один из игроков не сможет сделать ход, и это будет первый игрок. Таким образом, второй игрок сможет выиграть в данный игре, как бы ни играл первый.
Выигрышной стратегией назовём набор правил, следуя которым, один из игроков обязательно выиграет при произвольных ответах соперника.
Аналогично, ничейной стратегией назовём набор правил, следуя которым, один из игроков обязательно выиграет или сведёт игру к ничьей при произвольных ответах соперника.
Подчеркнём в определении стратегии условие «при произвольных ответах соперника». Важно понимать, что на месте игрока может оказаться что или кто угодно, например, компьютер. Нужно уметь отвечать на произвольные ходы соперника и в любом случае выигрывать.
Как было сказано выше, мы пытались выделить игры, в которых один из игроков обязательно выиграет при произвольных ответах соперника. Следующая теорема позволяет утверждать, что математические игры и есть искомый класс игр.
В любой математической игре существует либо выигрышная стратегия одного из игроков, либо ничейная стратегия для обоих игроков.
Идея доказательства этого утверждения в частном случае будет рассмотрена при решении задач методом анализа с конца (см. § 3).
С одной стороны, заметим, что данная теорема обобщается на случай игр, которые теоретически могут продолжаться бесконечно долго. Для этого в условии теоремы вместо существования ничейной стратегии для обоих игроков нужно потребовать, чтобы каждый игрок имел стратегию, позволяющую данному игроку не проиграть.
С другой стороны, рассмотрим игры, которые завершаются за конечное количество ходов выигрышем одного из игроков (и ничьих нет). Согласно теореме, у кого-то из игроков обязательно существует выигрышная стратегия, и он должен выиграть у своего соперника, как бы ни играл последний. Введём понятие правильной игры.
называется игра, в которой каждый из игроков применяет выигрышную или ничейную стратегию, если она у него есть.
Так, если игроки из примера 2 играют в правильную игру, второй игрок должен воспользоваться своей выигрышной стратегией (например, дополнять число до девяти; у него может быть также и иная выигрышная стратегия) и довести игру до победы.
Таким образом, ответить на вопрос, заданный в самом начале (см. пример 1), кто выиграет при правильной игре, можно так: необходимо найти определённую стратегию одного из игроков и доказать, что она является выигрышной.
В заключение параграфа отметим, что согласно теореме выигрышная или ничейная стратегия существуют даже в таких математических играх, как шахматы и шашки. Однако ни человеческий ум, ни современные вычислительные мощности пока не позволили найти эту стратегию…
Одним из способов нахождения выигрышных стратегий является удачный ответ на ход противника, например, учитывающий симметрию.
Два игрока по очереди ставят на шахматную доску слонов так, чтобы фигуры не били друг друга. Цвет фигур значения не имеет. Проигрывает тот, кто не сможет сделать ход. Кто выиграет при правильной игре?
Выиграет второй игрок. Для этого мысленно разрежем шахматную доску пополам линией, параллельной одной из сторон доски. Второй игрок должен ставить слона на место, симметричное полю, на которое текущим ходом поставил свою ладью первый игрок относительно проведённой оси. Докажем от противного, что второй игрок всегда сможет сделать ход.
Пусть это неверно и второй игрок не сможет сделать хода. Разберём два случая.
Случай 1. На поле предполагаемого хода уже стоит слон. Но этот слон не мог быть поставлен ранее вторым игроком, так как он ставит слонов только симметрично ходам первого игрока. Если первый игрок ранее поставил слона на это поле, то второй игрок был обязан своим ходом поставить слона на поле, симметричное полю противника. Однако по условию на это поле слона поставил первый игрок текущим ходом. Получаем противоречие.
Случай 2. Данное поле находится под боем какого-то слона. Заметим, что этот слон не был поставлен первым игроком на предыдущем ходу, так как два симметричных относительно оси слона не бьют друг друга. Тогда, в соответствии со стратегией второго игрока, слон, расположенный симметрично данному, также должен уже стоять на доске. Однако этот слон будет бить слона, поставленного первым игроком предыдущим ходом. Противоречие.
Таким образом, было доказано, что у второго игрока всегда есть допустимый ход, а так как игра должна когда-нибудь закончиться (на шахматной доске всего 64 клетки), то первый игрок когда-то не сможет сделать своего хода и проиграет.
В кучке лежат: а) `30` камней; б) `32` камня. За ход можно взять от одного до пяти камней из кучи. Проигрывает тот, кто не сможет сделать ход. Кто выигрывает при правильной игре?
В данном случае работает стратегия дополнения до шести. Пусть своим ходом первый игрок берёт `x in{1,2,3,4,5}` камней. Тогда в пункте а) второй игрок отвечает ходом `(6-x)`, и поскольку после каждого его хода количество камней будет делиться на шесть, то в итоге второй игрок выиграет.
В пункте б) выигрывает первый игрок. Первым ходом он должен взять два камня и свести задачу к пункту а), в котором он уже будет выступать как второй игрок.
Два игрока перемещают ладью из левого нижнего угла `("a"1)` шахматной доски в правый верхний `("h"8)`. За ход можно сместить ладью на любое количество клеток вверх или вправо. Кто выиграет при правильной игре?
Выиграет второй игрок. Для этого ему нужно во время ходов возвращать ладью на диагональ, проведенную из левого нижнего угла в верхний правый угол. Подумайте, почему первый игрок проиграет при любых своих ходах.
Вторым важным способом решения задач является решение задачи с конца. Предположим (хотя это и не всегда верно), что для обоих игроков одни и те же позиции являются выигрышными.
Вернёмся к примеру 9.
Для нахождения выигрышной стратегии рассмотрим общую задачу. Считаем, что начальная позиция является параметром, и будем искать выигрышную стратегию при старте с этой позиции. Будем обозначать знаком «`-`» позиции, в которых при правильной игре участник, начинающий играть из данной позиции, выиграет, и знаком «`+`» отметим позиции, ведущие к поражению[1].
Если игра начинается в поле `"h"8`, первый игрок уже проиграл – это позиция «`+`» (рис. 1).
Далее, если игра стартует с полей `"h"1-"h"7` или `"a"8-"g"8`, то начинающий игрок может за один ход достичь поля `"h"8` и выиграть. Это позиция «`-`» (рис. 2).
Рассмотрим ладью, стоящую в поле `"g"7`. У первого игрока есть только два хода – `"g"8` и `"h"7`. Но в обеих этих позициях стоит «`-`». Следовательно, второй игрок, стартующий из этих позиций, выиграет. Как бы ни ходил первый игрок, он проиграет. Это снова позиция «`+`».
Далее, рассмотрим группы полей `"g"1-"g"6` и `"a"7-"f"7` (рис. 3). Стартуя из этих полей, первый игрок может за один ход попасть в поле `"g"7`, которое помечено знаком «`+`». Любой ход второго игрока из `"g"7` ведёт к его проигрышу.
Продолжая таким образом заполнять шахматную доску, мы видим, что знаки «`+`» размещаются на диагонали `"a"1-"h"8` (рис. 4). В поле a1 стоит знак «`+`», поэтому первый игрок потерпит поражение.
Зафиксируем общие правила расстановки знаков «`+`» и «`-`»:
1) знаком «`-`» обозначаются позиции, в которых при правильной игре участник, стартующий из данной позиции, выиграет, и знаком «`+`» отмечаются позиции, ведущие к поражению;
2) знак «`-`» ставится в позиции, из которой можно за один ход прийти в позицию со знаком «`+`»;
3) знак «`+`» ставится в выигрышных позициях, а также в тех позициях, из которых все возможные ходы ведут только в позиции, уже отмеченные знаком «`-`»[2].
Таким образом, сначала нужно расставить знаки «`+`» в выигрышных позициях. На втором этапе нужно отметить знаком «`-`» те позиции, которые отделяет от выигрышных один ход. На третьем этапе следует просмотреть все позиции и найти «тупиковые», ведущие к положениям, обозначенным знаком «`-`». На игровом поле обязательно будет хотя бы одна такая позиция[3]. Второй и третий этапы необходимо поочередно повторять до тех пор, пока начальная позиция не будет помечена знаком «`+`» или «`-`», что и даст ответ на вопрос, кто выиграет при правильной игре.
Как же должен действовать побеждающий участник игры? Он должен стремиться ходить в позиции, отмеченные знаком «`+`». При этом после очередного хода соперника он опять окажется в позиции со знаком «`-`», так как по определению знака «`+`» все возможные ходы из этой позиции ведут только в позиции со знаком «`-`». Таким образом, стратегия выигрывающего игрока формулируется просто: делать ход в позиции, обозначенные знаком «`+`». По определению знака «`-`» из этой позиции существует хотя бы один ход в позицию, отмеченную знаком «`+`», поэтому такой ход у выигрывающего игрока всегда будет в наличии.
Отметим следующий факт. Если известно, что игра длится не более чем `n` ходов при любых действиях первого и второго игроков, то начальная позиция обязательно будет помечена не более чем за `n` повторений шагов `2` и `3`. Это является идеей доказательства основной теоремы из § 2 в частном случае игр, в которых ничейных позиций нет, и каждая позиция является выигрышной для одного из игроков.
Два игрока играют в следующую игру. Перед ними лежат две кучи камней, в первой – три камня, а во второй – два камня. У каждого игрока имеется неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в три раза число камней в какой-либо куче, или добавляет один камень в любую кучу. Выигрывает тот игрок, после хода которого, в двух кучах станет не менее `16` камней. Кто выиграет при правильной игре: игрок, сделавший первый ход, или игрок, сделавший второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
Попробуем изобразить позиции графически. Рассмотрим таблицу, в которой количество камней в первой куче будет соответствовать номеру столбца, а количество камней во второй куче – номеру строки. Чёрным цветом выделена позиция `(2, 3)`, с которой должна начинаться игра в условии:
1. Выигрышные позиции – точки с координатами `x`, `y`, где `x + y ≥ 16`. Данные точки обозначим знаком «`+`» в таблице ниже[4].
2. Далее, ставим знак «`-`» в позиции, которые отделяет от выигрышных один ход.
По условию, можно либо увеличить одну из кучек в три раза, либо добавить камень в одну из куч, т. е. мы должны поставить знак «`-`» в позицию `(x, y)`, если верно одно из условий: `x+y+1≥16`; `x+3y≥16`; `y+3x≥16`.
3. После чего, ставим знак «`+`» в те позиции, из которых все ходы ведут только в позиции, обозначенные знаком «`-`». Таковыми будут позиции `(0, 5)`, `(5, 0)` и `(4, 3)`, `(3, 4)`.
4. Знак «`-`» ставим в те позиции, стартуя из которых можно за один ход дойти до одной из позиций, отмеченных знаков «`+`» (поставленных на этапе 3).
Стартуя из позиций `(4, 0)`, `(0, 4)`, `(3, 3)`, `(2, 4)`, `(4, 2)`, можно попасть в позиции, обозначенные знаком «`+`», увеличив количество камней в одной из кучек на единицу. Из позиций `(1, 4)` и `(4, 1)` можно прийти в позиции со знаком «`+`», увеличив в три раза количество камней в меньшей куче.
5. Знак «`+`» ставим в те позиции, из которых все ходы ведут только в позиции, обозначенные знаком «`-`». На этот раз таковыми будут позиции `(2, 3)` и `(3, 2)`.
В позиции `(2, 3)` был поставлен знак «`+`», а это значит, что победит второй игрок.
При оформлении задачи необходимо указать выигрывающего игрока, записать его стратегию и показать, что этот игрок победит при любых ответах соперника. Если имеется таблица позиций, то стратегия выигрывающего игрока формулируется простым правилом: делать ходы в позиции, отмеченные знаком «`+`». Но эту стратегию рекомендуется записать в явном виде. Таблицу позиций же, наоборот, при оформлении работы можно не рисовать (она уже сделала свое дело: помогла определить победителя и найти его стратегию).
Покажем, что второй игрок может выиграть при произвольных ответах первого игрока.
Рассмотрим все возможные начальные ходы первого игрока и укажем правильные ответы соперника:
а) если первый игрок в три раза увеличивает число камней в одной из куч, то второй игрок должен увеличить количество камней в этой же куче также в три раза. Тогда в обеих кучах будет как минимум 2*3*3+3=21 камень. Второй игрок побеждает. Рассмотрение этого случая закончено;
б) если первый игрок из позиции (2, 3) делает ход (2, 4) или (3, 3), то второй игрок должен пойти в позицию (3, 4) (именно она в нашем случае обозначена знаком «+»). Теперь первый игрок делает второй ход (заметим, этот ход не может быть выигрышным). Возможны три варианта:
- первый игрок увеличивает в три раза количество камней в одной из куч. Тогда второй игрок повторяет это действие с оставшейся кучкой камней, получает в сумме 21 камень и выигрывает,
- первый игрок добавляет один камень в первую кучу – позиция (4, 4). Тогда второй игрок увеличивает количество камней в одной из куч в три раза, получает в сумме 16 камней и выигрывает,
- первый игрок добавляет один камень во вторую кучу – позиция (3, 5). Тогда второй игрок увеличивает количество камней во второй куче в три раза, получает в сумме 18 камней и выигрывает.
Таким образом, второй игрок побеждает при любых ходах своего соперника.
Обратите внимание, что стратегию второго игрока можно придумать, не основываясь на таблице позиций. Важно помнить: если вы пропустите или не разберёте хотя бы один ход соперника (проигрывающего игрока), это может быть чревато тем, что данная стратегия может оказаться в корне неверной. Также нужно внимательно отнестись к расстановке знаков «`+`» и «`-`» в таблице позиций: один неверно поставленный знак может изменить ответ. Лучше не торопиться и расставить только те знаки, в которых вы уверены на данный момент. И не существенно, если вы не поставите никакого знака в данной позиции на определенном этапе (например, по правилам его необходимо поставить, но вы этого не заметили). Главное – не поставить неверного знака.
[1] «`+`»-позиции иногда называют `"P"`-позициями, а «`-`»-позиции – `"N"`-позициями по первым буквам английских слов «Previous» (предыдущий) и «Nеxt» (следующий), указывающими, какой из игроков выиграет при старте из этой позиции – игрок, который пришёл в эту позицию последним ходом, или игрок, совершающий следующий ход из этой позиции.
[2] Недопустимо, чтобы из этой позиции один ход вёл в позицию, обозначенную знаком «`+`», а другой – вёл в позицию, ещё не обозначенную ни одним из знаков.
[3] Хотя убедиться в этом непросто, мы предлагаем читателю самостоятельно подумать, почему это верно.
[4] Хотя таблица должна быть бесконечной (количество камней может быть сколь угодно большим), достаточно нарисовать таблицу `17` x `17` – случаи, когда в одной из куч более `16` камней, нас не интересуют, так как все эти позиции являются выигрышными.
Данный способ является разновидностью анализа с конца и заключается в том, что мы будем анализировать в знаках «`+`» и «`-`» не все позиции, а только те, в которые можно прийти из начальной позиции. Для этого мы нарисуем дерево ходов из начальной позиции. Разберём этот метод на примере 10.
Первоначальная позиция - `(2,3)`. За один ход из этой позиции можно прийти в позиции: `(3,3)`; `(2,4)`; `(6,3)`; `(2,9)`, добавляя один камень в одну из куч или умножая количество камней в куче на три.
Наша цель, в конечном счёте, во все эти позиции поставить знаки «`+`» и «`-`». Чтобы поставить знак «`+`», нужно быть уверенным, что все ходы из этой позиции ведут в «`-`»; для того, чтобы поставить знак «`-`», нужно, чтобы хотя бы один ход из этой позиции вел к «`+`».
Выше приведённое означает, что если из позиции за один ход можно прийти в позицию с количеством камней, не меньшим `16` (что по условию задачи равносильно выигрышу), это - позиция, выигрышная для первого игрока, т. е. позиция «`-`». В связи с этим знаки «`-`» можно поставить в позициях `(6,3)` и `(2,9)`, умножая количество камней в большей куче на `3`, мы получим `6^(**)3+3=21` и `2+9^(**)3=29` камней соответственно, и выиграем.
Мы не сможем такого утверждать для позиций `(3,3)` и `(2,4)`, поэтому отразим в дереве все позиции, в которые мы можем прийти из них ещё за один ход. Две из полученных после двух ходов позиций повторяются (это позиция `(3,4)`). Можно не делать дубликат позиции `(3,4)`, а провести к ней пути как из позиции `(2,4)`, так и из позиции `(3,3)`. А можно - оставить как есть, что в данном случае мы и сделаем.
Обозначим знаком «`-`» позиции, из которых можно дойти за один ход до выигрышных. Из оставшихся позиций продолжаем дерево дальше позициями, в которые можно попасть за три хода
Из всех полученных позиций можно за один ход дойти до выигрышных. Поэтому, в них можно поставить «`-`» и далее дерево ходов не продолжать. Теперь, посмотрим на позиции `(3,4)` и `(4,3)`. Все ходы в этих позициях ведут в позиции со знаком «`-`», т. е. в позиции, проигрышные для пришедшего в них игрока (и выигрышные для начинающего с них игрока). Поэтому, начинающий из такой позиции при правильной игре проиграет - это позиции «`+`».
После этого, отметим знаком «`-`» позиции `(3,3)` и `(2,4)` уровнем выше как позиции, из которых существует хотя бы один ход в позицию, отмеченную знаком «`+`». И, наконец, позицию `(2,3)` отметим знаком «`+`» как позицию, все ходы из которой ведут в позиции со знаком «`-`».
Таким образом, в позиции `(2,3)` стоит знак «`+`»[1], а это означает, что в данной игре выиграет второй игрок. Его стратегия формулируется тем же правилом, что и ранее: делать ходы в позиции, отмеченные знаком «`+`». Стратегия выигрывающего игрока в явном виде («образец оформления примера») уже была описана ранее. Аналогично анализу с конца обратим внимание, что важно построить дерево позиций до конца - пропуск любой, даже самой маленькой, ветви может существенно поменять всю расстановку знаков в вершинах дерева существенно поменять всю расстановку знаков в вершинах дерева и даже привести к тому, что победит другой игрок. Причём последнее не является редкостью.
Отдельно отметим, что хотя «анализ с конца» и «дерево игры» являются различными вариациями одной и той же идеи, в некоторых случаях быстрее действовать одним методом, а в некоторых - другим. Так, если в игре легко отобразить схематично всё множество позиций (например, на клетчатом листе), с другой стороны, количество ходов до выигрыша может быть довольно большим (см. пример 9), гораздо легче действовать методом «анализ с конца». В примере 10 решения обоими методами примерно идентичны по трудозатратам.
Однако, если известно, что игра всегда заканчивается за малое количество ходов - логичнее нарисовать дерево игры. Более того, если множество позиций сложно или невозможно каким-либо образом изобразить схематически (например, если не две кучи камней, а три кучи) - «анализ с конца» вообще малоприменим – нужно рисовать дерево игры или вообще решать задачу методом «удачный ход».
[1] Поскольку данное дерево игры заполнялось знаками по тем же правилам, что и таблица позиций, знаки «`+`» и «`-`» в позициях, отмеченных на дереве и в таблице позиций ранее, должны совпадать.
