约瑟夫环 递归解法

问题：
已知n个人围成一圈（编号：1，2，3，…，n），从编号为1的人开始报数，报数为m的那个人出列；从他的下一个人又从1开始数，同样报数为m的人出列；依此循环下去，直到剩余一个人。求最后这一个人在最开始的序列中编号是几号？
显然，这个问题非常适合用循环链表。但是这里我们讨论一下其它解法。由于每次出列一个人以后，问题格式与最开始一样，只是数字规模变小了，所以考虑使用递归法。

1. #include <stdio.h>
   
2. int ysfh(int n, int m) //一共n个人，每次报m个
   
3. {
   
4.         return n==1?0 : (ysfh(n-1,m)+m)%n ;
   
5. }
   
6. int main()
   
7. {
   
8.         int total,gap;
   
9.         scanf("%d %d",&total,&gap);
   
10.         printf("%d\n",ysfh(total,gap) + 1);        
    
11.         return 0;
    
12. }

复制代码

执行结果：

50
3
11

• 本内容来源互联网，如涉及版权问题请及时联系站长
• 为防止代码解析，除代码框内<>为正常，其余请重新替换<>尖括号