一道数学题:N个人围成一圈,顺序标号1~N;从第一个人开始,每隔一个人出去一个人,直到只剩下一个人.例:N=6;出圈的人依次为:2,4,6,3,1;剩下的人是5.现给N(很大,大到这辈子都没法按照题目去模拟出

Question

一道数学题:N个人围成一圈,顺序标号1~N;从第一个人开始,每隔一个人出去一个人,直到只剩下一个人.例:N=6;出圈的人依次为:2,4,6,3,1;剩下的人是5.现给N(很大,大到这辈子都没法按照题目去模拟出答案),求剩下的人.

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,写出上面的通项公式.
查了一下,这类问题叫约瑟夫问题,通常是用编程解的……