n个人围成一圈,从第1个人开始顺序报号1、2、....k。凡报到k者推出圈子。找出最后留在圈子中的人原来的序号。本题要求用链表实现。n<50,k<50。
时间: 2024-04-07 20:28:41 浏览: 51
python 有n个人围成一圈,顺序排号,问最后留下的是原来第几号的那位。(示例)
5星 · 资源好评率100%
这是一个经典的约瑟夫问题。可以使用循环链表来实现,即将n个人的编号存入循环链表中,然后依次从头节点开始报数,每报到第k个人就将其从链表中删除,直到链表中仅剩一个节点,即为最后留在圈子中的人。
具体实现步骤如下:
1. 定义一个结构体Node,表示链表中的节点,包含成员变量编号和指向下一个节点的指针。
2. 构造循环链表,将n个人的编号存入链表中。
3. 定义一个指针p,指向链表的头节点,从头节点开始报数。
4. 使用循环遍历链表,每次将指针p向后移动k-1个节点,然后将下一个节点从链表中删除。
5. 循环执行步骤4,直到链表中仅剩一个节点。
6. 返回链表中剩余节点的编号,即为最后留在圈子中的人原来的序号。
以下是一个C++实现示例代码:
阅读全文