循环链表和约瑟夫问题 Circular list and Josephus problem

曲径通幽,隰有苌楚。夹岸百里,婀娜其实。 每周学习一个算法。

今天是星期六大年初九,该上班的上班,该上学的也马上开学了。今年过年感觉怎么样?你是不是又变胖了?上班的是不是觉得钱包空了?上学的是不是觉得最近不太常用电子支付改用现金了?过年不要玩野了,因为 Koan 带着新的算法回来了。另外再强调一遍,单项式求导已经完成并上传至了最大的同性交友网站,链接如下:https://github.com/Koan317/Differentiate。今年还请继续关注。

本次的算法需要用到特殊的数据结构:循环链表。

链表是创建在堆内存当中的链式存储结构,将尾节点指向头节点便形成了循环链表。链表是动态存储结构,长度可变。每个节点提供了两个信息,一个是当前节点的值,另一个是下一节点的地址。节点定义如下:

链表中有若干节点,同时还有两个标志性节点,即头节点和尾节点,这两个节点在遍历和删除等操作中扮演非常重要的角色。链表定义如下:

约瑟夫问题是一个基于循环链表提出来的问题,问题的内容是,一个旅行社为一个旅行团提供了一项服务,抽取其中一人为其提供免费旅行。抽取的方式是,给所有人编号,从 1 号开始每隔若干人就剔除一个人,数到最后一位回到 1 号,直到剩下最后一人。

我们简单分析就可以看出,只需生成一个顺序表作为所有人的编号,每隔若干项就删除一项,最后剩下的节点值就是享受免费旅行的人的编号。核心算法如下:

完整代码已经上传至同性交友网站:https://github.com/Koan317/Josephus

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180224G0U40Z00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励