本文最后更新于 159 天前，其中的信息可能已经有所发展或是发生改变。
摘要生成中
面对初中数学题里那个“分组使离差平方和最小”的猎奇难题，你是否还在苦思冥想手动试错？当大多数人被繁琐计算劝退时，有人直接用C++写出了一个暴力破解程序，瞬间将最优解从“猜谜”变成“秒出”。但这代码最震撼的不是它能算出答案，而是它用几行逻辑彻底颠覆了你对统计学的直觉认知——你以为的复杂优化，其实只是排序后的简单分割。想知道这套算法如何把教科书里的死题目变成动态演示吗？
— AI生成，仅供参考
该程序适用于数据分组，即分出组内离差平方和最小的2组
感谢同学开源。
背景
在《义务教育教科书 数学 八年级下册》（浙江教育出版社）的第78页出现了特别猎奇的题目：
To solve the problem,神人同学使用了十分牛逼，牛逼上天的C++编写了一个符合教科书中要求的程序。
程序设计
/*
用于计算如下问题：
给定一组数据x1,x2,...,xn
把这组数据分成两组，使组内离差平方和最小。
先输入n，再输入n个数，就可找出最优分组方案和对应的组内离差平方和
*/
#include<bits/stdc++.h>
using namespace std;
#define N 109
int n;
double a[N],sum[N];
int main()
{
scanf("%d",&n);
sum[0] = 0;
for(int i=1;i<=n;i++)
{
scanf("%lf",&a[i]);
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
sum[i] = sum[i-1] + a[i];
double x=1.0*sum[n]/n;
double d=0;
for(int i=1;i<=n;i++)
{
d += 1.0*(a[i]-x)*(a[i]-x);
}
printf("x=%.2lf D^2=%.2lf\n",x,d);
// 把前i个分成一组，剩余的分成另一组
double mn=1145141919810,ans;
for(int i=1;i<=n-1;i++)
{
double x1=1.0*sum[i]/i,x2=1.0*(sum[n]-sum[i])/(n-i);
double d12=d-1.0*i*(x1-x)*(x1-x)-1.0*(n-i)*(x2-x)*(x2-x);
if(d12<mn)
{
mn=d12;
ans = i;
}
for(int j=1;j<=i;j++)
{
if(j<i) printf("%.2lf ",a[j]);
else printf("%.2lf",a[j]);
}
printf("|");
for(int j=i+1;j<=n;j++)
{
printf("%.2lf ",a[j]);
}
printf(" %.2lf\n",d12);
}
printf("\n最优分组方案：\n");
for(int i=1;i<=ans;i++)
{
if(i<ans) printf("%.2lf ",a[i]);
else printf("%.2lf",a[i]);
}
printf("|");
for(int i=ans+1;i<=n;i++)
{
printf("%.2lf ",a[i]);
}
printf(" %.2lf\n",mn);
return 0;
}效果展示
本文采用 CC BY-NC-SA 4.0 国际许可协议进行许可。
转载请注明作者及原文链接，并遵循相同方式共享原则。
链接：
思路挺直接，排序后枚举，不错。
这代码看着舒服，没花里胡哨的。
如果数据是负数，排序后分组会不会有问题？
输出格式看着有点乱，能不能优化下排版？
之前做数据分析也写过类似的分组，不过用的K-means。
这代码风格，bits/stdc++.h好评，哈哈。
如果数据有重复值，分组结果会不会有多个最优解？
那要是数据本身是正态分布呢？还会有效吗？
好问题，重复值会导致多个分割点总离差平方和相同吧。
组内离差平方和最小不一定是最优吧，还要看组间差异？
其实组内最小化，组间差异自然就最大化了，等价吧。
之前做聚类也用过类似思路，不过是用Python写的。
数学题还能这么玩？666
现在谁还手算啊，早该出程序了😂
看不懂，但感觉很厉害的样子。
哈哈，教科书上的题终于有程序解了。
这波操作可以啊，变量名1145141919810笑死。
太贵了吧这也
笑死，这变量名太有灵性了。
如果数据量很大，这个算法还能用吗？
我试了下n=20也能跑，就是输出有点乱。
那个啥，求问这个咋改成三组的？