问题描述
n个人围成一圈，号码为1-n，从1开始报数，报到2的退出，剩下的继续从1开始报数，求最后一个人的号码。
算法分析
最直观的算法是用循环链表模拟。从首节点开始，不断删除第二个节点，直到只剩一个节点为止。时间复杂度是O(2n).
typedef struct josephusnode{ struct josephusnode *next; int item; }jnode; int listjosephus(jnode *head){ jnode *n = head; while(n->next!=n){ jnode *t = n->next; n->next = t->next; n = n->next; free(t); } int retv = n->item; free(n); return retv; }
更简单的方法是数学推导。Donald E. Knuth的《具体数学》有很详细精彩的推导过程，Josephus数具有这样的递归式：
j(1)=1
j(2n)=2j(n)-1
j(2n+1)=2j(n)+1
总结发现j（2m+n）=2n+1，代码很简单：
int mathjosephus(int n){ int x=n, y=n; while(n){ y = n; n &= n-1; } x = ~y&x; x = 1+(x<<1); return x; }
参考:
《具体数学》
code:
https://github.com/coderkian/algorithm/blob/master/josephus.c
原文：http://www.cnblogs.com/coderkian/p/3589987.html