讲题比赛讲稿

讲题比赛讲稿讲题比赛讲稿 一 问题的提出 我今天要讲的是第 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 3 22 2 1 3 当 2 n 2 时 有 n 2 2 1 例如 14 2 3 4 33 2 1 13 当 2 n 2 时 有 n 2 2 1 例如 29 2 3 444 2 1 27 当 n 2015 时 因为 2 2015 2 2015 2 2 1 所以 101110 2015 2 2 1 1983 10 所以 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 个孩子在老师的启发下 通过动手操作 分工合作很快找到了这 道题的窍门 充分展示了他们的聪明才智 其思维的灵活着实令人 赞叹 其实很多学生的思维往往优于我们成年人 作为教师 充分 发掘