7-3 约瑟夫环 分数 10 作者 usx程序设计类课程组 单位 绍兴文理学院 有n个人围成一圈（编号为1～n），从第1号开始进行1、2、3报数，凡报3者就退出，下一个人又从1开始报数……直到最后只剩下一个人时为止。请问此人原来的位置是多少号? 输入格式: 测试数据有多组，处理到文件尾。每组测试输入一个整数n（5≤n≤100）。 输出格式: 对于每组测试，输出最后剩下那个人的编号。

这是经典的约瑟夫环问题，可以使用循环链表或者数学公式来解决。下面给出使用数学公式的解法：

假设最终剩下的人的编号为 $f(n)$，则第一次报数后，编号为 $3$、$6$、$9$、$\cdots$ 的人出圈，剩下 $n_1=n-\lfloor\frac{n}{3}\rfloor$ 个人，且编号重新从 $1$ 开始。

对于剩下的 $n_1$ 个人，第二次报数后，编号为 $2$、$5$、$8$、$\cdots$ 的人出圈，剩下 $n_2=n_1-\lfloor\frac{n_1}{3}\rfloor$ 个人，且编号重新从 $1$ 开始。

对于剩下的 $n_2$ 个人，第三次报数后，编号为 $2$、$5$、$8$、$\cdots$ 的人出圈，剩下 $n_3=n_2-\lfloor\frac{n_2}{3}\rfloor$ 个人，且编号重新从 $1$ 开始。

以此类推，直到剩下一个人为止，即 $n_k=1$，此时剩下的那个人的编号就是 $f(n)$。因此，我们可以列出递推公式：

$$
n_{k}=n_{k-1}-\left\lfloor\frac{n_{k-1}}{3}\right\rfloor, \quad n_0=n \\
f(n)=3k-n_k+1
$$

根据递推公式，我们可以编写如下代码：