約瑟夫問(wèn)題是個(gè)有名的問(wèn)題：N個(gè)人圍成一圈嘁信，從第一個(gè)開(kāi)始報(bào)數(shù)勤哗，第M個(gè)將被殺掉抡爹，最后剩下一個(gè)，其余人都將被殺掉芒划。
那么第一個(gè)死的是（m-1)%n號(hào)冬竟，現(xiàn)在只剩下來(lái)n-1人，從m%n開(kāi)始報(bào)數(shù)民逼。
設(shè)f(n)表示共有n個(gè)人時(shí)最終存活的人泵殴，共10人，編號(hào)0-9缴挖，每次殺3號(hào)：
f(1)=0;只剩1個(gè)人袋狞，它的位置是pos=0；
f(2)=(0+3)%2=1;這個(gè)人在上一輪也存活映屋，它的位置是：pos=(0+m)%2;
f(3)=（1+3)%3=1這個(gè)人在上上一輪也存活苟鸯，它的位置是：pos=((0+m)%2+m)%3;
我們可以看出，最后一個(gè)殺死的人棚点，在前一輪的排序正好與 這一輪的排序相差m早处，因?yàn)榈箶?shù)第二輪從他開(kāi)始，數(shù)了m個(gè)數(shù)后正好到他瘫析。f[1]=(f[0]+3)%2=1;
以此類(lèi)推砌梆，他在倒數(shù)第三輪的排序正好與倒數(shù)第二輪相差m默责。
得到遞推公式: f[i]=(f[i-1]+m)%i
因此，可以得到:
int lastRemaining(int n, int m) {
int f[n+1];
f[1]=0;
for(int i=2;i<=n;i++)
{
f[i]=(f[i-1]+m)%i;
}
return f[n];
}
進(jìn)一步簡(jiǎn)化：
int lastRemaining(int n, int m) {
int res=0;
for(int i=2;i<=n;i++)
{
res=(res+m)%i;
}
return res;
}
