笔试时间：2025年11月19日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：终端款型聚类识别

某部门需要对终端的漫游业务体验进行保障，不同的终端对于网络的配置要求不同。现在需要通过终端的网络流量等特征，识别该终端的型号是什么。

通过包间隔时长、连接持续时长、漫游前信号强度及漫游后信号强度4个特征，对终端的型号进行聚类。已知终端型号类别为K类，采用Kmeans算法进行聚类，识别终端类型，并输出各类型终端数量。

Kmeans算法说明：

• 初始化：k个初始质心
• 分配：将每个数据点分配到距离最近的质心，形成k个簇。其中距离需要根据数据类型选择上文给定的度量方式
• 更新：用簇内所有点的均值，重新计算每个簇的质心
• 迭代：重复步骤2和3，直到质心不再发生变化（质心移动值小于10^-8）或达到最大迭代次数

本题说明：

1. 给定数据集中，默认K类终端都存在，不存在某款型终端个数为0的场景；
2. 为消除不同特征权重问题，给出数据均已做好归一化处理，并保留两位小数；
3. 为消除随机性，初始k个质心统一采用给定数据集前k个点；
4. 距离函数定义为：d_{x,y} = √(Σ_{k=1}^4 (x_k - y_k)^2)

输入描述

输出描述

输出k款终端数量，从小到大排序。

样例输入

3 20 1000 0.11 0.79 0.68 0.97 1.0 0.8 0.13 0.33 0.27 0.02 0.5 0.46 0.83 0.29 0.23 0.75 0.97 0.08 0.84 0.55 0.29 0.71 0.17 0.83 0.03 0.6 0.88 0.28 0.24 0.26 0.82 0.03 0.96 0.12 0.82 0.36 0.13 0.12 0.86 0.44 0.23 0.7 0.35 0.06 0.42 0.49 0.67 0.84 0.8 0.49 0.47 0.7 0.68 0.03 0.11 0.07 0.77 0.19 0.95 0.44 0.25 0.12 0.98 0.04 0.7 0.11 0.53 0.3 0.73 0.67 0.46 0.96 0.11 0.31 0.91 0.57 0.43 0.61 0.13 0.1

样例输出

4 6 10

参考题解

核心思路：

1. 状态定义：将每个位置拆分为两个状态节点，分别表示到达该位置时的最后一步移动类型
2. K-means算法步骤： 初始化阶段：质心选择，直接取数据集的前K个点作为初始质心分配阶段：对于每个数据点，计算它与所有质心的欧氏距离，将点分配到距离最近的质心所在的簇更新阶段：重新计算每个簇的质心（簇内所有点的坐标平均值）终止条件：质心移动距离小于10^-8（收敛）或达到最大迭代次数n

Python：

import sys
import math

def main():
    k,m,n = map(int, sys.stdin.readline().split())
    points = []
    for _ in range(m):
        points.append(list(map(float, sys.stdin.readline().split())))
    
    centroids = [row[:] for row in points[:k]]
    final_counts = [0] * k
    
    for _ in range(n):
        cluster_sums = [[0.0] * 4 for _ in range(k)]
        cluster_counts = [0] * k
        
        for p in points:
            min_dist = float('inf')
            closest_idx = -1
            for i in range(k):
                c = centroids[i]
                diff0 = p[0] - c[0]
                diff1 = p[1] - c[1]
                diff2 = p[2] - c[2]
                diff3 = p[3] - c[3]
                dist = math.sqrt(diff0 * diff0 + diff1 * diff1 + diff2 * diff2 + diff3 * diff3)
                if dist < min_dist:
                    min_dist = dist
                    closest_idx = i
            
            cluster_counts[closest_idx] += 1
            cluster_sums[closest_idx][0] += p[0]
            cluster_sums[closest_idx][1] += p[1]
            cluster_sums[closest_idx][2] += p[2]
            cluster_sums[closest_idx][3] += p[3]
        
        new_centroids = []
        ma