使用恒定的随机性源选择0到n之间的随机数。

Question

任务

给定一个正整数n小于以任何方式指定为输入的2^30，您的代码应该在0和n之间输出一个随机整数，包括在内。你所生成的数字应该被随机一致地选择。也就是说，从0到n的每个值都必须以相同的概率出现(参见规则和警告)。

规则和

注意事项

您的代码可以假设，任何内置于您的语言或标准库中的随机数生成器，如果声称是一致随机的，实际上是一致的。也就是说，您不必担心所使用的随机源的质量。然而，

• 您必须确定，如果您使用的随机源是统一的，那么您的代码将正确地从0输出一个统一的随机整数到n。
• 在调用内置或库随机函数时，任何参数都必须是常量。也就是说，它们必须完全独立于输入值。
• 您的代码可能终止用概率1，而不是保证终止。

Notes

• randInt(0,n)是无效的，因为它将输入作为内置函数或库函数的参数。
• rand()%n一般不会给出一个统一的随机数。作为betseg的一个例子，如果是intmax == 15和n = 10，那么您获得0-5的可能性要比6-10大得多。
• 由于有限个可能的浮点值在0到1之间，floor(randomfloat()*(n+1))一般也不会给出一个统一的随机数。

Answer 1

Python，61字节

from random import*
lambda n,x=2.**30:int(randrange(x)*-~n/x)

编辑:更新以避免被禁止的形式

Edit2:保存了2个字节，谢谢@JonathanAllan

Edit3:为一个功能齐全的解决方案支付了2个字节-再次感谢@JonathanAllan

Edit4:删除f=，保存2个字节

Edit5:由于@JonathanAllan，又保存了1个字节

Edit6:由于@JonathanAllan，又保存了2个字节

到现在为止，git的指责会指向我所做的坏事，而JonathanAllan则会指出帮助我的东西。

Edit7:当下雨的时候，它会倾泻--另外两个字节

Edit8:和另外两个字节

Answer 2

Prolog (SWI)，38字节

X*Y:-Z is 2^31,random(0,Z,Y),Y=<X;X*Y.

通过拒绝抽样进行工作。

在0到2^31-1 = 2147483647之间生成一个随机数，直到找到小于或等于输入的值。

我觉得我应该可以用剪裁来代替其他的，但是我不知道怎么做。

Answer 3

迷宫，63字节

 ?
 #00}__""*_
 ;    #"  _
{-{=  } "><)
!{ : ;"({ +
@  }}:  >`#

(感谢@MartinEnder在这里帮忙打高尔夫。)

迷宫是一种2D语言，它唯一的随机性来源是在如下情况下：

   x
  "<)
 " "
 " "

假设指令指针在x上并向下移动。它接下来将落在<上，如果堆栈的顶部为0(在上面的实际程序中总是如此)，则将当前行移出1：

   "
 "<)
 " "
 " "

指令指针现在在<上向下移动。在一个交界处，迷宫在堆叠顶部转弯--负是左转，正是右转，零是向前移动的。如果在这一点上堆栈的顶部仍然是零，我们不能向前或向后移动，因为没有路径，所以迷宫将随机地在左转或右转之间以相同的概率。

从本质上讲，上面的程序所做的就是使用随机性特性生成100位数字(这里由#00指定的100位数字)，并继续循环直到生成一个数字<= n。

对于测试来说，使用#0"代替10位数字可能会有帮助，因为"是一个非操作路径。在网上试试！

粗略解释：

 ?            <--- ? is input and starting point
 #0"}__""*_   <--- * here: first run is *0, after that is *2 to double
 ;    #"  _
{-{=  } "><)  <--- Randomness section, +0 or +1 depending on path.
!{ : ;"({ +        After <, the >s reset the row for the next inner loop.
@  }}:  >`#

 ^    ^
 |    |
 |    The " junction in this column checks whether the
 |    100-bit number has been generated, and if not then
 |    continue by turning right into }.
 |
 Minus sign junction here checks whether the generated number <= n.
 If so, head into the output area (! is output as num, @ is terminate).
 Otherwise, head up and do the outer loop all over again.