Josephus问题是下面的游戏: N个人从1到N编号,围坐成一个圆圈。从一号开始传递一个热土豆。经过M次传递后拿着热土豆的人被清除离座,围坐的圆圈缩紧,由坐在被清除的人后面的人拿起热土豆继续进行游戏。最后剩下的人获胜。因此,如果M=0和N=5,则依次被清除后,5号获胜。如果M=1和N=5,那么被清除的人的顺序是2,4,1,5.
a.编写一个程序解决M和N在一般值下的Josephus问题,应使你的程序尽可能地高效,要确保能够清除单元。
b. 你的程序的运行时间是多少?
c.如果M=1,你的程序的运行时间是多少?对于大的N(N>10000),其free例程是如何影响实际速度的?