圆圈中最后剩下的数字

思路：常规做法是就环形链表，可以用数组表示。
这里先容一种数学方法来解这类约瑟夫环问题。

f(n,m)表示n个数字(0,1,2,3...n-1)删除第m个数字末了剩下的数字。
剖析：第一个删除的数字为(m-1)%n，记作k.剩下的数字(k+1,k+2...n-1,0,1,2...k-1).剩下的n-1个数字末了剩下的数字也是f(n,m),以是存在映射关系:f(n,m) = g(n-1,m)

g(n-1,m) ---> f(n-1,m)

k+1 ---> 0k+2 ---> 1........n-1 ---> n-k-20 ---> n-k-11 --> n-k-2.........k-1 ---> n-2

从g(n-1,m)到f(n-1,m)的映射关系:p(x) = (x-k-1)%n该映射的逆映射是:p-1(x) = (x+k+1)%n

f(n,m) = g(n-1,m) = p-1[f(n-1,m)] = [f(n-1,m)+k+1]%n = [f(n-1,m)+m]%n因此:

f(n,m) = 0 .................. (n ==1)(f(n-1,m)+m)%n ...... ( n>1)

参考代码:

root@gt:/home/git/Code# ./a.out lastOne:87root@gt:/home/git/Code# cat lastOne.c #include <stdio.h>int lastOne(int n,int m){ if(n < 1 || m < 1) return -1; int last = 0; for(int i = 2;i < n;++i) last = (last + m)%i; return last;}int main(){ int res = lastOne(100,3); printf("lastOne:%d\n",res);}