初级编程通关练习题 #7 – 约瑟夫环

约瑟夫环问题是一个著名的倒数游戏,规则如下:给定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。那么删去一个数值后,第二个出局的数值位置就可以采用递归的思路来处理,计算公式如下:
f(n,k)=((f(n-1,k)+k-1){\bmod  n})+1,{\text{ with }}f(1,k)=1\,,