魔术师发牌问题

2020/01/04 81

算法 循环链表

一位魔术师掏出一叠扑克牌,魔术师取出其中13张黑桃,洗好后,把牌面朝下。说:“我不看牌,只数一数就能知道每张牌是什么?”魔术师口中念一,将第一张牌翻过来看正好是A;魔术师将黑桃A放到桌上,继续数手里的余牌,第二次数1,2,将第一张牌放到这叠牌的下面,将第二张牌翻开,正好是黑桃2,也把它放在桌子上。第三次数1,2,3,前面二张牌放到这叠牌的下面,取出第三张牌,正好是黑桃3,这样依次将13张牌翻出,全部都准确无误。

那么,魔术师手中牌的原始顺序是什么样子的?

这是典型的链表环问题,属于约瑟夫环的逆运算。需要逆向思维,依次添加数字,还原出最原始的顺序!

class Program
{
    static void Main(string[] args)
    {
        // create data
        var firstCard = new Card(0);
        Card cursor = firstCard;
        for (int i = 0; i < 12; i++)
        {
            var card = new Card(0);
            cursor.Next = card;
            cursor = card;
        }
        cursor.Next = firstCard;

        // start calculation
        for (int i = 1; i < 14; i++)
        {
            int j = 0;
            while (j < i)
            {
                cursor = cursor.Next;
                if (cursor.No == 0)
                {
                    j++;
                }
            }
            cursor.No = i;
        }

        ShowOrder(firstCard);
        Check(firstCard);
    }

    static void ShowOrder(Card firstCard)
    {
        Console.WriteLine("魔术师将牌的顺序进行调整完毕,顺序如下:");

        Card cursorOrder = firstCard;
        while (true)
        {
            Console.WriteLine(cursorOrder.No);
            cursorOrder = cursorOrder.Next;
            if (cursorOrder.No == 1)
            {
                break;
            }
        }
    }

    static void Check(Card card)
    {
        Console.WriteLine();
        Console.WriteLine("测试:");

        Card cursor = card;
        while (cursor.No != 13)
        {
            cursor = cursor.Next;
        }
        for (int i = 1; i < 14; i++)
        {
            for (int j = 1; j < i; j++)
            {
                cursor = cursor.Next;
            }
            Console.WriteLine(cursor.Next.No);
            cursor.Next = cursor.Next.Next;
        }
    }
}

class Card
{
    public int No { get; set; }
    public Card Next { get; set; }

    public Card(int no)
    {
        No = no;
    }
}

输出结果:

魔术师将牌的顺序进行调整完毕,顺序如下:
1
8
2
5
10
3
12
11
9
4
7
6
13

测试:
1
2
3
4
5
6
7
8
9
10
11
12
13
丽丽 01/04/2020 14:22:43

写的真棒👏🏻

评论