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