مثال ساختمان داده از صف اولويت با ليست ژيوندي
پانزده سال پیش منتشر شده
تعداد بازدید: 9591
کد پروژه: 1050
شرح پروژه
بهار 88 موعد تحويل: 29/2/88
اهداف پروژه
شبيه سازي يک فرايند مبتني بر رويداد (event-driven)
بکارگيري ساختمان داده هاي صف اولويت و ليست پيوندي
هدف اين پروژه شبيه سازي يک فروشگاه به منظور انجام يک تمرين برنامه نويسي با صفها است. مسئله اصلي اين است که مدير يک فروشگاه قصد دارد متوسط زمان انتظار مشتريان در فروشگاه و تعداد بهينه فروشندگان را تعيين کند. اين امر به او کمک مي کند تا تدابيري در جهت رضايتمندي مشتريان بيانديشد. هدف اين است که مشتريان به مدت طولاني در صف منتظر نماند و به علاوه تعداد فروشندگان زياد نباشد تا در هزينه هاي فروشگاه صرفه جويي شود. براي اين شبيه سازي نياز به دانستن اطلاعات زير است:
فروشگاه در ساعت 8 صبح باز مي شود و در ساعت 4 بعدازظهر مي بندد. اگر از ساعت 4 گذشته باشد اما هنوز مشتري در صف باشد به او سرويس مي دهند تا کارش به پايان برسد اما درهاي ورودي فروشگاه بسته مي شود و اجازه ورود مشتري جديد داده نمي شود.
فروشگاه داراي تعدادي فروشنده است. هر فروشنده داراي يک صف مجزا است. هنگامي که يک مشتري وارد مي شود به کوتاهترين صف ملحق مي شود. اگر چند صف داراي طول يکسان باشند سمت چپ ترين صف (صفي که به در نزديکتر است) را انتخاب مي کند.
تعدادي از صفها صف سريع ناميده مي شوند. اين صفها براي مشترياني است که 10 يا کمتر کالا خريده اند. به عبارت ديگر اگر مشتري 10 يا کمتر کالا خريد کرده باشد در يکي از صفهاي سريع مي ايستد.
ورودي مسئله
فروشگاه داراي مشترياني است که در زمانهاي مختلف وارد فروشگاه مي شوند. به علاوه مدت زمان سرويس مشتريان متفاوت است. اطلاعات مشتريان در فايل customers.txt قرار دارد. در هر خط از فايل اطلاعات نام مشتري، زمان ورود، زمان سرويس، تعداد کالاهايي که خريده است آورده شده است. اين اطلاعات با يک فاصله از هم جدا شده اند.
خروجي برنامه
1- متوسط زمان انتظار مشتريان را براي حالات زير مقايسه کنيد.
حالتي که تنها 5 صف معمولي تعريف شود (بدون در نظر گرفتن صفهاي سريع).
حالتي که 3 صف معمولي و 2 صف سريع تعريف شود.
2- متوسط زمان انتظار مشتريان براي 1، 5 و 10 فروشنده را مقايسه کنيد. صفها معمولي در نظر گرفته مي شوند.
نکته: زمان انتظار مشتري عبارت است از مدت زمان بين ورود مشتري به فروشگاه تا زماني که نوبت او براي پرداخت مي شود.
شبيه سازي مبتني بر رويداد
در اين روش شبيه سازي از صف اولويت براي پردازش رويدادها به ترتيب زمان وقوع آنها استفاده مي شود. هرگاه رويدادي رخ دهد در صف اولويت درج مي شود. هر رويداد بر حسب زمان وقوع خود در صف قرار مي گيرد. رويداد نزديکتر در ابتداي صف است. براي پياده سازي صف اولويت از ليست پيوندي مرتب استفاده شود.
در هر مرحله از شبيه سازي، رويداد بعدي (رويداد نزديکتر از لحاظ زماني) انتخاب و پردازش مي شود. تا زماني که صف خالي شود. در اين پروژه تعدادي از رويدادهاي ممکن عبارتند از ورود، سرويس (تخصيص يک فروشنده به مشتري) و خروج يک مشتري.
مراحل کار به صورت زير است: ابتدا رويدادهاي ورود مشتريان در صف اولويت درج مي شود. هرگاه رويداد جديدي رخ دهد در محل مناسب از صف قرار مي گيرد. هر فروشنده به نفر جلوي صف سرويس مي دهد. هرگاه کار يک مشتري به پايان رسيد صف را ترک مي کند. اين کار تا اتمام کار کليه مشتريان ادامه مي يابد
تو ضيحات تکميلي
فايل ورودي يک فايل متني به شکل زير است
تعداد کالاهاي خريدار شده مدت سرويس ساعت ورود نام مشتري
f 08:45 10 5
r 12:00 70 50
و..
ساعت ورود هميشه به همين شکل وارد مي شود00:00
مدت سرويس همواره برحسب دقيقه خواهد بود
دو نوع رويداد ر اين مثال تعرف مي شود ورود خروج
بايد يک صف وقايع اولويت براي پياده سازي اي پروزه تعريف شود
نام اين صف صف وقايع است و شامل نام مشتري ساعت رويداد است
براي پيادهخ سازي صف از ليست يوندي بايد استفاده شود
ابتدا برحسب زمان ورود مشتري هاتدر صف هاي کارمندان قرار مي گيرند
و سپس يکي يکي سرويس مي شوند و با رويداد خروج به مکان درست از صف انتقال مي يابند
اگر يک خروج و يک ورود همزمان انجام شود ابتدا خرو ج درج مي شود
اگر خروجي به ابتداي صف رسيد حذف مي شود
قابل تحویل:
مهارت ها و تخصص های مورد نیاز
بودجه
5,000 تومان تا 100,000 تومان
مهلت برای انجام
4روز
وضعیت مناقصه
انجام شده
درباره کارفرما
عضویت شانزده سال پیش
