棋盘正方形与长方形计数 C++ 实现及数学推导

好的，这是一个典型的数学与编程结合的问题。我们一步步来分析，并给出完整的 C++ 解决方案。 ## 🧩 问题分析 对于一个 `N x M` 的棋盘（N 行，M 列），我们需要计算： 1. **正方形的个数** 2. **长方形的个数（不包括正方形）** ### 🔢 数学公式推导 #### 📐 正方形个数 - 边长为 1 的正方形：`N * M` - 边长为 2 的正方形：`(N-1) * (M-1)` - 边长为 k 的正方形：`(N-k+1) * (M-k+1)`，其中 `k` 从 1 到 `min(N, M)` **公式**： ``` 正方形总数 = ∑_{k=1}^{min(N,M)} (N - k + 1) * (M - k + 1) ``` #### 📏 长方形（含正方形）总数 - 从 N 行中选择 2 条横线：`C(N+1, 2)` - 从 M 列中选择 2 条竖线：`C(M+1, 2)` - 总矩形数 = `C(N+1, 2) * C(M+1, 2)` **公式**： ``` 总矩形数 = N * (N+1) / 2 * M * (M+1) / 2 ``` #### 🔲 长方形（不含正方形）个数 ``` 长方形数 = 总矩形数 - 正方形数 ``` --- ## 💻 C++ 代码实现 ```cpp #include <iostream> using namespace std; int main() { int N, M; char comma; // 用于读取逗号 cin >> N >> comma >> M; // 计算正方形个数 int squares = 0; int minSide = min(N, M); for (int k = 1; k <= minSide; ++k) { squares += (N - k + 1) * (M - k + 1); } // 计算总矩形数（含正方形） long long totalRectangles = (long long)N * (N + 1) / 2 * M * (M + 1) / 2; // 长方形 = 总矩形 - 正方形 long long rectangles = totalRectangles - squares; // 输出结果 cout << squares << "," << rectangles << endl; return 0; } ``` --- ## 🧪 示例验证 输入： ``` 3,2 ``` 运行过程： - 正方形： 边长1: `3*2 = 6` 边长2: `2*1 = 2` 总数 = 6 + 2 = **8** - 总矩形：`C(4,2) * C(3,2) = 6 * 3 = 18` - 长方形 = 18 - 8 = **10** 输出： ``` 8,10 ``` 与题目一致 ✅ --- ## 🛠️ 关键点说明 | 概念 | 说明 | |------|------| | `min(N, M)` | 最大可能的正方形边长 | | `(long long)` 类型转换 | 防止 `N*(N+1)/2*M*(M+1)/2` 溢出，因为 `N, M` 最大为 100，乘积可达约 2500 万以上 | | 读入逗号 | 使用 `cin >> N >> comma >> M` 可以直接处理输入中的逗号分隔符 | --- ## ⚠️ 常见陷阱与注意事项 1. **整数溢出** 虽然 `N, M ≤ 100`，但 `N*(N+1)/2*M*(M+1)/2` 最大值为 `5050 * 5050 ≈ 25,502,500`，在 `int` 范围内。但为了代码健壮性，建议使用 `long long`。 2. **逗号输入处理** 输入格式为 `N,M`，中间没有空格。直接用 `cin >> N >> M` 会导致错误。需要用一个字符变量吞掉逗号。 3. **公式选择** 使用组合公式计算总矩形比双重循环更高效（O(1) 复杂度 vs O(N*M)）。 --- ## 📚 开发建议 - **代码复用性**：可将计算正方形和长方形的逻辑封装成函数，便于测试和复用。 - **输入校验**：可增加对输入格式、范围（1 ≤ N, M ≤ 100）的校验。 - **单元测试**：建议为不同边界情况（如 N=1, M=1 或 N=100, M=100）编写测试用例。 --- ## 🔗 学习资源推荐 - [组合数学基础 - 矩形计数问题](https://en.wikipedia.org/wiki/Combination) - [C++ 标准输入输出](https://en.cppreference.com/w/cpp/io/basic_istream) - 书籍：《算法竞赛入门经典》—— 刘汝佳（包含大量棋盘类计数问题） --- ######[AI写代码神器 | 1138点数解答 | 2026-06-06 07:56:17]