讲题比赛讲稿.doc

讲题比赛讲稿
一、问题的提出
我今天要讲的是第12题。题目为：有2015个同学站成一个圆圈，按顺时针方向编号：1—2015。现在从1号开始，按“0、1、0、1、0、1……”的方式报数，报到1的同学立即离开，不再参与报数。到最后只剩一个同学时报数停止。请问最后留下的这个同学的编号是多少？
二、问题分析
这道题其实源于一道很有意思约瑟夫问题。
约瑟夫问题，有时也称为约瑟夫斯置换，是一个出现在计算机科学和数学中的问题。据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数3该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
回到我今天要讲的题目。题目中将约瑟夫问题中的报数方式置换成“0、1、0、1……”循环报数，而且将结果也变成了“最后留下的同学的编号是多少？”虽然题目条件有了变化，但是仍然属于“约瑟夫问题”，可以用该类方法进行分析和解决。
三、问题的研究
拿到题目以后，我们对此题的研究经历了三个阶段。
第一阶段：自我摸索阶段
拿到题后，我简直有点懵。说实话，我从来没有遇到过这样的题。不过我想，通过网络搜索应该会有些眉目。可是当我将原题输入百度以后，却找不到答案。我只能对着题目，自己动手研究了。
首先我想到数的奇偶问题。当总人数为奇数时，第一轮留下的是所有奇数编号；而到第二轮……情况比较复杂了。而当总人数为偶数时，那么第一轮排除的是偶数编号；第二轮排除的就是4n的编号；第三轮时，剩下的编号可能是奇数个，怎么办呢？
再次受挫的我只能像个小学生一样从最原始的方法开始模拟游戏过程。我从3人开始研究3人留下的是3号；4人留下的是1号……当研究到8人留下是1号时，我恍如黑暗中窥见无限光明。于是我继续逐个研究，正如我所想，8—15人所留下的编号正好是奇数的递增排列。于是我大胆设想，从16—31人应该也是从1开始的奇数递增排列。依此类推，我终于找到了报数游戏的规律。而4、8、16、32……1024、2048这些数，正好是2的幂值。
整理自己的研究思路，我终于找到了解决这道题的方法。
设人数为n，那么
当 2≤n＜2时，有（n-2）×2+1 例如 （5-2）×2+1=3
当2≤n＜2 时，有（n-2）×2+1 例如 （14-2）×2+1=13
当2≤n＜2 时，有（n-2）×2+1 例如 （29-2）×2+1=27
……
当n=2015时，因为2≤2015＜2，（2015-2）×2+1，所以（2015-2）×2+1=1983
所以，2015个学生采取报数的方式，最后留下的编码为1983号。
通过研究还可以发现：所有留下的编号从1到下一个1为一组，每一组中都是从1开始递增的奇数，且每组元素的个数分别为1，2，4，8……也就是2的幂值递增的个数。
第二阶段；学生探究阶段
为了测试学生的数学思维灵活性和解决问题的能力，我决定在高年级学生中进行小练习。我在六年级选择了3名数学思维非常好的孩子，将题目交给他们进行研究。他们首先采用的是列举的方式去找留下的编号，可是数据太大，无法准确地找到编号。经过老师提示后，他们开始用“取纸片”来模拟游戏过程，用编好序号的纸片代表学生，然后按规则排队报数游戏，然后对每次游戏的结果进行记录。到24人时，他们很快就发现了留下编号的排列规律。于是他们大胆假设25—31人时，留下的编号应该是19—31中的奇数。而如果人数为32时，不可能留下编号33，因为编号不可能超过总人数。多么聪明的孩子呀！随着研究的深入，他们很快又找到了几个关键的数，像4、8、16、32、64、128、256、512、1024、2048……当人数是这些数时，留下的编号都是1，接下来就是奇数的递增排列。灵活的思维，强大的推理，加以细心的验证，得到的是多么伟大的发现呀！
第三阶段：渐入佳境阶段
通过两个阶段的研究，我对解这道题有了自己的认识。但是我总觉得我的研究还不够深入，对题目缺少理论上的更深层次的认识。找个机会特意请教正读高中的女儿，她说：“这个就是‘约瑟夫杀人游戏’呀！”约瑟夫游戏？原来这道题还蛮有背景的呀！于是我上网搜索，终于找到了关于约瑟夫问题的相关知识（见“问题分析”部分）。约瑟夫问题是一个出现在计算机科学和数学中的问题，在计算机编程的算法中，类似问题又称为约瑟夫环，也称作“丢手绢问题”。
约瑟夫环问题来源于公元6世纪犹太人的反罗马起义，这个问题非常流行，以至于几乎所有的编程入门和算法书籍都会提到这个问题，以作为数据结构或模拟算法的经典入门题。
关于约瑟夫环问题，网络上有很多关于计算机编程方法和数学方法的介绍，但是解题思路都涉及到比较高深的“链表实现”和“数组实现”问题，我琢磨半天都看不太明白。但是经过一番囫囵吞枣般的阅读，我大概明白了这个问题可以转化为一个倒推问题！通常解决这类问题时我们把编号从0—n-1，最后结果+1即为原问题的解。
约瑟夫问题一般可描述为：已知n个人（以编号0，1，2，3……n-1表示）围坐在圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列，求最后一个出列人的编号。
我们知道当第一个人出列之后，剩下的n-1个人组成了一个新的约瑟夫环，变换后就变成了(n-1)个人报数的子问题；如何知道(n-1)个人报数的子问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况 ……以此类推，我们最终会寻找到（n-n+1）的解。
回到我们的原题。2015个人会排除2014个人，每一轮排除一个人，我们不从1看起，从2015倒推起，假设倒数第二轮排除的人编号是n，那么最后剩下的人就是n+1。所以我们只要知道倒数第二轮(第2014轮)的那个人(编号n)等于多少。那么同理，第2014轮那个人编号是多少，我们看2013轮的人……以此类推回去，最终可以推到起始点1。
题中的2015人围成一圈，从1号起顺时针方向编号报数因而启发我们用一个循环的链来表示，可以使用结构数组来构成一个循环链。
四、问题延伸（这部分还没有研究清楚）
约瑟夫问题的题目的变化形式很多，但是万变不离其宗。
延伸一：猴子选王问题。
一堆猴子都有编号，编号是1，2，3 ...m，这群猴子（m个）按照1—m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
这道题
延伸二：17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难。于是议定：30个人围成一圈，从第一个人开始依次报数，每数到第9个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样才能使每次投入大海的都是非教徒？
题目中30个人围成一圈，因而启发我们用一个循环的链来表示，可以使用结构数组来构成一个循环链。结构中有两个成员，其一为指向下一个人的指针，以构成环形的链；其二为该人是否被扔下海的标记，为1表示还在船上。从第一个人开始对还未扔下海的人进行计数，每数到9时，将结构中的标记改为0，表示该人已被扔下海了。这样循环计数直到有15个人被扔下海为止。
延伸三：2009个人围成一圈报数，报到3的被杀死，最后留下的是哪两个编号的人留下来？
第一圈，将杀死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人

五、讲题反思
回顾对这道题的研究过程，我体会良多，主要有以下三点。
1．不断研究是数学教师进步的阶梯。师者传道授业解惑也。在知识日新月异的信息时代，倘若教师总是抱着自己的旧知识“老本”，不及时更新自己的知识体系，真的会成为这个社会的弃儿，何谈“传道授业解惑”？教师如果能潜心于学习、专注于研究，那么他不仅能开阔自己的眼界，而且能深刻体会到学生参与探究活动的心理，从而完善自己的教学。
2．指导学生研究是发掘潜能的法宝。这次讲题研究，六年级的3个孩子在老师的启发下，通过动手操作、分工合作很快找到了这道题的窍门，充分展示了他们的聪明才智，其思维的灵活着实令人赞叹。其实很多学生的思维往往优于我们成年人，作为教师，充分发掘聪明的孩子的思维火花，该是一件多么令人愉悦的事情！具有研究精神的教师，他培养的学生也会从小懂得发现问题和提出问题，也能主动地探究解决问题的方法，还能学会学习，有一颗永不止步的研究的心。
3．研究问题的过程需要锲而不舍的精神。在研究这道题的时候，我进行了模拟游戏、观察分析、猜测验证、归纳提炼，并且请教了很多数学高手，还从网络上进行了自我琢磨式的学习，终有所获。研究往往不是一蹴而就的事情，需要不断努力，不轻易放弃的精神。