مقدمه
یکی از الگوریتم های ساده که معمولا در درس ساختمان گسسته، طراحی الگوریتم و ساختمان داده به صورت پایه مطرح می شود الگوریتم فلوید وارشال می باشد. این الگوریتم با مرتبه O(N3) شاید یکی از بدترین انتخاب ها برای حل مسئله به علت کندی بیش از حد باشد. اما وقتی تعداد نود به اندازه کوچکتر از 200 باشد تفاوت قابل توجه ای با الگوریتم های خوب جایگزین ندارد و به علت پیاده سازی ساده و سریع این الگوریتم همیشه اگر در محدودیت های مساله قابل استفاده باشد جایگزین بقیه کاندید ها می شود.
رابرت فلوید و استفان وارشال همزمان باهم در مقالات مختلف در سال 1962 این الگوریتم را منتشر کردند، و به افتخارشان الگوریتم فلوید-وارشال نام گرفت که به اختصار به آن فلوید نیز گفته می شود، رابرت فلوید دارای یک الگوریتم خوب دیگر برای پیدا کردن دور در لیست پیوندی یا روابط بازگشتی بر اساس مقدار قبلی می باشد که باز با اسم الگوریتم فلوید مشهور است اما به اندازه این الگوریتم اعمال تعدی معروف نیست.
دلیل من برای انتخاب این الگوریتم برای بخش درسنامه الگوریتم ها، روزمره و ساده بودن الگوریتم فلوید بود که با توجه به بازدید های وبلاگ بنظر می رسد دانشجو های زیادی در طول ترم نیاز به مطالعه و استفاده از این الگوریتم دارند.

ادامه مطلب

سلام دوستان

قبلا یک سوال از مسابقه DM Contest ShareCode به اسم  حل مسئله کابل های در هم - Tangled in Cables Solotion را حل کرده بودیم در این مسابقه واقعا سوال های خوبی انتخاب شده بود و همه سوالها در واقع کاربرد یکی از الگوریتم ها بود.

خب سوال امروز مسئله نا مساوی هاست منبع اصلی سوال سایت ZOJ میباشد.

این سوال با دادن یک سری نامساوی از ما میخواهد که نامساوی های دیگری که نتیجه می دهد را پیدا کنیم . اشتباهی که زمان خواندن این سوال کردم باعث شد که برای چندین بار پشت سر هم Wrong Answer از سایت بگیرم . اما در آخر از دو روش مختلف از سایت ZOJ و Sharecode توانستم Accept بگیرم هر دو روش رو در ادامه به همراه کد توضیح میدهم ابتدا سوال را مطالعه کنید.

ادامه مطلب