约瑟夫问题

41一个人围成一个圈,由第一个人开始报数,没数到第3个人就自杀,那么剩下的是在第几个。

圈的问题,使用循环链表的数据结构就很好解答了

我这里没有用到循环链表的特性,我这种做法,普通的链表数组其实都可以做到。

使用一个计数器,每记到第几位,就移除对应位置的元素,所以需要一个能够准确指向对应元素的index,index随着计数器往下加,注意不能超过数组范围,超过就回到原点。

最重要的是,在移除之后,index指向的元素就是移除元素的后一个了,所以要把index往前移动一下再进行计数。

如果使用循环链表的特性,就是不停的下几位,移除,下几位,移除.....

class YueSeFuProbrom
{
    CycleLink<int> cycleLink = new CycleLink<int>();

    public void Cal(int pNum, int which)
    {
        cycleLink.Clear();
        //构建循环链表 表示圆圈
        for (int i = 1; i <= pNum; i++)
        {
            cycleLink.Add(i);
        }

        int index = 0;
        int counter = 0;
        int who = 0;
        while (cycleLink.GetCycleLinkLength() >= which)
        {
            index = index % cycleLink.GetCycleLinkLength();
            counter++;
            index++;
            if (counter % which == 0)
            {
                cycleLink.Delete(index, ref who);
                Console.Write(who + " ");
                index--;
            }
        }
        Console.WriteLine();
        Console.Write("活着的有:");
        for (int i = 1; i < which; i++)
        {
            cycleLink.GetElement(i, ref who);
            Console.Write(who + " ");
        }
        Console.WriteLine();
        Console.WriteLine();
    }
}



//测试
static void TestYueSeFu()
{
    YueSeFuProbrom yueSeFu = new YueSeFuProbrom();
    yueSeFu.Cal(5, 2);
    yueSeFu.Cal(100, 3);
    yueSeFu.Cal(6, 3);
    yueSeFu.Cal(41, 3);
}

捕获.PNG


首页 我的博客
粤ICP备17103704号