2025-9-huawei

编程

编程题 第21/22题

21、基于决策树的无线状态预测 通过分析基站的关键性能指标（如信号强度、干扰水平、用户数量等），可以预测网络是否处于正常状态（标签0）或劣化状态（标签1）。决策树算法因其直观的判断逻辑和快速的响应能力，被广泛应用于无线网络智能运维场景。 给定一组基站特征训练数据和对应的网络质量标签，请实现一个基于信息增益的决策树分类器，用于判断网络质量是否劣化。信息熵的定义为： $H(S) = -\sum_{i \in S} p_i * \log_2(p_i)$ 信息增益 = 划分前熵 - 划分后条件熵。 特殊情况处理：

• 当多个特征对应的信息增益相同时，优先选择索引较小的特征进行样本划分。
• 当没有特征对样本进一步划分时，该节点返回样本数较多的标签（若标签0和标签1数量一致，则默认返回标签0） 解答要求 时间限制: C/C++ 1000ms，其他语言：2000ms 内存限制: C/C++ 500MB，其他语言：1000MB 输入 第一行：整数n（1 ≤ n ≤ 1000），表示训练样本数量，整数m（2 ≤ m ≤ 10）表示特征数 接下来n行：每行包含m+1个整数，前m个是特征1-特征m对应的特征值(特征取值为0或1)，最后一个是要预测的类别标签(0或1) 下一行：整数q（1 ≤ q ≤ 100），表示查询样本数量 接下来q行：每行包含m个整数，表示查询样本的特征值(0或1) 输出 输出q行，每行一个整数(0或1)，表示对应查询样本的预测类别

样例1 复制 输入：10 3 1 0 1 1 1 0 0 0 1 1 1 1 1 1 0 1 0 0 1 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 1 1 0 1 1 1 3 1 0 1 1 0 0 0 1 0 输出：1 0 1 解释：数据包含10个样本，每个样本包含三个特征。基于训练数据，可以构建出如下决策树：

1. [特征2]
2. / \
4. [特征1] [特征1]
5. / \ / \
7. 标签=0 [特征2] [特征2] 标签=1
8. / \ / \
10. 标签=0 标签=1 标签=0 标签=1

样例2 复制 输入：6 2 1 1 1 0 0 0 1 0 1 0 1 0 1 1 1 0 0 0 2 1 1 0 0 输出：1 0 解释：训练数据包含6个样本，每个样本包含两个特征（特征1和特征2），构建得到的决策树如下：

1. [特征1]
2. / \
4. 标签=0 标签=1 原始值信息熵：-1/2 log(1/2) -1/2 log(1/2) = 1 使用特征1进行划分后：信息熵=1 log(1) = 0，增益为1 使用特征2进行划分后：信息熵=0.5 × 0.9183 + 0.5 × 0.9183 = 0.9183，增益为0.0817

import math

class Node:
    def __init__(self, feature=None, label=None):
        self.feature = feature  # 划分特征索引
        self.label = label      # 叶子节点标签
        self.children = {}      # 子树 {0: Node, 1: Node}

def entropy(labels):
    n = len(labels)
    if n == 0:
        return 0
    c0 = labels.count(0)
    c1 = labels.count(1)
    res = 0.0
    for c in [c0, c1]:
        if c > 0:
            p = c / n
            res -= p * math.log2(p)
    return res

def majority_label(labels):
    c0 = labels.count(0)
    c1 = labels.count(1)
    if c1 > c0:
        return 1
    else:
        return 0  # 平局返回0

def best_feature(data, labels, features):
    base_entropy = entropy(labels)
    best_gain = -1
    best_f = None
    n = len(data)
    for f in features:
        # 按特征f划分
        subset0 = [labels[i] for i in range(n) if data[i][f] == 0]
        subset1 = [labels[i] for i in range(n) if data[i][f] == 1]
        new_entropy = (len(subset0)/n)*entropy(subset0) + (len(subset1)/n)*entropy(subset1)
        gain = base_entropy - new_entropy
        if gain > best_gain + 1e-12:  # 更优
            best_gain = gain
            best_f = f
        elif abs(gain - best_gain) <= 1e-12 and best_f is not None and f < best_f:
            best_f = f
    return best_f, best_gain

def build_tree(data, labels, features):
    # 如果全是同一类
    if all(l == labels[0] for l in labels):
        return Node(label=labels[0])
    # 如果没有特征可分
    if not features:
        return Node(label=majority_label(labels))

    f, gain = best_feature(data, labels, features)
    if f is None or gain <= 1e-12:
        return Node(label=majority_label(labels))

    node = Node(feature=f)
    # 递归建树
    for v in [0, 1]:
        sub_data = [data[i] for i in range(len(data)) if data[i][f] == v]
        sub_labels = [labels[i] for i in range(len(data)) if data[i][f] == v]
        if not sub_data:
            node.children[v] = Node(label=majority_label(labels))
        else:
            new_features = [x for x in features if x != f]
            node.children[v] = build_tree(sub_data, sub_labels, new_features)
    return node

def predict(tree, sample):
    while tree.label is None:
        f = tree.feature
        v = sample[f]
        if v in tree.children:
            tree = tree.children[v]
        else:
            # 万一缺失，返回0
            return 0
    return tree.label

def main():
    n, m = map(int, input().split())
    data = []
    labels = []
    for _ in range(n):
        arr = list(map(int, input().split()))
        data.append(arr[:-1])
        labels.append(arr[-1])

    features = list(range(m))
    tree = build_tree(data, labels, features)

    q = int(input())
    for _ in range(q):
        sample = list(map(int, input().split()))
        print(predict(tree, sample))

if __name__ == "__main__":
    main()

编程 第22题

【华为校园招聘 AI】 编程题 第22/22题 22、无线网络优化中的基站聚类分析 【问题背景】在无线网络优化中，基站的位置分布直接影响信号覆盖质量。密集区域的基站可能造成资源浪费，而稀疏区域则会出现信号覆盖不足。 【任务要求】给定n个基站的二维坐标，使用K-Means算法将其划分为k个簇，再通过计算每个簇的轮廓系数（Silhouette Coefficient），识别信号覆盖最差的簇（轮廓系数最低），并在该簇中心新增基站以优化信号覆盖。 【算法过程】 1、使用前k个基站作为初始聚类中心，执行K-Means算法。K-means的结束条件为：最大迭代次数100或者所有簇中心点移动距离都不大于1e-6。 2、计算每个簇的轮廓系数（簇内所有点的轮廓系数平均值）。 3、找出轮廓系数最低的簇。 4、输出该簇的中心坐标（保留两位小数），作为新增基站的位置。 K-Means和轮廓系数的详细介绍见“提示”。 解答要求 时间限制: C/C++ 1000ms，其他语言：2000ms 内存限制: C/C++ 500MB，其他语言：1000MB 输入 第一行：基站数量n和聚类簇数k，之间以空格分开，其中n取值范围为[1,500]，k取值范围为[1,120]。 接下来n行：每行两个整数，表示基站的坐标x和y，其中x取值范围为[0,5000]，y取值范围为[0,3000]。 输出 新增基站的坐标：x,y（输出结果四舍五入保留两位小数，采用RoundingMode.HALF_EVEN）

样例1 输入：6 2 0 0 1 1 2 2 10 10 11 11 5 5 输出：8.67,8.67 解释：簇划分结果：簇0: [(0,0),(1,1),(2,2)]，中心(1,1)；簇1: [(5,5),(10,10),(11,11)]，中心(8.67,8.67) 轮廓系数：簇0的轮廓系数：0.82；簇1轮廓系数：0.35 答案：输出簇1中的中心点：(8.67,8.67)

样例2 输入：4 2 0 0 0 1 1 0 10 10 输出：0.33,0.33 解释：簇划分结果：簇0: [(0, 0), (0, 1), (1, 0)]，中心点：(0.33, 0.33)；簇1: [(10, 10)]，中心点：(10, 10) 轮廓系数：簇0的轮廓系数：0.92；簇1的轮廓系数：1.0 答案：输出簇0的中心点：0.33, 0.33 簇0: [A(0, 0), B(0, 1), C(1, 0)]； 簇1: [(10, 10)] 簇0的轮廓系数计算： 计算点 A(0, 0): 1、A同簇平均距离为1：A到B(0,1)距离1，A到C(1,0)距离1 2、A到簇1平均距离为14.142：A到D(10, 10)距离14.142 3、A的轮廓系数s(A)：0.929 计算点 B(0, 1): 1、B同簇平均距离为1.207：B到A(0, 0)距离1，B到C(1, 0)距离1.414 2、B到簇1平均距离为13.454：B到D(10, 10)距离13.454 3、B的轮廓系数s(B)：0.910 计算点 C(1, 0): 1、C同簇平均距离为1.207：C到A(0, 0)距离1，C到B(0, 1)距离1.414 2、C到簇1平均距离为13.454：C到D(10, 10)距离13.454 3、C的轮廓系数s(C)：0.910 簇0轮廓系数：(s(A)+s(b)+s(b))/3 = 2.749/3=0.92

提示 K-means 的算法步骤为: 1、选择初始化的前 k 个样本作为初始聚类中心 2、针对数据集中每个样本 $x_i$ 计算它到 k 个聚类中心的距离并将其分到距离最小的聚类中心所对应的类中 3、针对每个类别 $a_j$，重新计算它的聚类中心 $a_j = \frac{1}{|c_i|} \sum_{x \in c_i} x$（即属于该类的所有样本的质心）； 4、重复上面 2 3 两步操作，直到达到某个中止条件（迭代次数、最小误差变化等） 轮廓系数(Silhouette Coefficient Index)： 1、对于一个数据点 $i$，先计算它和簇内其他数据点的平均距离 $a_i$ 2、然后计算该点与不包含该点所在簇的其他簇内数据点的平均距离 $b_i$（簇间相似度），选取其中距离最小的那个作为 i 的簇间平均距离。 3、最后，计算数据点 $i$ 的轮廓系数：$s_i = \frac{b_i - a_i}{\max(a_i, b_i)}$ 将所有数据点的轮廓系数取平均值，即得到聚类算法的整体轮廓系数。若某个数据点所在簇的数据点数量小于等于1，则该点的轮廓系数为0。 RoundingMode.HALF_EVEN： 1、python默认的HALF_EVEN模式，其他语言按照如下规则处理: HALF_EVEN也称为“银行家舍入”或“向偶数舍入”。这种模式下，当小数部分恰好为0.5时，round() 会将结果舍入到最近的偶数 round(2.55, 1) 会返回2.6（因为6 是偶数） round(2.65, 1) 会返回2.6（因为6 是偶数） round(2.75, 1) 会返回2.8（因为8 是偶数） round(1.15, 1) 会返回1.2（因为2 是偶数）

调库实现：

from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_samples
import numpy as np

def main():
    n, k = map(int, input().split())
    points = [list(map(float, input().split())) for _ in range(n)]
    X = np.array(points)

    # 使用前k个点作为初始中心
    init_centers = X[:k]

    # KMeans 聚类
    kmeans = KMeans(
        n_clusters=k,
        init=init_centers,
        n_init=1,
        max_iter=100,
        tol=1e-6,
        random_state=0
    )
    labels = kmeans.fit_predict(X)
    centers = kmeans.cluster_centers_

    # 特殊情况：只有一个簇
    if k == 1 or n == 1:
        worst_idx = 0
    else:
        s = silhouette_samples(X, labels, metric="euclidean")
        cluster_scores = []
        for i in range(k):
            cluster_points = s[labels == i]
            if len(cluster_points) <= 1:
                # 按题意：单点簇不参与最差簇选择
                cluster_scores.append(float("inf"))
            else:
                cluster_scores.append(cluster_points.mean())
        worst_idx = int(np.argmin(cluster_scores))

    cx, cy = centers[worst_idx]
    print(f"{round(cx,2):.2f},{round(cy,2):.2f}")

if __name__ == "__main__":
    main()

GPT手写(只过了小部分用例)

import math
import numpy as np

def dist(p1, p2):
    return math.hypot(p1[0] - p2[0], p1[1] - p2[1])

def kmeans(X, k, max_iter=100, tol=1e-6):
    """自己实现的KMeans，返回 labels, centers"""
    n = len(X)
    centers = X[:k].copy()
    labels = [0] * n

    for _ in range(max_iter):
        # 分配
        for i, p in enumerate(X):
            labels[i] = min(range(k), key=lambda j: dist(p, centers[j]))
        # 更新
        new_centers = []
        for j in range(k):
            cluster_points = [X[i] for i in range(n) if labels[i] == j]
            if cluster_points:
                cx = sum(p[0] for p in cluster_points) / len(cluster_points)
                cy = sum(p[1] for p in cluster_points) / len(cluster_points)
                new_centers.append((cx, cy))
            else:
                new_centers.append((0.0, 0.0))
        # 判断收敛
        shift = max(dist(centers[j], new_centers[j]) for j in range(k))
        centers = new_centers
        if shift <= tol:
            break
    return labels, centers

def silhouette_samples(X, labels):
    """自己实现 silhouette，返回每个点的轮廓系数"""
    n = len(X)
    k = max(labels) + 1
    result = [0.0] * n

    clusters = [[] for _ in range(k)]
    for i, lab in enumerate(labels):
        clusters[lab].append(i)

    for i in range(n):
        p = X[i]
        lab = labels[i]
        same_cluster = clusters[lab]
        if len(same_cluster) <= 1:
            result[i] = 0.0
            continue

        # a_i: 簇内平均距离
        a_i = sum(dist(p, X[j]) for j in same_cluster if j != i) / (len(same_cluster) - 1)

        # b_i: 最近其他簇的平均距离
        b_i = math.inf
        for other_lab in range(k):
            if other_lab == lab or not clusters[other_lab]:
                continue
            avg_dist = sum(dist(p, X[j]) for j in clusters[other_lab]) / len(clusters[other_lab])
            b_i = min(b_i, avg_dist)

        if b_i == math.inf:
            result[i] = 0.0
        else:
            result[i] = (b_i - a_i) / max(a_i, b_i) if max(a_i, b_i) > 0 else 0.0
    return result

def main():
    n, k = map(int, input().split())
    points = [tuple(map(float, input().split())) for _ in range(n)]
    X = points

    labels, centers = kmeans(X, k)

    if k == 1 or n == 1:
        worst_idx = 0
    else:
        s = silhouette_samples(X, labels)
        cluster_scores = []
        for j in range(k):
            cluster_points = [s[i] for i in range(n) if labels[i] == j]
            if len(cluster_points) <= 1:
                cluster_scores.append(float("inf"))  # 单点簇不参与
            else:
                cluster_scores.append(sum(cluster_points) / len(cluster_points))
        worst_idx = int(np.argmin(cluster_scores))

    cx, cy = centers[worst_idx]
    print(f"{round(cx,2):.2f},{round(cy,2):.2f}")

if __name__ == "__main__":
    main()