MS的一道面试题[ZT]

Question

圆圈上顺时针排列着1,2,3,....2000 这2000个数. 从1开始,顺时针隔一个拿走一个(1最先被拿走,下一个是3被拿走). 问最后剩下是哪一个数字.要求给出一个比较有效率的算法！

Answer 1

奇偶校检法.假如一共有x个数,取走的都为奇数,那么如果x为奇数,最后剩下的就是x-1,如果x为偶数,最后剩下的就应该是x.

Answer 2

用c简单写了一下
void main()
{
int i=0;
bool flag=true;
int count=0;
int test[2000]={0}; for(i=0; i<2000; i++)
{
test[i]=i+1;
} while(count!=1)
{
printf("number remain in array:%d\n", count);
i=0;
count=0;
while(i<2000)
{
if(test[i]!=0)
{
if(flag)
{
test[i]=0;
count++;
}
flag=!flag;
}
i++;
}
} for(i=0; i<2000; i++)
{
if(test[i])
printf("the last number is: test[%d]=%d", i, test[i]);
} return;
}用链表效率更高

Answer 3

to:ShadowSniper(牛头人酋长(等级10)) 
人家说的是 问最后剩下是哪一个数字?
从1开始取,最后拿掉1999,接着继续啊剩下2000,2,4,6...接下来应该是拿掉2,6...问的就是最后剩下哪一个数

Answer 4

这上面有大家讨论的:http://community.csdn.net/Expert/topic/5194/5194500.xml?temp=.3021356