棋盘正方形与长方形数量计算详解

好的，这是一个非常经典的组合数学问题。我们来一步步分析并给出完整的解决方案。 ## 📐 问题分析 我们有一个 **N × M** 的棋盘（N行，M列），每个格子是 1×1 的小方格。需要计算： 1. **所有正方形的数量**（包括1×1, 2×2, ..., min(N,M)×min(N,M)）。 2. **所有长方形的数量**（不包括正方形，即长宽不相等，或长宽相等但这里我们默认排除所有正方形）。 --- ## 🧮 数学公式推导 ### 1️⃣ 计算所有矩形的总数（包括正方形） 在一个 N×M 的网格中，**所有矩形（包括正方形）的数量** 计算公式为： \[ \text{矩形总数} = \frac{N(N+1)}{2} \times \frac{M(M+1)}{2} \] **解释**： - 水平方向：选择两条不同的竖线，有 \(C(N+1, 2) = \frac{N(N+1)}{2}\) 种选法。 - 垂直方向：选择两条不同的横线，有 \(C(M+1, 2) = \frac{M(M+1)}{2}\) 种选法。 - 组合起来就是所有可能的矩形。 ### 2️⃣ 计算所有正方形的数量 正方形的边长 k 可以从 1 到 min(N, M)。对于每个边长 k： - 水平方向有 \(N - k + 1\) 个起始位置。 - 垂直方向有 \(M - k + 1\) 个起始位置。 所以总正方形数为： \[ \text{正方形总数} = \sum_{k=1}^{\min(N, M)} (N - k + 1) \times (M - k + 1) \] ### 3️⃣ 计算长方形的数量（不包括正方形） 直接用 **矩形总数 - 正方形总数** 即可： \[ \text{长方形数} = \text{矩形总数} - \text{正方形总数} \] --- ## 💻 代码实现（Python） ```python def count_shapes(N, M): # 计算所有矩形总数 total_rectangles = (N * (N + 1) // 2) * (M * (M + 1) // 2) # 计算所有正方形总数 total_squares = 0 min_side = min(N, M) for k in range(1, min_side + 1): total_squares += (N - k + 1) * (M - k + 1) # 长方形数 = 矩形总数 - 正方形数 total_rectangles_not_square = total_rectangles - total_squares return total_squares, total_rectangles_not_square # 示例 N, M = 3, 2 squares, rects = count_shapes(N, M) print(f"正方形数量: {squares}") print(f"长方形数量（不包括正方形）: {rects}") ``` **输出**： ``` 正方形数量: 8 长方形数量（不包括正方形）: 10 ``` --- ## 🧠 详细解释 | 元素 | 公式说明 | |------------------|--------------------------------------------------------------------------| | 矩形总数 | 选择两条水平线和两条垂直线的组合数。 | | 正方形总数 | 对每个可能的边长 k，累加所有可能的左上角位置数。 | | 长方形数 | 从矩形总数中减去正方形数，确保不重复计算。 | --- ## ⚡ 进阶优化建议 - **性能**：当 N, M 最大为 100 时，直接循环计算即可，复杂度 O(min(N,M))，完全可接受。若 N, M 更大（如 10^6），可使用 **等差数列求和公式** 直接计算正方形数，避免循环。 - **边界情况**： - 当 N=1 或 M=1 时，所有矩形都是 1×k 或 k×1 的形状，正方形的数量等于 min(N, M)。 - 使用 `//` 整数除法避免浮点误差。 - **通用性**：可以扩展为计算任意非正方形矩形（包括长宽相等的长方形？这里已明确排除）。 --- ## 🔍 常见陷阱 1. **忘记排除正方形**：直接计算长方形时容易忽略“不包括正方形”的条件。 2. **公式混淆**：长方形总数公式不要和排列组合混淆，这里是组合数而非排列数。 3. **整数溢出**：N, M=100 时结果在合理范围内，但如果 N, M 很大（如 10^5），需使用 Python 的大整数支持或改用数学库。 --- ## 📚 学习资源推荐 - **组合数学基础**：《具体数学》（Concrete Mathematics）—— 格点计数章节 - **在线练习**：洛谷 P2241【统计方形】、LeetCode 相关问题 - **应用场景**：棋盘问题、图像处理中矩形检测、UI布局计算等 --- ## 💡 开发建议 1. **先验证小规模示例**：手动计算 N=2, M=2 的结果，对照代码输出。 2. **使用断言测试**：编写测试用例确保正确性。 3. **抽象成函数**：将计算逻辑封装，便于复用和单元测试。 4. **文档注释**：在代码中写明公式来源，方便他人理解。 --- ######[AI写代码神器 | 1189点数解答 | 2026-06-06 08:07:47]