约瑟夫环问题是一个著名的倒数游戏,规则如下:给定N个游戏者,从第一个人开始计数,每K个人出局一人,继续从当前位置倒数,一直到最后剩下一个人为止。计算最后一个人在N个人中的位置。
譬如我们现在有八个人,每数三人就出局一人:
- [ 1,2,3,4,5,6,7,8 ] – 初始数列
- [ 1,2,4,5,6,7,8 ] => 3号出局
- [ 1,2,4,5,7,8 ] => 6号出局
- [ 2,4,5,7,8 ] => 1号出局
- [ 2,4,7,8 ] => 5号出局
- [ 4,7,8 ] => 2号出局
- [ 4,7 ] => 8号出局
- [ 7 ] => 4号出局,最后剩下的是 7 号
输入样例:
N= 500, K= 9
输出样例:
226
如果是五百人参加游戏,每数九人就出局一人,那么最后剩下的是第226号。
算法思路:
- 方法一:暴力破解,初始化从1到N的N个数值的数列,从第一个数值开始计数,每K个数值就删去一个,一直到最后剩下一个数值为止。
- 方法二:递归算法 – 如果以索引1开始计数,因为第一个出局的数值位置是 f (n,k) =(k – 1)mod n + 1。那么删去一个数值后,第二个出局的数值位置就可以采用递归的思路来处理,计算公式如下: