【算法练习题】纸牌游戏——小猫钓鱼

星期天小A和小B约在一起玩桌游,他们正在玩一个非常古怪的扑克游戏——“小猫钓鱼”。游戏规则是这样的:将一副扑克平均分成两份,每人拿一份。小A先拿出手中的第一张扑克牌放在桌上,然后小B叶拿出手中的第一张扑克牌,并放在小A扑克牌的上面,就像这样两人交替出牌。出牌时,如果某人打出的牌与桌面上某张牌面相同,可将两张相同的牌及其中所夹的牌全部取走,并依次放到自己手中牌的末尾。当任意一人手中的牌全部出完时,游戏结束,对手获胜。

假如游戏开始的时候,小A手中有6张牌,顺序为 2 4 1 2 5 6,小B手中也有6张牌,顺序为 3 1 3 5 6 4,并且小A先出牌。最终谁会获胜呢?

程序如下:

static void Main(string[] args)
{
    /*
        * 小猫钓鱼游戏
        * 输入: 数组A 2,4,1,2,5,6
        *       数组B 3,1,3,5,6,4 
        * 输出:A或者B
        * */

    int[] A = new int[] { 2, 4, 1, 2, 5, 6, 0, 0, 0, 0, 0, 0, 0 };
    int[] B = new int[] { 3, 1, 3, 5, 6, 4, 0, 0, 0, 0, 0, 0, 0 };
    int aHead = 0, aTail = 6;
    int bHead = 0, bTail = 6;
    int[] Stack = new int[A.Length*2];
    int sTop = 0;
    while(aHead != aTail && bHead != bTail) //如果小A和小B手里都有牌
    {
        //A
        Stack[sTop++] = A[aHead]; //小A出牌
        A[aHead] = 0; //将小A出掉的牌置零,用于调试可不加
        aHead++;
        if(aHead==A.Length) 
        {
            aHead = 0;
        }
        for(int i=0; i< sTop-1; i++) //检查桌面上面有没有和小A出的牌面相同
        {
            if(Stack[i] == Stack[sTop - 1])
            {
                for(int j=sTop-1; j>=i;j--) //如果有,依次取牌插回小A手里
                {
                    A[aTail] = Stack[j];
                    Stack[j] = 0;
                    sTop--;
                    aTail++;
                    if (aTail == A.Length)
                    {
                        aTail = 0;
                    }
                }
            }
        }
        //B
        Stack[sTop++] = B[bHead];
        B[bHead] = 0;
        bHead++;
        if (bHead == B.Length)
        {
            bHead = 0;
        }
        for (int i = 0; i < sTop - 1; i++)
        {
            if (Stack[i] == Stack[sTop - 1])
            {
                for (int j = sTop - 1; j >= i; j--)
                {
                    B[bTail] = Stack[j];
                    Stack[j] = 0;
                    sTop--;
                    bTail++;
                    if (bTail == B.Length)
                    {
                        bTail = 0;
                    }
                }
            }
        }
    }
    if(aHead == aTail)
    {
        Console.WriteLine("B win!");
    }
    else
    {
        Console.WriteLine("A win!");
    }
}
此条目发表在文章, 算法分类目录。将固定链接加入收藏夹。

发表评论