Question

一道数学题:N个人围成一圈,顺序标号1~N;从第一个人开始,每隔一个人出去一个人,直到只剩下一个人.例:N=6;出圈的人

Answer 1

n=1+(N-2^[log(2,N)])*2,[]为向下取整

当第一个人被踢出去时,把剩下的人重新编号,问题就相当于N-1个人的：原来的1号变成N-1号,剩下的新号等于原来的号-2.

这样可以列出递推公式：

记F(n)的值是最后剩下的人的序号

当F(n-1)=n-1时

F(n)=1

否则

F(n)=F(n-1)+2

然后可以根据这个递推公式和F(1)=1,写出上面的通项公式.

查了一下,这类问题叫约瑟夫问题,通常是用编程解的……