蓝桥杯省赛真题C++B组2024-握手问题

一、题目

【问题描述】

  小蓝组织了一场算法交流会议，总共有 50 人参加了本次会议。在会议上，大家进行了握手交流。按照惯例他们每个人都要与除自己以外的其他所有人进行一次握手(且仅有一次)。但有 7 个人，这 7 人彼此之间没有进行握手(但这 7 人与除这 7 人以外的所有人进行了握手)。请问这些人之间一共进行了多少次握手?
注意 A 和 B 握手的同时也意味着 B 和 A 握手了，所以算作是一次握手。              

二、思路

方法一：

        对于这种题，我一般是来找规律，我们从最简单的开始，有2个人的话，我们需要握手1次，3个人我们需要握手3次，四个人需要握手6次，5个人需要握手10次，6个人需要15次

人数	握手次数
2	1
3	3=2+1
4	6=3+2+1
5	10=4+3+2+1
6	15=5+4+3+2+1

        我们不难找到一些规律，握手次数是  人数-1 开始向下逐个相加到1，3个人就是3-1向下开始相加（2+1）

        但是题中说7个人是不相互握手的，我们假设3个人不握手，看上面的表，3个人将不握手3次（2+1），7个人将不握手6+5+4+3+2+1=21次

        50个人握手49+48+47+...+2+1=1225次

        又7个人不握手，1225-7=1204次

方法二：（代码）

三、代码

#include<iostream>
using namespace std;
int main(){
//	总握手次数计算：如果没有任何限制，50人两两握手的次数为组合数C(50, 2)。
//排除7人之间的握手次数：这7人之间没有握手，因此需要从总次数中减去C(7, 2)。int  total = 50;int subtract = 7;int  total_hands = total * (total - 1)/2;int subtract_hands = subtract * (subtract - 1)/2;cout<< total_hands-subtract_hands << endl;return 0;
} 

四、反思

组合

• 每次握手是 无序的（A 和 B 握手与 B 和 A 握手是同一件事）。

• 组合数 C(n,2) 正是用来计算 无序且不重复的两两配对 的数量，

排列数 A(n, m) 与组合数 C(n, m) 的求法_排列组合-CSDN博客