يونيو 09، 2009

مشروع Euler project: المشكلة رقم 5

المشكلة رقم 5:
العدد 2520 هو أصغر عدد يمكن أن يقسم على كل عدد بدءا من 1 إلى 10 دون أي باقي.

المطلوب:
ما هو أصغر عدد يمكن قسمته على كل الأعداد من 1 إلى 20 دون أن يكون هنالك باقي (القسمة بالتساوي)


الحل الأول (إستغرق 24 ثانية على حاسوبي):
def euler5():
    i = 20
    seq = range(2, 20+1)
    while True:
        for j in seq:
            if i % j  !=  0:
                break
            elif j == 20:
                return i

        i += 20


print euler5()
الشرح:
1. نستخدم الكود داخل دالة حتى تزيد من سرعة الأداء. الدالة تم تحديدها بواسطة الكلمة المفتحية def يليها إسمها euler5 المتبوع ب () ثم :

2. المتغيرة i هي التي ستتزايد قيمتها تصاعديا حتى تصل إلى الرقم الذي يمكنه القسمة على جميع الأعداد من 1 إلى 20
3. المتغيرة seq هي قائمة بالأرقام التي سيتم إستخدامها كقاسم. القائمة تحتوي على كل الأعداد من 2 إلى 20
4. الحلقة شرطية while. و بالصيغة التي كُتبت بها فستبقى تدور إلى الأبد أو حتى يتم كسرها بتعليمة break أو return

5. الحلقة التسلسلية for التي تدور من أول عدد في القائمة seq إلى آخر عدد فيها. في كل دورة تأخد المتغير j قيمة العدد التالي من القائمة
6. الجملة الشرطية if التي تقوم بإجراء القسمة لإختبار قيمة الباقي هل هي 0 أم لا. إدا كان الباقي (و ليس الخارج) لا يساوي 0 يتم كسر الحلقة for بواسطة التعليمة break و ذلك لنختصر المسافة لأنه لا دعي لإختبار كل الأعداد المتبقية في القائمة seq إن كان العدد الذي نحن بصدده باقي قسمته لا بساوي 0. بمعنى ليس قاسما طبيعيا. و بعد دلك ينتقل الكود للسطر الذي يحتوي على i += 20 حتى يتم الصعود بقيمة 20 في كل دورة من دورات الحلقة while.
7. أما إدا كانت كل الأعداد المتواجد في القائمة seq تقبل القسمة بشكل طبيعي على قيمة المتغيرة i، فبالضرورة إدن أن قيمة المتغيرة j ستكون مساوية ل 20 و ذلك لأنه آخر رقم في القائمة قابل للقسمة بشكل طبيعي. بمعنى أننا إجتزنا كل الأعداد في القائمة حتى وصلنا إلى 20. و بعد التأكد من ذلك نخرج من الدالة euler5() بنتيجة المتغيرة i و تم عرضها من طرف الدالة print


الحل الثاني (يتوصل إلى النتيجة بشكل آني):
def isPrime(value):
    for i in range(2, value):
        if value % i == 0:           
            return False
    return True


def sumMultiply(seq):
    r = 1
    for i in seq:
        r = r * i
    return r


def findDivisible(value, seq=[]):
    multiplier = 1   
    while True:
        for i in seq:
            if (value * multiplier) % i != 0:
                multiplier += 1
                break
            elif i == seq[-1]:
                return (value * multiplier)


nbr = 20
divs = [x for x in range(nbr, 1, -1)]
primes = sumMultiply(filter(isPrime, divs))

print findDivisible(primes, divs)

الشرح:
يبدو و كانه صعب لكنه سهل :)

1. قمنا بإضافة دالة isPrime(value) التي ستقوم بمعرفة هل العدد الذي حصلت عليه من المعيار value أهو عدد أولي ام لا. هذه الدالة سيتم إعتمادها و تحسينها في مشاكل مستقبلية.
2. دالة sumMultiply(seq) تقوم بإعطا الخارج بعد قيامها بعملية ضرب كل أعداد القائمة seq في بعضها البعض.
3. دالة findDivisible(value, seq=[]) تقوم بالبحث عن أول قاسم للأعداد التي توصلت بها من القائمة seq.

فكرة هذا الحل هو إيجاد الأعداد الأولية في قائمة الأعداد من 2 إلى 20 ثم إجراء عملية ضرب بعضها في بعض، و العدد الذي نحصل عليه من هذه العملية يتم إستخدامه كأساس/كمنطلق يتم إستخدامه للبحث عن مضاعف له يقبل القسمة على كل الأعداد من 2 إلى 20. و هذا هو ماتقوم به الأسطر الأخيرة.

هناك 7 تعليقات:

  1. العدد هو 232792560

    الكود بلغة السي شارب:
    private static int GetResult()
    {
    int i = 20;
    bool IsSussess = false;
    while (!IsSussess)
    {
    for (int j = 2; j <= 20; ++j)
    if (i % j != 0)
    break;
    else
    if (j == 20)
    IsSussess = true;
    ++i;
    }
    return i;
    }

    ردحذف
  2. @محمد الجوهري:
    عند تجربتي للكود حصلت على 232792561 بدلا من 232792560

    ردحذف
  3. Mohammed Berdai بسيطة ، أكتب return i-1
    عذرا على هذا الخطأ :)

    ردحذف
  4. محمد، بهذا أنت تدفعني لتعلم بايثون رغما عني ^_^
    بايثون (كما أرى من أول وهلة بدون تجربة استخدامها) كأنها c مع تحسينات تسهيل و جعل العمل مركز على الهدف من الكود لا الكود نفسه.
    أستغرب كيف لم تلق الإهتمام الكافي!

    ردحذف
  5. استطعت حل هذه المشكلة بدون استخدام البرمجة

    فضلت التفكير في المشكلة بدلا من حلها برمجيا

    الحل بسيط
    حيث أننا نضرب الأعداد الأولية من 10 ل 20 و هي:
    11 و 13 و 17 و 19
    في الأعداد الناتجة عن ضرب الأعداد الأولية الأخرى
    18 (حيث تتكون من 2*3*3 = 2*9) .. و بذلك نستثني الأعداد 2 و 3 و 9

    و هكذا حتى نحصل على:
    19*17*13*11*18*8*5*7

    ليصبح الناتج:
    232792560

    :)

    ردحذف
  6. @محمد من المغرب: أتمنى ذلك :)
    @BooDy: رائع، توصلنا إلى نفس الحل :) (أنظر الحل الثاني)

    ردحذف