作业帮连续自然数1,2,3...,.从1开始,留1,2划掉3,留4,5划掉6.到任意一个数,这么转圈下去,最后剩?
来源：学生作业帮助网 编辑：作业帮 时间：2024/11/15 17:45:44
连续自然数1,2,3...,.从1开始,留1,2划掉3,留4,5划掉6.到任意一个数,这么转圈下去,最后剩?
连续自然数1,2,3...,.从1开始,留1,2划掉3,留4,5划掉6.到任意一个数,这么转圈下去,最后剩?
连续自然数1,2,3...,.从1开始,留1,2划掉3,留4,5划掉6.到任意一个数,这么转圈下去,最后剩?
最后剩下都不是3的倍数 或者说剩下的任何一个自然数都不能被3整除
希望对你有所帮助
最后剩下的一定是3的倍数
这问题学名叫约瑟夫问题：（我原来明白过，现在忘了，以下是直接粘的，我有点懒得看。您先看吧，万一看完还不明白，再追问，我再想想）
我们以人数为2009为例计算，最后被杀死的人记为F(2009) 假设现在还剩下n个人，则下一轮将杀死[n/3]个人，还剩下n-[n/3]个人 设这n个人为a1,a2,...,a(n-1),an 从a1开始报数，一圈之后，剩下的人为a1,a2,a4,a5...
全部展开
这问题学名叫约瑟夫问题：（我原来明白过，现在忘了，以下是直接粘的，我有点懒得看。您先看吧，万一看完还不明白，再追问，我再想想）
我们以人数为2009为例计算，最后被杀死的人记为F(2009) 假设现在还剩下n个人，则下一轮将杀死[n/3]个人，还剩下n-[n/3]个人 设这n个人为a1,a2,...,a(n-1),an 从a1开始报数，一圈之后，剩下的人为a1,a2,a4,a5,...a(n-n mod 3-1),a(n-n mod 3+1),..,an 于是可得： 1、这一轮中最后一个死的是a(n-n mod 3),下一轮第一个报数的是a(n-n mod 3+1) 2、若3|n,则最后死的人为新一轮的第F(n-[n/3])个人 若n mod 3≠0 且f(n-[n/3])<=n mod 3则最后死的人为新一轮的第n-[n/3]+F(n-[n/3])-（n mod 3）人 若n mod 3≠0 且f(n-[n/3])>n mod 3则最后死的人为新一轮的第F(n-[n/3])-（n mod 3）人 3、新一轮第k个人对应原来的第 3*[(k-1)/2]+(k-1)mod 2+1个人 综合1，2，3可得： F(1)=1,F(2)=2,F(3)=2,F(4)=1,F(5)=4，F(6)=1， 当f(n-[n/3])<=n mod 3时 k=n-[n/3]+F(n-[n/3])-（n mod 3）,F(n)=3*[(k-1)/2]+(k-1)mod 2+1 当f(n-[n/3])>n mod 3时 k=F(n-[n/3])-（n mod 3） ，F(n)=3*[(k-1)/2]+(k-1)mod 2+1 这种算法需要计算 [log(3/2)2009]次 这个数不大于22，可以用笔算了 于是： 第一圈，将杀死669个人，这一圈最后一个被杀死的人是2007，还剩下1340个人， 第二圈，杀死446人，还剩下894人 第三圈，杀死298人，还剩下596人 第四圈，杀死198人，还剩下398人 第五圈，杀死132人，还剩下266人 第六圈，杀死88人，还剩下178人 第七圈，杀死59人，还剩下119人 第八圈，杀死39人，还剩下80人 第九圈，杀死26人，还剩下54人 第十圈，杀死18人，还剩36人 十一圈，杀死12人，还剩24人 十二圈，杀死8人，还剩16人 十三圈，杀死5人，还剩11人 十四圈，杀死3人，还剩8人 十五圈，杀死2人，还剩6人 F(1)=1,F(2)=2,F(3)=2,F(4)=1,F(5)=4，F(6)=1， 然后逆推回去 F(8)=7 F(11)=7 F(16)=8 f(24)=11 f(36)=16 f(54)=23 f(80)=31 f(119)=43 f(178)=62 f(266)=89 f(398)=130 F(596)=191 F(894)=286 F(1340)=425 F(2009)=634
收起