随机生成x个大小为[1,y]的正整数的求解解析

Question

问题：请编写函数foo(int x, int y, int n) 计算：随机生成x个大小为[1,y]的正整数，它们的和为n的概率是多少？
参考代码：

function recursion($x,$y,$n){
    if($n<$x || $n>$x*$y){
        $tmp[$x][$n] = 0;
    }else if($x === 1){
        if($y < $n){
            $tmp[$x][$n] = 0;
        }else{
            $tmp[$x][$n] = 1;
        }
    }
    if(isset($tmp[$x][$n])){
        return $tmp[$x][$n];
    }
    $tmp[$x][$n] = 0;
    for($i=1; $i<=$y; $i++){
        $tmp[$x][$n] += recursion($x-1, $y, $n-$i);
    }
    return $tmp[$x][$n];
 }
function foo($x, $y, $n){
    return recursion($x, $y, $n) * 1.0 / pow($y, $x);
}
$sum = 0;
for($i=1;$i<100;$i++){
    echo foo(5,10,$i),PHP_EOL;
    $sum += foo(5,10,$i);
}
echo 'sum:' . $sum;

看了网上的答案都是直接给代码，表示搞不懂为什么要循环遍历，还要用for循环i从1循环100次。具体希望大神可以从头到脚讲下这个代码的思路。小弟在此十分感谢。

Answer 1

那个循环是在计算5个来自[1,10]中随机整数的和等于1的概率，加上等于2的概率，等等这样不断累加，最后加上等于100的概率。因为这样的五个数字的和肯定在5和50之间，所以最后这些概率之和当然是1，从而可以验证foo的正确性。

你再看他计算foo这个概率是用的recursion(x,y,n)/(y^x)，因此recursion(x,y,n)是在计算取x个[1,y]间的随机整数，它们的和等于n的方法数。函数名提示我们他是用递归来算的。

你要取x个这样的数字的方法数是recursion(x,y,n)，现在按第一个取出的数分类。

• 如果第一个数是1，那么后面x-1个数字的和就必须是n-1，有recursion(x-1,y,n-1)种方法。
• 如果第一个数是2，那么后面x-1个数字的和就必须是n-2，有recursion(x-1,y,n-2)种方法。

等等。也就是说递归公式是：

recursion(x,y,n) = recursion(x-1, y, n-1) + recursion(x-1, y, n-2) + ... + recursion(x-1, y, 0)

这个递归公式如果直接写在代码里比较低效，因为会重复计算。所以他用了tmp[x][n]这个表格来缓存中间结果和边界条件（n不能太大或太小）。

通过以上分析再回去看代码，应该就比较清楚了。

Answer 2

//此函数作用递归 $x 到 $y 中的数有那些满足 $x * $y = $n 并放入$tmp 数组中 已 $x 和 $y 作为key区分
function recursion($x,$y,$n){

if($n<$x || $n>$x*$y){ // 1.如果 $n < $x 那么 $x+$y 肯定大于$n； 2. $n > $x *$y (这里疑问。这个函数应该不是算 $x+$y =$n 概率的 应该是算 $x*$y=$n 概率的)
    $tmp[$x][$n] = 0;
}else if($x === 1){
 // 判断 $x =1 的情况 再这种情况下 $y < $n 那么 1*$y肯定大于$n 然后就是
// 其他情况。这种情况下只有 $y=-$n 才满足 $x*$y = $n 所以 $tmp[$x][$n]=1
    if($y < $n){
        $tmp[$x][$n] = 0;
    }else{
        $tmp[$x][$n] = 1;
    }
}
//这里判断是否有条件成立 有 则可以返回了。
if(isset($tmp[$x][$n])){
    return $tmp[$x][$n];
}
//这里 遍历 $x 到 $y 是否还有还有存在 $x *$y =$n 的 有则加入到 $tmp中
//最后递归后返回
$tmp[$x][$n] = 0;
for($i=1; $i<=$y; $i++){
    $tmp[$x][$n] += recursion($x-1, $y, $n-$i);
}
return $tmp[$x][$n];

}
//这里 是算 具体某个 [$x,$y]范围的数到 $n为具体值的概率
function foo($x, $y, $n){

return recursion($x, $y, $n) * 1.0 / pow($y, $x);

}
$sum = 0;
//最后这里解释下为什么有循环 循环是别人算了 5,10 分别 与 $n = [1 ...100] 所有数的概率
for($i=1;$i<100;$i++){

echo foo(5,10,$i),PHP_EOL;
$sum += foo(5,10,$i);

}
echo 'sum:' . $sum;