曲径通幽,隰有苌楚。夹岸百里,婀娜其实。 每周学习一个算法。
今天是星期六大年初九,该上班的上班,该上学的也马上开学了。今年过年感觉怎么样?你是不是又变胖了?上班的是不是觉得钱包空了?上学的是不是觉得最近不太常用电子支付改用现金了?过年不要玩野了,因为 Koan 带着新的算法回来了。另外再强调一遍,单项式求导已经完成并上传至了最大的同性交友网站,链接如下:https://github.com/Koan317/Differentiate。今年还请继续关注。
本次的算法需要用到特殊的数据结构:循环链表。
链表是创建在堆内存当中的链式存储结构,将尾节点指向头节点便形成了循环链表。链表是动态存储结构,长度可变。每个节点提供了两个信息,一个是当前节点的值,另一个是下一节点的地址。节点定义如下:
链表中有若干节点,同时还有两个标志性节点,即头节点和尾节点,这两个节点在遍历和删除等操作中扮演非常重要的角色。链表定义如下:
约瑟夫问题是一个基于循环链表提出来的问题,问题的内容是,一个旅行社为一个旅行团提供了一项服务,抽取其中一人为其提供免费旅行。抽取的方式是,给所有人编号,从 1 号开始每隔若干人就剔除一个人,数到最后一位回到 1 号,直到剩下最后一人。
我们简单分析就可以看出,只需生成一个顺序表作为所有人的编号,每隔若干项就删除一项,最后剩下的节点值就是享受免费旅行的人的编号。核心算法如下:
完整代码已经上传至同性交友网站:https://github.com/Koan317/Josephus
领取专属 10元无门槛券
私享最新 技术干货