CU上面有这样一道微软面试题:

圆圈上顺时针排列着1,2,3,….2000 这2000个数. 从1开始,顺时针隔一个拿走一个(1最先被拿走,下一个是3被拿走). 问最后剩下是哪一个数字.
据说这是约瑟夫问题(Josephus’ Problem)，约瑟夫问题又是循环链表应用的典型例子。在苏格兰数学家Peter Guthrie Tait给出这个问题的通解后，又被称为Tait’s Problem。
这是解决办法：
(2000循环左移1)-1=1952 2000:
11111010000 2000循环左移1:
11110100001 2000循环左移1-1:
11110100000=1952
我用PHP试了一下，但是没有上面的简介，汗！

[code lang=”php”]

$arr=array();
for($i=1;$i<=2000;$i++){
$arr[]=$i;
}
echo “

“;
$tmp_arr=array();
$is_f=0;
$tmp_arr=$arr;
while(count($tmp_arr)>1){
for($i=0,$mx=count($arr);$i<$mx;$i++){
$item=$arr[$i];
if($item!=””){
if($is_f==1){
$is_f=0;
}else{
$arr[$i]=””;
$is_f=1;
}
}
}
$tmp_arr=array_filter($arr, “myempty”);
}
print_r($tmp_arr);

function myempty($var){
return ($var!= “”);
}

[/code]