华为校招&实习机试在线OJ刷题系统 ｜ 在线OJ注册使用教程

目录

题目

思路

Code

题目

题目内容：

信息熵表示数据集的不确定性：H(S) = − Σᵢ₌₁ᶜ pᵢ·log₂(pᵢ)。

数据集 S 中有 c 个类别，pᵢ 为第 i 类的出现频率。

按特征 A 划分后，不确定性减少的量是信息增益：IG(S, A) = H(S) − Σ_{v∈A} (|Sᵥ| / |S|)·H(Sᵥ)，其中 Sᵥ 是 A 取值为 v 的样本子集。信息增益越大，越适合用该特征分裂。

请实现按信息增益建树的决策树分类器。每条训练样本形如 [feature_1, feature_2, ..., feature_m, label]，特征与类别标签都用整数表示。特征从左到右的下标为 0, 1, …, m−1。

建树从根结点开始，规则如下：

- 若当前子集的标签全部相同，或没有尚未使用的特征，则该结点为叶子。叶子类别是子集中出现次数最多的标签；次数相同取较小的标签。

- 否则只在尚未使用的特征中选择信息增益最大的特征进行划分。信息增益相同则选择下标较小的特征。同一条从根到叶的路径上，每个特征至多使用一次。

- 只对当前子集里实际出现过的取值建立子结点，并在对应子集上递归。

预测时从根结点向下。若测试样本在当前特征上的取值没有出现在该结点的训练子集中，则输出该结点的多数标签（次数相同取较小标签）。

下列表格只帮助理解划分过程。真正的输入全部是整数，不需要把单词换成数字。

| Outlook | Wind | Play |

| --- | --- | --- |

| Sunny | Weak | No |

| Sunny | Strong | No |

| Overcast | Weak | Yes |

| Rain | Weak | Yes |

| Rain | Strong | No |

得到的决策树为：

```

Outlook

├── Sunny → No

├── Overcast → Yes

└── Rain

├── Weak → Yes

└── Strong → No

```

Outlook 划分后的信息增益最大，所以放在根结点。

输入格式：第一行一个整数 m，表示特征数。第二行一个整数 n，表示训练样本数。接下来 n 行，每行 m+1 个整数，前 m 个为特征值，最后一个为类别标签。随后一行一个整数 k，表示测试样本数。接下来 k 行，每行 m 个整数，为一条测试样本的特征值。

输出格式：共 k 行，每行一个整数，为对应测试样本的预测类别标签。

样例1

输入：

2 5 0 0 0 0 1 0 1 0 1 1 1 0 2 0 1 4 0 1 1 0 1 1 2 0

输出：

0 1 0 1

> 注：原文未提供输入/输出描述，本节由官方题解代码推断补全。

思路

整体思路：这是一道按信息增益（ID3）建决策树的模拟题，核心是把建树规则一步一步实现出来：每个内部结点在尚未使用的特征里挑信息增益最大的划分，标签纯了或特征用完就做成叶子，预测时从根往下走、走不动就回退到当前结点的多数类。

1. 读入特征数 m、训练样本数 n、n 条「m 个特征 + 1 个标签」的样本、测试数 k 和 k 条测试样本。所有数都是整数，标签和特征值都可以为负。

2. 实现多数类函数：统计每个标签出现次数，取次数最大的标签；次数并列时取数值较小的标签（先按标签升序比较，或只在严格更大时替换）。这个函数同时用于叶子定类和内部结点保存回退答案。

3. 实现熵与信息增益：熵 H = −Σ p·log2(p)，只对实际出现的类别求和，单一类别时熵为 0。对某个特征按取值分组，用组大小除以总数做权重，父集熵减去加权子集熵就是该特征的信息增益。

4. 建树：若当前子集标签全相同或没有剩余特征，返回叶子（类别为多数类）。否则按下标从小到大扫描所有剩余特征，只有增益比当前最优高出一个小容差（如 1e-9）才替换，这样增益并列时自然留下下标更小的特征。选中后按该特征的取值把子集拆成若干组，从剩余特征里删掉它，对每组递归建子树；结点上保存多数类，供预测遇到未见取值时回退。

5. 预测：从根出发，按测试样本在当前特征上的取值进入对应子结点；若该取值在结点的子结点表里不存在，直接返回结点上保存的多数类；走到叶子就输出叶子类别。

复杂度：建树每层要对每个候选特征做一次 O(n) 的分组统计，最坏 O(特征数² × n × 每层子集规模)，本题规模下完全够用；预测每次沿一条根到叶路径走，O(m)。空间为树的结点数，不超过样本数。坑点：增益并列必须取下标更小的特征，浮点比较要留容差；叶子与内部结点的多数类并列时都取较小标签；一条路径上每个特征只能用一次；预测遇到未见取值不是报错，而是回退到当前结点的多数类。

Code

C++

#include <bits/stdc++.h> using namespace std; const double EPS = 1e-9; /* 结点：叶子 feat = -1，label 存类别；内部结点 feat 为特征下标， maj 为多数类（预测遇到未见取值时回退），child 保存「取值 -> 子结点」 */ struct Node { int feat = -1, label = 0, maj = 0; map<int, Node*> child; }; /* 求多数类：统计每个标签出现次数，取次数最多的；并列时取较小的标签 */ int majority(const vector<int>& labs) { map<int, int> cnt; /* 按标签升序遍历，严格更大才替换，保证并列取小 */ for (int x : labs) cnt[x]++; int best = 0, bestC = -1; for (auto& [x, c] : cnt) if (c > bestC) { best = x; bestC = c; } return best; } /* 熵 H = -sum p*log2(p)，只对实际出现的类别求和；单一类别时为 0 */ double entropy(const vector<int>& labs) { int n = labs.size(); map<int, int> cnt; for (int x : labs) cnt[x]++; double h = 0; for (auto& [x, c] : cnt) { double p = (double)c / n; h -= p * log2(p); } return h; } /* 信息增益 = 父集熵 - 按特征 f 分组后的加权子集熵 */ double gainOf(vector<vector<int>>& rows, int f, int m) { int n = rows.size(); vector<int> labs(n); for (int i = 0; i < n; i++) labs[i] = rows[i][m]; double h = entropy(labs); map<int, vector<int>> grp; for (auto& r : rows) grp[r[f]].push_back(r[m]); double rem = 0; for (auto& [v, sub] : grp) rem += (double)sub.size() / n * entropy(sub); return h - rem; } /* 递归建树：rows 是当前子集，feats 是尚未使用的特征下标 */ Node* build(vector<vector<int>>& rows, vector<int> feats, int m) { Node* nd = new Node(); int n = rows.size(); vector<int> labs(n); for (int i = 0; i < n; i++) labs[i] = rows[i][m]; nd->maj = majority(labs); bool pure = true; for (int x : labs) if (x != labs[0]) { pure = false; break; } /* 标签已纯或特征用完：做叶子 */ if (pure || feats.empty()) { nd->feat = -1; nd->label = nd->maj; return nd; } /* 按下标从小到大扫描，增益高出容差才替换，并列时留下更小的下标 */ int best = feats[0]; double bestG = -1.0; for (int f : feats) { double g = gainOf(rows, f, m); if (g > bestG + EPS) { best = f; bestG = g; } } nd->feat = best; map<int, vector<vector<int>>> grp; for (auto& r : rows) grp[r[best]].push_back(r); vector<int> rest; for (int f : feats) if (f != best) rest.push_back(f); for (auto& [v, sub] : grp) nd->child[v] = build(sub, rest, m); return nd; } /* 预测：走到叶子输出；当前特征取值没见过时返回结点保存的多数类 */ int predict(Node* nd, vector<int>& x) { if (nd->feat == -1) return nd->label; auto it = nd->child.find(x[nd->feat]); if (it == nd->child.end()) return nd->maj; return predict(it->second, x); } int main() { /* 关同步后一次性读入，快且省事 */ ios::sync_with_stdio(false); cin.tie(nullptr); int m, n; cin >> m >> n; vector<vector<int>> rows(n, vector<int>(m + 1)); for (auto& r : rows) for (int j = 0; j <= m; j++) cin >> r[j]; int k; cin >> k; vector<int> feats(m); for (int i = 0; i < m; i++) feats[i] = i; Node* root = build(rows, feats, m); for (int i = 0; i < k; i++) { vector<int> x(m); for (int j = 0; j < m; j++) cin >> x[j]; cout << predict(root, x) << "\n"; } return 0; }

Java

import java.util.*; import java.io.*; public class Solution { static final double EPS = 1e-9; /* 叶子：leaf=true，label 存类别；内部结点：feat 为特征下标， maj 为多数类（预测遇到未见取值时回退），child 保存「取值 -> 子结点」 */ static class Node { boolean leaf; int label, feat, maj; Map<Integer, Node> child = new HashMap<>(); } /* 求多数类：统计每个标签出现次数，取次数最多的；并列时取较小的标签 */ static int majority(List<Integer> labs) { TreeMap<Integer, Integer> cnt = new TreeMap<>(); for (int x : labs) cnt.merge(x, 1, Integer::sum); int best = 0, bestC = -1; // TreeMap 按标签升序遍历，只有严格更多才替换，保证并列取小 for (Map.Entry<Integer, Integer> e : cnt.entrySet()) { if (e.getValue() > bestC) { best = e.getKey(); bestC = e.getValue(); } } return best; } /* 熵 H = -sum p*log2(p)，只对实际出现的类别求和；单一类别时为 0 */ static double entropy(List<Integer> labs) { int n = labs.size(); Map<Integer, Integer> cnt = new HashMap<>(); for (int x : labs) cnt.merge(x, 1, Integer::sum); double h = 0.0; for (int c : cnt.values()) { double p = (double) c / n; h -= p * (Math.log(p) / Math.log(2)); } return h; } /* 信息增益 = 父集熵 - 按特征 f 分组后的加权子集熵 */ static double gainOf(List<int[]> rows, int f, int m) { int n = rows.size(); List<Integer> labs = new ArrayList<>(); for (int[] r : rows) labs.add(r[m]); double h = entropy(labs); Map<Integer, List<Integer>> grp = new HashMap<>(); for (int[] r : rows) grp.computeIfAbsent(r[f], x -> new ArrayList<>()).add(r[m]); double rem = 0.0; for (List<Integer> sub : grp.values()) rem += (double) sub.size() / n * entropy(sub); return h - rem; } /* 递归建树：rows 是当前子集，feats 是尚未使用的特征下标 */ static Node build(List<int[]> rows, List<Integer> feats, int m) { Node nd = new Node(); List<Integer> labs = new ArrayList<>(); for (int[] r : rows) labs.add(r[m]); nd.maj = majority(labs); boolean pure = true; for (int x : labs) if (x != labs.get(0)) { pure = false; break; } /* 标签已纯或特征用完：做叶子 */ if (pure || feats.isEmpty()) { nd.leaf = true; nd.label = nd.maj; return nd; } /* 按下标从小到大扫描，增益高出容差才替换，并列时留下更小的下标 */ int best = feats.get(0); double bestG = -1.0; for (int f : feats) { double g = gainOf(rows, f, m); if (g > bestG + EPS) { best = f; bestG = g; } } nd.feat = best; Map<Integer, List<int[]>> grp = new HashMap<>(); for (int[] r : rows) grp.computeIfAbsent(r[best], x -> new ArrayList<>()).add(r); List<Integer> rest = new ArrayList<>(); for (int f : feats) if (f != best) rest.add(f); for (Map.Entry<Integer, List<int[]>> e : grp.entrySet()) nd.child.put(e.getKey(), build(e.getValue(), rest, m)); return nd; } /* 预测：走到叶子输出；当前特征取值没见过时返回结点保存的多数类 */ static int predict(Node nd, int[] x) { if (nd.leaf) return nd.label; Node nxt = nd.child.get(x[nd.feat]); if (nxt == null) return nd.maj; return predict(nxt, x); } public static void main(String[] args) throws IOException { /* 用 StreamTokenizer 一次性读入所有整数，避免 Scanner 逐行读在循环里切换出错 */ StreamTokenizer in = new StreamTokenizer(new BufferedInputStream(System.in)); in.nextToken(); int m = (int) in.nval; in.nextToken(); int n = (int) in.nval; List<int[]> rows = new ArrayList<>(); for (int i = 0; i < n; i++) { int[] r = new int[m + 1]; for (int j = 0; j <= m; j++) { in.nextToken(); r[j] = (int) in.nval; } rows.add(r); } in.nextToken(); int k = (int) in.nval; List<Integer> feats = new ArrayList<>(); for (int i = 0; i < m; i++) feats.add(i); Node root = build(rows, feats, m); StringBuilder sb = new StringBuilder(); for (int i = 0; i < k; i++) { int[] x = new int[m]; for (int j = 0; j < m; j++) { in.nextToken(); x[j] = (int) in.nval; } sb.append(predict(root, x)).append('\n'); } System.out.print(sb); } }

Go

package main import ( "bufio" "fmt" "math" "os" ) const eps = 1e-9 // 结点：叶子 isLeaf=true，label 存类别；内部结点 feat 为特征下标， // maj 为多数类（预测遇到未见取值时回退），child 保存「取值 -> 子结点」 type node struct { isLeaf bool label int feat int maj int child map[int]*node } // 求多数类：统计每个标签出现次数，取次数最多的；并列时取较小的标签 func majority(labs []int) int { cnt := make(map[int]int) for _, x := range labs { cnt[x]++ } best, bestC := 0, -1 // 收集标签并升序排序，只有严格更多才替换，保证并列取小 keys := make([]int, 0, len(cnt)) for k := range cnt { keys = append(keys, k) } sortInts(keys) for _, k := range keys { if cnt[k] > bestC { best, bestC = k, cnt[k] } } return best } func sortInts(a []int) { for i := 1; i < len(a); i++ { for j := i; j > 0 && a[j] < a[j-1]; j-- { a[j], a[j-1] = a[j-1], a[j] } } } // 熵 H = -sum p*log2(p)，只对实际出现的类别求和；单一类别时为 0 func entropy(labs []int) float64 { n := len(labs) cnt := make(map[int]int) for _, x := range labs { cnt[x]++ } h := 0.0 for _, c := range cnt { p := float64(c) / float64(n) h -= p * math.Log2(p) } return h } // 信息增益 = 父集熵 - 按特征 f 分组后的加权子集熵 func gainOf(rows [][]int, f, m int) float64 { n := len(rows) labs := make([]int, n) for i, r := range rows { labs[i] = r[m] } h := entropy(labs) grp := make(map[int][]int) for _, r := range rows { grp[r[f]] = append(grp[r[f]], r[m]) } rem := 0.0 for _, sub := range grp { rem += float64(len(sub)) / float64(n) * entropy(sub) } return h - rem } // 递归建树：rows 是当前子集，feats 是尚未使用的特征下标 func build(rows [][]int, feats []int, m int) *node { nd := &node{child: make(map[int]*node)} labs := make([]int, len(rows)) for i, r := range rows { labs[i] = r[m] } nd.maj = majority(labs) pure := true for _, x := range labs { if x != labs[0] { pure = false break } } // 标签已纯或特征用完：做叶子 if pure || len(feats) == 0 { nd.isLeaf = true nd.label = nd.maj return nd } // 按下标从小到大扫描，增益高出容差才替换，并列时留下更小的下标 best, bestG := feats[0], -1.0 for _, f := range feats { g := gainOf(rows, f, m) if g > bestG+eps { best, bestG = f, g } } nd.feat = best grp := make(map[int][][]int) for _, r := range rows { grp[r[best]] = append(grp[r[best]], r) } rest := make([]int, 0, len(feats)) for _, f := range feats { if f != best { rest = append(rest, f) } } for v, sub := range grp { nd.child[v] = build(sub, rest, m) } return nd } // 预测：走到叶子输出；当前特征取值没见过时返回结点保存的多数类 func predict(nd *node, x []int) int { if nd.isLeaf { return nd.label } if nxt, ok := nd.child[x[nd.feat]]; ok { return predict(nxt, x) } return nd.maj } func main() { // bufio.Scanner 默认缓冲区对大输入不够，这里换成 bufio.Reader 逐 token 读 reader := bufio.NewReaderSize(os.Stdin, 1<<20) var data []int for { var v int if _, err := fmt.Fscan(reader, &v); err != nil { break } data = append(data, v) } idx := 0 next := func() int { v := data[idx]; idx++; return v } m := next() n := next() rows := make([][]int, n) for i := 0; i < n; i++ { r := make([]int, m+1) for j := 0; j <= m; j++ { r[j] = next() } rows[i] = r } k := next() feats := make([]int, m) for i := 0; i < m; i++ { feats[i] = i } root := build(rows, feats, m) w := bufio.NewWriter(os.Stdout) defer w.Flush() for i := 0; i < k; i++ { x := make([]int, m) for j := 0; j < m; j++ { x[j] = next() } fmt.Fprintln(w, predict(root, x)) } }

C

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #define EPS 1e-9 /* ---------- 动态 int 数组 ---------- */ typedef struct { int *a; int len, cap; } Vec; void vec_push(Vec *v, int x) { if (v->len == v->cap) { v->cap = v->cap ? v->cap * 2 : 8; v->a = realloc(v->a, v->cap * sizeof(int)); } v->a[v->len++] = x; } /* ---------- 结点池 ---------- */ /* 叶子：feat = -1，label 存类别；内部结点：feat 为特征下标，maj 为多数类， childVal/childId 平行存储「取值 -> 子结点编号」（线性查找即可） */ typedef struct { int feat, label, maj; Vec childVal, childId; } Node; Node *pool; int poolLen, poolCap; int newNode() { if (poolLen == poolCap) { poolCap = poolCap ? poolCap * 2 : 64; pool = realloc(pool, poolCap * sizeof(Node)); } Node *nd = &pool[poolLen]; nd->feat = -1; nd->label = 0; nd->maj = 0; memset(&nd->childVal, 0, sizeof(Vec)); memset(&nd->childId, 0, sizeof(Vec)); return poolLen++; } /* 求多数类：统计每个标签出现次数，取次数最多的；并列时取较小的标签 */ int majority(int *labs, int n) { /* 复制后排序，相同标签相邻；只有严格更多才替换，保证并列取小 */ int *tmp = malloc(n * sizeof(int)); memcpy(tmp, labs, n * sizeof(int)); for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) if (tmp[j] < tmp[i]) { int t = tmp[i]; tmp[i] = tmp[j]; tmp[j] = t; } int best = 0, bestC = -1, i = 0; while (i < n) { int j = i; while (j < n && tmp[j] == tmp[i]) j++; if (j - i > bestC) { best = tmp[i]; bestC = j - i; } i = j; } free(tmp); return best; } /* 熵 H = -sum p*log2(p)，只对实际出现的类别求和；单一类别时结果为 0 */ double entropy(int *labs, int n) { int *tmp = malloc(n * sizeof(int)); memcpy(tmp, labs, n * sizeof(int)); for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) if (tmp[j] < tmp[i]) { int t = tmp[i]; tmp[i] = tmp[j]; tmp[j] = t; } double h = 0.0; int i = 0; while (i < n) { int j = i; while (j < n && tmp[j] == tmp[i]) j++; double p = (double)(j - i) / n; h -= p * log2(p); i = j; } free(tmp); return h; } /* 按特征 f 分组后的加权子集熵（rows[r][0..m-1] 是特征，rows[r][m] 是标签） */ double weightedEntropy(int **rows, int n, int f, int m) { int *vals = malloc(n * sizeof(int)); int nv = 0; /* 收集该列实际出现过的取值 */ for (int r = 0; r < n; r++) { int v = rows[r][f], seen = 0; for (int j = 0; j < nv; j++) if (vals[j] == v) { seen = 1; break; } if (!seen) vals[nv++] = v; } double rem = 0.0; for (int j = 0; j < nv; j++) { int cnt = 0; for (int r = 0; r < n; r++) if (rows[r][f] == vals[j]) cnt++; int *sub = malloc(cnt * sizeof(int)); int c = 0; for (int r = 0; r < n; r++) if (rows[r][f] == vals[j]) sub[c++] = rows[r][m]; rem += (double)cnt / n * entropy(sub, cnt); free(sub); } free(vals); return rem; } /* 递归建树：rows 存样本指针，feats 是尚未使用的特征下标，返回结点编号 */ int build(int **rows, int n, int *feats, int nf, int m) { int id = newNode(); Node *nd = &pool[id]; int *labs = malloc(n * sizeof(int)); for (int i = 0; i < n; i++) labs[i] = rows[i][m]; nd->maj = majority(labs, n); /* 多数类同时用于叶子和回退 */ int pure = 1; for (int i = 1; i < n; i++) if (labs[i] != labs[0]) { pure = 0; break; } free(labs); /* 标签已纯或特征用完：做叶子 */ if (pure || nf == 0) { nd->feat = -1; nd->label = nd->maj; return id; } /* 按下标从小到大扫描候选特征；增益高出容差才替换，并列时留下更小的下标 */ int best = feats[0]; double bestG = -1.0; for (int i = 0; i < nf; i++) { int *labsAll = malloc(n * sizeof(int)); for (int r = 0; r < n; r++) labsAll[r] = rows[r][m]; double h = entropy(labsAll, n); free(labsAll); double g = h - weightedEntropy(rows, n, feats[i], m); if (g > bestG + EPS) { best = feats[i]; bestG = g; } } nd = &pool[id]; nd->feat = best; /* 收集选中特征的实际取值，按取值拆分子集递归 */ int *vals = malloc(n * sizeof(int)); int nv = 0; for (int r = 0; r < n; r++) { int v = rows[r][best], seen = 0; for (int j = 0; j < nv; j++) if (vals[j] == v) { seen = 1; break; } if (!seen) vals[nv++] = v; } int *newFeats = malloc(nf * sizeof(int)); int c2 = 0; for (int i = 0; i < nf; i++) if (feats[i] != best) newFeats[c2++] = feats[i]; for (int j = 0; j < nv; j++) { int **sub = malloc(n * sizeof(int*)); int c = 0; for (int r = 0; r < n; r++) if (rows[r][best] == vals[j]) sub[c++] = rows[r]; int cid = build(sub, c, newFeats, c2, m); free(sub); nd = &pool[id]; /* 递归可能 realloc 池，重新取指针 */ vec_push(&nd->childVal, vals[j]); vec_push(&nd->childId, cid); } free(vals); free(newFeats); return id; } /* 预测：走到叶子输出；当前特征取值没见过时返回结点保存的多数类 */ int predict(int id, int *x) { Node *nd = &pool[id]; if (nd->feat == -1) return nd->label; for (int j = 0; j < nd->childVal.len; j++) if (nd->childVal.a[j] == x[nd->feat]) return predict(nd->childId.a[j], x); return nd->maj; } int main(void) { /* 一次性读入全部整数 */ static int *data = NULL; int dn = 0, cap = 1 << 20; data = malloc(cap * sizeof(int)); int v; while (scanf("%d", &v) == 1) { if (dn == cap) { cap *= 2; data = realloc(data, cap * sizeof(int)); } data[dn++] = v; } int idx = 0; int m = data[idx++]; /* 特征数 */ int n = data[idx++]; /* 训练样本数 */ int **rows = malloc(n * sizeof(int*)); for (int i = 0; i < n; i++) { rows[i] = malloc((m + 1) * sizeof(int)); for (int j = 0; j <= m; j++) rows[i][j] = data[idx++]; } int k = data[idx++]; /* 测试样本数 */ int *feats = malloc(m * sizeof(int)); for (int i = 0; i < m; i++) feats[i] = i; int root = build(rows, n, feats, m, m); for (int i = 0; i < k; i++) { int *x = malloc(m * sizeof(int)); for (int j = 0; j < m; j++) x[j] = data[idx++]; printf("%d\n", predict(root, x)); free(x); } return 0; }

Python

import sys from math import log2 sys.setrecursionlimit(100000) EPS = 1e-9 def majority(labs): # 求多数类：统计每个标签的出现次数，取次数最多的标签 # 参数 labs 是标签列表；次数并列时返回数值较小的标签 cnt = {} for x in labs: cnt[x] = cnt.get(x, 0) + 1 best = None best_c = -1 # 按标签升序遍历，只有严格更多的次数才替换，并列时留下较小的标签 for x in sorted(cnt): if cnt[x] > best_c: best = x best_c = cnt[x] return best def entropy(labs): # 计算熵 H = -sum p*log2(p)，只对实际出现的类别求和 # 单一类别时每个 p=1，结果为 0 n = len(labs) cnt = {} for x in labs: cnt[x] = cnt.get(x, 0) + 1 h = 0.0 for c in cnt.values(): p = c / n h -= p * log2(p) return h def gain(rows, f): # 计算按特征 f 划分的信息增益 = 父集熵 - 按取值分组后的加权子集熵 # 参数 rows 是样本（最后一列是标签），f 是特征下标 n = len(rows) h = entropy([r[-1] for r in rows]) grp = {} for r in rows: grp.setdefault(r[f], []).append(r[-1]) rem = 0.0 for labs in grp.values(): rem += len(labs) / n * entropy(labs) return h - rem def build(rows, feats): # 递归建树：rows 是当前子集，feats 是尚未使用的特征下标列表 # 返回 ("L", 标签) 或 ("N", 特征, 多数类, {取值: 子树}) labs = [r[-1] for r in rows] maj = majority(labs) # 标签已经全相同，或特征用完，做成叶子 if all(x == labs[0] for x in labs) or not feats: return ("L", maj) # 按下标从小到大扫描；增益没有明显更大就保留更小的下标（并列取小） best = feats[0] best_g = -1.0 for f in feats: g = gain(rows, f) if g > best_g + EPS: best = f best_g = g # 按选中特征的取值拆分子集 grp = {} for r in rows: grp.setdefault(r[best], []).append(r) rest = [f for f in feats if f != best] child = {} for v, sub in grp.items(): child[v] = build(sub, rest) # 结点上保存多数类，预测遇到未见取值时回退用它 return ("N", best, maj, child) def predict(node, x): # 从结点 node 出发预测样本 x 的标签 # 走到叶子直接输出；当前特征的取值没见过时，返回该结点的多数类 if node[0] == "L": return node[1] _, feat, maj, child = node v = x[feat] if v not in child: return maj return predict(child[v], x) def main(): data = sys.stdin.buffer.read().split() idx = 0 m = int(data[idx]); idx += 1 # 特征数 n = int(data[idx]); idx += 1 # 训练样本数 rows = [] for _ in range(n): rows.append([int(v) for v in data[idx:idx + m + 1]]) idx += m + 1 k = int(data[idx]); idx += 1 # 测试样本数 out = [] tree = build(rows, list(range(m))) for _ in range(k): x = [int(v) for v in data[idx:idx + m]] idx += m out.append(str(predict(tree, x))) sys.stdout.write("\n".join(out) + "\n") main()