أريد مساعدتكم في حل هذه المسألة:
لدى المزارع جون عدد من الأبقار 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 يعني أن اقل تكلفة هو 10 ثمكود:=== MIN:10: 0 | 1 | 2 | -3 | Press any key to continue . . .
السطر: 0 | 1 | 2 | -3 | يعني ان الطريق الأفضل هو من 0 إلى 1 إلى 2 إلى -3
أوكد لكم مرة أخرى أنا أريد طريقة أخرى غير طريقة تجربة كل الأحتمالات وأريد الحل مكتوباً بلغة PHP ويقوم بالحصول على بياناته من ملف
runcows.in ويطبع الحل في الملف runcows.out ويفضل ذكر الطريقة التي اعتمد عليها