0

早些时候，我在 Matlab 中为这种彩票功能编写了一个代码，只是为了测试它是否可能。但是，我实际上在 PHP 中需要它，所以我刚刚重写了代码，它似乎确实有效，但由于它涉及大量循环，我想确保我尽可能高效地完成它。

代码的作用：

您可以调用该函数$lotto -> type($users,$difficulty)，它将返回两个数字。这是解释，$users是在网站上注册的用户数量，即可能会买票的人。$difficulty是一个介于 1 和 10 之间的数字，其中 5 表示正常，1 表示容易，10 表示困难。这里的难度意味着匹配彩票上的所有数字有多难。

那么函数返回的数字是多少？那将是$n和$r。$n是彩票上的$r号码数量，是您可以从彩票中选择的号码数量。例如，在英国，一张国家彩票有 49 个号码，如果您选择 6。即$n = 49和$r = 6。

该函数如何计算这两个数字？在英国国家彩票中，有 13,983,816 种可能的彩票组合。如果我要运行$lotto -> type(13983816,1)它会返回array(49,6)。基本上，它试图做到这一点，所以有注册用户的数量就有尽可能多的票组合。

tl;博士，这是代码：

<?php
class lotto {
    public function type($users,$difficulty){
        $current_r = $r = 2;
        $current_n = 0;
        $difficulty = ($difficulty + 5) / 10; // sliding scale from 1 - 10
        $last_tickets_sold = 200; // tickets sold in last lotto
        $last_users = 100; // how many users there were in the last lotto
        $last_factor = $last_tickets_sold / $last_users; // tickets per user
        $factor = $last_factor * $difficulty;
        $users *= $factor;
        while($r <= 10){
            $u = 0;
            $n = $r;
            while($u < $users && $n < 50){
                $u = $this -> nCr(++$n,$r);
            }
            if($r == 2){
                $current_n = $n;
            } elseif(abs($this -> nCr($n,$r) - $users) < abs($this -> nCr($current_n,$current_r) - $users)){
                // this is a better match so update current n and r
                $current_r = $r;
                $current_n = $n;
            }
            $r++;
        }
        return array($current_n,$current_r);
    }
    private function nCr($n,$r){
        return $this -> factorial($n) / (
            $this -> factorial($r) * $this -> factorial($n - $r)
        );
    }
    private function factorial($x){
        $f = $x;
        while(--$x){
            $f *= $x;
        }
        return $f;
    }
}
$lotto = new lotto;
print_r($lotto -> type(1000,5));
?>
4

4 回答 4

2

我进行了快速扫描，发现了一些可以进一步优化的地方。

组合
您的算法是蛮力算法，可以进一步优化

private function nCr($n,$r){
    return $this -> factorial($n) / (
        $this->factorial($r) * $this->factorial($n - $r)
    );
}

到

function nCr($n,$r) {
    $top = 1;
    $sub = 1;

    for($i = $r+1; $i <= $n; $i++)
        $top *= $i;

    $n -= $r;
    for($i = 2; $i <= $n; $i++)
        $sub *= $i;

    return $top / $sub;
}

太多的组合计算
计算组合是昂贵的。

$u = 0;
$n = $r;
while($u < $users && $n < 50){
    $u = $this -> nCr(++$n,$r);
}

到

$n = $r + 1;
$u = nCr($n, $r);

while ($u < $users && $n < 50) {
    $n++;
    $u *= $n;
    $u /= ($n - $r);
}
于 2012-07-26T19:30:53.267 回答
1

立即观察到您可能会出现除以 0 错误

$last_factor = $last_tickets_sold / $last_users;

可以通过在它周围放置一个简单的 if 语句来解决

$last_factor = ($last_users == 0) ? 0 : $last_tickets_sold / $last_users;
于 2012-07-26T19:01:06.397 回答
0

无论对您的代码进行详细检查，您确定您的循环不需要继续或中断吗？

于 2012-07-26T19:05:22.437 回答
0

算法中factorial()的范围是 [0,50]，那么为什么不静态地预先计算呢？

private static $factorial=array(1);

private static genFactorial($max) {
    if( count( self::$factorial ) > $max ) return;
    foreach ( range(count(self::$factorial), $max) as $n ) {
        self::$factorial[$n] = $i*self::$factorial[$n-1];
    }
}

现在添加self::genFactorial(50);to__construct()或 totype()并替换对$this -> factorial($n)by 的引用self::$factorial[$n]。

这只是一个快速的代码转储；甚至没有进行编译检查，因此请原谅任何拼写错误等，但这样做是用数组元素获取替换函数调用（包括 while 循环）。

于 2012-07-26T23:05:54.187 回答