Bir Proje Euler bilinmez (özellikle PHP)

8 Cevap php

Orada başka bir yeni proje Euler soru ama bu biraz daha özel olduğunu düşünüyorum (PHP tabanlı çözümlerinde sadece gerçekten ilgileniyorum) ben yine soruyorum.

"1-20 numaraları herkes tarafından eşit bölünebilen en küçük sayı nedir?" Ile Question #5 görevler sizi

Şimdi, ben iki kez çözdük. Bir zamanlar çok verimsiz ve bir kez daha verimli ama ben uzakta özellikle gelişmiş cevap hala duyuyorum (ve ben matematik dolayısıyla benim kaba kuvvet çözüm özellikle katı değilim). Ben bu getirebileceği alanlarda bir çift görebilirsiniz ama siz bu soruna daha verimli çözüm gösterecektir eğer ben merak ediyorum.

* Spoiler: Burada optimum (çalıştırmak için 7 saniye) ama yine de tolere edilebilir bir çözüm daha benim azdır (ne çifte hakkında yapmak için emin değil ... sadece sadece 1 görmek iddia ...

    function euler5(){
        $x = 20;

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

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

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

        }echo $x;
     };

8 Cevap

php bu gibi görünecektir:

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

?>

Onun en az iki kat hızlı ne yayınlanmıştır daha.

Ana 1 ve 20 arasındaki tüm numaralar için faktörler. Her ana faktörünün maksimal üsler Sayma biz olan 16 = 2**4, 9 = 3**2 yanı sıra, 5, 7, 11, 13, 17, toplayın , 19 (her biri sadece bir kez ortaya çıkan). Çok çarpın ve size cevabım var.

Chris Jester-Young hakkıdır.

Eğer 1'den N numaraları herkes tarafından eşit bölünebilen en küçük sayı istiyorsa genel olarak, 2'den N tüm asal sayıları bulmak istersiniz, ve her biri için, herhangi bir bölen zamanların en büyük sayısını bulmak aralığında sayısı. Bu N. daha büyük değil başbakan büyük güç bularak hesaplanabilir

20 durumunda Chris işaret ettiği gibi, ^ 4 2 2 daha büyük olmayan 20 büyük güç, ve ^ 2 3 20 den 3 büyük değil en büyük güç olduğunu, ve diğer tüm asal için, yalnızca birinci güç 20 'den büyük değildir.

Sen ile ayrılır bazı sayılar kaldırabilirsiniz, örneğin 1 gereksizdir, tüm doğal sayılar da 2 gerekmez 1.Eğer bölünebilir ve bu nedenle, tüm sayılar birçok 2 ile bölünebilir (4, 8, 16, vb) Ayrıca, 2 ile bölünebilir. Bu nedenle, ilgili numaralar 11, 12, 13, 14, 15, 16, 17, 18, ve 19 olacaktır.

Yani:

<?
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");
}

Şimdiye kadar en hızlı ve en kısa php çözümdür. Hakkında 1.4x Czimi benim comp daha hızlı. Ama python çözüm kontrol, güzel bir algo şu.

Bazı insanlar gerçekten bu aşırı düşünüyorum ...

Ruby:

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

Basit matematik yapıyor @ İnsanlar; Ben egzersiz hedefi ise emin değilim. Sen yeni bir dil ve şeyler yapmak için yeni yollar öğrenmek için vardır. Sadece bir hesap makinesi ile yapıyor şeyleri gidiş doğru bir yol değildir.

Ve ben bu bir eski iplik bir post olduğunu biliyorum ama yine de google sonuçlarında gelir :)

Ben bu hızlı çözüm bulundu kodu (PHP) bunu yapıyor:

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 ();

Evet, CMS bir modifiye parçası. Eğer soruyu okurken, onlar zaten ilk 10 tamsayılar için mümkün olan en düşük sayı 2520 olduğunu belirtiyorlar çünkü hızlıdır ana nedenidir. Bunun, sadece 20 yerine 2520 ile artırmak. 126 kat daha az döngüler sonucu

Ben PHP söylediğimi biliyorum, ama burada Python benim kaba taslak.

#!/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)

Ben bunu yapmış olabilir gibi zarif değil, ama .15 s 2-2000 sayıların en küçük ortak katını hesaplar. Yinelemeli çözüm saniyede bir milyar adayları süreç olsaydı, bunu bitirmek için 10 ^ 849 yıl alacaktır.

Diğer bir deyişle, yanlış bir algoritma optimize zahmet etmeyin.

etiketler