【C++】B2092 开关灯

---

博客主页： [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C++

---

---

---

💯前言

• 在编程与算法学习中，想要析解一个优雅且有效的解法，基于了解题目规划与算法选择是自上考的重要步骤。本文重点分析 B2092 题目，并对不同解法进行比较和优化。通过对传统实现和优化实现的设计，带领课题中处理问题的方法和思考。
  C++ 参考手册
  

---

💯题目描述和解析

B2092 开关灯

题目描述

假设有 N 盏灯（N 为不超过 5000 的正整数），从 1 到 N 按顺序依次编号，初始时全部处于关闭状态：

• 第一个人（编号 1） 将所有灯打开；
• 第二个人（编号 2） 将编号为 2 的倍数灯切换为关闭；
• 第三个人（编号 3） 将编号为 3 的倍数灯切换为相反状态；以此类推；

最后问：当第 N 个人操作完成之后，有部分灯是关闭状态。问：这些关闭灯的编号是什么？

输入格式

一行，一个正整数 N，为灯的总量。

输出格式

一行，按顺序输出关闭灯的编号，编号与编号之间间隔一个空格。

解析

通过进一步分析可得：

1. 灯被操作次数规则：

   • 灯编号是一个正整数，被操作的次数等于该数的因子总数（包括自身）；
   • 非完全平方数因子总是偶数；完全平方数的因子数是奇数。

2. 灯最终状态：

   • 被操作偶数次，灯为关闭状态；
   • 被操作奇数次，灯为打开状态。

3. 解析完全平方数特性：

   • 对于每一个完全平方数，其因子数是奇数。例如，数 36 (= 6^2) 的因子为 1、2、3、6、9、18、36，共 9 个，是奇数。
   • 非完全平方数，例如 12，其因子为 1、2、3、4、6、12，共 6 个，是偶数。

因此，最终只需要找出 1 到 N 中的非完全平方数的编号。

---

💯实现代码对比：我的做法和老师的做法

我的代码实现

以下是我的代码：

#include <iostream>
using namespace std;const int N = 5000;
int arr[5000]; int main()
{int n = 0;cin >> n;for (int i = 1; i <= n; i++){arr[i] = 1;}if (n == 1 || n == 2 || n == 3)cout << 1 << endl;    else if (n > 3){for (int i = 1; i <= n; i++){arr[i] = 0;}for (int i = 2; i <= n; i += 2){arr[i] = 1;}for (int i = 3; i <= n; i++){for (int j = i; j <= n; j += i){if (arr[j] == 0)arr[j] = 1;elsearr[j] = 0;}}}for (int i = 1; i <= n; i++){if (arr[i] == 0)cout << i << " ";}return 0;
}

代码分析

1. 初始化数组：

   • 使用 arr[i] 表示灯的状态，1 表示关闭，0 表示打开。
   • 初始化为全关闭状态。

2. 状态切换逻辑：

   • 第一轮操作将所有灯置为打开。
   • 第二轮操作将所有偶数编号的灯关闭。
   • 从第三轮开始，依次对编号为当前轮数倍数的灯进行状态切换。

3. 最终输出：

   • 遍历数组，输出状态为关闭的灯编号。

优点

• 直观地模拟题目中每一轮的状态切换。
• 代码逻辑清晰易懂。

问题

• 时间复杂度较高，为 $O(N^2)$。
• 初始化和部分操作存在冗余。

---

老师的代码实现

以下是老师提供的代码：

#include <iostream>
#include <cstring>
using namespace std;const int N = 5010;
char arr[N]; // 下标为0的位置不使用int main()
{int n = 0;cin >> n;int i = 0;// 第一人将所有灯关闭，因为数组开始全是0，直接跳过操作for (i = 2; i <= n; i++){for (int j = i; j <= n; j++){if (j % i == 0){if (arr[j] == 1)arr[j] = 0;elsearr[j] = 1;}}}for (i = 1; i <= n; i++){if (arr[i] == 0)cout << i << " ";}cout << endl;return 0;
}

代码分析

1. 状态切换逻辑：

   • 外层循环控制第几轮操作；
   • 内层循环处理当前人的操作范围（倍数灯）。

2. 优化建议：

   • 条件 if (j % i == 0) 可以去掉，直接跳步循环 j += i。
   • 状态切换 if (arr[j] == 1) 部分可以替换为 arr[j] = !arr[j];。

---

💯优化思考

基于完全平方数的性质，可以直接优化代码，只需输出 1 到 $ \sqrt{N} $ 的平方数：

#include <iostream>
#include <cmath>
using namespace std;int main() {int n;cin >> n;for (int i = 1; i * i <= n; i++) {cout << i * i;if ((i + 1) * (i + 1) <= n) cout << " ";}return 0;
}

优点

1. 时间复杂度：

   • 原代码复杂度为 $O(N^2)$，优化后为 $O(\sqrt{N})$。

2. 空间复杂度：

   • 无需数组存储状态，优化为 $O(1)$。

---

💯概念解释

1. 因子与完全平方数：

   • 因子的总数决定了灯被操作的次数。
   • 非完全平方数因子总数为偶数，完全平方数因子总数为奇数。

2. 逻辑非运算：

   • 运算符 ! 表示取反：!0 = 1，!1 = 0。

---

💯小结

本文通过对 B2092 题目的多种实现方式进行分析与优化，从模拟实现到基于数学规律的优化，展示了从直观思考到高效解法的演进过程。希望读者通过本文的讲解，能够更加深入地理解问题的本质，并在实际编程中应用类似的优化思路。

---

---