0

以前、この種の宝くじ関数のコードを Matlab で書き、それが可能かどうかをテストしました。ただし、実際にはPHPで必要だったので、コードを書き直したところ、機能しているように見えますが、多くのループが含まれているため、できるだけ効率的に実行していることを確認したいと考えています.

コードの機能:

関数$lotto -> type($users,$difficulty)を呼び出すと、2 つの数値が返されます。説明$usersは次のとおりです。これは、ウェブサイトに登録されているユーザーの数です。つまり、チケットを購入する可能性のある人々です。$difficultyは 1 から 10 までの数字で、5 は通常、1 は簡単、10 は難しいです。ここでの難易度とは、宝くじのすべての数字を一致させることがどれだけ難しいかを意味します。

では、関数が返す数値は何でしょうか? それは$nと$rです。$nは宝くじに記載される数字の数で、$rは宝くじから選択できる数字の数です。たとえば、英国では、全国の宝くじのチケットに 49 の数字があり、そのうちの 6 つを選択する$n = 49とします$r = 6。

関数はこれら 2 つの数値をどのように計算しますか? 英国の国営宝くじでは、13,983,816 通りの異なるチケットの組み合わせが考えられます。実行する$lotto -> type(13983816,1)と、 が返されarray(49,6)ます。基本的には、チケットの組み合わせが登録者数だけあるようにしています。

tl;dr、コードは次のとおりです。

<?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

すぐに観察できるのは、ゼロ除算エラーの可能性があるということです。

$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);への参照をに置き換えます。 __construct()type()$this -> factorial($n)self::$factorial[$n]

これは簡単なコード ダンプです。コンパイルチェックさえしていないので、タイプミスなどを許してください。しかし、これが行うことは、関数呼び出し (while ループを含む) を配列要素フェッチに置き換えることです。

于 2012-07-26T23:05:54.187 に答える