高三信息学 CSP-J初试数学基础第三讲 教学设计：离散数学核心模型与算法思维构建

高三信息学CSPJ初试数学基础第三讲教学设计：离散数学核心模型与算法思维构建一、教学背景与素养定位CSPJ初试数学基础模块始终是区分优秀生与普通考生的分水岭。第三讲锚定于离散数学核心模型——组合计数、图论基础、博弈论入门与数论初步——这四个子模块的深度融合。依据《普通高中信息技术课程标准（2017年版2020年修订）》中“计算思维”核心素养的“抽象与概括、分解与建模”维度，本讲不再满足于公式罗列，而是致力于引导学生完成从“题海战术”到“模型识别、结构重构、策略迁移”的认知跃迁。教学目标直指三个层面：知识层面，精准掌握加法乘法原理的边界条件、鸽巢原理的构造技巧、图的遍历与连通性判定、Nim博弈的SG函数机制、同余理论在密码学中的原型应用；能力层面，建立“问题—模型—算法—复杂度”的完整分析链条，具备在O(1)或O(logn)时间复杂度内解决大规模参数问题的直觉与技巧；素养层面，培养面对陌生问题时的结构化拆解习惯、对边界条件的敏感度以及对证明严密性的追求。二、学情分析与教学策略高三信息学选修班学生普遍具备C++基础语法与基础数据结构操作能力，但存在三类典型认知断层：一是“公式依赖症”，遇到组合数计算机械套用C(n,m)而忽略重复元素、相邻限制、环形排列等变体；二是“图论恐惧感”，将图论等同于DFS/BFS代码模板，缺乏对欧拉回路、哈密顿路径、二分图判定等结构性质的数学直觉；三是“博弈盲区”，仅知Nim堆取石子异或结论，不理解SG函数的mex运算本质，更不知如何将复合游戏分解为子游戏求和。针对上述痛点，本讲采用“经典例题溯源—数学结构显性化—代码实现最小化—变式拓展迁移”四段式教学策略，配合“错误样本诊断”与“同伴互教”机制，强制学生在认知冲突中重构知识网络。三、重难点预判与破解路径重点一：组合计数中的“分类与分步”边界划分及“容斥原理”在多重限制条件下的层层剥离。破解路径：引入“生成函数”思想作为统一视角，用多项式乘法直观展示分类分步的代数本质，再退回到初试笔试可操作的“插空法、捆绑法、单元法”工具箱。重点二：图论中“度数序列判定”与“连通分量压缩”在初试简答题中的快速应用。破解路径：构建“度数和公式—哈维尔判理—缩点建模”三级跳思维脚手架，配合手工模拟练习替代代码调试。难点一：博弈论中SG函数的递推计算与周期性规律探测。破解路径：以“取石子游戏变种”为载体，引导学生手工构建SG函数表，发现周期性，再用数学归纳法证明周期成立条件，最后落实为O(1)查表代码。难点二：数论中“扩展欧几里得算法”求模逆元与“中国剩余定理”构造解的通用性理解。破解路径：从线性同余方程组入手，用“同余类划分”几何直观解释CRT构造过程，避免死记公式。四、教学过程设计（四课时，每课时45分钟）第一课时：组合计数——从公式到模型的结构重构【导入·认知冲突】（5分钟）投影三道看似相似实则本质不同的题目：1.从10本不同书中选5本分给5个同学，每人1本，有多少分法？2.10个相同球放入5个不同盒子，允许空盒，有多少放法？3.10个不同球放入5个相同盒子，不允许空盒，有多少放法？要求学生30秒内判断每题核心模型（排列、隔板法、第二类斯特林数）并说明理由。统计正确率，直观呈现“公式依赖症”现状。【深度剖析·加法乘法原理的边界显性化】（15分钟）核心问题：什么情况下“分类”必须互斥？“分步”必须有序？引入“决策树”可视化工具：每个叶子节点代表一种最终结果，内部节点代表选择时刻。加法原理对应决策树第一层分支互不相交；乘法原理对应每条路径长度固定且每步选择数与前序选择无关。经典反例：从5个男生、4个女生中选3人组成委员会，要求男女都有。错误解法：C(5,1)×C(4,1)×C(7,1)=140。决策树演示：同一委员会被重复计数多次。正确建模：总数减全男全女，或分“1男2女、2男1女”两类互斥相加。推广至“重复元素排列”：单词“MISSISSIPPI”字母全排列。决策树视角下，相同字母交换不产生新叶子，故除以各重复字母阶乘。【核心模型·鸽巢原理的构造艺术】（15分钟）从“抽袜子”模型升级至CSP真题改编：“某校1000名学生，每人选修3门课，共有20门课可选。证明：至少有多少名学生选修了完全相同的3门课？”关键步骤：构造“鸽巢”=C(20,3)=1140种课程组合；“鸽子”=1000名学生。ceiling(1000/1140)=1，即至少1名（废话），但追问“至少有多少名学生任意两门课相同”则需构造“两门课组合”作为鸽巢，C(20,2)=190，ceiling(1000/190)=6。再进阶：证明任意51个整数中，必有两个数之差能被50整除。鸽巢构造为模50余数类{0,1,…,49}。强调“构造等价类”是鸽巢原理的最高级用法。【容斥原理·层层剥离的代数逻辑】（10分钟）以“1~1000中能被2、3、5整除的数的个数”为载体，演示三集合容斥：|A∪B∪C|=|A|+|B|+|C||A∩B||A∩C||B∩C|+|A∩B∩C|现场编写Python片段验证，强调“交集对应最小公倍数”这一数论联系。变式拓展：若求“恰好能被其中一个整除”的个数？引导学生列出文氏图，用系数法：1×(单集和)2×(双交和)+3×(三交和)。【课堂练习·即时反馈】（5分钟）发放“组合计数微型卡”3道题：环形排列、整数拆分、带限制条件的网格走法。要求列决策树、写表达式、不算数值。收回批注，下节课开头公布典型错误。第二课时：图论基础——结构性质与笔试技巧的双重保障【导入·生活建模】（3分钟）展示“七桥问题”简化图、课程先修关系图、局域网拓扑图。提问：这些场景共同的数学抽象是什么？学生喊出“图”。确立“顶点=实体，边=关系”建模公式。【核心性质·度数序列与哈维尔判理】（15分钟）定理：无向图度数和=2×边数。推论：奇度顶点个数为偶数。实战演练：判断序列(4,4,3,3,2,2,1,1)是否为简单图度数序列。哈维尔算法步骤演示：①非增序排列②取最大度d，删除③剩余序列前d个各减1④重复直到全0或出现负数。手工演算全过程，强调“若出现负数则非图序列”。对比“Erdős–Gallai定理”作为理论补充，说明初试只需掌握哈维尔手工模拟。【连通性与欧拉/哈密顿判定】（15分钟）欧拉回路必要充分条件：连通且全为偶度。欧拉路径：连通且恰有2个奇度顶点。哈密顿回路：无简单充要条件，但引入“迪拉克定理”：n≥3且每个顶点度≥n/2则必有哈密顿回路；“奥雷定理”：任意两个非相邻顶点度和≥n则必有哈密顿回路。CSP真题变式：给定邻接矩阵，判断是否存在欧拉路径。教会学生“读矩阵算度数、查连通、数奇度”三步法，无需建图跑代码。【二分图与最小点覆盖/最大匹配】（10分钟）定义：顶点集可分为两个子集，边只跨子集。判定：无奇环⇔可二分图⇔二色着色成功。柯尼希定理：二分图中，最大匹配数=最小点覆盖数。初试考点：给定二分图邻接表，手工跑匈牙利算法找增广路，求最大匹配。现场演示“交替路→增广路→匹配数+1”过程，要求学生在草稿纸上同步操作。【缩点技术·有向图强连通分量】（7分钟）Tarjan算法原理简述：DFS时间戳+lowlink值+栈。初试简化版：给定小规模有向图（≤10顶点），手工找强连通分量，缩点成DAG，求入度为0的强连通分量个数（即最少加边使全图强连通的答案）。演练：某年CSP真题“消息传递”模型，缩点后统计零入度分量。第三课时：博弈论——从Nim堆到SG函数的体系化构建【导入·直觉与反直觉】（3分钟）三堆石子(3,4,5)，两人轮流任选一堆取任意多个，取走最后者胜。问先手必胜否？学生迅速异或：3⊕4⊕5=2≠0，先手胜。追问：为什么异或？若改为“取走最后者负”怎么办？引出“正常游戏”与“误ère游戏”区别，确立SG函数统一理论框架。【核心概念·mex与SG函数递推】（15分钟）定义：SG(x)=mex{SG(y)|y是x的后继状态}。mex=最小非负整数不在集合中。单堆取石子：可取1、2、3个。手工建表：x:012345678…SG:012301230…发现周期T=4。证明：SG(x+4)=mex{SG(x+3),SG(x+2),SG(x+1)}=mex{SG(x1),SG(x2),SG(x3)}=SG(x)。推广：允许取集合S={s1,s2,…,sk}个石子，SG函数最终周期性成立（有限状态机必循环）。初试大数取模技巧：预计算前200项，检测最小周期，O(1)查表。【复合游戏·SG函数求和与Nim和】（15分钟）斯普拉格格隆第定理：复合游戏SG=子游戏SG值异或和。实战：“拐角游戏”变种——棋盘上一枚棋子，每步可左移、下移、或左下斜移任意格，不可出界，无法移动者负。单游戏SG(x,y)=mex{SG(i,y),SG(x,j),SG(i,i)|i<x,j<y}。手工计算4×4棋盘SG表，发现主对角线SG=0，其余SG=x⊕y（类似Wythoff游戏但不同）。强调“观察对称性、猜测公式、数学归纳证明”三步走。【进阶模型·阶梯博弈与有向图游戏】（10分钟）给定有向无环图，棋子从起点出发，沿边移动，无法移动者负。每个顶点SG值=mex后继SG值。拓扑序逆序DP计算。CSP真题：“分巧克力”游戏——一块m×n巧克力，每次选一块沿网格线掰成两块，吃掉一块，剩下一块继续。SG(m,n)=mex{SG(i,n)⊕SG(mi,n),SG(m,j)⊕SG(m,nj)}。利用对称性与记忆化搜索，初试只需写出递推式并说明复杂度。【误ère游戏简析】（2分钟）所有子游戏均为“单堆取石子”且仅剩1石子时，误èreNim策略：若全为1堆，看堆数奇偶；否则按正常Nim策略。初试仅需识别此特例。第四课时：数论初步——同余体系与算法核心的代码级落地【导入·密码学原型】（3分钟）RSA加密核心：C≡M^e(modn)，解密需d满足ed≡1(modφ(n))。引出“模逆元”与“中国剩余定理”加速解密的工程意义。【扩展欧几里得·模逆元的统一入口】（15分钟）方程ax+by=gcd(a,b)。扩展欧几里得递推：gcd(a,b)=gcd(b,a%b)→x1,y1满足bx1+(a%b)y1=g→x=y1,y=x1(a/b)y1。代码模板（背诵级）：longlongexgcd(longlonga,longlongb,longlong&x,longlong&y){if(!b){x=1;y=0;returna;}longlongg=exgcd(b,a%b,y,x);y=a/bx;returng;}模逆元：gcd(a,p)=1时，exgcd(a,p,x,y)得到x为a模p逆元，调整(x%p+p)%p。考点陷阱：a、p不互质时逆元不存在；方程ax≡b(modp)有解当且仅当gcd(a,p)|b，解的个数为gcd(a,p)。【中国剩余定理·构造解的通用逻辑】（15分钟）方程组：x≡a1(modm1)x≡a2(modm2)…mk两两互质。构造：M=∏mi,Mi=M/mi,ti=Mi^{1}(modmi)。解x=Σai·Mi·ti(modM)。推广至不互质模数：合并方程。x≡a1(m1),x≡a2(m2)。令g=gcd(m1,m2)。若a1≡a2(modg)无解；否则合并为模lcm(m1,m2)的单一方程。演示合并步骤：m1·k≡a2a1(modm2)→除以g→(m1/g)·k≡(a2a1)/g(modm2/g)→求k0→x=a1+m1·k0。初试简答题常考：求满足条件的最小正整数，或统计区间[L,R]内解的个数。【费马小定理与欧拉定理·快速幂加速】（7分钟）a^{p1}≡1(modp),p质数，a不被p整除。a^{φ(n)}≡1(modn),gcd(a,n)=1。应用：计算a^b(modp)，b极大（如10^18）。若p质数，指数对p1取模；否则对φ(p)取模。注意：指数取模前提是底数与模互质，否则需用“欧拉定理降幂”技巧：a^b≡a^{bmodφ(p)+φ(p)}(modp)当b≥φ(p)。【卢卡斯定理与组合数取模】（5分钟）C(n,m)modp,p质数，n,m≤10^18。将n,m写成p进制：n=nk…n0,m=mk…m0。C(n,m)≡∏C(ni,mi)(modp)。预处理阶乘逆元至p1，O(log_pn)求解。CSP初试高频考点，必须熟练手写预处理+卢卡斯递归代码。五、分层作业与评价体系基础层（必做）：每模块3道典型题，要求写出模型识别标签、核心公式/递推式、时间复杂度分析。如“组合计数插空法O(1)”、“图论二分图判定O(V+E)”、“博弈SG函数周期检测O(T)”、“数论扩展欧几里得O(logn)”。提高层（选做）：CSP近三年真题改编题，要求完整手写C++代码，通过本地OJ测试。重点考察边界处理：n=0、模数非质数、图不连通、博弈终止态判定。拓展层（挑战）：开放性问题——设计一个“组合计数+博弈”混合游戏，给出规则、SG函数递推式、最优策略证明。鼓励学生制作可视化演示网页，纳入学期项目作品集。评价方式：过程性评价占60%（课堂微型卡正确率、错题重做笔记、同伴互教质量），终结性评价占40%（专项测验、期中模拟卷对应题目）。建立“模型识别准确率”“代码首次通过率”“证明规范完整度”三维画像，精准画像每位学生短板。六、教学反思与迭代预案预判学生在“容斥原理系数法”、“SG函数周期性证明”、“CRT不互质合并”三个环节易卡顿。备选方案：录制5分钟微视频推送班级群，配合“错题标签打卡”小程序，利用碎片时间二次触达。若整体掌握度低于70%，启用“翻转课堂”模式，课前自学推导，课上仅做变式实战与同伴辩论。期中后将本讲模型整合进“周周练”专项