プロジェクトオイラーパズル（特にPHP）

StackOverflow https://stackoverflow.com/questions/193514

  •  10-07-2019
  •  | 
  •  

質問

別の最近のプロジェクトオイラーの質問がありますが、これはもう少し具体的だと思います（PHPベースのソリューションにのみ本当に興味があるので）とにかく尋ねています。

質問＃5 のタスク：＆quot;最小のもの1から20までのすべての数値で均等に割り切れる数値？」

今、私はそれを二度解決しました。かつては非常に非効率的で、はるかに効率的でしたが、特に洗練された答えからはまだ遠いです（そして、数学では特に堅実ではないので、総当たり的な解決策です）。これを改善できる分野がいくつかありますが、この問題に対するより効率的な解決策を示すことができる人がいるかどうかは疑問です。

*ネタバレ：これは最適ではありません（実行に7秒）が、まだ許容できるソリューションです（二重$について何をすべきかわからない...ただ1つしか見えないふりをする... 

    function euler5(){
        $x = 20;

        for ($y = 1; $y < 20; $y++) {

            if (!($x%$y)) {

            } else {  
                $x+=20;
                $y = 1;  
            }   

        }echo $x;
     };
役に立ちましたか？

解決

phpでは、次のようになります。

<?php
function gcd($a,$b) {
    while($a>0 && $b>0) {
        if($a>$b) $a=$a-$b; else $b=$b-$a;        
    }
    if($a==0) return $b;
    return $a;
}
function euler5($i=20) {
    $euler=$x=1;
    while($x++<$i) {
        $euler*=$x/gcd($euler,$x);
    }
    return $euler;
}

?>

投稿したものの少なくとも2倍の速度です。

他のヒント

1から20までのすべての数の素因数を収集します。各素因数の最大指数をカウントすると、 16 = 2 ** 4 、 9 = 3 ** 2 、および5、7、11、13、17、19（それぞれ1回だけ表示されます）。たくさん掛けて、答えがあります。

クリス・ジェスター=ヤングは正しい。

一般に、1からNまでのすべての数で均等に割り切れる最小数が必要な場合、2からNまでのすべての素数を見つけ、それぞれについて最大数を見つけます範囲内の任意の数を分割します。これは、N以下の素数の最大の力を見つけることで計算できます。

20の場合、Chrisが指摘したように、2 ^ 4は20以下の2の最大の累乗であり、3 ^ 2は20以下の3の最大の累乗であり、他のすべての素数についてのみ、最初の累乗は20以下です。

たとえば、1は不要で、すべての自然数は1で割り切れる、たとえば2は必要ないため、すべての数字は2の倍数（4、8 、16など）も2で割り切れます。したがって、関連する番号は11、12、13、14、15、16、17、18、および19です。

だから：

<?
function eulerPuzzle()
{
  $integers = array( 11,12,13,14,15,16,17,18,19 );

  for ($n = 20; 1; $n += 20 ) {
    foreach ($integers as $int) { 
      if ( $n % $int ) { 
    break; 
      }
      if ( $int == 19 ) { 
    die ("Result:" . $n); 
      }
    }
  }
}

eulerPuzzle();
?>

<?php
$i=20;
while ($i+=20) {
    for ($j=19;$j!==10;--$j){
        if ($i%$j) continue 2;
    }
    die ("result: $i\n");
}

これまでのところ、最速かつ最短のphpソリューションです。私のコンプでは、Czimiの約1.4倍高速です。しかし、Pythonソリューションを確認してください。これは素晴らしいアルゴリズムです。

一部の人々は本当にこれを過剰に考えています...

Rubyの場合：

puts 5*7*9*11*13*16*17*19

@簡単な計算をする人。それが運動の目標かどうかはわかりません。あなたは新しい言語と物事を実行する新しい方法を学ぶことです。電卓でそれをするだけでは物事を進める正しい方法ではありません。

そして、これが古い古いスレッドの投稿であることは知っていますが、それでもGoogleの結果に表示されます：）

コード（PHP）で実行することで、これが最速のソリューションであることがわかりました。

function eulerPuzzle() {
    $integers = array (11, 12, 13, 14, 15, 16, 17, 18, 19 );

    for($n = 2520; 1; $n += 2520) {
        foreach ( $integers as $int ) {
            if ($n % $int) {
                break;
            }
            if ($int == 19) {
                die ( "Result:" . $n );
            }
        }
    }
}

eulerPuzzle ();

はい、CMSからの変更された部分です。それが高速である主な理由は、質問を読んだときに、最初の10個の整数の可能な最小数が2520であるとすでに述べているためです。そのため、20ではなく2520だけインクリメントできます。 p>

あなたがPHPを言ったことは知っていますが、ここにPythonでの大まかなドラフトがあります。

#!/usr/bin/env python

from operator import mul

def factor(n):
    factors = {}
    i = 2
    while i < n and n != 1:
        while n % i == 0:
            try:
                factors[i] += 1
            except KeyError:
                factors[i] = 1
            n = n / i
        i += 1
    if n != 1:
        factors[n] = 1
    return factors

base = {}
for i in range(2, 2000):
    for f, n in factor(i).items():
        try:
            base[f] = max(base[f], n)
        except KeyError:
            base[f] = n

print reduce(mul, [f**n for f, n in base.items()], 1)

これは私が作成できたほどエレガントではありませんが、0.15秒で2から2000までの最小公倍数を計算します。反復ソリューションが1秒あたり10億の候補を処理できる場合、完了するには10 ^ 849年かかります。

言い換えれば、間違ったアルゴリズムを最適化することを気にしないでください。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top