一种非常巧妙地解题方法|教家长辅导奥数


今天的题目是关于约瑟夫环问题,

所用知识不超过小学4年级。

题目(5星难度):

某学校有2018个学生围成一个大圆圈做游戏,这些学生的编号按顺时针依次为1、2、3、…、2018。从1号学生开始不断顺时针报数,报数是偶数的学生就退出游戏。最后剩下一个学生的编号是多少?

辅导办法:

题目写给小朋友,让他自行思考解答,若20分钟还不能解答,由家长进行讲解。

讲解思路:

这种类型的题目,

如果不能直接求解,

是因为2018人不好处理,

不妨从好处理的人数开始考虑,

再推广到一般的情况。

根据游戏的淘汰规则,

如果人数是2、4、8、16……,

都是最容易考虑的特殊情况。

步骤1:

先思考第一个问题,

如果游戏人数是2、4、8、16……等,

最后剩余的人编号是多少?

这个问题比较简单,

剩下的都是1号。

只有2个人转1圈,

有4个人转2圈,

有8个人就转3圈,

有16个人就转4圈,

以此类推,

转10圈剩1个人是1024人游戏。

其中1024人游戏是比较特别的,

在步骤2中我们将用到。

步骤2:

再思考第二个问题,

2018个人游戏到多少号就剩1024人了?

步骤1中最后之所以考虑1024,

是因为1024*2=2028 > 2018,

第一圈游戏中间就会只剩1024人。

此时退出游戏的人数为2018-1024=994,

因此第1988=994*2号退出后就剩1024人。

步骤3:

综合上述两个问题,

从步骤2知道,

从1989号第一次报数开始,

圈里只有1024人了。

报数只是淘汰偶数,

把游戏看作这1024人重新开始报,

结合步骤1的结论,

第一个报数的人总是能留在最后,

所以最后剩下的是第1989号。

注:这种类型的问题称作约瑟夫环,

是计算机编程的常见练习题。

思考题:

某学校有2018个学生围成一个大圆圈做游戏,这些学生的编号按顺时针依次为1、2、3、…、2018。从1号学生开始不断顺时针报数,报数是奇数的学生就退出游戏。最后剩下一个学生的编号是多少?