المطلوب في هذا التمرين كتابة خوارزمية تحسب جميع الإمكانيات لأرقام يقوم بإدخالها المستخدم
مثال:
إذا المستخدم الأرقام: 2، 3، 4، 7
يقوم البرنامج بحساب المجاميع: (2، 2+4، 2+4+3، 2+4+3+7، 2+4+7، 2+3، 2+3+7، 2+7، 4، 4+3، 4+3+7، 4+7، 3، 3+7، 7)
المدة: 15 يوم
العملية أشبه بـ Brute force لكنها أبسط...
كل الحلول مقبولة
27-07-2010, 09:24 PM (آخر تعديل لهذه المشاركة: 27-07-2010, 09:28 PM بواسطة kachwahed.)
@TF6M
وعليكم السلام ورحمة الله وبركاته
حل صحيح مبدئيا، لكنه يقتصر على الأرقام.
للتذكير: مجموع الاحتمالات يمثل مجموع nCr حيث r عدد الإدخالات وn حجم كل مجموعة
إذ لا وجود للتكرارات، لأن: 1+2=2+1 !
مثال: كم مجموعة متكونة من 3 أرقام يمكن تكوينها من أصل 10 أرقام. الجواب 3nCr10
13-08-2010, 01:38 AM (آخر تعديل لهذه المشاركة: 13-08-2010, 01:44 AM بواسطة kachwahed.)
السلام عليكم
أولا أعتذر عن التأخير
...
الحل بسيط جدا ويعتمد على فهم جيد لمبدأ عمل الخوارزمية
سأقوم بالشرح باستخدام جدول من الأحرف (Array of Chars) والمبدأ واحد (Integers/Strings...)
حسنا...
منهجية تفكير:
ما هو المطلوب؟
المطلوب من خلال أرقام مثلا: 2، 3، 4، 7 إيجاد جميع عمليات الجمع الممكنة بين هذه الأرقام دون تكرار الاحتمالات لأن 2+3=3+2
كيف نصل إلى هذا المطلوب؟
لتفادي الخلط بين الرتبة والعنصر سنستخدم حروف لاتينية: A, B, C, D
من الصعب جدا إيجاد الحل مباشرة دون تحليل النتائج
بعبارة أخرى دعونا نعيد ترتيب نتائج بشكل يسهل تفسيرها
بعد بضعة محاولات نحصل على عرض منطقي جدا:
كود :
A
A+B
A+B+C
[color=Red] A+B+C+D [/color]
A+B+[color=Blue]D[/color]
A+C
A+C+D
A+D
B
B+C
B+C+D
B+D
C
C+D
D
الآن بدأت الأمور تتضح شيئا فشيئا
كيف نحصل على الخوارزمية الصحيحة؟
من خلال هذا العرض الأخير نستنتج التحليل الآتي:
- البداية بإضافة أول عنصر (A)
-> إذا وجد عنصر بعده (B) نضيه إليه (لاحظ ترتيب التجميعات فوق!)
-> إذا لم يوجد شيء بعده (يعني وصلنا إلى آخر عنصر من الجدول هنا A+B+C+D حيث لا شيء بعد D)
-> -> نقوم بحذف العنصر الأخير (D) وتغيير الذي قبله بالعنصر الموالي (أنظر السطر الأحمر: حذفنا D وعوضنا الذي قبله (C) بالعنصر الموالي: D)
وهكذا انتهينا
كيف نحرر الخوارزمية؟
نقوم بترجمة كل سطر مما سبق إلى ما يوافقه من التعليمات مع تجزئة الكود.
- لدينا الجدول:
PHP كود :
var arChar: array[0..3] of char; begin arChar[0] := 'A'; arChar[1] := 'B'; arChar[2] := 'C'; arChar[3] := 'D';
لنحصل على ترتيب آخر عنصر من السلسلة:
PHP كود :
function GetLastCharIndex(var Item: string; arChar: array of Char): Integer; begin if Item = '' then Result := -1 else Result := Pos(Item[Length(Item)], arChar)-1; end;
للحصول على عدد الاحتمالات الممكنة:
PHP كود :
function GetPossibilies(arChar: array of Char): Integer; var i: Integer; begin Result := 0; for i := 0 to High(arChar) do Result := Result+ nCr(High(arChar)+1, i); end;
nCr من هنا.
نبدأ بإضافة الأحرف إلى السطر في متغير نصي Item ثم إضافته إلى TListBox نسميها lbResults
كل ذلك يجري في إجرائية مستقلة تأخذ جدول من الأحرف كمعلمة (Parameter) ولتكن ParseNum
PHP كود :
procedure TfMain.ParseNum(var arChar: array of Char); var ItemsCount: Integer; { نقوم بكتابة السطر على هذه السلسلة ثم نضيفها إلى القائمة } Item: string; begin { حساب عدد الاحتمالات الممكنة} ItemsCount := GetPossibilies(arChar); { يستمر الطواف على الجدول مادمنا لم نبلغ عدد الاحتمالات الممكنة} while lbResults.Count < ItemsCount do begin { -> إذا لم نصل إلى نهاية الجدول } if High(arChar) > GetLastCharIndex(Item, arChar) then begin { هذا الفحص فقط لعدم إضافة علامة الجمع في أول السطر... } if Item = '' then Item := arChar[GetLastCharIndex(Item, arChar)+1] else { -> نضيف إلى السطر الحرف الموالي } Item := Item + '+'+ arChar[GetLastCharIndex(Item, arChar)+1]; end else begin { -> أما إذا بلغنا نهاية الجدول: فنقوم بحذف آخر عنصر } Delete(Item, Length(Item)-1, 2); { ... ونغير العنصر الذي قبله بالعنصر الموالي من الجدول } Item[Length(Item)] := arChar[GetLastCharIndex(Item, arChar)+1]; end; { -> في الأخير نطبع محتوى السطر } lbResults.Items.Add(Item); end; end;
وهكذا نصل إلى المطلوب. المثال مرفق ومعه مثال باستخدام TStringsـ ـ ـ
حوصلة
هذه خوارزمية بسيطة أسميتها Brute Force Shuffle مفيدة في بعض الحسابات التجارية وغيرها...
الهدف من التمرين ليس الخورازمية بذاتها وإنما طريقة فهم وتحليل المشكلات الحسابية لإيجاد الحلول البرمجية...
ملاحظة: يمكن طرح أمثلة أخرى لمن يريد. وحان الآن وقت طرح الملفات المصدرية.
إقتباس : البداية بإضافة أول عنصر (A)
-> إذا وجد عنصر بعده (B) نضيه إليه (لاحظ ترتيب التجميعات فوق!)
-> إذا لم يوجد شيء بعده (يعني وصلنا إلى آخر عنصر من الجدول هنا A+B+C+D حيث لا شيء بعد D)
-> -> نقوم بحذف العنصر الأخير (D) وتغيير الذي قبله بالعنصر الموالي
أخى kachwahed
أتعرف
أمور كثيرة لا يحلها الكود بقدر ما يحلها المنطق
مثال أقل ما يقال عنه أنه رائع
منطق رائع و كود جميل
شكرا لك