يونيو 13، 2009

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

المشكلة رقم 9:
تتألف ثلاثية فيثاغورس من الأعداد الصحيحة a < b < c بحيث تحقق العلاقة a2 + b2 = c2
مثال: 3^2 + 4^2 = 9 + 16 = 25 = 5^2

المطلوب:
توجد تحديدا ثلاثية فيثاغورس واحدة تكون فيها a + b + c = 1000
أجد abc

الحل الأول:
def pytha_Triplet(n):
    for a in range(1, n+1):
        for b in range(a+1, n+1):
            for c in range(n-a-b, b, -1):
                if a + b + c == n:
                    if (a**2) + (b**2) == (c**2):
                        return a*b*c

print pytha_Triplet(1000)

الشرح:
1. نقوم بتحديد دالة pytha_Triplet و تأخذ المعيار n. بداخلها يوجد حلقة تسلسلية تبدأ من 1 حتى آخر عدد (قيمة n). بداخلها توجد حلقة أخرى تبدأ من قيمة المتغيرة a+1 (الممثلة للمرحلة التي وصلت إليها الحلقة السابقة) و حتى آخر عدد ( وهو 1000 المعبر عنه ب n). و في داخل هذه الحلقة توجد حلقة أخرى تبدأ تنازليا من قيمة n-a-b حتى تصل إلى قيمة المتغيرة b (الممثلة للمرحلة التي وصلت إليها الحلقة الثانية). ثم بعد ذلك يتم إختبار مجموع a+b+c هل يتساوى مع n. إذا كان الشرط صحيحا يتم إجراء إختبار ثاني لمعرفة هل قيمة المتغيرتين a أُس 2 + b أُس 2 يتساوين مع قيمة المتغيرة c أُس 2. إدا كان الشرط صحيحا تخرج الدالة بنتيجة قيمة a*b*c
2. يتم عرض نتيجة الدالة pytha_Triplet

> كما تلاحظون هذه الحل يعتمد على طريقة تقليدية للعثور على ما نريد و هو يهدر الكثير من وقت المعالج.

الحالي الثاني (أسرع):
def pytha(n):
    a, b, c = 1, 2, n-3
    while (a < n/3):
        if a**2 + b**2 == c**2:
            return a*b*c
        elif c-1 > b+1:
            a, b, c = a, b+1, c-1
        else:
            a, b, c = a+1, a+2, n-(a+1)*2-1

print pytha(1000)

الشرح:
1. نكتب ذالة pytha و تأخد n كمعيار. بذاخلها يوجد:
2.1. يتم تعين قيمة 1 للمتغيرة a، و قيمة 2 للمتغيرة 2 و قيمة n-2 للمتغيرة c في آن واحد.
2.2. نحتاج إلى حلقة شرطية تبقى تدور ما دامت قيمة المتغيرة a أصغر من ثلث قيمة n. لماذ!؟ لأن ثلث قيمة n هو 333 و إدا كانت a = 333 فإن بالضرورة على b أن تكون أكبر من a بمعنى أنها على الأقل يجب أن تكون 334 و إذا كانت b = 334 فبالضرورة أن تكون قيمة c أكبر من b و بذلك فإن أصغر قيمة ممكنة ل c في هذه الحالة هو 335. و إذا قمنا بحساب مجموع a+b+c سنحصل على 1002 و بذلك فإدا وصلت قمية المتغيرة إلى ثلث قيمة n على الحلقة الشرطية بالخروج.
2.3. يتم إختبار قوة a في 2 + قوة b في 2 هل تتساوى مع قوة c في 2. إدا كان الشرط صحيح تخرج الدالة بمجموع ضرب قيمة a*b*c
2.4 إدا كان الشرط خاطئا يتم إختبار هل c-1 ما زالت أكبر من قيمة b+1. إدا كان الشرط صحيحا تبقى قيمة المتغيرة على حالها و تزيد قيمة b بـ 1 و تنقص قيمة c بـ 1 ثم تمر الحلقة إلى الدورة التالية.
2.5 أما إذا كان الشرطين السابقين خاطئين يتم تحديث قيمة a لتساوي a+1. ثم تصير b تساوي قيمة a+2 و قيمة c تساوي n ناقص قيمة (a+b) المعبر عنها بـ (a+1 مضروبة في 2) ناقص 1
3. يتم عرض نتيجة الدالة pytha بواسطة print

هناك تعليقان (2):

  1. for(a=1; a<1000; a++)
    {
    for(b=a+1; b<1000; b++)
    {
    for(c=b+1; c<1000; c++)
    {
    if(a*a +b*b==c*c && a+b+c==1000)
    printf("a= %i, b= %i, c= %i", a, b, c);
    }}}

    وضعت a*a+b*b==c*c كشرط أول لتحقق فيتاغورس، و الشرط الثاني a+b+c==1000 أن يكون مجموع ثلاثية فيتاغورس يساوي 1000، إن تحقق هذا فسنطبع قيم a و b و c. بما أنه سيحقق مرة واحدة (حسب السؤال) تحت العدد 1000 فسيتم الطبع مرة واحدة و لن نحتاج لإيقاف for.

    صحح يا مصحح ^_^

    ردحذف
  2. كتبت الحل مع الشرح.
    @محمد: 100 100 :)

    ردحذف