知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 08 - 灯泡开关 ## 题目 有 100 个灯泡,初始全部是**灭**的。进行 100 轮操作: - 第 1 轮:按下所有编号为 **1 的倍数**的开关(即所有灯泡) - 第 2 轮:按下所有编号为 **2 的倍数**的开关(2, 4, 6, 8, ...) - 第 3 轮:按下所有编号为 **3 的倍数**的开关(3, 6, 9, ...) - ... - 第 100 轮:按下所有编号为 **100 的倍数**的开关(只有 100) 每次按下开关,灯的状态翻转(灭 → 亮,亮 → 灭)。 问:最后哪些灯是亮的? ## 大白话理解 想象一排 100 盏灯,全关着。你按 100 次"奇特的规则"去拨动开关:第 1 次把所有的都按一遍,第 2 次每隔一个按一个,第 3 次每隔两个按一个……最后,哪些灯会亮着? ``` 简化到 10 盏灯,手动跟踪: 灯编号: 1 2 3 4 5 6 7 8 9 10 初始: ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ (○=灭) 第1轮(按1的倍数): ● ● ● ● ● ● ● ● ● ● (●=亮) 第2轮(按2的倍数): ● ○ ● ○ ● ○ ● ○ ● ○ 第3轮(按3的倍数): ● ○ ○ ○ ● ● ● ○ ○ ○ 第4轮(按4的倍数): ● ○ ○ ● ● ● ● ● ○ ○ ... 最终(第10轮后)亮着:1、4、9 全是完全平方数! ``` --- ### 核心推理:灯被按了几次? ``` 灯 k 在第 i 轮被按 ⇔ i 是 k 的因子(因数) 例如灯 12: 因子:1, 2, 3, 4, 6, 12 → 共 6 个 被按 6 次 → 亮(1)→灭(2)→亮(3)→灭(4)→亮(5)→灭(6) → 最终灭的(按了偶数次) 例如灯 16: 因子:1, 2, 4, 8, 16 → 共 5 个 被按 5 次 → 亮→灭→亮→灭→亮 → 最终亮的(按了奇数次) 关键规律: 因子个数是奇数 → 灯亮 因子个数是偶数 → 灯灭 ``` --- ### 什么数的因子个数是奇数? ``` 一般数的因子成对出现: 12 = 1×12 = 2×6 = 3×4 → 3 对 → 6 个(偶数) 但完全平方数有一个"自配对"的因子: 16 = 1×16 = 2×8 = 4×4 → 4 出现了两次但只算一个因子 → 因子数 = 2对 + 1个 = 5 个(奇数) 所以:只有完全平方数的因子个数是奇数! ``` ``` 100 以内的完全平方数: 1² = 1 2² = 4 3² = 9 4² = 16 5² = 25 6² = 36 7² = 49 8² = 64 9² = 81 10² = 100 答案:{1, 4, 9, 16, 25, 36, 49, 64, 81, 100},共 10 盏灯亮 ``` --- ### 推广到 N 盏灯 ``` N 盏灯,N 轮操作后,亮着的灯 = N 以内的所有完全平方数 答案数量 = ⌊√N⌋ 个 例如: 100 盏 → ⌊√100⌋ = 10 盏 200 盏 → ⌊√200⌋ ≈ 14 盏 1000 盏 → ⌊√1000⌋ ≈ 31 盏 ``` ```java public List<Integer> bulbSwitch(int n) { List<Integer> result = new ArrayList<>(); for (int i = 1; i * i <= n; i++) { result.add(i * i); } return result; } ``` --- ## 一句话总结 每盏灯被按的次数 = 其编号的因子个数。只有完全平方数的因子个数是奇数(因为有一个因子与自己配对),所以最后亮着的灯都是完全平方数:1, 4, 9, 16, 25, 36, 49, 64, 81, 100。 --- 下一篇:[09 - 帽子颜色](./09-hat-color.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入