华为校招实习机试在线OJ刷题系统 在线OJ注册使用教程目录题目思路Code题目题目内容CARTClassification and Regression Trees分类树通过二元切分递归地将数据划分为不纯度最小的子集。它通过基尼系数Gini Index计算最优分裂特征和点形成二叉树结构适用于处理离散和连续数据。本题要求应用CART分类树模型预测客户是否购房。给定一个训练数据集通过构建CART二叉决策树使用基尼指数选择最优特征和最优切分点对输入的测试样本进行预测。划分规则对于每个特征尝试所有可能的取值作为切分点将数据划分为左子集和右子集左子集为特征值 切分点的样本右子集为特征值 ≠ 切分点的样本。数据集说明包含4个特征和1个标签所有取值的输入转换为整数枚举。特征1年龄段0: 18-30岁; 1: 31-40岁; 2: 41-55岁; 3: 56岁及以上特征2婚姻状况0: 单身; 1: 恋爱; 2: 已婚特征3是否有房0: 无; 1: 有特征4是否有工作0: 无; 1: 有标签购房结果0: 否; 1: 是。基尼指数计算公式对于包含 K 个类别的数据集$p_k$ 为指定标签的样本占比$Gini(D) 1 - \sum_{k1}^{K} p_k^2$。加权基尼指数对于特征 A 的切分点 v将 D 划分为 $D_1(A v)$ 和 $D_2(A \neq v)$$Gini(D, A, v) \frac{|D_1|}{|D|} \times Gini(D_1) \frac{|D_2|}{|D|} \times Gini(D_2)$。预测规则叶子节点的预测类别为该节点中样本数最多的类别若多个类别样本数相同取类别编号较小的。停止分裂条件满足任一条件即停止节点中所有样本标签相同节点中样本数小于 2无法找到使基尼指数降低的切分点。平局处理规则遍历特征时按特征编号从小到大特征1 → 特征2 → 特征3 → 特征4对于每个特征遍历其所有可能的取值作为切分点按取值从小到大计算每个切分点的加权基尼指数选择基尼指数最小的切分点当多个特征的基尼指数相同且均为最小值时选择特征编号较小的特征当同一特征内多个取值的基尼指数相同且均为最小值时选择取值较小的作为切分点即左子集为 等于该较小值。输入格式第一行给出整数 N表示训练集的客户人数4 ≤ N ≤ 20随后 N 行每行 5 个整数依次是 4 个特征和 1 个标签整数之间以空格分隔接下来一行给出整数 M表示待预测的样本人数1 ≤ M ≤ 10随后 M 行每行 4 个整数依次是 4 个特征。输出格式输出一行共 M 个整数依次为 M 个测试样本在所建 CART 树上的预测结果整数之间以空格分隔。样例1输入20 0 0 0 1 1 0 0 1 0 0 0 1 0 0 0 0 1 1 1 1 0 2 0 1 1 1 0 0 0 0 1 0 1 1 1 1 1 0 1 1 1 1 1 0 0 1 2 1 0 0 2 0 0 1 1 2 0 1 0 1 2 1 0 0 0 2 1 1 1 1 2 2 0 0 0 3 0 0 0 0 3 0 1 1 0 3 1 0 1 1 3 1 1 0 0 3 2 0 1 0 10 1 1 1 0 2 0 0 1 3 2 0 1 0 0 1 0 1 2 1 0 2 1 0 0 3 0 1 1 0 1 1 1 1 0 0 0 2 2 0 0输出0 1 0 0 0 0 0 1 0 0思路整体思路按题面规则现建一棵 CART 二叉分类树。每个节点选一个特征和一个取值做二元切分左子树放该特征等于这个取值的样本右子树放不等于的样本。只有加权基尼指数比当前节点严格更小的切分才接受否则停止分裂变成叶子。1. 读入 N 条训练记录4 个特征 1 个标签和 M 条测试记录。2. 建树是递归过程。先统计当前节点样本里标签 0 和标签 1 的人数样本数小于 2、标签已纯只剩一类、或找不到能严格降低基尼的切分三种情况任一成立就直接做叶子叶子预测人数更多的类别两类人数打平取编号较小的 0。3. 每个节点枚举切分特征按编号 1 到 4 从小到大每个特征在节点内出现过的取值也按从小到大。把当前节点的基尼写成整数分数 (tot^2 - c0^2 - c1^2) / tot^2左右子集同理加权基尼通分后是 num/den (g1*n2 g2*n1) / (tot*n1*n2)。全程用整数交叉相乘比较大小避免浮点误差。4. 接受条件是加权基尼严格小于当前节点基尼num*base_d base_n*den 才接受而更新最优切分时用的是严格小于num*best_den best_num*den 才替换相等不替换。这样平局自然留下更小的特征编号和更小的取值正好满足题面的平局规则。5. 一侧为空的切分所有样本该特征都等于或不等于某取值直接跳过没有意义。6. 预测时每个测试样本从根往下走特征值等于切分值进左子树否则进右子树走到叶子输出类别。复杂度特征 4 个、每个特征取值不超过 4 种都是常数。每个节点只扫自己的样本每个样本出现在从根到叶的一条链上建树 O(N^2)M 个测试样本各走一条根到叶路径预测 O(N*M)。N ≤ 20、M ≤ 10规模极小。关键坑点一是叶子平局两类人数相同取编号小的 0二是严格降低基尼才分裂和平局保留更小特征/取值这两条都要用严格不等号实现写成 会破坏平局规则三是切分点的左子集是等于该取值的样本不要建反。CodeC#include bits/stdc.h using namespace std; int a[25][5]; // 数样本集合里标签 0 和标签 1 各有多少个 pairint, int stat(const vectorint ids) { int c0 0; for (int i : ids) if (a[i][4] 0) c0; return {c0, (int)ids.size() - c0}; } // 递归建树。叶子用 {-1, 类别} 表示内部节点 {特征, 切分值, 左, 右} struct Node { int f, v; int left -1, right -1; // 子节点下标-1 表示叶子 int lab; // 叶子的预测类别 }; vectorNode tree; int build(const vectorint ids) { pairint, int cc stat(ids); int c0 cc.first, c1 cc.second; int tot ids.size(); // 叶子预测人数多的类别打平取编号小的 0 int lab c0 c1 ? 0 : 1; // 样本不足 2 个或标签已纯停止分裂 if (tot 2 || c0 0 || c1 0) { tree.push_back({-1, 0, -1, -1, lab}); return tree.size() - 1; } // 当前节点的基尼写成整数分数(tot^2 - c0^2 - c1^2) / tot^2 long long baseN (long long)tot * tot - (long long)c0 * c0 - (long long)c1 * c1; long long baseD (long long)tot * tot; bool found false; long long bestNum 0, bestDen 1; int bestF -1, bestV 0; vectorint bestL, bestR; // 平局规则特征编号从小到大同一特征内取值从小到大 // 基尼用整数交叉相乘比较只有严格变小才替换平局留下更小的特征/取值 for (int f 0; f 4; f) { setint vals; for (int i : ids) vals.insert(a[i][f]); for (int v : vals) { vectorint L, R; for (int i : ids) (a[i][f] v ? L : R).push_back(i); if (L.empty() || R.empty()) continue; // 一侧为空没意义 pairint, int lc stat(L); pairint, int rc stat(R); int l0 lc.first, l1 lc.second; int r0 rc.first, r1 rc.second; long long n1 L.size(), n2 R.size(); // 左右子集的基尼分子n^2 - c0^2 - c1^2 long long g1 n1 * n1 - (long long)l0 * l0 - (long long)l1 * l1; long long g2 n2 * n2 - (long long)r0 * r0 - (long long)r1 * r1; // 加权基尼通分num/den long long num g1 * n2 g2 * n1; long long den (long long)tot * n1 * n2; // 只有严格降低基尼的切分才接受 if (num * baseD baseN * den) continue; if (!found || num * bestDen bestNum * den) { found true; bestNum num; bestDen den; bestF f; bestV v; bestL L; bestR R; } } } if (!found) { tree.push_back({-1, 0, -1, -1, lab}); // 找不到能降低基尼的切分变成叶子 return tree.size() - 1; } int me tree.size(); tree.push_back({bestF, bestV, -1, -1, lab}); int lc build(bestL); // 注意先占位再递归避免递归时 vector 扩容失效 int rc build(bestR); tree[me].left lc; tree[me].right rc; return me; } int main() { int n; scanf(%d, n); for (int i 0; i n; i) for (int j 0; j 5; j) scanf(%d, a[i][j]); vectorint ids(n); for (int i 0; i n; i) ids[i] i; int root build(ids); int m; scanf(%d, m); for (int k 0; k m; k) { int x[4]; for (int j 0; j 4; j) scanf(%d, x[j]); // 沿树往下走特征值等于切分值进左子树否则进右子树 int cur root; while (tree[cur].f 0) cur x[tree[cur].f] tree[cur].v ? tree[cur].left : tree[cur].right; printf(%d%c, tree[cur].lab, k 1 m ? : \n); } return 0; }Javaimport java.util.*; import java.io.*; public class Solution { static int[][] a; // 数样本集合里标签 0 和标签 1 各有多少个 static int[] stat(ListInteger ids) { int c0 0; for (int i : ids) if (a[i][4] 0) c0; return new int[]{c0, ids.size() - c0}; } // 递归建树。返回节点编号节点 [特征, 切分值, 左孩子, 右孩子, 叶子类别] // 叶子的特征存 -1预测类别存 leafLab static int[][] tree new int[200][5]; static int nodeCnt 0; static int build(ListInteger ids) { int[] c stat(ids); int c0 c[0], c1 c[1]; int tot ids.size(); // 叶子预测人数多的类别打平取编号小的 0 int lab c0 c1 ? 0 : 1; // 样本不足 2 个或标签已纯停止分裂 if (tot 2 || c0 0 || c1 0) { tree[nodeCnt] new int[]{-1, 0, -1, -1, lab}; return nodeCnt; } // 当前节点的基尼写成整数分数(tot^2 - c0^2 - c1^2) / tot^2 long baseN (long) tot * tot - (long) c0 * c0 - (long) c1 * c1; long baseD (long) tot * tot; boolean found false; long bestNum 0, bestDen 1; int bestF -1, bestV 0; ListInteger bestL null, bestR null; // 平局规则特征编号从小到大同一特征内取值从小到大 // 基尼用整数交叉相乘比较只有严格变小才替换平局留下更小的特征/取值 for (int f 0; f 4; f) { TreeSetInteger vals new TreeSet(); for (int i : ids) vals.add(a[i][f]); for (int v : vals) { ListInteger L new ArrayList(), R new ArrayList(); for (int i : ids) { if (a[i][f] v) L.add(i); else R.add(i); } if (L.isEmpty() || R.isEmpty()) continue; // 一侧为空没意义 int[] lc stat(L), rc stat(R); long n1 L.size(), n2 R.size(); // 左右子集的基尼分子n^2 - c0^2 - c1^2 long g1 n1 * n1 - (long) lc[0] * lc[0] - (long) lc[1] * lc[1]; long g2 n2 * n2 - (long) rc[0] * rc[0] - (long) rc[1] * rc[1]; // 加权基尼通分num/den long num g1 * n2 g2 * n1; long den (long) tot * n1 * n2; // 只有严格降低基尼的切分才接受 if (num * baseD baseN * den) continue; if (!found || num * bestDen bestNum * den) { found true; bestNum num; bestDen den; bestF f; bestV v; bestL L; bestR R; } } } if (!found) { tree[nodeCnt] new int[]{-1, 0, -1, -1, lab}; // 无法降低基尼变成叶子 return nodeCnt; } int me nodeCnt; tree[me] new int[]{bestF, bestV, -1, -1, lab}; int leftChild build(bestL); // 先递归再回填孩子编号 int rightChild build(bestR); tree[me][2] leftChild; tree[me][3] rightChild; return me; } public static void main(String[] args) throws IOException { // 全程只用 nextInt 读整数避免 Scanner 在不同读取模式间切换造成错位 BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StreamTokenizer tk new StreamTokenizer(br); tk.nextToken(); int n (int) tk.nval; a new int[n][5]; for (int i 0; i n; i) for (int j 0; j 5; j) { tk.nextToken(); a[i][j] (int) tk.nval; } ListInteger ids new ArrayList(); for (int i 0; i n; i) ids.add(i); int root build(ids); StringBuilder sb new StringBuilder(); tk.nextToken(); int m (int) tk.nval; for (int k 0; k m; k) { int[] x new int[4]; for (int j 0; j 4; j) { tk.nextToken(); x[j] (int) tk.nval; } // 沿树往下走特征值等于切分值进左子树否则进右子树 int cur root; while (tree[cur][0] 0) cur x[tree[cur][0]] tree[cur][1] ? tree[cur][2] : tree[cur][3]; if (k 0) sb.append( ); sb.append(tree[cur][4]); } System.out.println(sb); } }Gopackage main import ( bufio fmt os sort ) var a [25][5]int // node 递归树的节点。叶子f -1lab 是预测类别内部节点特征 f、切分值 v、左右孩子 type node struct { f, v, left, right, lab int } var tree []node // stat 数样本集合里标签 0 和标签 1 各有多少个 func stat(ids []int) (int, int) { c0 : 0 for _, i : range ids { if a[i][4] 0 { c0 } } return c0, len(ids) - c0 } func build(ids []int) int { c0, c1 : stat(ids) tot : len(ids) // 叶子预测人数多的类别打平取编号小的 0 lab : 1 if c0 c1 { lab 0 } // 样本不足 2 个或标签已纯停止分裂 if tot 2 || c0 0 || c1 0 { tree append(tree, node{-1, 0, -1, -1, lab}) return len(tree) - 1 } // 当前节点的基尼写成整数分数(tot^2 - c0^2 - c1^2) / tot^2 baseN : int64(tot)*int64(tot) - int64(c0)*int64(c0) - int64(c1)*int64(c1) baseD : int64(tot) * int64(tot) found : false var bestNum, bestDen int64 bestF, bestV : -1, 0 var bestL, bestR []int // 平局规则特征编号从小到大同一特征内取值从小到大 // 基尼用整数交叉相乘比较只有严格变小才替换平局留下更小的特征/取值 for f : 0; f 4; f { valSet : map[int]bool{} for _, i : range ids { valSet[a[i][f]] true } vals : make([]int, 0, len(valSet)) for v : range valSet { vals append(vals, v) } sort.Ints(vals) for _, v : range vals { var L, R []int for _, i : range ids { if a[i][f] v { L append(L, i) } else { R append(R, i) } } if len(L) 0 || len(R) 0 { continue // 一侧为空没意义 } l0, l1 : stat(L) r0, r1 : stat(R) n1, n2 : int64(len(L)), int64(len(R)) // 左右子集的基尼分子n^2 - c0^2 - c1^2 g1 : n1*n1 - int64(l0)*int64(l0) - int64(l1)*int64(l1) g2 : n2*n2 - int64(r0)*int64(r0) - int64(r1)*int64(r1) // 加权基尼通分num/den num : g1*n2 g2*n1 den : int64(tot) * n1 * n2 // 只有严格降低基尼的切分才接受 if num*baseD baseN*den { continue } if !found || num*bestDen bestNum*den { found true bestNum, bestDen num, den bestF, bestV f, v bestL, bestR L, R } } } if !found { tree append(tree, node{-1, 0, -1, -1, lab}) // 无法降低基尼变成叶子 return len(tree) - 1 } me : len(tree) tree append(tree, node{bestF, bestV, -1, -1, lab}) lc : build(bestL) // 先递归再回填孩子编号 rc : build(bestR) tree[me].left lc tree[me].right rc return me } func main() { // 输入很小但按惯例把缓冲区放大防止大输入被截断 sc : bufio.NewScanner(os.Stdin) sc.Buffer(make([]byte, 1024*1024), 1024*1024) sc.Split(bufio.ScanWords) next : func() int { sc.Scan() v : 0 for _, c : range sc.Bytes() { v v*10 int(c-0) } return v } w : bufio.NewWriter(os.Stdout) defer w.Flush() n : next() for i : 0; i n; i { for j : 0; j 5; j { a[i][j] next() } } ids : make([]int, n) for i : range ids { ids[i] i } root : build(ids) m : next() for k : 0; k m; k { x : [4]int{} for j : 0; j 4; j { x[j] next() } // 沿树往下走特征值等于切分值进左子树否则进右子树 cur : root for tree[cur].f 0 { if x[tree[cur].f] tree[cur].v { cur tree[cur].left } else { cur tree[cur].right } } if k 0 { fmt.Fprint(w, ) } fmt.Fprint(w, tree[cur].lab) } fmt.Fprint(w, \n) }C#include stdio.h #include stdlib.h #define MAXN 25 #define MAXNODE 60 int a[MAXN][5]; /* 数样本集合里标签 0 和标签 1 各有多少个 */ void stat(int *ids, int cnt, int *c0, int *c1) { *c0 0; for (int i 0; i cnt; i) if (a[ids[i]][4] 0) (*c0); *c1 cnt - *c0; } /* 递归建树。叶子f -1lab 是预测类别内部节点特征 f、切分值 v、左右孩子 */ typedef struct { int f, v, left, right, lab; } Node; Node tree[MAXNODE]; int nodeCnt 0; int build(int *ids, int cnt) { int c0, c1; stat(ids, cnt, c0, c1); int tot cnt; /* 叶子预测人数多的类别打平取编号小的 0 */ int lab c0 c1 ? 0 : 1; /* 样本不足 2 个或标签已纯停止分裂 */ if (tot 2 || c0 0 || c1 0) { tree[nodeCnt] (Node){-1, 0, -1, -1, lab}; return nodeCnt; } /* 当前节点的基尼写成整数分数(tot^2 - c0^2 - c1^2) / tot^2 */ long long baseN (long long)tot * tot - (long long)c0 * c0 - (long long)c1 * c1; long long baseD (long long)tot * tot; int found 0, bestF -1, bestV 0; long long bestNum 0, bestDen 1; int bestL[MAXN], bestR[MAXN], bestLn 0, bestRn 0; int L[MAXN], R[MAXN]; /* 平局规则特征编号从小到大同一特征内取值从小到大 基尼用整数交叉相乘比较只有严格变小才替换平局留下更小的特征/取值 */ for (int f 0; f 4; f) { /* 收集该特征在节点内出现过的取值并排序取值最多 4 种 */ int vals[4], vn 0; for (int i 0; i cnt; i) { int v a[ids[i]][f], seen 0; for (int j 0; j vn; j) if (vals[j] v) seen 1; if (!seen) vals[vn] v; } for (int i 0; i vn; i) /* 小规模插入排序 */ for (int j i 1; j vn; j) if (vals[j] vals[i]) { int t vals[i]; vals[i] vals[j]; vals[j] t; } for (int vi 0; vi vn; vi) { int v vals[vi], ln 0, rn 0; for (int i 0; i cnt; i) { if (a[ids[i]][f] v) L[ln] ids[i]; else R[rn] ids[i]; } if (ln 0 || rn 0) continue; /* 一侧为空没意义 */ int l0, l1, r0, r1; stat(L, ln, l0, l1); stat(R, rn, r0, r1); long long n1 ln, n2 rn; /* 左右子集的基尼分子n^2 - c0^2 - c1^2 */ long long g1 n1 * n1 - (long long)l0 * l0 - (long long)l1 * l1; long long g2 n2 * n2 - (long long)r0 * r0 - (long long)r1 * r1; /* 加权基尼通分num/den */ long long num g1 * n2 g2 * n1; long long den (long long)tot * n1 * n2; /* 只有严格降低基尼的切分才接受 */ if (num * baseD baseN * den) continue; if (!found || num * bestDen bestNum * den) { found 1; bestNum num; bestDen den; bestF f; bestV v; for (int i 0; i ln; i) bestL[i] L[i]; for (int i 0; i rn; i) bestR[i] R[i]; bestLn ln; bestRn rn; } } } if (!found) { tree[nodeCnt] (Node){-1, 0, -1, -1, lab}; /* 找不到能降低基尼的切分变成叶子 */ return nodeCnt; } int me nodeCnt; tree[me] (Node){bestF, bestV, -1, -1, lab}; tree[me].left build(bestL, bestLn); tree[me].right build(bestR, bestRn); return me; } int main(void) { int n; if (scanf(%d, n) ! 1) return 0; for (int i 0; i n; i) for (int j 0; j 5; j) scanf(%d, a[i][j]); int ids[MAXN]; for (int i 0; i n; i) ids[i] i; int root build(ids, n); int m; scanf(%d, m); for (int k 0; k m; k) { int x[4]; for (int j 0; j 4; j) scanf(%d, x[j]); /* 沿树往下走特征值等于切分值进左子树否则进右子树 */ int cur root; while (tree[cur].f 0) cur x[tree[cur].f] tree[cur].v ? tree[cur].left : tree[cur].right; printf(%d%c, tree[cur].lab, k 1 m ? : \n); } return 0; }Pythonimport sys def main(): data sys.stdin.read().split() pos 0 def nxt(): nonlocal pos v int(data[pos]) pos 1 return v n nxt() a [[nxt() for _ in range(5)] for _ in range(n)] def stat(ids): # 数一下样本集合里标签 0 和标签 1 各有多少个 c0 sum(1 for i in ids if a[i][4] 0) return c0, len(ids) - c0 def build(ids): c0, c1 stat(ids) tot len(ids) # 叶子预测人数多的类别打平取编号小的 0 lab 0 if c0 c1 else 1 # 样本不足 2 个或标签已纯停止分裂 if tot 2 or c0 0 or c1 0: return [-1, lab] # 当前节点的基尼写成整数分数 (tot^2 - c0^2 - c1^2) / tot^2 base_n tot * tot - c0 * c0 - c1 * c1 base_d tot * tot best None # 平局规则特征编号从小到大同一特征内取值从小到大 # 基尼用分数比较只有严格变小才更新平局自然留下更小的特征/取值 for f in range(4): for v in sorted({a[i][f] for i in ids}): left [i for i in ids if a[i][f] v] right [i for i in ids if a[i][f] ! v] if not left or not right: continue # 一侧为空的切分没有意义 l0, l1 stat(left) r0, r1 stat(right) n1, n2 len(left), len(right) # 左右子集的基尼也写成整数分子 n^2 - c0^2 - c1^2 g1 n1 * n1 - l0 * l0 - l1 * l1 g2 n2 * n2 - r0 * r0 - r1 * r1 # 加权基尼 (g1/n1 g2/n2) / tot通分后是 num/den num g1 * n2 g2 * n1 den tot * n1 * n2 # 只有严格降低基尼的切分才接受num*base_d base_n*den if num * base_d base_n * den: continue if best is None or num * best[1] best[0] * den: best [num, den, f, v, left, right] if best is None: return [-1, lab] # 找不到能降低基尼的切分变成叶子 return [best[2], best[3], build(best[4]), build(best[5])] def ask(node, x): # 沿树往下走特征值等于切分值进左子树否则进右子树 while node[0] 0: node node[2] if x[node[0]] node[1] else node[3] return node[1] root build(list(range(n))) m nxt() ans [str(ask(root, [nxt() for _ in range(4)])) for _ in range(m)] print( .join(ans)) main() 
长河君 · 2026/11/3 10:43:37 · 阅读 1.2k 华为校招机考真题 AI方向 2026-10-14【基于CART分类树预测客户购房选择】
华为校招实习机试在线OJ刷题系统 在线OJ注册使用教程目录题目思路Code题目题目内容CARTClassification and Regression Trees分类树通过二元切分递归地将数据划分为不纯度最小的子集。它通过基尼系数Gini Index计算最优分裂特征和点形成二叉树结构适用于处理离散和连续数据。本题要求应用CART分类树模型预测客户是否购房。给定一个训练数据集通过构建CART二叉决策树使用基尼指数选择最优特征和最优切分点对输入的测试样本进行预测。划分规则对于每个特征尝试所有可能的取值作为切分点将数据划分为左子集和右子集左子集为特征值 切分点的样本右子集为特征值 ≠ 切分点的样本。数据集说明包含4个特征和1个标签所有取值的输入转换为整数枚举。特征1年龄段0: 18-30岁; 1: 31-40岁; 2: 41-55岁; 3: 56岁及以上特征2婚姻状况0: 单身; 1: 恋爱; 2: 已婚特征3是否有房0: 无; 1: 有特征4是否有工作0: 无; 1: 有标签购房结果0: 否; 1: 是。基尼指数计算公式对于包含 K 个类别的数据集$p_k$ 为指定标签的样本占比$Gini(D) 1 - \sum_{k1}^{K} p_k^2$。加权基尼指数对于特征 A 的切分点 v将 D 划分为 $D_1(A v)$ 和 $D_2(A \neq v)$$Gini(D, A, v) \frac{|D_1|}{|D|} \times Gini(D_1) \frac{|D_2|}{|D|} \times Gini(D_2)$。预测规则叶子节点的预测类别为该节点中样本数最多的类别若多个类别样本数相同取类别编号较小的。停止分裂条件满足任一条件即停止节点中所有样本标签相同节点中样本数小于 2无法找到使基尼指数降低的切分点。平局处理规则遍历特征时按特征编号从小到大特征1 → 特征2 → 特征3 → 特征4对于每个特征遍历其所有可能的取值作为切分点按取值从小到大计算每个切分点的加权基尼指数选择基尼指数最小的切分点当多个特征的基尼指数相同且均为最小值时选择特征编号较小的特征当同一特征内多个取值的基尼指数相同且均为最小值时选择取值较小的作为切分点即左子集为 等于该较小值。输入格式第一行给出整数 N表示训练集的客户人数4 ≤ N ≤ 20随后 N 行每行 5 个整数依次是 4 个特征和 1 个标签整数之间以空格分隔接下来一行给出整数 M表示待预测的样本人数1 ≤ M ≤ 10随后 M 行每行 4 个整数依次是 4 个特征。输出格式输出一行共 M 个整数依次为 M 个测试样本在所建 CART 树上的预测结果整数之间以空格分隔。样例1输入20 0 0 0 1 1 0 0 1 0 0 0 1 0 0 0 0 1 1 1 1 0 2 0 1 1 1 0 0 0 0 1 0 1 1 1 1 1 0 1 1 1 1 1 0 0 1 2 1 0 0 2 0 0 1 1 2 0 1 0 1 2 1 0 0 0 2 1 1 1 1 2 2 0 0 0 3 0 0 0 0 3 0 1 1 0 3 1 0 1 1 3 1 1 0 0 3 2 0 1 0 10 1 1 1 0 2 0 0 1 3 2 0 1 0 0 1 0 1 2 1 0 2 1 0 0 3 0 1 1 0 1 1 1 1 0 0 0 2 2 0 0输出0 1 0 0 0 0 0 1 0 0思路整体思路按题面规则现建一棵 CART 二叉分类树。每个节点选一个特征和一个取值做二元切分左子树放该特征等于这个取值的样本右子树放不等于的样本。只有加权基尼指数比当前节点严格更小的切分才接受否则停止分裂变成叶子。1. 读入 N 条训练记录4 个特征 1 个标签和 M 条测试记录。2. 建树是递归过程。先统计当前节点样本里标签 0 和标签 1 的人数样本数小于 2、标签已纯只剩一类、或找不到能严格降低基尼的切分三种情况任一成立就直接做叶子叶子预测人数更多的类别两类人数打平取编号较小的 0。3. 每个节点枚举切分特征按编号 1 到 4 从小到大每个特征在节点内出现过的取值也按从小到大。把当前节点的基尼写成整数分数 (tot^2 - c0^2 - c1^2) / tot^2左右子集同理加权基尼通分后是 num/den (g1*n2 g2*n1) / (tot*n1*n2)。全程用整数交叉相乘比较大小避免浮点误差。4. 接受条件是加权基尼严格小于当前节点基尼num*base_d base_n*den 才接受而更新最优切分时用的是严格小于num*best_den best_num*den 才替换相等不替换。这样平局自然留下更小的特征编号和更小的取值正好满足题面的平局规则。5. 一侧为空的切分所有样本该特征都等于或不等于某取值直接跳过没有意义。6. 预测时每个测试样本从根往下走特征值等于切分值进左子树否则进右子树走到叶子输出类别。复杂度特征 4 个、每个特征取值不超过 4 种都是常数。每个节点只扫自己的样本每个样本出现在从根到叶的一条链上建树 O(N^2)M 个测试样本各走一条根到叶路径预测 O(N*M)。N ≤ 20、M ≤ 10规模极小。关键坑点一是叶子平局两类人数相同取编号小的 0二是严格降低基尼才分裂和平局保留更小特征/取值这两条都要用严格不等号实现写成 会破坏平局规则三是切分点的左子集是等于该取值的样本不要建反。CodeC#include bits/stdc.h using namespace std; int a[25][5]; // 数样本集合里标签 0 和标签 1 各有多少个 pairint, int stat(const vectorint ids) { int c0 0; for (int i : ids) if (a[i][4] 0) c0; return {c0, (int)ids.size() - c0}; } // 递归建树。叶子用 {-1, 类别} 表示内部节点 {特征, 切分值, 左, 右} struct Node { int f, v; int left -1, right -1; // 子节点下标-1 表示叶子 int lab; // 叶子的预测类别 }; vectorNode tree; int build(const vectorint ids) { pairint, int cc stat(ids); int c0 cc.first, c1 cc.second; int tot ids.size(); // 叶子预测人数多的类别打平取编号小的 0 int lab c0 c1 ? 0 : 1; // 样本不足 2 个或标签已纯停止分裂 if (tot 2 || c0 0 || c1 0) { tree.push_back({-1, 0, -1, -1, lab}); return tree.size() - 1; } // 当前节点的基尼写成整数分数(tot^2 - c0^2 - c1^2) / tot^2 long long baseN (long long)tot * tot - (long long)c0 * c0 - (long long)c1 * c1; long long baseD (long long)tot * tot; bool found false; long long bestNum 0, bestDen 1; int bestF -1, bestV 0; vectorint bestL, bestR; // 平局规则特征编号从小到大同一特征内取值从小到大 // 基尼用整数交叉相乘比较只有严格变小才替换平局留下更小的特征/取值 for (int f 0; f 4; f) { setint vals; for (int i : ids) vals.insert(a[i][f]); for (int v : vals) { vectorint L, R; for (int i : ids) (a[i][f] v ? L : R).push_back(i); if (L.empty() || R.empty()) continue; // 一侧为空没意义 pairint, int lc stat(L); pairint, int rc stat(R); int l0 lc.first, l1 lc.second; int r0 rc.first, r1 rc.second; long long n1 L.size(), n2 R.size(); // 左右子集的基尼分子n^2 - c0^2 - c1^2 long long g1 n1 * n1 - (long long)l0 * l0 - (long long)l1 * l1; long long g2 n2 * n2 - (long long)r0 * r0 - (long long)r1 * r1; // 加权基尼通分num/den long long num g1 * n2 g2 * n1; long long den (long long)tot * n1 * n2; // 只有严格降低基尼的切分才接受 if (num * baseD baseN * den) continue; if (!found || num * bestDen bestNum * den) { found true; bestNum num; bestDen den; bestF f; bestV v; bestL L; bestR R; } } } if (!found) { tree.push_back({-1, 0, -1, -1, lab}); // 找不到能降低基尼的切分变成叶子 return tree.size() - 1; } int me tree.size(); tree.push_back({bestF, bestV, -1, -1, lab}); int lc build(bestL); // 注意先占位再递归避免递归时 vector 扩容失效 int rc build(bestR); tree[me].left lc; tree[me].right rc; return me; } int main() { int n; scanf(%d, n); for (int i 0; i n; i) for (int j 0; j 5; j) scanf(%d, a[i][j]); vectorint ids(n); for (int i 0; i n; i) ids[i] i; int root build(ids); int m; scanf(%d, m); for (int k 0; k m; k) { int x[4]; for (int j 0; j 4; j) scanf(%d, x[j]); // 沿树往下走特征值等于切分值进左子树否则进右子树 int cur root; while (tree[cur].f 0) cur x[tree[cur].f] tree[cur].v ? tree[cur].left : tree[cur].right; printf(%d%c, tree[cur].lab, k 1 m ? : \n); } return 0; }Javaimport java.util.*; import java.io.*; public class Solution { static int[][] a; // 数样本集合里标签 0 和标签 1 各有多少个 static int[] stat(ListInteger ids) { int c0 0; for (int i : ids) if (a[i][4] 0) c0; return new int[]{c0, ids.size() - c0}; } // 递归建树。返回节点编号节点 [特征, 切分值, 左孩子, 右孩子, 叶子类别] // 叶子的特征存 -1预测类别存 leafLab static int[][] tree new int[200][5]; static int nodeCnt 0; static int build(ListInteger ids) { int[] c stat(ids); int c0 c[0], c1 c[1]; int tot ids.size(); // 叶子预测人数多的类别打平取编号小的 0 int lab c0 c1 ? 0 : 1; // 样本不足 2 个或标签已纯停止分裂 if (tot 2 || c0 0 || c1 0) { tree[nodeCnt] new int[]{-1, 0, -1, -1, lab}; return nodeCnt; } // 当前节点的基尼写成整数分数(tot^2 - c0^2 - c1^2) / tot^2 long baseN (long) tot * tot - (long) c0 * c0 - (long) c1 * c1; long baseD (long) tot * tot; boolean found false; long bestNum 0, bestDen 1; int bestF -1, bestV 0; ListInteger bestL null, bestR null; // 平局规则特征编号从小到大同一特征内取值从小到大 // 基尼用整数交叉相乘比较只有严格变小才替换平局留下更小的特征/取值 for (int f 0; f 4; f) { TreeSetInteger vals new TreeSet(); for (int i : ids) vals.add(a[i][f]); for (int v : vals) { ListInteger L new ArrayList(), R new ArrayList(); for (int i : ids) { if (a[i][f] v) L.add(i); else R.add(i); } if (L.isEmpty() || R.isEmpty()) continue; // 一侧为空没意义 int[] lc stat(L), rc stat(R); long n1 L.size(), n2 R.size(); // 左右子集的基尼分子n^2 - c0^2 - c1^2 long g1 n1 * n1 - (long) lc[0] * lc[0] - (long) lc[1] * lc[1]; long g2 n2 * n2 - (long) rc[0] * rc[0] - (long) rc[1] * rc[1]; // 加权基尼通分num/den long num g1 * n2 g2 * n1; long den (long) tot * n1 * n2; // 只有严格降低基尼的切分才接受 if (num * baseD baseN * den) continue; if (!found || num * bestDen bestNum * den) { found true; bestNum num; bestDen den; bestF f; bestV v; bestL L; bestR R; } } } if (!found) { tree[nodeCnt] new int[]{-1, 0, -1, -1, lab}; // 无法降低基尼变成叶子 return nodeCnt; } int me nodeCnt; tree[me] new int[]{bestF, bestV, -1, -1, lab}; int leftChild build(bestL); // 先递归再回填孩子编号 int rightChild build(bestR); tree[me][2] leftChild; tree[me][3] rightChild; return me; } public static void main(String[] args) throws IOException { // 全程只用 nextInt 读整数避免 Scanner 在不同读取模式间切换造成错位 BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StreamTokenizer tk new StreamTokenizer(br); tk.nextToken(); int n (int) tk.nval; a new int[n][5]; for (int i 0; i n; i) for (int j 0; j 5; j) { tk.nextToken(); a[i][j] (int) tk.nval; } ListInteger ids new ArrayList(); for (int i 0; i n; i) ids.add(i); int root build(ids); StringBuilder sb new StringBuilder(); tk.nextToken(); int m (int) tk.nval; for (int k 0; k m; k) { int[] x new int[4]; for (int j 0; j 4; j) { tk.nextToken(); x[j] (int) tk.nval; } // 沿树往下走特征值等于切分值进左子树否则进右子树 int cur root; while (tree[cur][0] 0) cur x[tree[cur][0]] tree[cur][1] ? tree[cur][2] : tree[cur][3]; if (k 0) sb.append( ); sb.append(tree[cur][4]); } System.out.println(sb); } }Gopackage main import ( bufio fmt os sort ) var a [25][5]int // node 递归树的节点。叶子f -1lab 是预测类别内部节点特征 f、切分值 v、左右孩子 type node struct { f, v, left, right, lab int } var tree []node // stat 数样本集合里标签 0 和标签 1 各有多少个 func stat(ids []int) (int, int) { c0 : 0 for _, i : range ids { if a[i][4] 0 { c0 } } return c0, len(ids) - c0 } func build(ids []int) int { c0, c1 : stat(ids) tot : len(ids) // 叶子预测人数多的类别打平取编号小的 0 lab : 1 if c0 c1 { lab 0 } // 样本不足 2 个或标签已纯停止分裂 if tot 2 || c0 0 || c1 0 { tree append(tree, node{-1, 0, -1, -1, lab}) return len(tree) - 1 } // 当前节点的基尼写成整数分数(tot^2 - c0^2 - c1^2) / tot^2 baseN : int64(tot)*int64(tot) - int64(c0)*int64(c0) - int64(c1)*int64(c1) baseD : int64(tot) * int64(tot) found : false var bestNum, bestDen int64 bestF, bestV : -1, 0 var bestL, bestR []int // 平局规则特征编号从小到大同一特征内取值从小到大 // 基尼用整数交叉相乘比较只有严格变小才替换平局留下更小的特征/取值 for f : 0; f 4; f { valSet : map[int]bool{} for _, i : range ids { valSet[a[i][f]] true } vals : make([]int, 0, len(valSet)) for v : range valSet { vals append(vals, v) } sort.Ints(vals) for _, v : range vals { var L, R []int for _, i : range ids { if a[i][f] v { L append(L, i) } else { R append(R, i) } } if len(L) 0 || len(R) 0 { continue // 一侧为空没意义 } l0, l1 : stat(L) r0, r1 : stat(R) n1, n2 : int64(len(L)), int64(len(R)) // 左右子集的基尼分子n^2 - c0^2 - c1^2 g1 : n1*n1 - int64(l0)*int64(l0) - int64(l1)*int64(l1) g2 : n2*n2 - int64(r0)*int64(r0) - int64(r1)*int64(r1) // 加权基尼通分num/den num : g1*n2 g2*n1 den : int64(tot) * n1 * n2 // 只有严格降低基尼的切分才接受 if num*baseD baseN*den { continue } if !found || num*bestDen bestNum*den { found true bestNum, bestDen num, den bestF, bestV f, v bestL, bestR L, R } } } if !found { tree append(tree, node{-1, 0, -1, -1, lab}) // 无法降低基尼变成叶子 return len(tree) - 1 } me : len(tree) tree append(tree, node{bestF, bestV, -1, -1, lab}) lc : build(bestL) // 先递归再回填孩子编号 rc : build(bestR) tree[me].left lc tree[me].right rc return me } func main() { // 输入很小但按惯例把缓冲区放大防止大输入被截断 sc : bufio.NewScanner(os.Stdin) sc.Buffer(make([]byte, 1024*1024), 1024*1024) sc.Split(bufio.ScanWords) next : func() int { sc.Scan() v : 0 for _, c : range sc.Bytes() { v v*10 int(c-0) } return v } w : bufio.NewWriter(os.Stdout) defer w.Flush() n : next() for i : 0; i n; i { for j : 0; j 5; j { a[i][j] next() } } ids : make([]int, n) for i : range ids { ids[i] i } root : build(ids) m : next() for k : 0; k m; k { x : [4]int{} for j : 0; j 4; j { x[j] next() } // 沿树往下走特征值等于切分值进左子树否则进右子树 cur : root for tree[cur].f 0 { if x[tree[cur].f] tree[cur].v { cur tree[cur].left } else { cur tree[cur].right } } if k 0 { fmt.Fprint(w, ) } fmt.Fprint(w, tree[cur].lab) } fmt.Fprint(w, \n) }C#include stdio.h #include stdlib.h #define MAXN 25 #define MAXNODE 60 int a[MAXN][5]; /* 数样本集合里标签 0 和标签 1 各有多少个 */ void stat(int *ids, int cnt, int *c0, int *c1) { *c0 0; for (int i 0; i cnt; i) if (a[ids[i]][4] 0) (*c0); *c1 cnt - *c0; } /* 递归建树。叶子f -1lab 是预测类别内部节点特征 f、切分值 v、左右孩子 */ typedef struct { int f, v, left, right, lab; } Node; Node tree[MAXNODE]; int nodeCnt 0; int build(int *ids, int cnt) { int c0, c1; stat(ids, cnt, c0, c1); int tot cnt; /* 叶子预测人数多的类别打平取编号小的 0 */ int lab c0 c1 ? 0 : 1; /* 样本不足 2 个或标签已纯停止分裂 */ if (tot 2 || c0 0 || c1 0) { tree[nodeCnt] (Node){-1, 0, -1, -1, lab}; return nodeCnt; } /* 当前节点的基尼写成整数分数(tot^2 - c0^2 - c1^2) / tot^2 */ long long baseN (long long)tot * tot - (long long)c0 * c0 - (long long)c1 * c1; long long baseD (long long)tot * tot; int found 0, bestF -1, bestV 0; long long bestNum 0, bestDen 1; int bestL[MAXN], bestR[MAXN], bestLn 0, bestRn 0; int L[MAXN], R[MAXN]; /* 平局规则特征编号从小到大同一特征内取值从小到大 基尼用整数交叉相乘比较只有严格变小才替换平局留下更小的特征/取值 */ for (int f 0; f 4; f) { /* 收集该特征在节点内出现过的取值并排序取值最多 4 种 */ int vals[4], vn 0; for (int i 0; i cnt; i) { int v a[ids[i]][f], seen 0; for (int j 0; j vn; j) if (vals[j] v) seen 1; if (!seen) vals[vn] v; } for (int i 0; i vn; i) /* 小规模插入排序 */ for (int j i 1; j vn; j) if (vals[j] vals[i]) { int t vals[i]; vals[i] vals[j]; vals[j] t; } for (int vi 0; vi vn; vi) { int v vals[vi], ln 0, rn 0; for (int i 0; i cnt; i) { if (a[ids[i]][f] v) L[ln] ids[i]; else R[rn] ids[i]; } if (ln 0 || rn 0) continue; /* 一侧为空没意义 */ int l0, l1, r0, r1; stat(L, ln, l0, l1); stat(R, rn, r0, r1); long long n1 ln, n2 rn; /* 左右子集的基尼分子n^2 - c0^2 - c1^2 */ long long g1 n1 * n1 - (long long)l0 * l0 - (long long)l1 * l1; long long g2 n2 * n2 - (long long)r0 * r0 - (long long)r1 * r1; /* 加权基尼通分num/den */ long long num g1 * n2 g2 * n1; long long den (long long)tot * n1 * n2; /* 只有严格降低基尼的切分才接受 */ if (num * baseD baseN * den) continue; if (!found || num * bestDen bestNum * den) { found 1; bestNum num; bestDen den; bestF f; bestV v; for (int i 0; i ln; i) bestL[i] L[i]; for (int i 0; i rn; i) bestR[i] R[i]; bestLn ln; bestRn rn; } } } if (!found) { tree[nodeCnt] (Node){-1, 0, -1, -1, lab}; /* 找不到能降低基尼的切分变成叶子 */ return nodeCnt; } int me nodeCnt; tree[me] (Node){bestF, bestV, -1, -1, lab}; tree[me].left build(bestL, bestLn); tree[me].right build(bestR, bestRn); return me; } int main(void) { int n; if (scanf(%d, n) ! 1) return 0; for (int i 0; i n; i) for (int j 0; j 5; j) scanf(%d, a[i][j]); int ids[MAXN]; for (int i 0; i n; i) ids[i] i; int root build(ids, n); int m; scanf(%d, m); for (int k 0; k m; k) { int x[4]; for (int j 0; j 4; j) scanf(%d, x[j]); /* 沿树往下走特征值等于切分值进左子树否则进右子树 */ int cur root; while (tree[cur].f 0) cur x[tree[cur].f] tree[cur].v ? tree[cur].left : tree[cur].right; printf(%d%c, tree[cur].lab, k 1 m ? : \n); } return 0; }Pythonimport sys def main(): data sys.stdin.read().split() pos 0 def nxt(): nonlocal pos v int(data[pos]) pos 1 return v n nxt() a [[nxt() for _ in range(5)] for _ in range(n)] def stat(ids): # 数一下样本集合里标签 0 和标签 1 各有多少个 c0 sum(1 for i in ids if a[i][4] 0) return c0, len(ids) - c0 def build(ids): c0, c1 stat(ids) tot len(ids) # 叶子预测人数多的类别打平取编号小的 0 lab 0 if c0 c1 else 1 # 样本不足 2 个或标签已纯停止分裂 if tot 2 or c0 0 or c1 0: return [-1, lab] # 当前节点的基尼写成整数分数 (tot^2 - c0^2 - c1^2) / tot^2 base_n tot * tot - c0 * c0 - c1 * c1 base_d tot * tot best None # 平局规则特征编号从小到大同一特征内取值从小到大 # 基尼用分数比较只有严格变小才更新平局自然留下更小的特征/取值 for f in range(4): for v in sorted({a[i][f] for i in ids}): left [i for i in ids if a[i][f] v] right [i for i in ids if a[i][f] ! v] if not left or not right: continue # 一侧为空的切分没有意义 l0, l1 stat(left) r0, r1 stat(right) n1, n2 len(left), len(right) # 左右子集的基尼也写成整数分子 n^2 - c0^2 - c1^2 g1 n1 * n1 - l0 * l0 - l1 * l1 g2 n2 * n2 - r0 * r0 - r1 * r1 # 加权基尼 (g1/n1 g2/n2) / tot通分后是 num/den num g1 * n2 g2 * n1 den tot * n1 * n2 # 只有严格降低基尼的切分才接受num*base_d base_n*den if num * base_d base_n * den: continue if best is None or num * best[1] best[0] * den: best [num, den, f, v, left, right] if best is None: return [-1, lab] # 找不到能降低基尼的切分变成叶子 return [best[2], best[3], build(best[4]), build(best[5])] def ask(node, x): # 沿树往下走特征值等于切分值进左子树否则进右子树 while node[0] 0: node node[2] if x[node[0]] node[1] else node[3] return node[1] root build(list(range(n))) m nxt() ans [str(ask(root, [nxt() for _ in range(4)])) for _ in range(m)] print( .join(ans)) main()