Random Generator

Question

给一个1到3的random generator，构造一个1到n的random generator。

Solution

用3进制数来求解。首先求出n至少需要几位3进制数来表示，假设需要x位。然后利用1到3的random generator来产生依次产生每一位上的随机数（因为3进制每一位上是0到2，所以要将得到的随机数－1）。再将得到的随机数转化为十进制整数。因为x位3进制的数能表示的十进制的数的范围是0~3^x - 1，因此得到的随机数可能比n大。如果得到的结果大于n，则重新产生随机数。

如果调用这个n random generator很多次，很可能产生很多次重复的随机数。因此，可以将得到的合法3进制的数及其对应的十进制的数保存在一个table里来优化时间。每次产生一个随机数，就和n比较，如果大于n，则重新产生，否则去table寻找其对应的十进制数。如果没有找到，则说明该随机数第一次产生，将该随机数的3进制及其十进制形式保存在table里。