蓝桥杯握手问题：组合数学与算法优化解析

1. 蓝桥杯握手问题解析

这道蓝桥杯真题看似简单，实则蕴含了组合数学的精妙思想。我们先来看题目描述：在一个50人的聚会中，有7个人彼此之间不握手，其余43个人之间正常握手。要求计算实际发生的握手总次数。

1.1 问题建模与组合数学基础

握手问题本质上是图论中的完全图边数计算问题。在组合数学中，n个人两两握手的次数就是组合数C(n,2)，也就是从n个人中选取2个人的组合数。其计算公式为：

code复制C(n,2) = n*(n-1)/2

这个公式的推导很简单：第一个人可以和剩下的n-1个人握手，第二个人可以和剩下的n-2个人握手（已经和第一个人握过了），依此类推，最后一个人不需要再主动握手。所以总次数就是：

code复制(n-1) + (n-2) + ... + 1 + 0 = n*(n-1)/2

1.2 原题解法分析

题目给出的解法非常巧妙：

cpp复制#include<iostream>
using namespace std;
int main(){
    int sum=0;
    for(int i=0 ; i<50 ; i++){
        sum += i;
    }
    int num=0;
    for(int i=0 ; i<7 ; i++){
        num += i;
    }
    int result;
    result = sum-num;
    cout<<result;
    return 0; 
}

这段代码的计算逻辑是：

1. 先计算50个人完全互相握手的次数（1225次）
2. 再计算7个人互相握手的次数（21次）
3. 最后用总数减去7人内部的握手次数（1225-21=1204）

这种"全集减去子集"的思路在组合数学中非常常见，也是解决这类问题的有效方法。

1.3 为什么不能简单相加

很多初学者可能会想：既然有43个人互相握手，为什么不直接计算1+2+...+42呢？这是因为：

1. 43个人不仅要彼此握手，还要和那7个人握手
2. 7个人虽然彼此不握手，但都要和43个人握手
3. 所以握手分为两部分：
   • 43人内部的握手：C(43,2)=903
   • 43人与7人之间的握手：43×7=301
   • 总次数：903+301=1204

这与原解法结果一致，验证了其正确性。

2. 算法优化与数学推导

2.1 循环计算的数学优化

原代码使用了两个循环来计算累加和：

cpp复制for(int i=0 ; i<50 ; i++){ sum += i; }  // 计算0+1+...+49
for(int i=0 ; i<7 ; i++){ num += i; }   // 计算0+1+...+6

这其实可以用等差数列求和公式来优化：

code复制sum = n*(n-1)/2

所以可以改写为：

cpp复制int sum = 49*50/2;    // 1225
int num = 6*7/2;      // 21
int result = sum - num; // 1204

这样的优化：

1. 时间复杂度从O(n)降到O(1)
2. 避免了循环带来的性能开销
3. 代码更简洁，可读性更好

2.2 组合数公