c******a
发帖数: 198 | 1 1. Given a method (public int Rand()) that returns any random integer in the
int range, write a wrapper method that returns a random number within a
specific range [min, max], assuming int.MinValue <= min <= max <= int.
MaxValue.
my solution was: min + (Rand() - int.MinValue) * (max - min + 1) / (int.
MaxValue - int.MinValue + 1), and use long type to account for overflow
issue. is this solution correct?
2. Given a M*N matrix where some cells are blocked and there may or may not
be a cell which contains a target object. A person starts from a random cell
on the matrix and moves to find the object. You are given the below helper
method:
bool MoveUp() // Returns true and the person moves up if the upside adjacent
cell is within the border and is not blocked. Otherwise, returns false and
the person stays in current cell.
bool MoveDown()
bool MoveLeft()
bool MoveRight()
bool PickUp() // Returns true if the current cell contains the object.
Otherwise, returns false.
Describe the algorithm and write down the full code of a method (bool
FindObject(IPerson p)) to determine whether there is a target object on the
matrix or not. Note that the method takes an interface parameter. |
j********r
发帖数: 127 | 2 1. return min + (rand() - min) % (max - min + 1);
2. DFS (depth first search) or BFS (breadth first search)
the
not
cell
helper
【在 c******a 的大作中提到】
: 1. Given a method (public int Rand()) that returns any random integer in the
: int range, write a wrapper method that returns a random number within a
: specific range [min, max], assuming int.MinValue <= min <= max <= int.
: MaxValue.
: my solution was: min + (Rand() - int.MinValue) * (max - min + 1) / (int.
: MaxValue - int.MinValue + 1), and use long type to account for overflow
: issue. is this solution correct?
: 2. Given a M*N matrix where some cells are blocked and there may or may not
: be a cell which contains a target object. A person starts from a random cell
: on the matrix and moves to find the object. You are given the below helper
|
c******a
发帖数: 198 | 3 is this also correct or wrong? if wrong, what are potential issues? thanks.
min + Rand() * (max - min + 1) / (int.MaxValue - int.
MinValue + 1) |
j********r
发帖数: 127 | 4 溢出啊，来回类型cast啊，而且逻辑也完全错误，
你代入Rand() = 0, 和Rand()= int.MinValue算一下
min + Rand() * (max - min) / (int.MaxValue - int.
MinValue + 1)
【在 c******a 的大作中提到】
: is this also correct or wrong? if wrong, what are potential issues? thanks.
: min + Rand() * (max - min + 1) / (int.MaxValue - int.
: MinValue + 1)
|
f********y
发帖数: 156 | 5 From int_min to int_max, there are 2^32 numbers.
if 2^32 is not divisible by (max- min +1), then the probability is not
uniform.
【在 j********r 的大作中提到】
: 1. return min + (rand() - min) % (max - min + 1);
: 2. DFS (depth first search) or BFS (breadth first search)
:
: the
: not
: cell
: helper
|
j********r
发帖数: 127 | 6 两个整型区间互相映射，如果两者长度不互为倍数，不可能分布率完全一样。
【在 f********y 的大作中提到】
: From int_min to int_max, there are 2^32 numbers.
: if 2^32 is not divisible by (max- min +1), then the probability is not
: uniform.
|
c******a
发帖数: 198 | 7 sorry, my solution was below. this one should be logically correct. (the
previous one had a typo.)
min + (Rand() - int.MinValue) * (max - min + 1) / (int.MaxValue - int.
MinValue + 1)
【在 j********r 的大作中提到】
: 溢出啊，来回类型cast啊，而且逻辑也完全错误，
: 你代入Rand() = 0, 和Rand()= int.MinValue算一下
: min + Rand() * (max - min) / (int.MaxValue - int.
: MinValue + 1)
|
c******a
发帖数: 198 | 8 i like your modulo idea. but your solution may also have an overflow issue,
when rand() returns int.MaxValue and min is int.MinValue.
i think this modified one should work without overflow.
return min + rand() % (max - min + 1);
【在 j********r 的大作中提到】
: 两个整型区间互相映射，如果两者长度不互为倍数，不可能分布率完全一样。
|
T*****u
发帖数: 7103 | 9 bingo
【在 f********y 的大作中提到】
: From int_min to int_max, there are 2^32 numbers.
: if 2^32 is not divisible by (max- min +1), then the probability is not
: uniform.
|
f**********e
发帖数: 288 | |
l*n
发帖数: 529 | 11 需要想办法把(M, N)和(m, n)映射到(0, N-M)和(0, n-m)，这其中用long来处理
overflow。另外丢弃qmax*(n-m)<=x <=N-M的部分即可，以保证取模时的均匀分布。遇
到丢弃即重新拿一个随机数，最坏情况是丢弃近一半，但是5次不选中概率是1/(2^5)，
十次不中是1/(2^10)，最终期望是2次。
,
【在 c******a 的大作中提到】
: i like your modulo idea. but your solution may also have an overflow issue,
: when rand() returns int.MaxValue and min is int.MinValue.
: i think this modified one should work without overflow.
: return min + rand() % (max - min + 1);
|
