最近程序员面试题涌进知乎,这是简单题。
第一问:怎么扔。立刻答:六面骰子扔两次,规定一种情况重扔,其余35种情况分成7组。
第二问:上述算法平均要扔几次?答:肯定是2次多一点,x = 2 + x * 1/36。
第三问:如果需要反复生成,而且假设扔骰子代价高昂,希望扔次数尽可能少,应该怎么做,理论最少几次?答:理论最少log_6(7)次,1次多一点,信息极限。一种实现方法是批量生成,比如一批扔12次骰子,可以生成11个结果,当然也可能需要再重扔12次。12和11是手动选的数字,也不一定就是最好。为了降低抖动,可能要加个队列。
更新:上述算法的输出是7个等概率的随机数,而非1/7概率的结果。
编辑于 2023-11-18 14:26・IP 属地北京