Lexi's Leetcode solutions

[summery] Random数总结

Posted on: October 12, 2013

Point:

  • randN() 表示能生成0~N-1这N个数。
  • 一般除呀余呀之类的都是从0开始最好,如果题中不是从0开始,自己-1最后再+1。
  • a % b就是(0, 1, …, b – 1),一共b个。

Example 1: 用randK()来实现randN() (K < N,用小的生产大的)

  1. 比如rand5() -> rand7()
  2. 想要生成0 – 20 evenly distributed
  3. int a = 5 * rand5() + rand5() = 5 * (0 … 4) + (0…4) = (0, 5, 10, 15, 20) + (0…4) = (0..24)
  4. 然后如果a < 3 * 7,, return a % 7
  5. if a >= 3 * 7, do it again

Example 2:  用randN()来实现randK()(用大的生成小的)

  1. 用rand10() -> rand4()
  2. 已经有(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
  3. 想生成(0, 1, 2, 3)
  4. 10 % 4 = 2, 说明%1, %2的几率由于最后两个数的出现比%别的的几率都大了。所以要想办法除掉最后两个数
  5. 所以rand10结果是8, 9的时候,扔掉重算
  6. rand10结果<8的时候,就可以用这个数%K,就是结果了。
Advertisements
Tags:

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: