首页 > 其他分享 >约瑟夫问题

约瑟夫问题

时间:2022-09-22 15:35:58浏览次数:54  
标签:curBoy 指向 创建 约瑟夫 问题 编号 节点

  • 简介
设编号为 1,2,… n 的 n 个人围坐一圈,约定编号为 k(1<=k<=n)的人从 1 开始报数,数到 m 的那个人出列,它的下一位又从 1 开始报数,数到 m 的那个人又出列,依次类推,直到所有人出列为止,由此产生一个出队编号的序列

# 解决思路
用一个不带头结点的循环链表来处理 Josephu 问题:先构成一个有 n 个结点的单循环链表,然后由 k 结点起从 1 开始计数,计到 m 时,对应结点从链表中删除,然后再从被删除结点的下一个结点又从 1 开始计数,直到最后一个结点从链表中删除算法结束

第1个人开始报数,数到2,则第2个节点出圈,第3个节点则变成2

首先让first和curBoy指向第1个节点
创建第2个节点后,第2个节点与第1个节点形成1个闭环,将curBoy指向第2个节点
创建第3个节点,依次类推

标签:curBoy,指向,创建,约瑟夫,问题,编号,节点
From: https://www.cnblogs.com/chniny/p/16719472.html

相关文章