见鬼，结果还就这样了

原题：（CIA面试题？） （参考链接： http://club.pchome.net/topic_1_15_3420979_1__.html）

两个人A和B玩游戏。方法是：A选定一个长度为3的正反序列“正反反”，B选定另一个不同的长度为3的正反序列正正反。
现在开始反复丢一枚出现正反的可能性都是1/2的硬币，直到出现A或B选定的正反序列为止。谁的序列出现了，谁就是赢家。问A和B获胜的概率各是多少？

一开始闷住了，那些已经淡忘的排队论啊马尔可夫链啊在乱转，感觉很害怕，希望不要和那些东西沾上边。

定一下神发现不关马尔可夫什么事情（当然，不是真的无关）。是CS一路的，二叉树。

<正> (0,1) （A没戏了）

<正>

反 B (0,1)

(正)

(正)

[反]

反A (1,0)

初始点

<正>

(正)

[反]

[反]

(正)

[反]

[反]

这棵树里，对相同括号的节点，从其开始的子树的A，B获胜概率组合是一致的，于是对圆括号（设A获胜概率为P1）和方括号（设A获胜概率为P2）列式：

P1 = 0.5×P2

P2 = 0.5×P1 +0.5

于是P1 = 1/3

所以在初始点0.5×P1+0.5×P2=0.5。即总的来说A，B的获胜概率相等，和直觉一样（当然直觉还是有些摇摆的）。

题目出的比较次，如果B选其他的（比如反正反？）就有些分别了。不知道在考什么，考直觉？不像（当然如果考生都是像后天中的sam那样口算微积分的则另当别论）。

经dede提醒发现可能算错，重算一次：划线节点的概率和初始点相同。列式结果：A（正反反）获胜概率1/3，B（正正反）获胜概率2/3。这个问题容易算错的地方就是在节点归类上。（再次验证以下程序在节点归类上是正确的）

感谢dede （Robbie T. Mosaic）提供的基于（伪）随机数的C#仿真程序。一开始这个程序有点问题，dede也抱怨“反正反”情形似乎也是各0.5概率。后来终于发现是数组初始化值为0改变了初始条件。以下是演示“反正反”和“正正反”的代码。改了代码运行后，我发现输出结果和理论计算不一致（“正正反”获胜的概率大），经过验算才发现是我算错了，然后把结果和dede谈了一下。直觉来看“正正反”的概率大，因为一旦进入“正正”模式就是“正正反”的天下了。

using System;

public class TestProg
{
    public readonly int LastCount = 3;

    public static void Main()
    {
        TestProg prog = new TestProg();
        prog.NsMain();
    }

    public void NsMain()
    {
        Random rand = new Random();
        int i;
        int count;

        for (i = 0, count = 0; i < 1000; i++) {
            count += DoOneRound(rand);
        }
        Console.WriteLine("PNP won {0} times out of {1}", count, 1000);
    }

    public int DoOneRound(Random rand)
    {
        int[] lastthree = new int[LastCount];

        int j;
        for (j = 0; j < LastCount; j++)
        {
            lastthree[j] = -1;
        }

        while(true)  
        {
            for (j = 0; j < LastCount - 1; j++) {
                lastthree[j] = lastthree[j + 1];
            }
            lastthree[j] = rand.Next() % 2;
            if (lastthree[0] == 0 && lastthree[1] == 1 && lastthree[2] == 0) {
                Console.WriteLine("NPN wins");
                return 0;
            } else if (lastthree[0] == 1 && lastthree[1] == 1 && lastthree[2] == 0) {
                Console.WriteLine("PPN wins");
                return 1;
            }
        }
    }
}

看来这个问题还是比较容易算错的，我想把算法整理一下变成代码：

using System;
using System.Collections.Generic;

namespace CoinGames
{
    class Whowins
    {
        class WinningCondition
        {
            public int[][] Sequences = null;

            public int[][] Rescuers = null;

            bool IsEqual(int[] seq, int aStart, int aEnd, int bStart, int bEnd)
            {
                int ap;
                int bp;
                for (ap = aStart, bp = bStart; ap < aEnd && bp < bEnd; ap++, bp++)
                {
                    if (seq[ap] != seq[bp])
                    {
                        return false;
                    }
                }
                if (ap < aEnd || bp < bEnd)
                {
                    return false;
                }
                return true;
            }

            // it gave me a reminiscence of KMP
            // but it's stronger
            int[] Rescue(int[] seq)
            {
                int n = seq.Length;
                int[] resq = new int[n];

                foreach (int s in seq)
                {
                    Console.Write(s);
                }
                Console.WriteLine();

                for (int i = 0; i < n; i++)
                {
                    resq[i] = -1;
                    for (int j = i - 1; j >= 0; j--)
                    {
                        if (IsEqual(seq, 0, j, i - j, i) && seq[i] != seq[j])
                        {
                            resq[i] = j;
                            break;
                        }
                    }
                }

                foreach (int s in resq)
                {
                    Console.Write(s);
                }
                Console.WriteLine();
                return resq;
            }

            public void Rescue()
            {
                Rescuers = new int[Sequences.Length][];
                for (int i = 0; i < Sequences.Length; i++)
                {
                    Rescuers[i] = Rescue(Sequences[i]);
                }
            }

            public State Transition(State state, int c)
            {
                State newState = new State(state);
                for (int i = 0; i < this.Sequences.Length; i++)
                {
                    if (this.Sequences[i][newState.Pos[i]] == c)
                    {   // An ordinary progress
                        newState.Pos[i]++;
                    }
                    else
                    {   
                        do
                        {
                            newState.Pos[i] = Rescuers[i][newState.Pos[i]];
                        } while (newState.Pos[i] >= 0 && Sequences[i][newState.Pos[i]] != c);
                        newState.Pos[i]++;
                    }
                    if (newState.Pos[i] == Sequences[i].Length)
                    {
                        newState.bHasWinner = true;
                    }
                }
                return newState;
            }
        }

        class State : IComparable<State>
        {   // deja vu? yes, inspired by LR syntactical parsing!
            public int[] Pos = null;
            public bool bHasWinner = false;

            public override String ToString()
            {
                String r = "[";
                bool first = true;
                foreach (int p in Pos)
                {
                    if (first)
                    {
                        first = false;
                    }
                    else
                    {
                        r += ",";
                    }
                    r += p.ToString();
                }
                r += "]";
                return r;
            }

            public State(WinningCondition wc)
            {
                Pos = new int[wc.Sequences.Length];
                for (int i = 0; i < this.Pos.Length; i++)
                {
                    Pos[i] = 0;
                }
            }

            public State(State that)
            {
                Pos = new int[that.Pos.Length];
                for (int i = 0; i < that.Pos.Length; i++)
                {
                    Pos[i] = that.Pos[i];
                }
            }

            public int CompareTo(State that)
            {
                for (int i = 0; i < Pos.Length; i++)
                {
                    int thisPos = this.Pos[i];
                    int thatPos = that.Pos[i];
                    int cmp = thisPos.CompareTo(thatPos);
                    if (cmp != 0)
                    {
                        return cmp;
                    }
                }
                return 0;
            }
        }

        static void Main(String[] args)
        {
            try
            {
                double[] probList = new double[]{0.5, 0.5};
                WinningCondition wc = new WinningCondition();
                wc.Sequences = new int[][]{new int[]{0,1,0}, new int[]{1,1,0}};
                wc.Rescue();

                State root = new State(wc);
                Queue<State> q = new Queue<State>();
                List<State> states = new List<State>(){root};
                q.Enqueue(root);

                while (q.Count > 0)
                {
                    State state = q.Dequeue();

                    // print out the formula for the node
                    String formula = state + " = ";
                    for (int i = 0; i < probList.Length; i++)
                    {
                        State newState = wc.Transition(state, i);
                        int index = states.BinarySearch(newState);
                        if (index < 0 && !newState.bHasWinner)
                        {
                            index = -index - 1;
                            states.Insert(index, newState);
                            q.Enqueue(newState);
                        }

                        if (i != 0)
                        {
                            formula += " + ";
                        }
                        formula += "(P{" + i +  "}=" + probList[i] + ")";
                        formula += " * ";
                        formula += newState;
                    }
                    Console.WriteLine(formula);
                }

            }
            catch (Exception e)
            {
                Console.WriteLine("Exception/n {0}", e);
            }
            
        }
    }
}

经过一番调试，应该输出正确了。结果是NPN胜率3/8。这个程序给出的是围绕某个玩家的各节点的求解算式，如果要排成线性方程组，还需要若干代码，然后可以交给Matlab求解；如果要一般性解出方程，还需加高斯消去法之类（这个问题中矩阵是稀疏的应该有快速算法）；为了解出解析解，需要实现有理数类并完成运算方法或重载。至此初步完成这个问题的全部机器求解。总的来看C#的代码紧凑性还是很高的，一般我求解问题代码不太精简，但在这里200行代码也就解决问题的核心部分，而且代码的可读性也不错。