前两天看到一道小米的面试题

[mskf]

是这样的，如果你玩过 dota2 的话，很简单一句话，n 个球的卡尔有多少个技能

没玩过的话，大概介绍一下，卡尔有三个球，冰球 Q，雷球 W，火球 E，不同的组合对应不同的技能 QQQ （极冷）,QQW （峰哥漫步）,QQE （冰墙）,WWW （磁暴）,WWQ （吹风）,WWE （灵动迅捷）,EEQ （火人）,EEW （陨石）,EEE （天火）,QWE （推波）一共十个技能（不算天赋）

所以说如果卡尔有 4 个球，或者 n 个球，他会有几个技能呢

[trcnkq]

(n+2)*(n+1)/2

[jin5354]

f(n) = C(n-1, 2n-1)
查了下资料，这种解法真是太巧了，f(4) = C(3, 7) = 35

[siyemiaokube]

高中 oi 选手让各位再感受一些压力吧(◐‿◑)
上面说到的 C(n-1, 2n-1)，其实可以再展开说好多，不妨从“生成函数”入手查一些资料

[siyemiaokube]

@HeavenlyChorus
>只想说一句 r-combination 的 r 应该是写在后面的，如此:C(n,r),楼上几位都写反了

“ C ”这种苏式组合数记法，一般默认上标在前下标在后。美式的括号记法，确实是(n,r)

[staticer]


[HeavenlyChorus]

@siyemiaokube 学习了 我学校教的是我说的那样

[atVoid]

有放回组合问题，推导挺有意思的。https://zhuanlan.zhihu.com/p/33841038 C(n+m-1,n-1) n 个球 m 个框(盒子)

[NullPoint]

没太懂，QQE EQQ QEQ EEQ EQE QEE，算俩技能

[whi147]

(r+n-1)!/r!(n-1)! r=4 n=4

[seraphv3]

有 3 个按键，QWE，需要按 3 次，相当于把 3 个球（ 3 次按键的动作）放到 3 个盒子（ QWE ）中，找出可区分的排布数。
3 个盒子有 2 个隔板，这 2 个隔板和 3 个球一起就有 5 个位置，5 个位置中任选 2 个放隔板，其他的就是球，所以就是 C(2,5)
Q W E
|x |x |x |
|xx |x | |
|x |xx | |
...
|xxx| | |
| |xxx| |


PS:盒子中放球的模型不像想象的那么简单，统计力学里面有 Maxwell-Boltzmann 统计（比如气体分子）、Fermi-Dirac 统计（比如电子）、Bose-Einstein 统计（比如光子），用这道题的统计方式来统计样本空间（不同的排布是可区分的）就对应于 Bose-Einstein 统计，有一个简单的 Polya ’ s urn model 可以实现它

[calpes]

@coderluan 其实我是这么理解的，一定的数学基础是合格程序员的先决条件，如果你没有高中水平的数学知识，你根本不可能是一个合格的程序员，如果我是面试官(事实上我确实是)，我一定不会给一个没有数学常识的人任何机会。

[mxalbert1996]

@coderluan 因为你让我觉得没有跟你沟通的必要。一个对算法稍微有点理解的人也至少不会把算法和公式对立起来。

[laydown]

如果 4 个球的话，按 1 个键就是 4 种，按 2 个键，就是 10 种，按 3 个键就是 20 种，按 4 个键就是 35 种，合起来就是 4+10+20+35，共 69 种。

重复组合的概念。

[ihciah]

卡特兰数？

[mingl0280]

@lxy42 O(n^4)的算法和数学的 O(1)的算法，是正常人都知道该用啥……

[mingl0280]

@coderluan 这道题只需要高中水平的数学知识，如果你连这点知识都没有，最好别称自己为程序员，笑掉大牙的。

[Variazioni]

这年头没玩过 dota2 都不能去小米了？

[graysheeep]

qqwrv

[coderluan]

@calpes 是啊，所以我说的一直都加上了， “更” “不能满足”“没谁高级”“相辅相成” ，不知道你们咋理解的成我吹算法捧数学的。

[coderluan]

@mxalbert1996 是有人先说的数学更高级，我反驳他时明确用了“相辅相成的东西，何来的”更高级“？”#13

你还能理解成我把“算法和公式对立”。我也不知道咋和你沟通了。再送你句 “我只能说我觉你根本没理解语文是个什么东西”。