Возможно об этих двух методах следовало написать с самого начала, т.к. из них легко вывести все предыдущие методы. Начнем с метода ислючения.




У нас имеется две открытые клеточки. В одной стоит единица, в другой - четверка. У каждой цыферки есть своя область действия - это неоткрытые клетки вокруг неё. Например область действия единички я обозначил красным цветом на первом рисунке. Она состоит из семи клеточек. В одной из этих семи клеточек есть мина. Область действия четверки я обозначил синим цветом. В четырех из семи этих клетках стоят мины. Далее я обозначил синим цветом область, которая будет общей для единицы и четверки. Она состоит из четырех клеток.
Далее внимателно следите за моими рассуждениями. В красной области не более одной мины, значит в синей области тоже не более одной мины. Сумма мин в синей и

Вот схема следующего правила



Точкой обозначена клетка, которая пустая, значит на неё нужно кликнуть левой кнопкой мыши.
Здесь в качестве знака вопроса может выступать не только пустая клетка, но и край игрового поля. Если имеется длинный ряд из единиц, то это правило можно применить многократно. Например так.

Наконец-то мы подошли к самому главному методу. Это метод вычитания. Рассмотрим пример.



Что мы имеем? Проблема заключается в том, что клетка в углу занята миной. Помимо этого еще имеется куча мин, которые вконец все запутали. Что делать?
Давайте представим, что было бы если бы этих мин не было. Т.е. давайте вычтем эти мины.


Если вы внимательно прочитали предыдущую статью, то для вас не составит труда расставить мины.




Я надеюсь вы осознали, на сколько это крутой метод. Этим методом можно пользоваться в любой ситуации, и не просто можно, а нужно! Как только вы поставили где-нибудь мину, сразу вычитайте её и смотрите, как выглядит поле без неё. Если вы часто будете это делать, то в скором времени вы научитесь видеть поле без мин. Вы будете ощущать себя как Нео в матрице, и за этими цыферками сразу видеть мины.
К самому методу мне добавить больше нечего. Приведу наиболее часто встречаемые примеры.

Теперь расмотрим ситуацию, в которой у нас имеется ряд из чередующихся единичек и двоек. Вот несколько примеров



Если вы стречаете ситуацию один-два-один это значит, что вы можете смело ставить мины напротив единичек и кликнуть напротив двойки. Но это только при условии, что в третьем ряду нет мин. Еще раз напомню, что знак вопроса означает, что нам не важно, какая там цыфра, но там точно не мина. Если там будет мина, то эта ситуация решается очень легко. Но мы рассмотрим эту проблему в следующей статье.
Едем дальше




Не обязательно запоминать это все, потому что этот список можно продолжать бесконечно. Я хочу обратить внимание, что когда число двоек кратно трем (3, 6, 9, 12 и т.д.), то остается неопределенность. Давайте выведем общее правило для всех этих случаев. Это правило выглядит так. Я называю его "один-два-мина".



Если мы видем последовательность один-два, то мы смело ставим мину, не глядя на то, что идет дальше.
Вот еще несколько правил, которые я отнес к этой же теме.

Для начала попытаюсь объяснить, почему я так назвал свою методичку. Казалось бы, тут все понятно. Имеется минное поле, которое надо разминировать, отсюда и название "теория минных полей". Но я вкладываю в это название еще и другой смысл. Слово "поле" употребляется не только для обозначения некоторого участка земли, на котором растет трава, одуванчики, цветочки всякие. Вы же слышали такие понятия, как электрическое поле, магнитное поле, гравитационное поле. Дак вот представьте, что наша мина окружена неким полем.



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



Иногда очень полезно смотреть на минное поле как на мины, окруженные цыфрами, а не как на цыфры, окруженные минами. Но если вы ничего не поняли из того, что я хотел сказать, можете просто забыть. И так поехали дальше.
Допустим имеется такая ситуация.

Здесь гораздо больше информации, чем кажется. На самом деле тут можно проставить мины по периметру, не делая лишних кликов.




Самую первую мину мы ставим естественно в угол. Остальные ставим так, чтобы покрыть каждую единичку, но так чтобы поля не пересекались. Вообще если имеется длинный ряд из единичек то мины вдоль него распологаются через две клетки



Таким образом мы можем вывести первое правило, которое мы назовем "мина-один-один-мина". Вот схема этого правила.



Здесь знаком вопроса мы обозначим клетку, в которой не важно какая цыферка, но мы точно знаем, что там мины нет. Черная мина - это мина, которая уже была поставлена, а красная - это та, которую надо поставить. Или наоборот :)

В завершении я попрошу вас еще раз внимательно посмотреть на эту последовательность.

У нас получается, что каждая третья клетка содержит мину. Наперед замечу, что в Сапере очень многое повторяется с периодом 3. Если мы не знаем, где поставить первую мину, то перед нами встает три варианта расстановки.
Вообще, ситуацию, когда имеется ряд из одних единиц или из одних двоек, я называю "единственная неопределенность". Всегда, когда у нас чередуются двойки и единицы, это зацепка, которая выдает расположение мин. Но об этом в следующей статье.

В виндовсе есть одна замечательная стандартная игра Сапер. В свое время я очень увлекался ею, пытался научиться очень быстро разминирывать поля, установить рекорд. Я долго исследовал, но рекорд установить так и не смог. Некоторые мои знакомые решают эту задачу гораздо быстрее меня. Но в одном я убедился точно, сапер - это гораздо больше, чем кажется на первый взгляд. В нем есть закономерности, которые не очевидны, но которые могут существенно помочь в решении. Для меня количество ситуаций, в которых приходится выбирать наугад значительно сократилось.
Я даже написал небольшую методичку по этой игре, которую назвал "Теория минных полей" и показал её своим друзьям. Они сказали, что идеи очень хорошие, но написано на очень непонятном языке. Та методичка уже давно утеряна, по-этому попытаюсь её восстановить, чтобы было максимально понятно.
Перед написанием данной статьи я специально погуглил в интернете на эту тему. Оказалось я не один такой умный :), уже существуют целые научные труды на игру Сапер. Мне влом их всех читать, просто напишу то, что я знаю. В основном ниже я буду писать о точных методах, которые дают однозначный ответ, но некоторые знания в теории вероятности нам тоже могут помочь. Например следующая ситуация



Из за мины, которую мы обозначили звездочкой, мы не можем точно знать, как расположены мины в оставшихся 4х клетках. Здесь у нас имеется 3 варианта.



Практика показала, что первый случай бывает гораздо чаще, чем остальные. Я попытался понять почему, и некоторые расчеты показали, что первый случай бывает, кажется, в 5 раз чаще. Но об этом позже.
Итак если вы внимательно почитаете мои статьи, то ниже приведенная задача, будет решаться вами за доли секунды


Заинтриговал? Продолжение следует ...

Это знаменитый мысленный эксперимент вряд ли кто-то проделывал на самом деле. Да в этом и нет необходимости. На то он и мысленный эксперимент. Он показывает, как можно перенести эффекты, свойственные для мира микрочастиц на накрообъекты.
Суть его заключается в следующем. Имеется Ученый и некоторая замкнутая система, в которой находится живой Кот. Так же в замкнутой системе находится некий прибор для измерения состояния частицы и сама частица. Так как частица находится в состоянии суперпозиции, то в результате измерения с равной вероятностью частица может оказаться либо в состоянии |0> либо в |1>. Прибор устроен таким образом, что если частица окажется в состоянии |0>, то Коту в кровь вводится отравляющее вещество и тот умирает :(. Вся эта система находится в замкнутом состоянии от внешнего наблюдателя - Ученого. В тот момент, когда прибор производит измерение, измеряемая частица запутывается с измерительным прибором и соответственно с Котом. В результате вся эта замкнутая система переходит в состояние суперпозиции, состоящем из двух состояний. В одном состоянии частица - |0> и Кот умирает, а во втором частица - |1> и Кот живет. Т.е. наш Кот получается и жив и мертв одновременно. Затем Ученый вскрывает замкнутую систему и в этот момент происходит декоггеренция и Кот переходит в одно из состояний - либо жив, либо мертв.
Чтобы лучше понять, что происходит, я нарисовал следующие картинки.



Это наша исходная лабораторная установка. Обратите внимание, что частица находится в двух состояниях одновременно. Далее происходит измерение и частица запутывается с Котом.


В результате мы видим, что Кот тоже переходит в состояние суперпозиции и становится и жив и мертв. Далее происходит вскрытие замкнутой системы и вся система запутывается с окружением.




Мы видим, что вся вселенная как бы раздваивается. В одной вселенной наш Ученый находит Кота живым, а в другой наш Ученый находит Кота мертвым. Это наглядно показывает, как происходит декоггеренция, почему для Ученого Кот с равной вероятностью оказывается либо жив, либо мертв.

Как мы уже говорили в предыдущей статье, частица может находиться в одном из своих возможных состояний или в них обоих одновременно. В последнем случае говорят, что частица находится в состоянии суперпозиции. Состояние суперпозиции возможно если система замкнута, т.е. не контактирует с окружающей средой. Например, если поместить электрон в замкнутое пространство и попытаться представить, куда направлен его спин, то для внешнего наблюдателя возможны два состояния электрона - спин направлен втодь магнитного поля либо против него. Обозначим их через |0> и |1>. Поскольку система замкнута, то электрон может находится в них одновременно с определенной долей вероятности, например |0> с вероятностью 0.2 и |1> - 0.8 . Как только мы произведем измерение спина, то электрон перескочит в одно из этих состояний в соответствии с вероятностью этого состояния.
Представим теперь, что у нас имеется другой электрон в замкнутой системе. Он находится в состоянии |0> с вероятностью 0.4 и |1> с вероятностью 0.6. Если эти два электрона находятся в разных замкнутых системах и не взаимодействуют друг с другом, то результат измерения одного электрона не влияет на результат измерения другого. Но как только между ними произошло взаимодействие, они переходят в так называемое запутанное состояние и теперь уже нельзя говорить о состоянии каждого из них отдельно. Если в нашем примере каждый электрон имеет 2 возможных состояния, то вместе они могут находиться в 4х состояниях, а именно: |00>, |01>, |10>, |11>. Каждое из них имеет свою долю вероятности. Например 0.1, 0.1, 0.3 и 0.6 соответственно. Как только мы производим измерение одной из частиц, состояние другой так же изменяется, а запутанность между частицами исчезает.
Интересно то, что частицы могут быть запутаны по одному параметру, но не запутаны по другому. Например, два фотона, выпущенные атомом в одно и то же время, могут находиться на значительном расстоянии, но они всегда будут иметь одинаковую поляризацию. Т.е. имеется два равновероятных состояния |00> и |11>. Как только мы измерили поляризацию одного фотона, второй фотон сразу же перейдет в состояние с такой же поляризацией, не зависимо от того на каком расстоянии они находятся.
Попытаюсь поподробнее объяснить, что же означает состояние запутанности. Тут нам поможет обычная теория вероятности. Пусть у нас имеется переменная А, которая может принимать значения 0 и 1, и имеется переменная Б, которая тоже может принимать значения 0 и 1. Каждая из них задается таблицей. Например так.



Но если у нас есть две случайные величины, то они задаются таблицей совместных вероятностей.



В этой таблице записаны вероятности какждой из 4х возможных комбинаций. Просуммировав числа в столбцах и в строках, мы получим вероятности каждого из событий поотдельности. А теперь зададимся вопросом, зависит ли значение переменной А от значения переменной Б и наоборот?
Представим, что мы точно знаем, что переменная А приняла значение 1, что мы тогда можем сказать о значении переменной Б? Для этого возьмем вторую строчку таблицы, что соответствует А=1.




Теперь пронормируем эту строчку таким образом, чтобы в сумме получилась единица. А именно поделим 0.32 и 0.48 на 0.8. Получим следующий результат.



В результате мы получили все те же вероятности 0.4 и 0.6 для Б. Если мы проделаем ту же операцию с первой строчкой, то получим то же самое. Это значит, что независимо от того, какое значение примет А, переменная Б примет свои значения с теми же вероятностями. Если Б не зависит от А, то и А не зависит от Б. Вы можете проделать то же самое со столбцами и убедиться в этом. Для того, чтобы построить такую таблицу, в которой две переменные не зависят друг от друга, достаточно в каждой ячейке поставить вероятность, равную произведению вероятноствей соответствующих значений. Т.е. в ячейку 0 0 мы поставим значение равное 0.2*0.4 = 0.8. При любом отклонении от этих значений мы получим два взаимосвязанных события. Рассмотрим пример, приведенный выше.




Здесь каждое из событий поотдельности имеет те же вероятности, что и в предыдущем примере. Но теперь если взять одну из строчек или столбцов и пронормировать, то получится, что вероятности изменятся. Например возьмем А=1.




Имея такой критерий, мы всегда можем сказать, запутаны у нас частицы или нет. Например, если имеется четыре равновероятных события |00>, |01>, |10>, |11>, то первая и вторая частицы независимы. А если имеются события |00> и |11>, то две частицы зависимы. А что же происходит, когда мы производим измерение над частицами, почему частицы переходят в одно из состояний? В этом случае говорят, что замкнутая система запутывается с окружением. Это мы с вами рассмотрим в следующей статье про кота Шредингера.

Изучая язык scheme, столкнулся с таким понятием, как континуэйшены (continuation). Почему-то в интернете не удалось найти более или менее нормальный пример. Немного подумав, я решил восполнить этот пробел. Далее в этой статье попытаюсь привести небольшой примерчик, и последовательно подойти к использованию континуэйшеннов и внедрить их в программу.
Я буду использовать функции reset и shift. С помощью этих функций можно захватить часть остаточных вычислений и как-нибудь их использовать. Например

>(display (reset (+ (* 2 3) (shift kk 1) (* 5 6))))
1

В момент времени, когда интерпретатор дошел до вычисления функции shift, в стеке хранится следующее остаточное вычисление

(display (reset (+ 6 X (* 5 6))))

Функция shift берет часть этих вычислений, заключенных между reset и shift и присваивает их переменной kk. Таким образом kk присваивается следующая функция

(lambda (X) (+ 6 X (* 5 6)))

Это всегда функция от одной переменной. Тут стоит обратить внимание на следующие вещи. Во-первых функция display не вошла в наши остаточные вычисления, потому что она находится снаружи reset. Во-вторых, у нас получилась функция, которая вычисляет сумму трех слагаемых. При чем первое слагаемое уже вычислено. Второе слагаемое, где находился shift, это наша переменная. А третье слагаемое еще не вычислено.
Далее внутри shift идет последовательность комманд, которые будут выполнены, и результат последней будет возввращен из reset. В нашем случае, это просто 1, которая просто возвращается из reset в display. На самом деле, там может быть гораздо больше комманд, которые могут использовать kk как функцию. Если мы напишем

>(display (reset (+ (* 2 3) (shift kk (kk 1)) (* 5 6))))
37

то это будет равносильно

(display (+ (* 2 3) 1 (* 5 6)))

Таким образом у нас есть выбор, либо сразу вернуть какое-либо значение из reset, либо продолжить работу программы, вернув какое-либо значение из shift, либо например вычислить функцию kk с несколькими различными значениями, сравнить результат и вернуть тот, который нас больше всего устроит.
Конечно, такое определение не дает представления, как же все таки это можно использовать. По-этому давайте рассмотрим пример. Допустим у нас есть функция

>(define (collect fun lst (sum 0))
(if (empty? lst)
sum
(collect fun (cdr lst) (fun sum (car lst)))))

С помощью этой функции мы можем вычислить сумму всех элементов списка, или произведение или еще что-нибудь.

>(define (mult sum x) (* sum x))
>(collect mult '(3 5 2) 1)
30

>(remainder (collect mult '(3 5 2) 1) 7)
2

В последнем примере мы вычислили остаток от деления полученного произведения на 7. Т.е (3*5*2)%7 = 30%7 = 2. Далее попытаемся немного преобразовать это выражение, добавив туде reset и shift. Конечно, сложно придумать такую задачу, в которой нам бы потребовалось вычислять остаток от деления, просто попытаемся представить, что нам действительно это нужно. Я позже объясню, почему именно остаток от деления.
Давайте теперь напишем вот так и посмотрим что будет

>(define (mult2 sum x)
(mult sum
(if (list? x)
(shift kk
0)
x)))

>(reset (remainder (collect mult2 '(3 4 5) 1) 17))
9
>(reset (remainder (collect mult2 '(3 (3 4) (5 2)) 1) 17))
0

Теперь у нас функция возвращает остаток от деления произведения всех элементов списка, но если в этом списке попадается какой-нибудь другой список, то выполнение программы прерывается и сразу возвращается значение 0. Т.е. континуэйшены можно использовать например для обработки ошибок, чтобы сразу выходить из какого-нибудь блока программы.
Немного модифицируем программу

>(define (mult2 sum x)
(mult sum
(if (list? x)
(shift kk
(display (kk (list-ref x 0)))
(display " ")
(display (kk (list-ref x 0)))
(display " ")
0)
x)))

>(reset (remainder (collect mult2 '(3 (2 4) 5) 1) 17))
13 9 0

Что делает эта функция. В общем-то тоже самое. Оно по прежнему возвращает 0, если у нас попадается какой-нибудь список. Выражение
(display (kk (list-ref x 0)))
можно перевести так: "отобрази мне пожалуйста, что бы мы получили, если бы за место этого списка, я бы подставил значение первого элемента". Т.е.
(reset (remainder (collect mult2 '(3 2 5) 1) 17))
3*2*5 % 17 = 30%17 = 13
затем мы выводим результат, который бы получился, если бы мы подставили второй элемент списка вместо самого списка
3*4*5 % 17 = 60%17 = 9

Т.е. мы можем например сравнить два результата и вывести например максимальный. Для этого нам понадобится еще одна функция.

>(define (max fun lst)
(collect (lambda (x y)
(if (> (fun y) x)
(fun y)
x))
lst))

Функция max принимает два аргумента: функцию и список. Затем она применяет эту функцию к какждому элементу списка и возвращает результат, который был максимальным. Например

>(max (lambda (x) (* x x)) '(3 4 1))
16

Естественно, квадрат второго элемента списка будет максимальным. Теперь еще раз преобразуем нашу функцию

>(define (mult2 sum x)
(mult sum
(if (list? x)
(shift kk
(max kk x))
x)))

>(reset (remainder (collect mult2 '(3 (2 4) 5) 1) 17))
13

Т.е. наша функция проверяет, при каком значении (2 или 4) получится больший результат, и возвращает максимальный

>(reset (remainder (collect mult2 '(3 2 5) 1) 17))
13
>(reset (remainder (collect mult2 '(3 4 5) 1) 17))
9

А теперь объясню, почему мы использовали именно остаток от деления. Просто если бы мы просто вычисляли произведение всех элементов списка, то вполне очевидно, что максимальный результат получался бы при максимальном значении. Т.е.

>(reset (collect mult2 '(3 2 5) 1))
30
>(reset (collect mult2 '(3 4 5) 1))
60
>(reset (collect mult2 '(3 (2 4) 5) 1))
60

Т.е. нам было бы проще просто найти максимальное из 2 и 4, а потом уже подставить это значение. Это было бы не интересно. А когда результат еще делится по модулю, то сложно предсказать, при каком значении, результат получился бы максимальным. Например, у нас получился больший результат при 2, чем при 4.
И на последок отмечу, что наша супер-функция работает для случая, когда списков несколько.

>(reset (remainder (collect mult2 '(3 (4 3) (2 5 3)) 1) 17))
11

Попробуйте отгадать, при каких значениях получился такой результат?

>(reset (remainder (collect mult2 '(3 4 2) 1) 17))
7
>(reset (remainder (collect mult2 '(3 3 2) 1) 17))
1
>(reset (remainder (collect mult2 '(3 4 5) 1) 17))
9
>(reset (remainder (collect mult2 '(3 3 5) 1) 17))
11
>(reset (remainder (collect mult2 '(3 4 3) 1) 17))
2
>(reset (remainder (collect mult2 '(3 3 3) 1) 17))
10

И на последок добавлю одно важное обстоятельство. Все цыклы были написаны с помощью рекурсий и не было объявлено ни одной переменной. Именно по-этому в какждый момент времени состояние работы программы полностью содержится в остаточных вычислениях, которые мы захватываем с помощью reset и shift. Если бы мы использовали цыкл и дополнительные переменные например в функции collect, то вполне возможно, что ничего бы не заработало.

Есть один очень известный эксперимент. Не помню, кто его впервые поставил, но в последствии его повторяли много раз и он дает понять основные законы квантового мира.
Имеется такая установка:
1. источник, излучающий постоянный поток электронов
2. некоторая перегородка, в которой имеется два отверстия
3. экран, который фиксирует попадание на него электронов

В результате на экране получаются области, в которые электроны попадают наиболее часто, и области, в которые электроны попадают редко. И эти области чередуются между собой. Картина очень похожа на ту, которая получается при интерференции света.
В этом нет ничего удивительного, ведь все мы со школы знаем, что любые элементарные частицы могут вести себя и как частицы, и как волна. По-этому поток электронов как волна распространяется до перегородки, после чего, пройдя через отверстия, у нас получается уже две волны, которые накладываются друг на друга.

В результате получаем вот такую интерференционную картину

Что произойдет, если закрыть одно из отверстий?

Одна волна пропала, интерференции больше не происходит, и на экране получается обычное нормальное распределение.

Но ученый, который ставил этот эксперимент, на этом не остановился. В попытках выяснить, через какое все-таки отверстие пролетает электрон, он поставил прибор у одного из отверстий (обычный счетчик Гейгера).

В результате на экране интерференционная картина исчезла. Поток электронов от одного отверстия просто суммировался с потоком из другого. Это было неожиданно, ведь досконально известно, что прибор, не вносит никакие изменения в эксперимент и никоим оразом не влияет на скорость и другие параметры частицы. Он просто считывает определенную информацию, а именно, пролетела ли заряженная частица через него. Данный эксперимент проводили при различных начальных условиях, например когда поток электронов очень слабый. Практически в опыте учавствует только один электрон. И результат был тот же самый. Когда за этим электроном никто не наблюдает, он ведет себя как волна и проходит через оба отверстия одновременно, а потом интерферирует сам с собой. А когда имеется прибор, он случайным образом оказывается либо у одного отверстия, либо у другого.

В результате была разработана так называемая теория декоггеренции. Суть её заключается в следующем. Если у имеется замкнутая система(например электрон, за которым никто не наблюдает), то она может находиться в одном из своих возможных состояний, либо во всех этих состояниях одновременно, где каждое состояние имеет определенную долю вероятности. Такое состояние называется суперпозицией. А когда система размыкается (мы проводим определенное измерение над системой), то она переходит в одно из этих состояний случайным образом, в соответствии с вероятностью этого состояния.
Например, у нас имеется черный ящик. Внутри находится електрон. Мы хотим узнать куда направлен спин электрона. Я не знаю точно, что это такое. Просто когда над частицей производится такой эксперимент, её спин оказывается либо направлен вдоль магнитного поля, либо против него. В этих случаях говорят "спин направлен вверх" или "спин направлен вниз". Не важно, что именно это означает, просто у нас имеется электрон, который может находиться в двух состояниях: спин вверх и спин вниз. Обозначим одно состояние как 0, а другое как 1. Тогда состояние этой замкнутой системы записывается как:
а * |0> + b * |1>

символами |0> и |1> принято обозначать состояния 0 и 1
Коэффициенты a и b - комплексные, и на них действует условие нормировки
|a|^2 + |b|^2 = 1
|a|^2 и |b|^2 - вероятности состояний 0 и 1 соответственно

Например, имеется замкнутая система в состоянии
0.6 |0> + 0.8 |1>

тогда
0.6^2 = 0.36
0.8^2 = 0.64
это значит, что спин электрона с вероятностью 36% направлен вверх, а с вероятностью 64% направлен вниз. При чем это не просто статистика, о возможных состояниях системы, эти два состояния реально существуют одновременно.
После того, как мы открыли черный ящик и провели соответсвующее измерение, происходит процесс декоггеренции и электрон перескакивает в одно из этих состояний. И у нас получается например
1 |1>

Процесс, обратный декоггеренции, называется рекоггеренция. Это когда мы берем электрон, закрываем в черном ящике и хорошенько взбалтываем. У нас получается например
0.707 |0> + 0.707 |1>

кстати, не забывайте, что коэффициенты a и b - комплексные. Это значит, что система может находиться например в таком состоянии
0.707i |0> + 0.707 |1>
или
0.707 |0> - 0.707 |1>
или
0.707i |0> + 0.5+0.5i |1>

и все эти состояния принципиально отличаются друг от друга