b********a
发帖数: 5418 | 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.
2. 如何设计一套钞票的面值，使得当表示1~31的数字时，所需要的钞票总张数最小。
这个题目不是很清楚，是把这31个数字都表示出来一共所用钞票张数最小？还是要表示每一个数字所需
要的钞票张数都比其他方法需要的少？
3.A person is going inside a tunnel with length 100. The distance from him
to one end of the tunnel (which is behind him) is 30. A train behind is
also running towards him. The speed of the train is twice as fast as the
people. Is it good for him to turn back or he shoul | g******d
发帖数: 511 | 2
给定前三个数。有了和，就知道后三个数得出同样和的可能性是多少.
示每一个数字所需
http://www.mitbbs.com/article_t/JobHunting/31594253.html
这个少一个条件吧。Ａ在30处的时候,train离A多远?
【在 b********a 的大作中提到】
: 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.
: 2. 如何设计一套钞票的面值，使得当表示1~31的数字时，所需要的钞票总张数最小。
: 这个题目不是很清楚，是把这31个数字都表示出来一共所用钞票张数最小？还是要表示每一个数字所需
: 要的钞票张数都比其他方法需要的少？
: 3.A person is going inside a tunnel with length 100. The distance from him
: to one end of the tunnel (which is behind him) is 30. A train behind is
: also running towards him. The speed of the train is twice as fast as the
: people. Is it good for him to turn back or he shoul
| b********a
发帖数: 5418 | 3 2的链接我看过了，没讨论出所以然了啊。。。我第一反应也是2进制，可是有另外的人说不是最佳。。
。
【在 g******d 的大作中提到】
:
: 给定前三个数。有了和，就知道后三个数得出同样和的可能性是多少.
: 示每一个数字所需
: http://www.mitbbs.com/article_t/JobHunting/31594253.html
: 这个少一个条件吧。Ａ在30处的时候,train离A多远?
| c**********e
发帖数: 2007 | 4 1，2，4，8，16 is the answer.
You can not use 4 bills to express all from 1 to 31.
Neither you can use 5 bills with face values different from 1，2，4，8，16
to express all from 1 to 31.
人说不是最佳。。
【在 b********a 的大作中提到】
: 2的链接我看过了，没讨论出所以然了啊。。。我第一反应也是2进制，可是有另外的人说不是最佳。。
: 。
| c**********e
发帖数: 2007 | 5
He should go forward.
If the distance from the train to the tunnel is between 40 and 60, he will have time to get out by going forward, but do not have time to get out by going backward.
If the distance is less than 40, he will not get out either way.
If the distance is greater than 60, he will get out either way.
【在 b********a 的大作中提到】
: 2的链接我看过了，没讨论出所以然了啊。。。我第一反应也是2进制，可是有另外的人说不是最佳。。
: 。
| b********a
发帖数: 5418 | 6 有人给出了1，3，7，15的答案，1-31最多也是5张。
这个题目究竟是问什么？1，3，7，15比1，2，4，8，16少一张所以最优？
【在 c**********e 的大作中提到】
: 1，2，4，8，16 is the answer.
: You can not use 4 bills to express all from 1 to 31.
: Neither you can use 5 bills with face values different from 1，2，4，8，16
: to express all from 1 to 31.
:
: 人说不是最佳。。
| c**********e
发帖数: 2007 | 7 Using 1,3,7,15, how do you express 2?
I think each bill can be only used once. If it can be used more than once, it is another problem.
【在 b********a 的大作中提到】
: 有人给出了1，3，7，15的答案，1-31最多也是5张。
: 这个题目究竟是问什么？1，3，7，15比1，2，4，8，16少一张所以最优？
| i*****e
发帖数: 5233 | 8 1 1
【在 c**********e 的大作中提到】
: Using 1,3,7,15, how do you express 2?
: I think each bill can be only used once. If it can be used more than once, it is another problem.
| h**6
发帖数: 4160 | 9 3-1
it is another problem.
【在 c**********e 的大作中提到】
: Using 1,3,7,15, how do you express 2?
: I think each bill can be only used once. If it can be used more than once, it is another problem.
| n******h
发帖数: 50 | 10 用1 2 4 8 16表示1到31共需5×32/2=80张票子，亏了。 | | | A*********r
发帖数: 564 | 11 第一道题有谁算出来了么？
我算了半天，觉得这道题作为ｂｒａｉｎ ｔｅａｓｅｒ挺难的，最后的结果不是个好
数字（我的直觉告诉我应该是一个好看的数字，比如１／１０），很有可能我算错了。。
我从四位数开始：
任意一个２个位数的和ｋ范围是０．．１８， 假如用Ｆ（Ｋ）表示和为Ｋ的
２位数，则
Ｆ（ｋ）＝ｋ＋１ （ｋ＜１０）， ｏｒ １９－ｋ ｆｏｒ ｋ＞＝１０
这样对于任意一个已经选定的前两位数，如果和为Ｋ的话，则可能形成的四位数为（Ｆ
（ｋ）－１）＊Ｆ（ｋ） （当ｋ小于１０的时候要减去首位为０的情况）
Ｆ（ｋ）＊Ｆ（ｋ） 当ｋ不小于１０的时候
这样累加起来 ｓｕｍ｛１..9} { (k*(k+1) } +sum {10..18} { (19-k)^2} 就是所有
的前两位和后两位和相等四位数个数，然后除以所有的四位数个数 ９＊１０^3应该就
是所求得概率，我算的结果为 ６１５／９０００＝0.068
示每一个数字所需
【在 b********a 的大作中提到】
: 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.
: 2. 如何设计一套钞票的面值，使得当表示1~31的数字时，所需要的钞票总张数最小。
: 这个题目不是很清楚，是把这31个数字都表示出来一共所用钞票张数最小？还是要表示每一个数字所需
: 要的钞票张数都比其他方法需要的少？
: 3.A person is going inside a tunnel with length 100. The distance from him
: to one end of the tunnel (which is behind him) is 30. A train behind is
: also running towards him. The speed of the train is twice as fast as the
: people. Is it good for him to turn back or he shoul
| A*********r
发帖数: 564 | 12 提上来，看有没有大牛来解一解。。
。。
【在 A*********r 的大作中提到】
: 第一道题有谁算出来了么？
: 我算了半天，觉得这道题作为ｂｒａｉｎ ｔｅａｓｅｒ挺难的，最后的结果不是个好
: 数字（我的直觉告诉我应该是一个好看的数字，比如１／１０），很有可能我算错了。。
: 我从四位数开始：
: 任意一个２个位数的和ｋ范围是０．．１８， 假如用Ｆ（Ｋ）表示和为Ｋ的
: ２位数，则
: Ｆ（ｋ）＝ｋ＋１ （ｋ＜１０）， ｏｒ １９－ｋ ｆｏｒ ｋ＞＝１０
: 这样对于任意一个已经选定的前两位数，如果和为Ｋ的话，则可能形成的四位数为（Ｆ
: （ｋ）－１）＊Ｆ（ｋ） （当ｋ小于１０的时候要减去首位为０的情况）
: Ｆ（ｋ）＊Ｆ（ｋ） 当ｋ不小于１０的时候
| p********7
发帖数: 549 | | A*********r
发帖数: 564 | 14 感觉有点像扔三个筛子，然后求两次扔的和相等的概率是多少，不过这个目前网上也没
有找到正解。。
我都想写程序直接穷举了。。
【在 p********7 的大作中提到】
: 第一个题感觉很难
| p********7
发帖数: 549 | 15 比执塞子难，这个还有开头不是0的情况考虑
【在 A*********r 的大作中提到】
: 感觉有点像扔三个筛子，然后求两次扔的和相等的概率是多少，不过这个目前网上也没
: 有找到正解。。
: 我都想写程序直接穷举了。。
| h**6
发帖数: 4160 | 16 每一个数字都是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。那么无论多少个数
字都 | A*********r
发帖数: 564 | 17 哇，你这个算的Ｆ（ｋ）跟我的一样，看来我原来的思路还是对的。。
不过我从两个数字推导到三个数字花了好长时间，能说说你是怎么这么快得到卷积的么？
45,
【在 h**6 的大作中提到】
: 每一个数字都是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
| A*********r
发帖数: 564 | 18 对，我刚开始也试了二进制和四进制，发现都比１０进制的递推公式简单一些，而且套
不起来。。
【在 h**6 的大作中提到】
: 每一个数字都是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
| h**6
发帖数: 4160 | 19 前面是1到10的和，然后每次加上两项的差，+8，+6，+4，+2，+0，后面是对称的-2，-
4，-6，-8…… | A*********r
发帖数: 564 | 20 就本题而言，最后的概率应该不是平方和，因为要刨去首位为０的情况，不过只要有了
Ｆ（ｋ）， 其他的算起来就很简单了。。
45,
【在 h**6 的大作中提到】
: 每一个数字都是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
| | | A*********r
发帖数: 564 | 21 去查了一下卷积和ＦＦＴ，看来要算法和数学都牛才能达到这个提纲挈领的水平。。
多谢ｈａｎ６答疑。。
45,
【在 h**6 的大作中提到】
: 每一个数字都是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
| p********7
发帖数: 549 | | p********7
发帖数: 549 | 23 这个题太变态了，一定是6位数，搞的还有那么多例外出来 | A*********r
发帖数: 564 | 24 对啊，积分不熟练的人如我，从二位推三位的时候，就这么一个式子
Ｆ3(k)=sum{ {i=0..9} {F2(k-i)} }
想要得到最后的Ｆ３（ｋ）的表达式（只包含ｋ），我推得满头大汗，早知道是积分，
我就不应该去推的。。 后来放弃成递归公式，跟ｈａｎ６的不谋而合：
F3(k)=
F3(k-1)+ F2(k) if k<10
F3(k-1)+F2(k)-F(k-10) 10<=k<19
F3(k-1)-F(k-10) k>=19
【在 p********7 的大作中提到】
: 从2位推3位发现果然是积分，好解法
|
|
