编号为1,2,…,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始以6作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,再从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有人全部出列为止。 输入格式: 首先输入一个整数T,表示测试数据的组数,然后是T组测试数据。每组测试数据第一行输入n,第二行输入n个不超过20的正整数,依次表示这n个人所持有的密码。 输出格式: 对于每组测试,按照出列的顺序输出各人的编号。每两个编号之间留一个空格。
时间: 2023-09-30 14:07:25 浏览: 115
约瑟夫(Josephus)环问题:编号为1,2,3,…,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)
5星 · 资源好评率100%
这是经典的约瑟夫问题,可以使用循环链表来模拟整个过程。
具体步骤如下:
1. 构建循环链表,每个节点存储该人的编号和密码。
2. 从第一个人开始报数,每数到m就删除该节点,并将m更新为该节点的密码。
3. 继续从下一个人开始报数,重复上述过程,直至所有人都被删除。
4. 输出删除的顺序即可。
代码如下:
阅读全文