买了个笔记本,结果里面什么软件也没有# Hardware - 计算机硬件
t*e
1 楼
1. 6 digits number, each changes from 0 to 9. Find the odds that sum of
first three is the same as the sum of last three.
大牛han6曾给出如下解答, 无奈小弟实在看不懂,哪位高人能出来详细解答一下
另小弟明早Bloomberg onsite, 请各位等我面经
发信人: han6 (周瑜), 信区: JobHunting
标 题: Re: 问几个brain teaser
发信站: BBS 未名空间站 (Tue Sep 28 14:46:27 2010, 美东)
每一个数字都是0~9的iid
一个数字的情况,总和为0~9的方法分别为
1, 1, 1, 1, 1, 1, 1, 1, 1, 1
两个数字的情况,总和为0~18的方法为以上的卷积
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
三个数字的情况,总和为0~27的方法为以上的卷积
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 63, 69, 73, 75, 75, 73, 69, 63, 55,
45,
36, 28, 21, 15, 10, 6, 3, 1
然后计算平方和为:55252
则概率为 55252/1000000
如果考官要你推广到m进制的n个数字相等(前后共2n个数字)
那么,可以告诉他,或者她:
利用 FFT 进行 logn 次卷积,其中最长的一次长度为 mn/2
总复杂度为:mnlog(mn)logn
不用FFT的话,由于卷积的特殊性,可以达到mn^2,考虑 FFT 的额外开销,实际速度可
能相差不
大。
如果这是一个二进制的问题,即每个数字只能是 0 或 1。那么无论多少个数
字都可以很容易的求出结果,因为其历次卷积得到了杨辉三角。
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
first three is the same as the sum of last three.
大牛han6曾给出如下解答, 无奈小弟实在看不懂,哪位高人能出来详细解答一下
另小弟明早Bloomberg onsite, 请各位等我面经
发信人: han6 (周瑜), 信区: JobHunting
标 题: Re: 问几个brain teaser
发信站: BBS 未名空间站 (Tue Sep 28 14:46:27 2010, 美东)
每一个数字都是0~9的iid
一个数字的情况,总和为0~9的方法分别为
1, 1, 1, 1, 1, 1, 1, 1, 1, 1
两个数字的情况,总和为0~18的方法为以上的卷积
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
三个数字的情况,总和为0~27的方法为以上的卷积
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 63, 69, 73, 75, 75, 73, 69, 63, 55,
45,
36, 28, 21, 15, 10, 6, 3, 1
然后计算平方和为:55252
则概率为 55252/1000000
如果考官要你推广到m进制的n个数字相等(前后共2n个数字)
那么,可以告诉他,或者她:
利用 FFT 进行 logn 次卷积,其中最长的一次长度为 mn/2
总复杂度为:mnlog(mn)logn
不用FFT的话,由于卷积的特殊性,可以达到mn^2,考虑 FFT 的额外开销,实际速度可
能相差不
大。
如果这是一个二进制的问题,即每个数字只能是 0 或 1。那么无论多少个数
字都可以很容易的求出结果,因为其历次卷积得到了杨辉三角。
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1