能用水泥补树洞吗？ - 未名空间MITBBS历史存档

t*e2016-12-23 08:12

1 楼

一道非常基础的题，我觉得自己是不是理解不对，请大牛们赐教。
career cup 150上的：
given a generator for random number 1 to 5, write a generator for random
number 1 to 7.
书上有很长的分析，最后给了一个有点复杂的code。
一模一样的题在leetcode上也有：http://www.leetcode.com/2010/11/rejection-sampling.html
也是长篇分享，最后有复杂的code。
我就想的特简单：同时run两个random5（），那么random5() + random5()的范围就是
2 to 10。
然后取 2 to 8这一段，除7取模，不就好了？
这样对吗？那那些个分析都什么意思呢？

h*22016-12-23 08:12

2 楼

新买的房子，门口有颗百年芙蓉树，模样很不错。可惜中间一个大树洞，里面的木头如
棉絮。为了安全，恐怕得把它给锯了。但是又有点舍不得，毕竟是百年大树，还会开花。
谁知道怎么修补那个树洞？能不能简单地把水泥灌进去凝固？

i*h2016-12-23 08:12

3 楼

这样难道出来的不都是偶数了？

【在 t********e 的大作中提到】

: 一道非常基础的题，我觉得自己是不是理解不对，请大牛们赐教。
: career cup 150上的：
: given a generator for random number 1 to 5, write a generator for random
: number 1 to 7.
: 书上有很长的分析，最后给了一个有点复杂的code。
: 一模一样的题在leetcode上也有：http://www.leetcode.com/2010/11/rejection-sampling.html
: 也是长篇分享，最后有复杂的code。
: 我就想的特简单：同时run两个random5（），那么random5() + random5()的范围就是
: 2 to 10。
: 然后取 2 to 8这一段，除7取模，不就好了？

h*22016-12-23 08:12

4 楼

好像不能用水泥；
How to Patch a Hole in a Tree Trunk
The recommended method for patching a tree hole is to use a thin metal flap
or screening covered with plaster over the tree hole. This will prevent
animals and water from entering the hole and create a surface that the bark
and outer living layers can eventually grow back over.
Before patching a tree hole, it is a good idea to remove any water from the
hole and any soft rotted wood. Do not remove any wood that is not soft as
this can damage the outer layer of the tree and allow disease and rot to
enter the living part of the tree.

N*N2016-12-23 08:12

5 楼

要求应该是分布要一样吧
假设原来两个都是uniform，加起来就不是uniform
回忆一下中心极限定理，如果很多个uniform相加，就接近正态分布了

【在 t********e 的大作中提到】

: 一道非常基础的题，我觉得自己是不是理解不对，请大牛们赐教。
: career cup 150上的：
: given a generator for random number 1 to 5, write a generator for random
: number 1 to 7.
: 书上有很长的分析，最后给了一个有点复杂的code。
: 一模一样的题在leetcode上也有：http://www.leetcode.com/2010/11/rejection-sampling.html
: 也是长篇分享，最后有复杂的code。
: 我就想的特简单：同时run两个random5（），那么random5() + random5()的范围就是
: 2 to 10。
: 然后取 2 to 8这一段，除7取模，不就好了？

h*22016-12-23 08:12

6 楼

howard Feed N Wax 防止进一步腐烂。
Wound Dressings to Slow Decay: Howard Feed-N-Wax - Prune Like a Pro

t*e2016-12-23 08:12

7 楼

不好意思 typo 是random5() + random5() 独立的，已经改了

【在 i***h 的大作中提到】

: 这样难道出来的不都是偶数了？

h*22016-12-23 08:12

8 楼

看了一下网络内容，打算如下：
1.清理树洞内松软的木头。
2.找个类似于Howard Feed-N-Wax - Prune 内壁刷一下避免进一步腐烂。
3.洞口拿铝泊纸折叠几次堵住洞口。
4.用水泥在铝泊纸表面刷一下，彻底封住洞口。
5.水泥凝固后，表面再用Howard Feed-N-Wax - Prune 刷一遍，避免雨水进入水泥周围
的伤口。
大家看看我的计划怎样？

t*e2016-12-23 08:12

9 楼

是的，要求是uniform

【在 N**N 的大作中提到】

: 要求应该是分布要一样吧
: 假设原来两个都是uniform，加起来就不是uniform
: 回忆一下中心极限定理，如果很多个uniform相加，就接近正态分布了

h*22016-12-23 08:12

10 楼

If you decide to cap the hole, start by scraping out as much of the soft,
rotted wood as you can. Then cover the hole with a piece of aluminum sheet
metal, which won't rust. Cut it so that it overlaps the edges of the hole by
a half inch or so, then bed the metal in a fat bead of silicone sealant and
tack it in place with a few 1¼-inch stainless-steel siding nails.
You can paint the patch to blend in with the rest of the trunk.
If you seal the hole with foam, remove the rotted wood first, then use a
canned spray that's formulated to fill big gaps. Once it hardens, trim the
excess so that it will shed water. And be sure to paint the plug; sunlight
breaks down unprotected foam.

i*h2016-12-23 08:12

11 楼

1 + 1 = 2
1 + 2 = 3
2 + 1 = 3
2 + 2 = 4
所以random2() + random2()不是 random3（）

【在 t********e 的大作中提到】

: 不好意思 typo 是random5() + random5() 独立的，已经改了

y*22016-12-23 08:12

12 楼

不懂，不过看你做了这么仔细的研究，应该错不了，赞一个 👍
对了，恭贺乔迁之喜：）

花。

【在 h***2 的大作中提到】

: 新买的房子，门口有颗百年芙蓉树，模样很不错。可惜中间一个大树洞，里面的木头如
: 棉絮。为了安全，恐怕得把它给锯了。但是又有点舍不得，毕竟是百年大树，还会开花。
: 谁知道怎么修补那个树洞？能不能简单地把水泥灌进去凝固？

t*e2016-12-23 08:12

13 楼

wiki上搜到的
The sum of two independent, equally distributed, uniform distributions
yields a symmetric triangular distribution.
我原来果然想得太简单了

T*m2016-12-23 08:12

14 楼

我看到有人用水泥补树洞的。

花。

【在 h***2 的大作中提到】

: 新买的房子，门口有颗百年芙蓉树，模样很不错。可惜中间一个大树洞，里面的木头如
: 棉絮。为了安全，恐怕得把它给锯了。但是又有点舍不得，毕竟是百年大树，还会开花。
: 谁知道怎么修补那个树洞？能不能简单地把水泥灌进去凝固？

N*N2016-12-23 08:12

15 楼

那就是leetcode上的答案，其实不难：
用两个rand5()得到一个范围更大的均匀分布，然后只取出其中1-7的部分就行，或者在
这个范围取出7的整数倍个

【在 t********e 的大作中提到】

: 是的，要求是uniform

h*22016-12-23 08:12

16 楼

一个英文网站说可能以后锯树的人不知道里面有水泥因此受伤，所以有点犹豫。所以打
算先塞进塑料袋塞满，表面再覆盖铝箔纸弄平，最后在表面再覆盖薄水泥。就不知这样
能不能行。

【在 T*******m 的大作中提到】

: 我看到有人用水泥补树洞的。
:
: 花。

g*e2016-12-23 08:12

17 楼

rand5 * rand5 does not yield 1-25 uniform distribution...

【在 N**N 的大作中提到】

: 那就是leetcode上的答案，其实不难：
: 用两个rand5()得到一个范围更大的均匀分布，然后只取出其中1-7的部分就行，或者在
: 这个范围取出7的整数倍个

i*h2016-12-23 08:12

18 楼

rand5 * 5 + rand5

【在 g**e 的大作中提到】

: rand5 * rand5 does not yield 1-25 uniform distribution...

g*e2016-12-23 08:12

19 楼

wrong again

【在 i***h 的大作中提到】

: rand5 * 5 + rand5

i*h2016-12-23 08:12

20 楼

you mean
(rand5 - 1) * 5 + rand5
?

【在 g**e 的大作中提到】

: wrong again

f*w2016-12-23 08:12

21 楼

尼马 rand5()*rand5()这个连7都没有，还均匀分布
run 两次是 run 两次
第一次的结果是i, 第二次的结果是j
let x = i*5 + j, then u get 1-25 evenly distributed

【在 N**N 的大作中提到】

: 那就是leetcode上的答案，其实不难：
: 用两个rand5()得到一个范围更大的均匀分布，然后只取出其中1-7的部分就行，或者在
: 这个范围取出7的整数倍个

g*e2016-12-23 08:12

22 楼

面试的时候最好一次答对，或者在面试官发问之前发现问题

【在 i***h 的大作中提到】

: you mean
: (rand5 - 1) * 5 + rand5
: ?

N*N2016-12-23 08:12

23 楼

我没仔细看，理解错了。。改了。。

【在 g**e 的大作中提到】

: rand5 * rand5 does not yield 1-25 uniform distribution...

s*n2016-12-23 08:12

24 楼

如果说不是整数的话，
rand（5）来7次，(rand_1(5) + rand_2(5) + rand_3(5) + rand_4(5) + rand_5(5) )
/7

是

【在 t********e 的大作中提到】

: 一道非常基础的题，我觉得自己是不是理解不对，请大牛们赐教。
: career cup 150上的：
: given a generator for random number 1 to 5, write a generator for random
: number 1 to 7.
: 书上有很长的分析，最后给了一个有点复杂的code。
: 一模一样的题在leetcode上也有：http://www.leetcode.com/2010/11/rejection-sampling.html
: 也是长篇分享，最后有复杂的code。
: 我就想的特简单：同时run两个random5（），那么random5() + random5()的范围就是
: 2 to 10。
: 然后取 2 to 8这一段，除7取模，不就好了？

i*h2016-12-23 08:12

25 楼

这个。。。

)

【在 s*****n 的大作中提到】

: 如果说不是整数的话，
: rand（5）来7次，(rand_1(5) + rand_2(5) + rand_3(5) + rand_4(5) + rand_5(5) )
: /7
:
: 是

N*N2016-12-23 08:12

26 楼

也不能。。加了就不是均匀分布了
不是整数就简单了，均匀分布乘一个常数和加一个常数都仍然是均匀分布，scale然后
平移就可以变成任意均匀分布

)

【在 s*****n 的大作中提到】

: 如果说不是整数的话，
: rand（5）来7次，(rand_1(5) + rand_2(5) + rand_3(5) + rand_4(5) + rand_5(5) )
: /7
:
: 是

m*x2016-12-23 08:12

27 楼

感觉现在板上的水平比半年到一年前下降很多。看来牛人都找到满意的工作了。呵呵

【在 N**N 的大作中提到】

: 也不能。。加了就不是均匀分布了
: 不是整数就简单了，均匀分布乘一个常数和加一个常数都仍然是均匀分布，scale然后
: 平移就可以变成任意均匀分布
:
: )

g*e2016-12-23 08:12

28 楼

从来都是这样轮回的，这是个牛人辈出的时代。只有我这样混吃等死的还混迹于job
hunting

然后

【在 m*x 的大作中提到】

: 感觉现在板上的水平比半年到一年前下降很多。看来牛人都找到满意的工作了。呵呵

c*p2016-12-23 08:12

29 楼

两个uniform random一加，结果就不平均了。
你想想扔两个骰子，点数和是7的概率最大，是2和12的概率最小。
所以概率不是平均分布的。

是

【在 t********e 的大作中提到】

: 一道非常基础的题，我觉得自己是不是理解不对，请大牛们赐教。
: career cup 150上的：
: given a generator for random number 1 to 5, write a generator for random
: number 1 to 7.
: 书上有很长的分析，最后给了一个有点复杂的code。
: 一模一样的题在leetcode上也有：http://www.leetcode.com/2010/11/rejection-sampling.html
: 也是长篇分享，最后有复杂的code。
: 我就想的特简单：同时run两个random5（），那么random5() + random5()的范围就是
: 2 to 10。
: 然后取 2 to 8这一段，除7取模，不就好了？

c*p2016-12-23 08:12

30 楼

这个就错得离谱了吧。。。

)

【在 s*****n 的大作中提到】

: 如果说不是整数的话，
: rand（5）来7次，(rand_1(5) + rand_2(5) + rand_3(5) + rand_4(5) + rand_5(5) )
: /7
:
: 是

z*w2016-12-23 08:12

31 楼

int cal() {
int c = 0;
while (true) {
int a = rand5();
int b = rand5();
a --;
b --;
c = a * 5 + b;
if (c < 21) break;
}
int res = c % 7;
return res + 1;
}

g*y2016-12-23 08:12

32 楼

不要妄自菲薄，任何时候版上的水平相差不大，都是正态分布，水平高的不一定爱出来
说话。
不能因为能否快速正确地解一道题来判断水平，就好像面试一样，我觉得最有效的不是
面面俱到地cover每一个题，而是在有些题上有很好的发挥，就足够impress对方了。
培训的时候教练说了一句：你面试的所有目的，是看未来的5年，你想跟这个人天天一
起工作吗？
我不会要求同事是从来都正确的圣人，但我希望他有与众不同的地方。

【在 m*x 的大作中提到】

: 感觉现在板上的水平比半年到一年前下降很多。看来牛人都找到满意的工作了。呵呵

S*12016-12-23 08:12

33 楼

From wiki,
The central limit theorem (CLT) states that, given certain conditions, the
mean of a sufficiently large number of independent random variables, each
with finite mean and variance, will be approximately normally distributed.[1
]

S*12016-12-23 08:12

34 楼

Therefore, run random7 once, to get each row uniformed. Then run rondom7
again, to get each column uniformed. Using a matrix will help to understand
why the 49 cells are uniformed.

[1

【在 S******1 的大作中提到】

: From wiki,
: The central limit theorem (CLT) states that, given certain conditions, the
: mean of a sufficiently large number of independent random variables, each
: with finite mean and variance, will be approximately normally distributed.[1
: ]

w*o2016-12-23 08:12

35 楼

为什么不能用rand5（）* 5 + rand5()?
我看没什么问题，关键看你怎么取舍数字。
比如：
int ret = 0;
while(ret < 10)
ret = rand5() * 5 + reand5()；
return (ret % 7) + 1;

【在 g**e 的大作中提到】

: wrong again

g*e2016-12-23 08:12

36 楼

这样当然是可以的。大路解法不是抛弃大于21的数字嘛

【在 w***o 的大作中提到】

: 为什么不能用rand5（）* 5 + rand5()?
: 我看没什么问题，关键看你怎么取舍数字。
: 比如：
: int ret = 0;
: while(ret < 10)
: ret = rand5() * 5 + reand5()；
: return (ret % 7) + 1;

t*a2016-12-23 08:12

37 楼

我的思路是扔两个5面体色子r1,r2，组合出一个新数字x=(r1-1)*5+r2-1
x就会均匀落在[0,24],截去尾部得到[0,20]
然后算x/3整除的结果，会落在[0,6]中
R code以及数值实验（用这个新色子扔1million次之后看分布状况）参见如下链接
http://kangtu.me/~kangtu/study/interview.html#sec-10

是

【在 t********e 的大作中提到】

: 一道非常基础的题，我觉得自己是不是理解不对，请大牛们赐教。
: career cup 150上的：
: given a generator for random number 1 to 5, write a generator for random
: number 1 to 7.
: 书上有很长的分析，最后给了一个有点复杂的code。
: 一模一样的题在leetcode上也有：http://www.leetcode.com/2010/11/rejection-sampling.html
: 也是长篇分享，最后有复杂的code。
: 我就想的特简单：同时run两个random5（），那么random5() + random5()的范围就是
: 2 to 10。
: 然后取 2 to 8这一段，除7取模，不就好了？