N*M棋盘矩形数量计算C++实现及推导详解

好的，这是一个非常经典的数学组合问题。我们来详细分析和实现它。 ## 📌 问题分析：棋盘中的矩形个数 在一个 `N * M` 的网格中，**矩形** 由四条边围成，即两条水平线和两条竖直线。 - **水平线**的选取：一共有 `N + 1` 条水平线（包括边界），我们需要从中选出 2 条作为矩形的上下边。 - **竖直线**的选取：一共有 `M + 1` 条竖直线（包括边界），我们需要从中选出 2 条作为矩形的左右边。 矩形的总数等于： \[ \text{矩形总数} = C(N+1, 2) \times C(M+1, 2) \] 其中 \( C(n, 2) = \frac{n \times (n-1)}{2} \)。 ### ✅ 公式推导 \[ \text{矩形的个数} = \frac{N \times (N+1)}{2} \times \frac{M \times (M+1)}{2} \] **注意：这个公式计算的是所有非退化的矩形（即面积不为0），没有包含正方形与矩形的区分，因为正方形本身也是矩形的一种特殊情况。** --- ## 💻 C++ 代码实现 ```cpp #include <iostream> using namespace std; int main() { int N, M; cin >> N >> M; // 计算组合数 C(N+1, 2) 和 C(M+1, 2) long long rectCount = (long long)N * (N + 1) / 2 * M * (M + 1) / 2; cout << rectCount << endl; return 0; } ``` ### 🔍 代码说明 - 使用 `long long` 类型防止整数溢出（N和M最大为100，乘积最大约为 `100*101/2 * 100*101/2 ≈ 25502500`，在 `int` 范围内，但为了更安全，使用 `long long`）。 - 先计算组合数 `N*(N+1)/2` 和 `M*(M+1)/2`，再相乘。 - 输入输出使用 `cin` / `cout`，简单高效。 --- ## 🧩 示例验证 输入： ``` 3 2 ``` 计算： - 水平线选法：\( C(4,2) = \frac{4\times3}{2} = 6 \) - 竖直线选法：\( C(3,2) = \frac{3\times2}{2} = 3 \) - 矩形总数：\( 6 \times 3 = 18 \) 输出： ``` 18 ``` 与题目示例一致。 --- ## ⚠️ 常见陷阱与注意事项 1. **区分“正方形”与“矩形”** 本题只要求矩形个数，包含正方形（正方形是特殊的矩形）。若题目要求“非正方形的矩形”，则需要减去正方形数量。 2. **数据类型选择** 当N和M接近100时，结果最大约 2500 万，32位 `int` 够用，但建议用 `long long` 以避免未来扩展时的溢出风险。 3. **边界条件** 当 N=1 或 M=1 时，公式仍适用： - N=1, M=1 → 矩形数量 = \( C(2,2) \times C(2,2) = 1 \times 1 = 1 \) - N=1, M=100 → 矩形数量 = \( 1 \times \frac{100\times101}{2} = 5050 \) --- ## 🚀 进阶思考：如果要求“正方形”个数？ 若想同时计算**正方形的个数**，公式为： \[ 正方形个数 = \sum_{k=1}^{\min(N,M)} (N - k + 1) \times (M - k + 1) \] 结合矩形总数，可以轻松求出非正方形的矩形数量。 --- ## 🎓 开发建议 - **使用数学公式简化问题**：很多棋盘/网格计数问题都可以转化为组合数学问题，避免暴力枚举。 - **注意输入格式**：一行两个数，可以用 `cin >> N >> M` 或 `scanf`。 - **考虑可读性**：代码中注释清楚公式来源，方便日后维护。 <br> ######[AI写代码神器 | 966点数解答 | 2026-06-06 07:39:51]