r*********n
发帖数: 4553 | 1 其实有限次方法也不是不可行的，因为电脑都是finite precision。
比如我给的方法，1/7用base 5来表示，小数点后面有无穷循环位，但是实际上考虑10
位就足够了，因为5^(-10)已经很小了，如果觉得不够就用20位，30位。
这种方法模拟出来的rand7()和真正的rand7()在用起来是没有差别的，因为在rand7()
重复之前，你的counter已经溢出了。 |
|
w********p
发帖数: 948 | 2 谢谢yishan， thrust， rainbowrain 的帮忙解释。
这样可以吗？ 假设rand5() 产生1，到 5， 用 rand5() 实现 rand7() 产生 1到7。
（和楼主的题，有点点不一样）
rand7() 用三个rand5（）， 每个rand5()产生一个bit. 每个rand5() 遇到5的时候
drop，这样可以吗？
public int rand7() {
int randNum = 0;
int returnNum = 0;
for ( int i=0; i<3; i++) {
while ( (randNum = rand5()) == 5 ) {
}
int bit = randNum % 2;
returnNum += (bit<
}
return returnNum;
}
这个最后是产生了0－7，还是不符合需要，不过可以过滤掉不想要的0。
这个和最佳答案比，思路还是差很多。 |
|
u*****o
发帖数: 1224 | 3 既然这个题的思路是equally distributed那么我们的目标就是每个数只有一种
表达式，那么可不可以GENERALIZE成下面的CASE呢
rand3 to rand5 => 3*rand3+rand3 map to 0-8; delete 5-8, map 0-4 to 0-4 by %5
（当然这个例子没什么意义）
rand7 to rand11 => 7*rand7+ rand7 map to 0-48; delete 40-48, map 0-39 to 0-
10 by %11; |
|
t****t
发帖数: 6806 | 4 这是个老题我再说一遍:
N次调用rand5()产生的等概率状态数是5^N. 正确产生rand7()需要的等概率状态数必须
是7的倍数. 5^N永远不能被7整除. 所以任何试图用有限次调用rand5()来产生有限个
rand7()的算法, 从数学上都必定是错误的. 正确的算法必定有一个无限循环调用rand5
().
这就好比用5进制写1/7. 如果有人说他有一个写法能用有限位5进制数写出1/7, 你不用
看他的结果就知道他是错的. |
|
s*******r
发帖数: 197 | 5 carreercup那本书上有解释啊
int rand7() {
while (1) {
int num = 5*(rand5()-1) + rand5() - 1;
if (num < 21) return num % 7;
}
} |
|
m****u
发帖数: 3915 | 6 carreercup那本书上有解释啊
int rand7() {
while (1) {
int num = 5*(rand5()-1) + rand5() - 1; // 得出[0,24]的平均分布
if (num < 21) return num % 7; //只取前21个, 前21个也是平均分布,然后mod 7
就行了
}
} |
|
c*******L
发帖数: 125 | 7 这个答案我觉得不严谨
rand5()产生的是[1,5]的均匀分布
但是最后产生的rand7()却是[0,6]的
应该再稍微修改一下
7 |
|
m*****k
发帖数: 64 | 8 莫非我看的书是旧版的？
那本书上先描述了怎么从rand2->rand3写。然后说
In order to generate a random number between 1 and 7, we just need to
uniformly generate
a larger range than we are looking for and then repeatedly sample until
we get a number that
is good for us. We will generate a base 5 number with two places with
two calls to the RNG.
int rand7() {
while (1) {
int num = 5*(rand5()-1) + rand5() - 1;
if (num < 21) return num % 7;
}
}
并没有解释怎么推到的。[0,24]的平均分布是怎么做出来的？谢谢
7 |
|
y****n
发帖数: 743 | 9 简单证伪：
rand5()返回整数，只可能有5种不同值；
那么，(6*rand5()/4)也只会有5种不同值。所以不是rand7() |
|
m*********g
发帖数: 170 | 10 rand5() 产生0，1，2，3，4的概率应该是一样的吧 -- 都是20%。
rand5()/4得到0，0.25，0.5，0.75，1。把0.5去掉后【0，1】的概率就一样了。
rand7() = rand5() + get012()
//我们用rand5()来得到0，2，4. 排除1和3.
int get012()
{
int res = 0;
do
{
res = rand5();
}
while(res ==1 || rand5() == 3)
return res / 2;
} |
|
L********e
发帖数: 159 | 11 这个不保证有限次实验内实现。rand5在有限次实验中只能产生5的幂种状态，不可能被
7整除从而实习均匀的rand7。最直观有效的方法就是rejec sampling吧。 |
|
t****t
发帖数: 6806 | 12 你要搞清楚>=2的不输出的意思. "不输出"是指如果出现>=2的情况, 就重来一次. 你不
能说使用者调用一次rand2()却没有得到结果, 对吧. 按照这个算法, 输出0或1的概率
就是1/2.
关键点在于"重来"是不能避免的, 而且一定是不定次数的重来. 凡是用有限次rand5()
产生rand7()(或者rand2(), rand3())的算法, 都一定是错的. |
|
y****n
发帖数: 743 | 13 (rand5() + rand5() +rand5() +rand5() + rand5() +rand5() +rand5() ) %7
不可行。
因为你不能保证结果是均匀的。
rand5()+rand5()+rand5()+rand5()+rand5()+rand5()+rand5()
结果为14的概率远远大于结果是0或28的概率。
thrust的解释是正确的，有限次rand5()不可能产生rand7()
number |
|
y****n
发帖数: 743 | 14 这个算法不对，Rand7()的值范围应该是[0..6]。
你的算法有可能返回7。 |
|
y****n
发帖数: 743 | 15 这道题相对高效一点的算法是：
public int Rand7()
{
int num = 100;
while (num >= 21)
num = Rand5() * 5 + Rand5();
return num / 3; //或者 return num % 7;
} |
|
w********p
发帖数: 948 | 16 没写清楚，我是想产生 用rand5() which create 1 to 5 to implement rand7() to
generate random number from 1 to 7 . 和楼主的原题有点点差别。思路相思。
不好意思，让大家迷惑了。不过还是多了个 0； 还是要修改下。 |
|
w***y
发帖数: 6251 | 17 太激动了，终于看到一个自认为我很明白可以掰扯几句的题目haha
我没仔细看过cc150上的答案，如果rand5的意思是1-5均匀分布，这个的答案应该是5*(
rand5-1)+rand5， 对应一个1-25的均匀分布； 如果rand5产生0-4的均匀分布，5*
rand5+rand5 对应一个0-24的均匀分布。
把rand5想象成一个5-side的骰子，两个骰子的结果计算到一起，就很好理解为什么这
个公式会生成另外range 25的均匀分布数字
一个range 25的均匀分布转化成rand7， 就是再用一下rejection和取模 |
|
t**a
发帖数: 33 | 18 Think about rand2 to rand3 firstly:
throw twice.
11=1
12=2
21 =3
22 rethrow
The left part is like binary number.
rand5 to rand7 can also work by throwing twice, you have 25 candidates, make
use of the first 21 to reduce the possibility of rethrow. |
|
m*****g
发帖数: 226 | 19 我怎么记得是
rand7()
{
i= rand5()*rand5();
if(i<=21) return i%7+1;
else return rand7();
}
样: |
|
h****8
发帖数: 599 | 20 来自主题: JobHunting版 - 问一个老题 如何用rand5（返回1~5） 来做一个rand7（返回1~7）的函数
答案如下但是不理解：
int rand7()
{
while (1)
{
int num = 5*(rand5() -1) + rand5（）- 1；
if (num < 21) return num % 7;
}
} |
|
x*****p
发帖数: 1707 | 21 Even the formula
5*(rand5 - 1) + (rand5 - 1) mod 7
can not generate an evenly distributed rand7
Assume rand5 generates 1, 2, 3, 4, 5, we set X = rand5 - 1
and Y = rand5 - 1. Then we have the following table for 5X + Y mod 7
X Y 5X+Y
0 0 0
0 1 1
0 2 2
0 3 3
0 4 4
1 0 5
1 1 6
1 2 0
1 3 1
1 4 2
2 0 3
2 1 4
2 2 5
2 3 6
2 4 0
3 0 1
... 阅读全帖 |
|
D***n
发帖数: 149 | 22 19.10 Write a method to generate a random number between 1 and 7, given
a method that generates a random number between 1 and 5 (i.e., implement
rand7() using rand5()).
看了书的答案还是不太明白啊。。。为什么rand2()用decision tree表示，到leaf会有
3的result？？
answer: public static int rand7()
{
while(true)
{
int num = 5 * ( rand5() - 1) + ( rand5() - 1);
if ( num < 21 ) return ( num % 7 + 1);
}
}
哪位高手能解释一下这段代码的正确性？？ |
|
n****e
发帖数: 678 | 23 Write a method to generate a random number between 1 and 7, given a method
that generates a random number between 1 and 5 (i.e., implement rand7()
using rand5()).
给出的解是：
public static int rand7() {
while (true) {
int num = 5 * (rand5() - 1) + (rand5() - 1);
if (num < 21) return (num % 7 + 1);
}
}
想问一下为什么这么做是对的？
如果这样写对吗？
while (true) {
int num = 5 * (rand5() - 1) + (rand5() - 1);
if (num < 7) return (num + 1);
}
或者
while (true) {
int num = 5 * (rand5() - 1) +... 阅读全帖 |
|
T**********a
发帖数: 15 | 24 //19.9Write a method to generate a random number between 1 and 7, given
a method
//that generates a random number between 1 and 5 (i.e., implement rand7(
) using
//rand5())
public static int rand5(){
return (int)(Math.random()*100) % 5+1;
}
public static int rand7() {
while (true) {
int num = 5 * (rand5() - 1) + (rand5() - 1);
if (num < 21) return (num % 7 + 1);
}
}
Question:
for the following line:
return (i... 阅读全帖 |
|
m*****n
发帖数: 5245 | 25 ☆─────────────────────────────────────☆
howiknow (dd) 于 (Sun May 3 01:21:24 2009) 提到:
how to do this?
thanks.
☆─────────────────────────────────────☆
yangcheng (牛魔王) 于 (Sun May 3 01:31:20 2009) 提到:
不行的
☆─────────────────────────────────────☆
hypocenter (振源) 于 (Sun May 3 01:33:23 2009) 提到:
这样不是平均分布的
☆─────────────────────────────────────☆
shuiguan (guanshui) 于 (Sun May 3 02:46:52 2009) 提到:
no can do
☆─────────────────────────────────────☆
algorithmics (沙盘推演) 于 (Sun Ma |
|
n******r
发帖数: 1247 | 26 int rand10(){
int x=rand5();
while (x==3) x=rand5();
if (x<3) return rand5();
else return rand5()+5;
}
int rand7(){
int x=rand10();
while (x>7) x=rand10();
return x;
} |
|
s*****i
发帖数: 355 | 27 a = rand31();
b = rand31();
c = (a-1)*31 + (b-1); //uniform distributed between 0 and 960
return c%32;
rand5 -> rand7 照葫芦画瓢的 |
|
o****d
发帖数: 2835 | 28 思路跟 rand5 rand7 一样
rand31() 产生每个数x1,x2...的概率是 1/2^31
所以产生一对(x1,x2)的概率就是 1/2^62
因为只需要2^32个数 于是将所有pair 每2^30形成一组就是了
于是就有了2^32个组，每组代表一个数就是了
具体实现上当然不需要用乘 那太大了
看x2的某一位（比如最高位）是0 还是1 就可以了
所以最终的答案就是从x2里面拿某一位插入到x1中的某一位就是了 |
|
P*******e
发帖数: 1353 | 29 general hiring，PhD，看大家讨论收获不说，也简单汇报一下。
坐了一晚上飞机题记不全了，简要说几个吧，老题比较多
1. implement queue using two stack
2. design an algorithm to return top 10 seached location on google map
3. rand5 -> rand7
4. binary search找最小测试序列用来reproduce runtime crash
5. biased coin toss
6. how to create password with a random password generate and a list of forb
idden strngs
7. if you can jump one or two stairs in one time, how many different ways to
climb N stairs. |
|
c****s
发帖数: 241 | 30 3)那个我错了，多谢，多谢。正确的应该是这个吧：
rand7(){
int i;
do{
i=(rand5()-1)*5+rand5();
} while(i>21);
return i%7;
} |
|
p******y
发帖数: 708 | 31 . rand5 -> rand7
有一种说法是：
产生一个5进制数，产生的方法就是用random5()-1产生该5进制数的各位权值，然后将
此数转换为10进制数对7求余。
不知道这种思路对不对 |
|
|
m*****k
发帖数: 64 | 33 我看了careercup,但是还不太理解，谁能解释一下么？ |
|
s*****i
发帖数: 355 | 34 你自己已经写出来了啊
5*(rand5()-1) 生成的是 0, 5,10,15,20各20％的概率
rand5()-1 是0,1,2,3,4各20％概率
两者相加，就是0-24各1/25的概率
天天啃算法，基本的概率和排列组合也要看看
mod |
|
m*****k
发帖数: 64 | 35 if (num < 21) return num % 7;
前21个也是平均分布,那么我取num<14也可以么？
7 |
|
|
E*******0
发帖数: 465 | 37 1. rand5()->rand2() and rand4();
2. we can find 11/12/13/14/21/22/23/24, and we can find uniform 12/13/14/21/
22/23/24.
for 1. If we have 5 balls (1,2,3,4,5), the prob of choosing each ball is 1/5
. If we only choose 3,4,5, the prob of choosing each ball (one of 3,4,5) is
1/3. So we can easily get rand2() and rand4().
for 2. since all the 8 cases are uniformly distributed, when we choose the
first ball as 1 and choose the second ball as 1, we just ignore it.
So we can get 7 cased uniformly distr |
|
K******g
发帖数: 1870 | 38 请教一下，为什么
已知rand[1,5], 求rand[1,7].
可以像下面一样做呢？
int rand7()
{
while (1)
{
int num = 5*(rand5() -1) + rand5（）- 1；
if (num < 21) return num % 7;
}
}
有什么理由吗？ |
|
s*******s
发帖数: 27 | 39 5*(rand5()-1) + (rand5()-1) gives rand24, which can be used to generate
rand7() |
|
f**********8
发帖数: 2276 | 40 int rand7()
{
while (1)
{
int num = 5*(rand5() -1) + rand5（）- 1；
if (num < 21) return num % 7;
}
}
谁能解释一下这个解答？看不懂 |
|
i**r
发帖数: 40 | 41 num = 5*(rand5() -1) + rand5（）- 1
Using two rand5() to generate uniformly distributed random number in the
range of [0, 24]
if (num < 21) return num % 7;
Discard num >= 21 so that rand7() will output random number [0..6] uniformly
. |
|
r*******l
发帖数: 511 | 42 用rand5 产生 rand7
5*(rand5 -1) + (rand5-1)
为啥不直接5*rand5 to get < 25, then mod 7?
谁来说说 |
|
x*****p
发帖数: 1707 | 43 So if rand5 is iid, then it is impossible to generate rand7 also with iid. |
|
l*******o
发帖数: 791 | 44 这样做行么？
unsigned short int rand_7()
{
bool high,middle,low;
high=rand5()>3?1:0;
middle=rand5()>3?1:0;
low=rand5()>3?1:0;
unsigned short int result=high*4+middle*2+low;
return result;
}
unsigned short int rand7()
{
unsigned short int res=rand_7();
while(!res)
{
res=rand_7();
}
return res;
} |
|
s*****n
发帖数: 5488 | 45 这题以前有讨论。以前也没理解就是记住了。今天推了一下。
int rand7()
{
int a;
while( (a=(rand5()-1)*5+(rand5()-1)) > 20 );
return a/3 + 1;
}
trick是，第一次生成5*[0..4],第二次生成[0..4],so 所有可能组合是
0 0
0 1
0 2
0 3
0 4
5 0
5 1
5 2
5 3
5 4
10 0
10 1
10 2
10 3
10 4
.....
从而生成了0 到24的等概率随机数。除去后面4个不需要的数，就是0..20的随机数。
退而光之，如果用rand x 生成rand y,x如果小于y.那么
先构成(rand x -1)* x + rand x -1 的随进数先。因为rand x - 1正好落在前面的空
隙中，不会出现重复。 |
|
s*****u
发帖数: 15 | 46 5*(rand5 - 1) + (rand5 - 1) 必须是7的倍数时，才可以mod7得到rand7.
具体倍数是多少只影响效率，不影响答案，所以取3*7最优。 |
|
|
x****3
发帖数: 62 | 48 刚拿到书, 还没看. 题是从http://www.crackingthecodinginterview.com考的. 感觉跟第4版差别不大.
Chapter 1 Arrays and Strings
1.1 Unique Characters in String
1.2 Reverse String in C
1.3 Check Permutation
1.4 Replace Spaces
1.5 String Compression
1.6 Rotate Image / Matrix
1.7 Set Row or Column to 0
1.8 Check Rotation Using isSubstring
Chapter 2 Linked Lists
2.1 Remove Duplicates
2.2 Find kth to Last Element
2.3 Delete Node from Middle
2.4 Partition List
2.5 Add Two Lists
2.6 Get Front of Loop in Circular List
2.7 Check ... 阅读全帖 |
|
x****3
发帖数: 62 | 49 刚拿到书, 还没看. 题是从http://www.crackingthecodinginterview.com考的. 感觉跟第4版差别不大.
Chapter 1 Arrays and Strings
1.1 Unique Characters in String
1.2 Reverse String in C
1.3 Check Permutation
1.4 Replace Spaces
1.5 String Compression
1.6 Rotate Image / Matrix
1.7 Set Row or Column to 0
1.8 Check Rotation Using isSubstring
Chapter 2 Linked Lists
2.1 Remove Duplicates
2.2 Find kth to Last Element
2.3 Delete Node from Middle
2.4 Partition List
2.5 Add Two Lists
2.6 Get Front of Loop in Circular List
2.7 Check ... 阅读全帖 |
|
d********t
发帖数: 9628 | 50 用rand5()产生rand7()，有大侠能指教的吗？ |
|
