该算法实际应用:扎克伯格在大二的时候, 扎克伯格被女友甩了之后,一气之下黑了所有宿舍的相册,将所有女生的照片放在Facemash上供人评比.
大二的时候, 小石同学决定把这个过程都实现一遍. 但这只是在电影中描述, 小石同学决定亲自了解该算法并转换成可执行代码.
每个女生都有一个1400的基础颜值,,可称作“旧颜值”,在供人评比之后,将会通过公式计算出“新颜值”。
其实使用的是国际象棋比赛中,进行排名的一种算法.
埃洛等级分系统(Elo rating system)
假设女生A和B的当前颜值分别为RA和RB.
A对B的胜率期望值当为:
类似B对A的胜率为:
举例说明:
假如一位女生在比赛中的真实得分(胜=1分,和=0.5分,负=0分)和她的胜率期望值不同,则她的颜值要作相应的调整。
例如,女生A颜值为1613,与颜值为1573的女生B战平。若K取32,则A的胜率期望值为
因而A的新颜值RA为1613+32*(0.5-0.5573)=1611.166;
结合数据, 转换成公式
在不断的两两比较之后,由此可以得出他们的颜值排名。
然后就知道校花是谁了。
基本参数说明: 基础颜值:1400,K取32,胜=1分,和=0.5分,负=0分
比如实际输入数据第一行是:
---------------------------
1 2 1
----------------
表示 1号女生 和 2号女生比较 1号女生胜,
E1=1/(1+1)= 0.5, R1 = 1400+32*(0 - 0.5) = 1384
E2 = 0.5, R2 = 1400+32*(1-0.5) = 1416