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