游客您好
第三方账号登陆
Lv.9 管理员
1366号会员,2057活跃度,2018/12/07 加入学习
  • 176发帖
  • 161主题
  • 2关注
  • 5粉丝
这个人很懒,什么也没有留下。
最新推荐更多

[综合技巧] 约瑟夫环 递归解法

[复制链接]
风起云甬 发表于 2020-12-20 11:11:10 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
问题:
已知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




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

发布资源 快速回复 站点服务大厅 搜索 官方群