مساعدة في حل مسألة

[حسن جدوع]

أريد مساعدتكم في حل هذه المسألة:

لدى المزارع جون عدد من الأبقار N موجودين في الحظيرة (يعني N هو عدد الأبقار)

لسوء الحظ ، قامت هذه الأبقار بالهروب من الحظيرة والتوزع حول المزرعة

وثم بدأوا بتخريب المزرعة وتكسر الأغراض (الخ)

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

لحسن حظ المزارع جون بأن الأبقار كلها متوزعة على خط مستقيم نفرض أن هذا الخط مرقم من -(لانهاية) إلى +(لانهاية)

وكل بقرة موجود بالمكان x (حيث x هو بعد البقرة على نقطة المبدأ لهذا المستقيم)

يبدأ المزارع جون من النقطة 0 ويستطيع المشي خطوة واحدة كل دقيقة (مثلاً هو بالمكان 0 بعد دقيقة يمكنه أن يتوجه إلى -1 أو +1) وكل بقرة تقوم بتخريب

المزرعة بمعدل 1 دولار كل دقيقة

إذا وصل المزارع جون إلى أحد الأبقار يبدأ فوراً بتلقيحها وبالتالي تتوقف عن التخريب

مهمتك الآن كتابة برنامج بلغة PHP يحسب أقل عدد خسائر للمزارع جون (مقدرة بالدولار)

المعطيات:

الدخل هو عبارة عن ملف باسم runcows.in بالشكل التالي:

السطر الأول: يعطيك الرقم N الذي هو عبارة عن عدد الأبقار
السطر الثاني: يعطيك احداثيات كل بقرة على المستقيم المذكور كل رقم مفصول عن الآخر بمسافة ( )


الخرج هو عبارة عن ملف runcows.out:

تقوم بانشاء هذا الملف ثم كتابة سطر وحيد يحوي أقل عدد من الخسائر للمزارع جون


مثال: لنفرض أن ملف الدخل runcows.in يحوي البيانات

5
-7 -2 1 7 8

إذاً عدد البقرات الهاربة هي 5 واحذاثيات كل منها هي -7 -2 1 7 8 بافتراض أن المزارع جون سوف يبدأ
مسيره من النقطة 0 الآن عليه أن يقوم بالذهاب إلى البقرات الخمسة لتلقيحهم كي لا يخسروه 1 دولار بالدقيقة لكل بقرة

الحل هو:
في الدقيقة 1: يدهب المزارع جون إلى المكان (-1) وبالتالي يخسر 5 دولارات لأن عدد الابقار 5
في الدقيقة 2: يدهب المزارع جون إلى المكان (-2) وبالتالي يخسر 5 دولارات فيصل الي البقرة الأولى (التي في المكان -2)ويلقحها
في الدقيقة 3: يدهب المزارع جون إلى المكان (-1) وبالتالي يخسر 4 دولارات لأن البقرة السابقة هدئت ولن تخرب فيقبى 4 بقرات غاضبة
في الدقيقة 4: يدهب المزارع جون إلى المكان (0) وبالتالي يخسر 4 دولارات
في الدقيقة 5: يدهب المزارع جون إلى المكان (1) وبالتالي يخسر 4 دولارات ثم يلقح البقرة التي في المكان 1
في الدقيقة 6: يدهب المزارع جون إلى المكان (2) وبالتالي يخسر 3 دولارات
في الدقيقة 7: يدهب المزارع جون إلى المكان (3) وبالتالي يخسر 3 دولارات
في الدقيقة 8: يدهب المزارع جون إلى المكان (4) وبالتالي يخسر 3 دولارات
في الدقيقة 9: يدهب المزارع جون إلى المكان (5) وبالتالي يخسر 3 دولارات
في الدقيقة 10: يدهب المزارع جون إلى المكان (6) وبالتالي يخسر 3 دولارات
في الدقيقة 11: يدهب المزارع جون إلى المكان (7) وبالتالي يخسر 3 دولارات ثم يلقح البقرة الموجودة في هذا المكان
في الدقيقة 12: يدهب المزارع جون إلى المكان (8) وبالتالي يخسر 2 دولارات ثم يلقح البقرة الموجودة في هذا المكان
ثم يسير في كل دقيقة حتى يصل إلى البقرة -7 فيكلفه 15 دولار خلال 15 دقيقة فيلقحها
ويكون قد خسر بالمجموع: 57 دولار

إذاً الطريق من 0 إلى -2 إلى 1 إلى 7 إلى 8 إلى -7 هو أقل خسائر للمزارع جون بمقدار 57 دولار (حاول أن تجرب طريق أخر لن تجد طريقاً يكلف أقل تكلفة

من الدولارات)


وبالتالي يتم طباعة الرقم 57 في الملف runcows.out

انتهت المسألة


لقد حاولت أن ابسط شرح المسألة قدر الإمكان

ولكني يا اخواني لم استطع أن احل هذه المسألة إلا بطريقة تجربة جميع الأحتمالات(الطرق) ولكن هذه الطريقة تكلف وقتاً خصوصاً مع الأرقام الكبيرة وتكلف

مساحة كبيرة في الذاكرة

لذلك أنا أريد طريقة أخرى أقصر غير تجريب كل الاحتمالات (ربما عن طريق حل رياضي أو اي شي)


ولكي اساعدكم يوجد ملف مرفق مبرمج بلغة c++ يحل المسألة باعتماد مبدأ تجريب كل الاحتمالات من المؤكد انه سوف يفيدكم

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

مثال

3
-3 1 2

فيقوم البرنامج مباشرة باخراج الحل وهو :

===
MIN:10:
0 | 1 | 2 | -3 |
Press any key to continue . . .

حيث MIN:10 يعني أن اقل تكلفة هو 10 ثم
السطر: 0 | 1 | 2 | -3 | يعني ان الطريق الأفضل هو من 0 إلى 1 إلى 2 إلى -3

أوكد لكم مرة أخرى أنا أريد طريقة أخرى غير طريقة تجربة كل الأحتمالات وأريد الحل مكتوباً بلغة PHP ويقوم بالحصول على بياناته من ملف

runcows.in ويطبع الحل في الملف runcows.out ويفضل ذكر الطريقة التي اعتمد عليها

[الفريد]

في تمرين بقرة جون ... (1 ثم -2 ثم -7 ثم 7 ثم 8 ) الخسارة 53

[أبو كامل]

إن كنت تريد حل برمجي مباشر فسيصعب ذلك.

لكن للتوجيه، يمكنك البحث في بحوث العمليات operation research والبحث في لغات البرمجة الخاصة بهذا العلم.

[حسن جدوع]

في تمرين بقرة جون ... (1 ثم -2 ثم -7 ثم 7 ثم 8 ) الخسارة 53

من 0 إلى 1 تخسر 5
من 1 إلى -2 تخسر 12
من -2 إلى -7 تخسر 15
من -7 إلى 7 تخسر 28
من 7 إلى 8 تخسر 1

المجموع أكبر من 57 لذلك هذا ليس حلاً

[Abdullah Alhoshan]

لا تنسى مشاركاتنا بالحل اذا وجدت .. حاولت بشكل سريع فهم المسأله لكن يبي لها تفكير اكثر .

[Cenrak]

السلام عليكم و رحمة الله و بركاته،
بما إنك فاهم بالبرمجة، و بسبب قرب الـ syntax بس الـ ++C و الـ PHP، سأقوم بطرح أفكار بس و الباقي عليك.

1. الطريقة المضمونة:
يبغالها زي ما قلت تدور على كل الاحتمالات. لكن السؤال، ما هي الاحتمالات؟
هذه رسمة سريعة سويتها لجزء، في الحقيقة نصف، الاحتمالات في السؤال:

نقطة البداية صفر دايما. و لأنه على محور أفقي، معناته إنه في بقرة على يمينه و يساره (فرضية)، بس في المثال يوجد.

فـ يبدأ المزارع من 0. تكون يمينه بقرة على بعد 1، و بقرة عن يساره على بعد 2 (الموجودة في -2).
طيب المشكلة ما تعرف أي الطرق يمكن يجيبلك أقل خسائر. فـ بنبني binary tree، كل طريق يمثل احتمالية.

فأول احتالمية، يروح للبقرة عن يمينه. طيب؟ إذا وصل لازم نحسب برضه إذا راح للبقرة اللي في -2 و 7. و تستمر لحد ما تغطي الاحتمالات.
مشكلة الطريقة هذه إنها بتاخذ وقت طويل كل ما كثرت المدخلات،
في أسوأ الأحوال، مستحيل تعدي عملية
و هذا كثير لأنه صارت الخوارزمية اسمها non-polynomial algorithm ...
طيب هذه ايش حلها؟ عادة يستخدموا شئ اسمه greedy algorithms أو "الخوارزميات الطماعة" و هدفها الوصول لنتيجة "مرضية" بوقت سريع. و طبعا نسبة "الرضى" لازم تكون مقبولة.

طيب ايش الخوارمزيات المرضية في هذه الحالة؟
من عندي، (لسه ممشي حالي في الخوارزميات ) بس هذه أحد الطرق اللي جات معايا.
الهدف من الخوارزيمة: تقليل الخسائر.
يعني: محاولة تلقيح الأبقار بأسرع وقت
يعني: محاولة إنك تمسك الأبقار الأقرب فـ الأقرب لنقطة المزارع
يعني: تبدأ بـ 0، تمسك 1، بعدها -2، -7، 7، بعدها 8. مجموع الخسائر 5+12+15+28+1=61
الخوارزميات الطماعة مو دايما ناجحة. بس تجيب نتائج مش بطالة نوعا ما

بأدورلك على خوارزميات ثانية و اردلك

رائد