约瑟夫环问题:每次从这个圆圈中删除第 m 个数字(第一个为当前数字本身,第二个为当前数字的下一个数字)。当一个数字删除后,从被删除数字的下一个继续删除第 m 个数字。求出在这个圆圈中剩下的最后一个数字。
据说之前,这些数字是死囚,能抽到最后一个的人能活着……
模拟的方法弱爆了,有递推公式的,假设有n个人,每轮第k个人被杀掉,递推公式如下:
如果想知道推导过程,可以看维基百科:"Josephus problem"
即初始sum=0,我们从i=2开始(i就是上面公式的n),每次另sum = (sum+m)%i即可。据说下面这货是动态规划的一种啊……
// N people, Delete mth int josephus(int n, int m) { int i; int sum = 0; for(i=2;i<=n;i++) { sum = (sum+m)%i; } return sum; }