设有编号为1,2,......,n的n个体围成一个圈,从第1个体发轫报数,报到m时结束报数,报m的人出圈。再从他的下一个体起从新报数,报到m时结束报数,报m的出圈......遵循这个礼貌实行下来,直到全部人齐备出圈为止。求终末留下来的人编号。
为了使题目简化,咱们思量n个体编号为0 ~ n-1的环境,每 m 个体退出一个体,咱们称之为(n, m)题目。
第一个体(即编号为正在模n下同余m的人)退出之后,对剩下的 n-1 个体从新编号,则新题目的k号正在原题目中对应 k+m 号。以是(n, m)题目的解 J (n, m) = J (n-1, m)+m 且 J (1, m) = 0(模n旨趣下)。据此,通过递推的技巧能够取得 J (n, m)。
“正在实施中约瑟夫题目平常用代码实行求解刘谦的魔术中行使的便是m=2 的出格环境”
中邦青年报(ID:zqbcyol 中青报·中青网记者:张力友 编辑:李丽)
本文由:猫先生 提供