有n个人围成一圈(编号为1~n),从第1号开始进行1、2、3报数,凡报3者就退出,下一个人又从1开始报数……直到最后只剩下一个人时为止。请问此人原来的位置是多少号?
时间: 2023-05-31 21:20:49 浏览: 272
Python使用列表完成程序的编写:有n个人围成一圈,顺序排号。从第一个人开始报数(从1到m报数),凡是报到m的人退出圈子,问最后留下的是原来第几号的人。
5星 · 资源好评率100%
### 回答1:
这是一个经典的约瑟夫问题。最后剩下的人的编号可以用递推公式求解:
f(n,m) = (f(n-1,m)+m) % n
其中,f(n,m)表示n个人报数,每报到第m个人出列时,最后剩下的人的编号。当n=1时,f(n,m)=。
因此,如果有n个人,每报到第3个人出列,最后剩下的人的编号为:
f(n,3) = (f(n-1,3)+3) % n
例如,当n=6时,最后剩下的人的编号为:
f(6,3) = (f(5,3)+3) % 6
= ((f(4,3)+3) % 5 + 3) % 6
= (((f(3,3)+3) % 4 + 3) % 5 + 3) % 6
= ((((f(2,3)+3) % 3 + 3) % 4 + 3) % 5 + 3) % 6
= (((((f(1,3)+3) % 2 + 3) % 3 + 3) % 4 + 3) % 5 + 3) % 6
= (((((+3) % 2 + 3) % 3 + 3) % 4 + 3) % 5 + 3) % 6
= 3
因此,原来位置为3的人最后剩下。
### 回答2:
这道题目需要运用到约瑟夫问题的思路。
约瑟夫问题是一个有名的问题:N个人围成一圈,从第一个人开始报数,报到M的人出圈,直到最后只剩下一人,问这个人原来的位置。其实就是给出N、M,求最后胜利者的编号。
而本题中的约瑟夫问题只是稍作变化,每次报数一直到3而不是M。
我们先考虑一个人的情况,只有一个人时,该人原来的位置是1号。
接下来考虑2个人的情况,先假设第一次报数的人编号为1号,则第一次淘汰的是2号,剩下的是1号,此时1号再次从1开始报数,淘汰2号,最终剩下的是1号,即原来的位置。
再考虑3个人的情况。第一次报数仍由1号开始,1、2、3报数,淘汰第3个人,剩下的是1号和2号,此时2号又从1开始报数,淘汰第1个人,最终剩下的是2号。
再考虑4个人的情况。第一次报数仍由1号开始,1、2、3报数,淘汰第3个人,剩下1、2、4号,此时4号从1开始报数,报到2时淘汰2号,报到3时淘汰1号,最终剩下4号。
可以发现,对于一个初始位置为第x号的人,当人数为n时,最终被淘汰的位置是 (x+2) % n,下一个开始报数的人的位置就是 (x+3) % n。所以可以逆推出最终剩下的人的位置。
假设最终剩下的人的位置为p,初始人数为n,则最终递推公式为:
p = 0 (n=1)
p = (p+3) % i (i=2,3,...,n)
最终得出的p就是原来的位置。
### 回答3:
这是一个经典的约瑟夫问题,可以使用数学归纳法来解决。
首先考虑只有一个人的情况,显然此人原来的位置就是1号。
接下来考虑有两个人的情况。如果从1号开始报数,那么第一轮报数后,2号退出,剩下1号;如果从2号开始报数,那么第一轮报数后,1号退出,剩下2号。因此,此时剩下的人原来的位置应该是2号。
接着考虑有三个人的情况。如果从1号开始报数,那么第一轮报数后,3号退出,剩下1号和2号;第二轮报数后,1号退出,剩下2号;如果从2号开始报数,那么第一轮报数后,1号退出,剩下2号和3号;第二轮报数后,3号退出,剩下2号。因此,此时剩下的人原来的位置应该是3号。
接下来可以尝试推导一下n个人的情况。假设n个人最后只剩下第x个人,那么在n-1个人时,如果从第1个人开始报数,那么第一轮后,第m个人退出(m为(n-1)%3),剩下n-1个人;如果从第m+1个人开始报数,那么第一轮后,第x-1个人退出,剩下n-1个人。因此,可以得到如下递推公式:
f(1) = 1
f(n) = (f(n-1) + m) % n + 1
其中,f(n)表示n个人最后只剩下的那个人的编号,m为(n-1)%3。
这样,就可以用递归或循环的方式依次求出f(2)到f(n),从而得到原来的位置。
需要注意的是,由于题目中的编号是从1开始的,因此最终答案需要加上1。另外,当n为1时,答案就是1。
阅读全文