مسألة المثلثات الأولية

Speed_Of_Light كتب:

إذا كان القاسم المشترك الأصغر لأطوال أضلاعه = 1

GCD هو القاسم المشترك الاكبر ! :wink: .

على أية حال ..... جاري المحاولة في هذه المسألة ...!

عذراً :blush: خطأ إملائي :blush: تم التصحيح

لقد قمت بكتابة برنامج لحل المسألة في جافا ... لكنه يستغرق وقتاً كبيراً و(11 ثانية للمثلثات التي لا يزيد محيطها عن 1000 !)

أظن أنه يجب إيجاد إلتفاف رياضي أولاً ثم تطبيقه برمجياً :)

بانتظار محاولتك

السلام عليكم

أسف على التأخير لانشغالي كثييرا هذه الايام ..

لقد فكّرت جديا" بالمسألة ..و على الرغم من استخدامي الماتلاب لتأدية واختصار الكثير من العمليات الرياضية المعقدة ...فأنه لم يستطع حتى الوصول الى جميع حلول المثلثات ذات المحيط

الاصغر أو تساوي 1000,مع أني اتبعت خوارزمية جيدة يمكن شرحها لاحقا"...

يمكن أن يلاحظ من الصورة :

1- حتى يصل i الى 10000 استغرق 4 دقائق ونتج عن ذلك 22935 حل .. متضمنا" ذلك المثلثات المتساوية الساقين (حالة تكرار عنصرين)

2- انتظرت i حتى وصل الى 20000 فأصبحت الحلول 85120 حل ..وكلما كبرت قيمة العداد زادت الحلول وزاد زمن التحليل ..

ألية عمل الخوارزمية :

1- يوجد مثلث متساوي الاضلاع واحد فقط هو المثلث 1,1,1 لان المثلثات المتساوية الاضلاع الاخرى لا تحقق شرط القاسم

2-بدل البحث في الامكانات أي توافيق (997,3)

قمت بايجاد توافيق (997,2) بذلك أكون أنتجت جميع التشكيلات الممكنة لرقمين دون تكرار 496506 ثنائية ...

ثم عند كل ثنائية قمت بايجاد جميع القيم التي يمكن أن تشكل الضلع الثالث للمثلث بتطبيق القاعدة (كل ضلع في مثلث أصغر من مجموع الضلعين وأكبر من فرقهما)

3- بعد ذلك أقوم بتطبيق شروط المسألة من المحيط و القاسم المشترك ثم القيام بحذف التكرار ان وجد .. لأحصل على المطلوب ..

4- بهذه الطريقة أكون قد أخذت بالاعتبارأيضا" المثلثات متساوية الساقين.

Speed_Of_Light كتب:

و(11 ثانية للمثلثات التي لا يزيد محيطها عن 1000 !)

سأفترض أنك حللت فقط الارقام غير المكررة ... والبالغة توافيق (997,3) أي : 164674490 (بدون المثلثات المتساوية الساقين )

يرجى شرح خوارزميتك !..... لتبيان ألية البحث في جميع هذه الامكانات بـ 11 ثانية ...

المرجو الشرح أكتر ......و شكرا على الموضوع :wink:

أخوكم مبتدئ لذا أرجو المعذرة ........(لقد بدأت البرمجة للتو ) :blush: :ph34r:

الكود ببايثون :

الرد السابق بالنسبة لاحتمالية الألف ...

و مازال الجواب ناقصا حتى مع ذلك حيت يعرض لي الاحتمالات فقط من دون حساب عددها ............ :unsure:

أرجوكم إخواني أنا لا زلت جدد مبتدئ كيف يمكن إدخال القيم المخرجة في قائمة بحيت يمكن إستعمال الدالة len عليها لمعرفة الاحتمالات ...

متلا [٩،٢،١ ] و [٥،٤،٣ ] يحققان شرط التمرين بالنسبة لمتلت محيطه ١٢ فكيف أدخلها في قائمة بهذا الشكل .......

NouvList = [[٥،٤،٣ ],[٩،٢،١ ]]

علما أنني جربتها على الكود السابق بتعريف متغير على الشكل السابق لكن احتمال واحد هو الذي يدخل في القائمة ........ :unsure:

أرجو التوضيح [لا نتعبكم معانا ]......أو أي حلول أخرى .......

مازلت مبتدئ في الخوارزميات و المرجو إيجاد التفاف رياضي لتطبيقه :blush: :blush:

السلام عليكم

أعمل على خوارزمية أخرى .. أظن بأنها ستفلح بأيجاد المطلوب بسرعة وتخفف على ماتلاب استهلاك موارد النظام ... :sleep:

The_IfL كتب:

متلا [٩،٢،١ ] يحققان شرط التمرين بالنسبة لمتلت محيطه ١٢ فكيف أدخلها في قائمة بهذا الشكل .......

ومن قال لك بأن الاعداد 1,2,9 هي أضلاع من مثلث ...! :excl: .. (راجع متى يكون حل المثلث مستحيلا")

أتمنى عليك أخي العزيز قراءة المسألة .. وفهمها بشكل دقيق .. وستجد المساعدة ان شاء الله ..

بالتوفيق ..

نعم أخي والله أنا جديد في عالم البرمجة .........بالنسبة للمسألة علي أن أفهمها جيدا كما قلت أخي ... :blush: :blush: :blush:

وسأعمل على الحل و البركة فيكم [شكرا على الملحوظة :unsure: ]...

جزاك الله خيرا أخي الكريم :lol:

أخي نعم بالنسبة لما قلت سأضيف خاصية [مجموع ضلعي متلت أكبر من الضلع التالت ]....

الآن أحصل على النتائج كيف يمكن أن أدخلها في Lists بحيت يسهل إستعمال الدالة .....

مشكور أخي مرة أخرى على التنبيه :blush:

عذراً على التأخير ...

بالرغم من عدم وضوح السؤال فيما يتعلق بحساب المثلثات المتكررة أم لا ... فأنا افترضت أن المثلثين اللذين لهما نفس الأبعاد هما مثلث واحد

بالنسبة للخوارزمية فهي أبسط مما ذكرته، إليك الكود (Java):

public class PrimitiveTriangles {
    final int maxPerimeter = 1000;

    public PrimitiveTriangles() {
        int a = 1, b = 1, c = 1, sum = 0, t;
        for (a = 1; a <= b; a++) {
            for (b = 1; b <= c; b++) {
                for (c = 1;; c++) {
                    if ((a + b + c) > maxPerimeter) {
                        break;
                    }
                    t = GCD(a, b);
                    if (t == 1) {
                        sum++;
                    } else {
                        if (GCD(t, c) == 1) {
                            sum++;
                        }
                    }
                }
            }
        }
        System.out.println("sum=" + sum);
    }

    private int GCD(int a, int b) {
        if (b == 0) {
            return a;
        }
        return GCD(b, a % b);
    }

    public static void main(String[] args) {
        PrimitiveTriangles primitiveTriangles = new PrimitiveTriangles();
    }
}

و أخيرة بقي لي مشكل إدخال النتائج في Lists و مشكل الوقت .............. :blush: :blush:

أخي Devd جزاك الله خيرا هل يمكنك شرح خوارزمية بسيطة ....بارك الله فيك أخي و زادك علما ...

إن كان هناك أي خطأ أخبروني : :blush: [الكود مطبق على محيط أصغر من 1000]

يبدو أنني نسيت أن أتحقق من كون المثلث مقبول ... تم تصحيح الكود :(

والآن يتم حساب المثلثات التي محيطها أقل من 1000 في حوالي 5 ثوان حيث يصبح عدد المثلثات 23253252

هذا هو الكود بعد التعديل:

public class PrimitiveTriangles {

    final int maxPerimeter = 1000;

    public PrimitiveTriangles() {
        int a = 1, b = 1, c = 1, sum = 0, t;
        for (a = 1; a <= b; a++) {
            for (b = 1; b <= c; b++) {
                for (c = 1;; c++) {
                    if ((a + b + c) > maxPerimeter) {
                        //System.out.println("a=" + a + ",b=" + b + ",c=" + c + " Exceeding Perimeter");
                        break;
                    }
                    if (!validTriangle(a, b, c)) {
                        //System.out.println("a=" + a + ",b=" + b + ",c=" + c + " Invalid Triangle!");
                        continue;
                    }
                    t = GCD(a, b);
                    if (t == 1) {
                        sum++;
                        //System.out.println("a=" + a + ",b=" + b + ",c=" + c + " Triangle counted");
                    } else {
                        if (GCD(t, c) == 1) {
                        //System.out.println("a=" + a + ",b=" + b + ",c=" + c + " Triangle counted");
                            sum++;
                        }
                    }
                }
            }
        }
        System.out.println("sum=" + sum);
    }

    private int GCD(int a, int b) {
        if (b == 0) {
            return a;
        }
        return GCD(b, a % b);
    }

    private boolean validTriangle(int a, int b, int c) {
        if ((a + b > c && Math.abs(a - b) < c
                || b + c > a && Math.abs(b - c) < a
                || a + c > b && Math.abs(a - c) < b)) {
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        PrimitiveTriangles primitiveTriangles = new PrimitiveTriangles();
    }
}

هل هذه هي الخوارزمية الأمثل ؟

إن كان هناك تحسينات ممكنة، أرجو اقتراحها

كما أتمنى أن يقوم أحد الأخوة بتطبيق الخوارزمية على MatLab لمقارنة الأداء

Speed_Of_Light كتب:

هل هذه هي الخوارزمية الأمثل ؟

إن كان هناك تحسينات ممكنة، أرجو اقتراحها

كما أتمنى أن يقوم أحد الأخوة بتطبيق الخوارزمية على MatLab لمقارنة الأداء

طبعا اخى الكريم هذه ليست الخوارزمية الأمثل ولا حتى خوارزميه مقبوله :). لدى ملاحظات وتحفظات كثيرة عليها , لكن دعنى اولا استفسر عن بعض الامور حتى يكون الحكم صحيح.

ما وظيفة الامر break فى الخوارزميه؟ هل يستخدم لكسر الحلقة الداخليه لـ c فقط؟ ام سيكسر جميع الحلقات دفعة واحده؟

ما وظيفة الامر continue فى الخوارزميه؟ هل يستخدم لتجاهل باقى الخطوات التى تليه فى الحلقة الداخل لـ c والذهاب لقيمة c التاليه؟ ام سيكسر الحلقة الداخليه c ويذهب للقيمة التاليه للحلقة b؟

منتظر ردك اخى الكريم ومن ثم سأضع تعليقى على الخوارزميه ،،،

عذراً على التأخير ...

break تستخدم لكسر الحلقة الداخلية فقط

continue لتجاهل باقي الحلقة والإكمال من العنصر التالي

السلام عليكم

Speed_Of_Light كتب:

هل هذه هي الخوارزمية الأمثل ؟

إن كان هناك تحسينات ممكنة، أرجو اقتراحها

مع أنني لست صديقا" جيدا لـ كومبايلر الجافا ... الا أنني أستطيع ان أضع هذه الملاحظة على هذا الكود :

اذا كان كومبايلر الجافا ..مشابها" لـ لغات البرمجة الاخرى ..هذا يعني ان الحلقة C ستصل الى الرقم 999 في الدورة الاولى قبل اغلاقها!

اذا صح ذلك ...كان عليك أن تضع شرط عداد الحلقة C لا يتجاوز 500 بدلا" من كتابة شرط مجموع الاضلاع , لأنه في حال التجاوز سيكون c أكبر من a+b وهذا مخالف لشرط المثلث أعتقد بذلك ستختصر الكثير من العمليات ...حاول تطبيق هذه الملاحظة ..وأخبرني بالزمن الجديد

Speed_Of_Light كتب:

كما أتمنى أن يقوم أحد الأخوة بتطبيق الخوارزمية على MatLab لمقارنة الأداء

انشغالي هذه الايام كثيرا" يحول دون ذلك ... ولكني سأعود اليها قريبا" :cool:

السلام عليكم ورحمة الله

اخونا الفاضل Speed_Of_Light

بداية كما نوه اخونا الفاضل Devd , فإن عدد العمليات الحسابيه هنا مبالغ فيه بشكل كبير ويمكن توفيره بناء على ملاحظته وبعض الملاحظات التى سأضعها هنا ان شاء الله.

وملاحظاتى على خوارزمية حضرتك , سأحاول تلخيص ما استطيع منها فى النقاط التاليه

اولا: صراحة انا لم ارى برنامج قبل ذلك فيه متغير الحلقة التكرارية الخارجيه يعتمد على متغير الحلقة التكرارية الدخليه !!! دائما يكون العكس تماما ، اى انه يمكن وضع شرط على متغير الحلقة التكرارية الداخليه بناءا على قيمة الحلقة التكرارية الخارجية. لأنه ببساطه اى تغيير ، مهما كان صغير , على المتغير الخارجى سيؤثر مباشرة فى المتغير الداخلى , وليس العكس.

فأنت حضرتك اتخذت a هو متغير الحلقة التكرارية الخارجية , و b هو متغير الحلقة التكرارية الدخليه. ووضعت شرط على ان a<=b فى الحلقة الخارجيه. فكيف تتخيل ان يكون هذا الشرط مؤثر واصلا b ستتحرك بحرية حتى تصل الى القيمة القصوى لها فى الحلقه التكرارية الدخليه , وبالتالى سينعدم تأثيرها بعد ذلك ولن يكون للشرط الذى وضعته اى تأثير مطلقا. وكذلك الحال مع كل من المتغير c والمتغير b.

ثانيا: بشكل الخوارزميه الحالى , سيكون هناك مثلثات متكرره. وبالتالى بالإضافة الى الوقت الضائع ستكون النتائج ايضا خاطئة.

فمثلا ، فى اول الامر a=1 , b=1 , c=1 وبعد ذلك ستزيد قيمة c لتكون c=2. يبقى كده عندنا المثلث ذو الاضلاع 1 و 1 و 2. بعد ان تصل c الى قيمتها القصوة وتنكسر الحلقة الخاصة بها , فسيكون قيم المتغيرات فى بداية الدورة الجديدة هى a=1 , b=2 , c=1 , اى اننا عدنا مرة ثانيه للمثلث الذى اضلاعه هى 1 و 1 و 2. وبالتالى نفس المثلث سيتم احتسابه مرتين. وسيحدث الامر ذاته عندما تكون a=2 , b=1 , c=1.

ثالثا: حضرتك جعلت الخوارزميه تكسر حلقة المتغير c عندما يزيد محيط المثلث عن maxPerimeter. ولكنك تركت نفس الحلقه تستمر عندما لا يتحقق شرط ان a, b, c اضلاع مثلث !!! لماذا؟

المفروض ان قيمة a,b ثابته (فى الحلقة الداخليه) ولكن قيمة c تزداد. فالمنطقى جدا انه طالما وصلت c لقيمة معينه اصبحت عندها لا تصلح لتكون ضلع مثلث مع a, b يبقى اكيد كل القيم الاكبر لها لن تصلح ايضا. وبالتالى كان يجب ان تضع break بدلا من continue.

رابعا: لا يوجد داعى اصلا لاستخدام الدالة التى تتحقق من هل قيم a, b, c تمثل اضلاع مثلث ام لا. اخونا Devd اشار قبل كده ان اى ضلع فى مثلث دائما يكون اصغر من حاصل جمع الضلعين الاخرين واكبر من حاصل طرحهما. وبالتالى كنت ممكن تضع شرطين اضافيين على عداد الـ c وكنت هتوفر حسابات كثيرة جدا.

هذه بعض الملاحظات السريعه. وان شاء الله تعالى فى اسرع وقت ممكن , سأضع بعض التوضيحات التى من الممكن ان تجعل الخوارزميه اخف واسرع كثيرا مما هى عليه الان.

اسف على الإطالة وبالله التوفيق ،،،

تلميح يحل السؤال بالطول و بالعرض :excl:

هل تعرفون Sieve_of_Eratosthenes؟!

يمكنك حل السؤال الذي طرحتموه يا أخوة بنفس طريقة اكتشاف الأعداد الأولية, إضافة إلى الأسئلة رقم: 69, 72, 73,

بالمناسبة, مهما حاولت أنت تقوم بعمل Optimization للخوارزمية التي تقوقون بطرحها, و التي حاولت معها بالطول و بالعرض :) سيبقى اكتشاف الـ Primitive Triangle و تحديداً عن طريق GCD عملية مكلفة جداً,

و تزداد التكلفة كلما زاد عدد خانات العدد.

تحياتي للجميع و بالتوفيق مع الموقع الرائع PE

اقتباس

هل تعرفون Sieve_of_Eratosthenes؟!

من اقدم الخوارزميات لايجاد جميع الاعداد الاولية اصغر من عدد معين n. ان لم تكن اقدمها.

الخوارزمية:

1. ضع الاعداد من 2 الى n في مصفوفه.

2. ضع المؤشر عند اول خلية في المصفوفة .

3. ابحث عن جميع مضاعفاتها في الخلايا اللاحقة و احذفها (ساويها بالصفر مثلا)

4. انقل المؤشر الى الخلية اللاحقة ان كانت صفر انتقل للتي تليها .

والا كرر الخطوة 3 حتى تصل الى اخر عدد n

الخوارزمية سريعة وتكلف اقل بكثير من n^2 .كما يمكن تقسيم العمليات على اكثر من معالج ببساطة وبالتالي زيادة سرعة ادائها .

أهلاً أخي إبراهيم,

أنا الحقيقة قصدت الفكرة نفسها, و لم أقصد الأعداد الأولية بالتحديد.

أولاً, هذه الطريقة واجهت مشكلة فيها في البداية, و لكن من "هنا" جاء الحل :)

كنت أريد حساب عدد المثلثات, الصحيحة الأضلع بطول محيط p على سبيل المثال, و لكن لم أستطع إيجاد طريقة صحيحة. و لكن بمجرد الحصول على هذه المعلومة من الرابط السابق, يمكنك عمل Sieving للمثلثات الغير أولية.

حيث تبدأ من المحيط عندما يكون 3 و تنتهي عندما يكون المحيط 10000000.

على سبيل المثال, عندما يكون طول المحيط خمسة, فهناك نفس "العدد" من تلك المثلثات و لكن بصيغة أخرى, حيث تكون تلك الأطول من مضاعفات المثلثات التي محيطها 10, بالتأكيد بعد أن تطرح

جميع المثلثات الغير أولية من جميع الأطوال, تقوم بجمع عدد المثلثات الأولية و تظهر النتيجة.. هذا هو الكود بـ ++C, ربما يكون أوضح من ++C لو قام أحد الأخوة بكتابته بـ matlab أو python :)

typedef unsigned long long bigint; // bigint is just a large integer!

// "nint" function: round to nearest integer
bigint round(double r) {
	return static_cast<bigint>
		(
			(r > 0.0) ? floor(r + 0.5) : ceil(r - 0.5)
		);
}

bigint count_integer_triangles_with_integer_sides(bigint perimeter)
{
	return 
		round((perimeter*perimeter) / 12.0)
		-
		(perimeter / 4)*((perimeter+2) / 4);
}

int main()
{
	const bigint max_perimeter = 10000000 + 1;
	bigint perimeters[max_perimeter] = {0};

	for(std::size_t i = 0; i < max_perimeter; ++i)
		perimeters = count_integer_triangles_with_integer_sides(i);

	// the smallest perimeter with integer sided triangle
	// has a perimeter of length == 3
	for(std::size_t i = 3; i < max_perimeter; ++i)
	{
		for(std::size_t j = i*2; j < max_perimeter; j += i)
			perimeters[j] -= perimeters;
	}

	// print the sum of all perimeters in the array.
	bigint sum = 0;
	for(std::size_t i = 0; i < max_perimeter; ++i)
		sum += perimeters;

	std::cout << sum;
}

بالمناسبة, كما قلت سابقاً, الأسئلة 69 و 72 و 73, يمكن حلها بنفس الطريقة, أي الـ Sieving, و لكن الفرق, أنها هذه المسألة جننتي و لم أجد طريقة لحساب عدد

المثلثات الصحيحة لمحيط بطول p مثلاً! شكراً لـ Wolfarm :P

تحياتي,

يا شباب,

كنت قد فتحت موضوعاً في SO حول هذه المسألة بالذات, و قبلت الإجابة التي تعطي الطريقة لعد المثلثات دون استخدام الصيغة الموجودة في رابط Wolfarm في حلي في الأعلى,

أنا قلت بأني لم أستطع إيجاد طريقة لحساب عدد المثلثات الصحيحة بمحيط طوله p على سبيل المثال,

هل هناك من يستطيع أن يشرح لنا "بطريقة أبسط", طريقة ذلك الشخص الذي أجاب أو حتى بطريقته الخاصة؟

الصراحة رغم أني حللت السؤال, إلا أني لم أستطع حتى الآن أن أحل هذه العقدة :(

حاولت فهم حل المجيب عن السؤال في SO و لكن محاولاتي باءت بالفشل أيضاً :(

السلام عليكم ورحمة الله

اخى الفاضل خالد

لا اعلم الصراحة هل حلك السابق بطريقة الـ Sieving يعطى نتائج صحيحة ام لا؟ ولكنه بالطبع حل سريع جدا وعبقرى جدا لحل المسألة.

بخصوص سؤالك عن إجابة هذا الشخص فى الموقع المشار اليه:

هل تريد توضيح لكل رده؟ ام الخلاصة فقط؟

عامة خلاصة إجابته , ان عدد المثلثات التى أطوال أضلاعها صحيحة ومحيطها هو P هو نفس عدد التقسيمات التى يمكنك استخدامها لتقسيم العدد P الى ثلاث اعداد صحيحة موجبة r, q, p، تحت شرط ان تكون جميع الاعداد من نفس نوع العدد P ، بمعنى انه لوكان العدد P فردى فيجب ان تكون الثلاث اعداد r, q, p فرديه , ولو كان العدد P زوجى فيجب ان تكون الثلاث اعداد r, q, p زوجيه.

مثال: لنفترض ان P=7 ، إذا يمكننا تقسيمها لثلاث اعداد (فرديه) بالشكل التالى

1 و 1 و 5

1 و 3 و 3

فقط لاغير ، فيكون عدد المثلثات ذات الاطول الصحيحة والتى محيطها 7 هو "مثلثان فقط" نظرا لانه يوجد عدد 2 تقسمه (فرديه) فقط.

ثم ينصحك هذا الشخص أن تقوم بتكرار هذا الامر على عدة قيم مختلفة لـ P ومن ثم استنتاج قانون عام منها.

هذا والله اعلى واعلم ،،،

كيف نتحقق من صحة النتيجة ؟

أنا نتج معي 5777137721072966245

الكود في جافا:

public class Main {

    static Long count_integer_triangles_with_integer_sides(long per) {
        return (per * per) / 12 - (per / 4) * ((per + 2) / 4);
    }

    public static void main(String[] args) {
        int max_perimeter = 10000000;

        long perimeters[] = new long[max_perimeter+1];

        for (int i = 0; i <= max_perimeter; ++i) {
            perimeters = count_integer_triangles_with_integer_sides(i);
        }

        for (int i = 3; i <= max_perimeter; ++i) {
            for (int j = i * 2; j < max_perimeter; j += i) {
                perimeters[j] -= perimeters;
            }
        }

        long sum = 0;
        for (int i = 0; i <= max_perimeter; ++i) {
            sum += perimeters;
        }

        System.out.println("sum: " + sum);
    }
}

السلام عليكم ,,,

أستاذي عماد,

قمت بتجربة الحل و حصلت على الإجابة الصحيحة رغم أني لا أعتبر أني حللته حقيقة لأني لم أستنتج طريقة لعد المثلثات دون استخدام الصيغة الموجود في Wolfarm :)

بالنسبة للـ Partitioning فأنا قمت بكتابة خوارزمية لعد الـ partitions of an integer لحل أسئلة أخرى, و لكن لا أعرف الطريقة لعد partitions ضمن شروط معينة,

أتمنى لو كان هناك شيء يمكننا قراءته تنصحنا به أستاذي العزيز,

أعتقد أنك أعطيت مثالاً للتقسيمات, و لكن:

اقتباس

1 و 1 و 5

لا تعتبر مثلث أصلاً, لأن 5 > 2

أخ Speed_Of_Light,

إجابتك قريبة جداً, و لكنك نسيت استخدام دالة التقريب nint أو ما يسمى round to nearest integer عند كتابة الصيغة,

تحياتي,