w*****3
发帖数: 101 | | j*****u
发帖数: 1133 | 2 FT，
让你自己写random函数？
【在 w*****3 的大作中提到】
: java
: 不准用
: math.random()
| r******d
发帖数: 308 | 3 不知道标准的shuffle card是什么算法
我每次洗牌都把牌分成两半， 然后左边一张， 右边一张地把牌混起来。
那用一个array放入所有的牌， 反复call一个洗牌的函数。 在那个函数里面把牌的前
面一半和后面一般间隔混起来？
void fun()
{
.....
for ( int i =1; i
{
card_after[i]=card_before[i];
card_after[i+1]=card_before[i+n/2];
}
} | I**********s
发帖数: 34 | 4 http://en.wikipedia.org/wiki/Shuffling
"Shuffling algorithms
In a computer, shuffling is equivalent to generating a random permutation of
the cards. There are two basic
algorithms for doing this, both popularized by Donald Knuth.
The first is simply to assign a random number to each card, and then to sort
the cards in order of their random
numbers. This will generate a random permutation, unless any of the random
numbers generated are the
same as any others (i.e. pairs, triplets etc). This can be eliminated either
assigning new random numbers to
these cases, or reduced to an arbitrarily low probability by choosing a
sufficiently wide range of random
number choices. If using efficient sorting such as mergesort or heapsort,
this is an O(n log n) algorithm.
The second, generally known as the Knuth shuffle or Fisher–Yates shuffle,
is a linear-time algorithm which
involves moving through the pack from top to bottom, swapping each card in
turn with another card from a
random position in the part of the pack that has not yet been passed through
(including itself). Providing that
the random numbers are unbiased, this will always generate a random
permutation."
【在 w*****3 的大作中提到】
: java
: 不准用
: math.random()
| w*****3
发帖数: 101 | 5 这题是MS的onsite题，
我觉得random是必须的吧，
难道这题是压力测试？ | E********a
发帖数: 124 | 6
you are talking about perfect shuffling, like A1A2A3B1B2B3 <-> A1B1A2B2A3B3
I guess lz talked about random shuffling
【在 r******d 的大作中提到】
: 不知道标准的shuffle card是什么算法
: 我每次洗牌都把牌分成两半， 然后左边一张， 右边一张地把牌混起来。
: 那用一个array放入所有的牌， 反复call一个洗牌的函数。 在那个函数里面把牌的前
: 面一半和后面一般间隔混起来？
: void fun()
: {
: .....
: for ( int i =1; i: {
: card_after[i]=card_before[i];
|
|
