约瑟夫有没有想过自己被戴了绿帽

最后剩下的数是334。
这个问题基本没法用O(n)的复杂度来做，我来阐述一下我的观点。
头44个数基本都有规律可循，因为要从1开始加，加到999，然后减少一人，这样的话勉强可以总结出一下规律：
1 第一次计算时是 1000-999= 1，第一个被Kill的是1000-1=999
2 第二次计算可用 999 -999= 0，第二次被Kill的是 999-0=999，因为999被Kill掉了，所以第二次被Kill的是998
3 第三次计算可用 998 -999=-1，这次结果为正，所以要向右数，即997-(-1)=1000(因为998、999都被减掉了)
4 在这之后的<1000的数就有公式可以算了。例如：
997-999=-2 (1000-(-2))%1000=2
996-999=-3 (2-(-3))%1000=5
995-999=-4 (5-(-4))%1000=9
设前结果为x，差值为y，就能得到以下公式：
(x-(-y))%1000=x1
编程的话一个循环就能搞定。
但是当循环到第二遍，即得出的数大于1000后，该公式就不成立了。举个例子吧：
954-999=-45 (989-(-45))%1000=34,显然这个数不对，因为[1，34]和[989，1000]这两个区间内有9个被删掉的数未被计算在内（998、999、1000、2、5、9....)。
总结以上可以得出：
整除指令有效以后，数的分布都要从新被计算一遍，因为假设第一次整除的[1，1000]被删掉50个数，那么第二次整除后[1，1000]内就绝对会被删掉至少51个数。每运算结束后都要把区间[x，x1]或[x1，x]内已经减掉的值计算在里面，因此，编程的话可以在这个地方化简一下，但是绝对还得用双循环实现。时间复杂度依据情况会有：O(n^2)>x>O(n)，x是化简后算法的时间复杂度。

补充：
有啊，像我说的那样，如果想让时间复杂度在O(n^2)>x>O(n)这个范围内，就需要额外的数组来存储数据。如果有1000人的话就建立一个有1000个元素的一维数组，默认用零填充。如果某人被杀掉了就用1来标识。如果这么做的话就可以用我上面总结的公式作了，不过还需要两层循环才能搞定。给你一个例子吧。
#include <stdio.h>
#define MAX 1000
#define STEP 999
main()
{
int sign[MAX],n[MAX],c,t,b;
for(c=0;c<MAX;++c){sign[c]=0;n[c]=c+1;}
c=MAX;b=-1;
while(c>1)
{
t=0;
while(t<STEP)
{
b=++b%1000;
if(b==995)
c=c;
if(!sign[b])
++t;
}
sign[b]=1;
--c;
printf("%5d",n[b]);
}
for(c=0;sign[c];++c);
printf("\n The last Person`s Number is %d\n",n[c]);
return 0;
}

用容器作的话开发效率会很高，但是灵活性和运行效率肯定不高，非要用STL作的话我也想不出什么组合可以搞定这个问题，又要随机访问又要删除元素不移动数组，就像左眼向左看右眼向右看一样哈！基本不可能完成的任务，不过不排除世界上有人做得到这一说。哈哈，开个玩笑。
实际上就算是数组链表要想达到随机访问也需要移动数列的。除非你能找到规律并总结出一个公式，每次调用该公式都能精确计算被Kill的人的编号。如果不行的话，就只能用一个标识来说明是否被Kill掉，我想用struct定义个结构体也是不错的选择。但是归根结底，想随机访问，就一定不可能有链表那样的处理速度。妥协的选择就只能加上一个标识来解决本问题。

999是吗