مشروع لغز أويلر (خاصة في PHP)

Question

هناك سؤال آخر حديث لمشروع Euler ولكني أعتقد أن هذا أكثر تحديدًا (أنا مهتم حقًا فقط بالحلول المستندة إلى PHP) لذا فأنا أسأل على أي حال.

السؤال رقم 5 المهام التي تقوم بها:"ما هو أصغر عدد يقبل القسمة على جميع الأرقام من 1 إلى 20؟"

الآن، لقد قمت بحلها مرتين.مرة واحدة بشكل غير فعال للغاية ومرة ​​أخرى بكفاءة أكبر ولكني ما زلت بعيدًا عن إجابة معقدة بشكل خاص (وأنا لست قويًا بشكل خاص في الرياضيات ومن ثم حل القوة الغاشمة الخاص بي).أستطيع أن أرى بعض المجالات التي يمكنني من خلالها تحسين هذا ولكنني أتساءل عما إذا كان بإمكان أي منكم إظهار حل أكثر فعالية لهذه المشكلة.

*المفسد:هذا هو الحل الأمثل (7 ثوانٍ للتشغيل) ولكن لا يزال الحل مقبولاً (لست متأكدًا مما يجب فعله بشأن ضعف $...فقط تظاهر أنك ترى 1 فقط...

    function euler5(){
        $x = 20;

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

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

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

        }echo $x;
     };

Answer 1

في 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;
}

?>

إنه أسرع مرتين على الأقل مما نشرته.

Answer 2

جمع العوامل الأولية لجميع الأعداد من 1 إلى 20.بحساب الأسس القصوى لكل عامل أولي، نحصل على ذلك 16 = 2**4, 9 = 3**2, ، بالإضافة إلى 5، 7، 11، 13، 17، 19 (يظهر كل منها مرة واحدة فقط).اضرب الكمية، وستحصل على إجابتك.

Answer 3

كريس جيستر يونج على حق.

بشكل عام، إذا كنت تريد أصغر عدد قابل للقسمة بالتساوي على جميع الأرقام من 1 إلى N، فستحتاج إلى العثور على جميع الأعداد الأولية من 2 إلى N، ولكل منها، ابحث عن أكبر عدد من المرات التي يتم فيها القسمة على أي عدد رقم في النطاق.يمكن حساب ذلك من خلال إيجاد القوة الأعظم للأعداد الأولية التي لا تزيد عن N.

في حالة العدد 20، كما أشار كريس، 2^4 هي القوة الأعظم للعدد 2 لا تزيد عن 20، و3^2 هي القوة الأعظم للعدد 3 لا أكبر من 20، وبالنسبة لجميع الأعداد الأولية الأخرى، القوة الأولى فقط لا يزيد عن 20.

Answer 4

يمكنك إزالة بعض الأرقام التي يتم القسمة عليها، على سبيل المثال 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();
?>

Answer 5

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

هو أسرع وأقصر حل PHP حتى الآن.أسرع بحوالي 1.4 مرة من Czimi الموجود على شركتي.لكن تحقق من حل بايثون، إنه خوارزمية رائعة.

Answer 6

بعض الناس يبالغون في التفكير في هذا الأمر..

في روبي:

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

Answer 7

@الأشخاص الذين يقومون بعمليات حسابية بسيطة؛لست متأكدًا مما إذا كان هذا هو الهدف من التمرين.عليك أن تتعلم لغات جديدة وطرقًا جديدة لأداء الأشياء.مجرد القيام بذلك باستخدام الآلة الحاسبة ليس هو الطريقة الصحيحة للتعامل مع الأشياء.

وأنا أعلم أن هذا منشور في موضوع قديم ولكنه لا يزال يظهر في نتائج جوجل :)

من خلال القيام بذلك بالكود (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.السبب الرئيسي لأنه أسرع هو أنه عندما تقرأ السؤال، يذكرون بالفعل أن أقل عدد ممكن للأعداد الصحيحة العشرة الأولى هو 2520.لذلك، يمكنك فقط زيادة بمقدار 2520 بدلاً من 20.مما أدى إلى حلقات أقل بـ 126 مرة

Answer 8

أعلم أنك قلت 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)

إنه ليس أنيقًا كما كان بإمكاني صنعه، ولكنه يحسب المضاعف المشترك الأصغر للأرقام من 2 إلى 2000 في .15 ثانية.إذا كان الحل التكراري الخاص بك قادرًا على معالجة مليار مرشح في الثانية، فسوف يستغرق الأمر 10^849 عامًا للانتهاء.

بمعنى آخر، لا تهتم بتحسين الخوارزمية الخاطئة.