C++实现棋盘正方形与长方形计数方法及数学原理

好的，这是一个经典的棋盘格计数问题。下面我会用C++为你详细解答，包括数学原理、代码实现以及一些开发上的建议。 ## 🎯 问题分析 对于一个 `N × M` 的棋盘格（格子为单位方格），我们需要计算： 1. **正方形的总数**：所有可能的边长从 1 到 `min(N, M)` 的正方形个数。 2. **长方形的总数（不包括正方形）**：所有可能的矩形个数减去正方形个数。 **数学公式**： - 矩形总数 = 所有可能的 `(长, 宽)` 组合数 公式：`C(N+1, 2) * C(M+1, 2)` 解释：在 N 行中选择两行作为上下边界，在 M 列中选择两列作为左右边界。 - 正方形总数 = 对边长 `k` 从 1 到 `min(N, M)`，`(N - k + 1) * (M - k + 1)` 求和。 - 长方形（不含正方形）总数 = 矩形总数 - 正方形总数。 ## 💻 C++ 代码实现 ```cpp #include <iostream> using namespace std; int main() { int N, M; cout << "请输入棋盘的行数 N 和列数 M (1<=N,M<=100): "; cin >> N >> M; // 1. 计算正方形总数 long long squares = 0; int minDim = min(N, M); for (int k = 1; k <= minDim; ++k) { squares += (long long)(N - k + 1) * (M - k + 1); } // 2. 计算矩形总数（所有长方形+正方形） long long totalRectangles = (long long)N * (N + 1) / 2 * M * (M + 1) / 2; // 3. 计算长方形（不包括正方形） long long rectangles = totalRectangles - squares; cout << "正方形个数: " << squares << endl; cout << "长方形个数（不包括正方形）: " << rectangles << endl; return 0; } ``` ### 🧩 关键点解释 - **`C(N+1, 2)` 公式**： 在 N 行中，选择两行（包括重复选择？不，这里是选择两条不同的水平线）。 实际上 `C(N+1, 2) = N*(N+1)/2`，表示所有可能的上下边界选择方式。 因为矩形的上下边界可以是 0 到 N 的任意两条线（包括边界线），所以是 `N+1` 条线中选 2 条，不重复。 - **`long long` 类型**： N,M 最大 100，矩形总数最大为 `100*101/2 * 100*101/2 = 5050 * 5050 ≈ 25,502,500`，仍在 `int` 范围内，但为了代码健壮性，特别是当题目要求更大范围时，使用 `long long` 更安全。 ## 🛠️ 分步执行流程 1. **输入**：读取 N 和 M。 2. **计算正方形**： - 遍历边长 k = 1 到 min(N, M) - 每个边长对应的正方形数量 = `(N - k + 1) * (M - k + 1)` - 累加得到总正方形数。 3. **计算所有矩形**： - 使用组合公式：`N*(N+1)/2 * M*(M+1)/2` 4. **得到长方形数**：总矩形 - 正方形。 5. **输出结果**。 ## 🚧 常见陷阱与进阶建议 1. **数据类型溢出**： 尽管 N,M ≤ 100 结果较小，但若题目增大范围，`int` 可能溢出。建议始终使用 `long long` 或 `unsigned long long`。 2. **公式理解错误**： 不要把矩形总数误认为是 `N*M` 或 `N*(N+1)*M*(M+1)/4`（分子少乘了？不对，上面公式正确）。 验证：1×1 棋盘，正方形=1，矩形=1，长方形=0。公式：`1*2/2 * 1*2/2 = 1`，正确。 3. **性能优化**： 对于 N,M 最大 100，O(min(N,M)) 复杂度完全可行。如果 N,M 非常大（比如 10^6），则需要用公式直接计算正方形总和： `squares = sum_{k=1}^{min(N,M)} (N-k+1)*(M-k+1)` 这个可以推导出封闭形式（但本题无需）。 ## 📚 学习资源推荐 - **组合数学基础**：理解 `C(n,2)` 的来源，推荐《具体数学》或 LeetCode 相关题解。 - **C++ 数据类型**：学习 `long long`、`int64_t` 等类型的使用场景，推荐 [cppreference.com](https://en.cppreference.com/w/)。 ## 💡 开发建议 - **先做数学推导，再写代码**：此类计数问题，数学公式比模拟更高效且不易出错。 - **添加边界测试**：例如 N=1, M=1；N=1, M=100；N=100, M=100，确认结果正确。 - **使用 constexpr 或宏定义边界**：提高代码可维护性。 **示例运行**： ``` 请输入棋盘的行数 N 和列数 M (1<=N,M<=100): 2 3 正方形个数: 8 长方形个数（不包括正方形）: 10 ``` 验证：2×3 棋盘，矩形总数 = `2*3/2 * 3*4/2 = 3*6 = 18`，正方形数 = 2×2有2个，1×1有6个，共8个，长方形=18-8=10，正确。 ######[AI写代码神器 | 1350点数解答 | 2026-06-06 08:10:15]