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);
}