约瑟夫环问题的解答

解题思路:模拟or递归（这里解题基于我的代码）

注意事项:1.使用模拟的话 一定要注意报数是迟于检查的 所以初始化count=1;每次元素退场后都需要初始化count=1.

               2. 当你模拟一遍之后 你就会对这个 i=(i+1)%n大彻大悟（我也是模拟一遍后开始理解取模运算的 核心就是数组的起点是从0开始的 约瑟夫环的递归函数是基于0-based 而非1-based）

参考代码:

 模拟法：

1. #include<iostream>

2. using namespace std;

3. 
   

4. 
   

5. int main() {

6. 
   

7. int n;

8. cin >> n;

9. int mimic = n;//这里不能进行n--因为最后我们数组循环需要n值 即i=(i+1)%n;

10. int count = 1;//一定初始化为1 数数总是比判断后一步 后面退出元素后count也是初始化为1

11. int a[200] = {};//数组初始化为0 当模拟退场时 a[i]=-1(死），a[i]=0(活）

12. int i = 0;//首先是数组一般是从0开始 其次是取模运算返回0时刚好对应起点a[0] 别初始化为1

13. while (mimic > 1)

14. {

15. //对数组元素进行判断 两种 1：活着继续报数 2. 出局

16. if (a[i] == 0 && count != 3)

17. {

18. count++;

19. }

20. else if (a[i] == 0 && count == 3)

21. {

22. a[i] = -1;//出局

23. mimic--;

24. count = 1;

25. }

26. i = (i + 1) % n;

27. }

28. //检查数组 找出活着的元素a[i]=0

29. for (int i = 0; i < n; i++)

30. {

31. if (a[i] == 0)

32. {

33. cout << i + 1;//对应1-based;

34. break;

35. }

36. }

37. 
    

38. return 0;

39. }

-----------------------------------------------------------------------------------------------------------------------------------------

2.递归法

这里主要是理解这个递归函数 即f(n,m)= (f(n-1,m)+m)%n 这里解释一下这个递归函数（大前提是我们从0开始数 数到2结束） 假设我们有6个人 

先考虑5个人的情况 他们分别是0，1,2,3,4 数到2就出局 那么谁会活下来呢？ 是3   

回到6个人的情况 当我们出局第一个人时（编号是2） 此时将环连接构成新环（编号是3的位置变成0） 这时情况就是5个人的情况了 新环里编号是3的人一定是那个不死鸟 要是知道它在旧环里的位置就好了 顺着这个思路 我们发现 新环里的数+3不就刚好对应上旧环吗 于是我们用（这里的3是f(5,3))3+3 可是6这个编号根本就不存在啊？ 要是画图 你会发现新环3其实是和旧环0是重叠的 所以f(6,3)里0这个编号一定是不死鸟  我们可以通过6%6就得到0这个编号 所以我们利用%运算来映射新环在旧环里的位置 至此递归关系一目了然

1. #include<isotream>

2. using namespace std;

3. 
   

4. int ring(int n)

5. {

6. if (n == 0)

7. {

8. return 0;

9. }

10. else

11. {

12. return (ring(n - 1) + 3) % n;

13. }

14. }

15. 
    

16. int main() {

17. int n;

18. cin >> n;

19. cout << n + 1;// 这里一定要n+1对应现实1-based

20. 
    

21. return 0;

22. }