مقدمه مترجم

الگوریتم Maximoum Flow Minimoum Cut یکی از الگوریتم های کاربردی است که معمولا در چالش های متوسط و سطح بالا برنامه نویسی ظاهر میشود از کاربرد های این الگوریتم میتوان به برنامه ریزی خطوط هوایی برای عدم تداخل اشاره کرد و همچنین مسائلی که میتوان با چند مدل سازی از ورودی مسئله را با یک مسئله بیشینه جریان تبدیل کرد در سوالات  مسابقات داخلی از جمله مسابقات منطقه ای غرب‌ آسیا (‌صنعتی شریف)‌ و مسابقه داخلی دانشگاه امیرکبیر دیده شده است. این مقاله از بخش الگوریتم های TopCoder ترجمه شده  و اولین مقاله غیر تالیفی منتشر شده در این وبلاگ محسوب میشود. قسمت پیشرفته تر این الگوریتم نیز در اسرع وقت ترجمه شده و منتشر میشود.  لینک مقاله انگلیسی


مقدمه نویسنده
این مقاله مسئله ای را پوشش میدهد که معمولا در زندگی روزمره و طبق انتظار در چالش های برنامه نویسی رخ میدهد و مسابقات TopCoder نیز در این مورد استثنا نیست. مقاله بیشتر برای برنامه نویسانی که با موضوع آشنایی ندارند نوشته شده اما میتواند برای با تجربه ها نیز مفید واقع شود. مقالات زیادی در این رابطه نوشته شده و الگوریتم های شناخته شده زیادی نیز برای حل این مسئله وجود دارد. الگوریتمی که در اینجا ارائه میشود با اینکه سریعترین نیست اما سودهایی مثل سادگی و کارآمدی دارد. و به خاطر این دو معمولا ترجیح داده میشود. توصیه میشود که خواننده پیش از ادامه مقاله ای را در زمینه نظریه گراف ها مطالعه کند زیرا مفاهیمی که در نظریه گراف ها مطرح میشود پیشنیاز درک مفاهیمی که اینجا مطرح میشود میباشد.


مسئله استاندارد بیشینه جریان Maximum Flow Problem
وقتی به یک مسئله بیشینه جریان بر میخوریم ساده ترین حالت صورت مسئله میتواند به این شکل باشد: " با داشتن لیستی از لوله ها با شدت جریان متفاوت که از انتها به هم وصل شده اند. مقدار بیشینه ای از آب که میتوان از یک نقطه شروع به یک نقطه پایان منتقل کرد چقدر است؟" یا به صورت "شرکتی دارای خط تولیدی در شهر X میباشد که نیاز است محصولاتش به شهر Y منتقل شود. به شما راه های یک طرفه ای داده شده است که هر یک دو شهر از کشور را با یک بیشینه تعداد کامیون عبوری به هم متصل میکند. بیشترین تعداد کامیونی که شرکت میتواند از آنها برای انتقال محصولات استفاده کند چقدر است؟"

ادامه مطلب

در این پست به معرفی مسابقات برنامه نویسی داخلی پیش رو با اولویت زمان میپردازیم. برگزاری هرچه بیشتر این مسابقات قطعا موجب افزایش شور و هیجان برنامه نویسی در کشور میشود و میتوان آینده روشنی برایشان ترسیم کرد.


توصیه به شرکت کنندگانی که میخواهند بطور حرفه ای مسابقات برنامه نویسی را دنبال کنند علاوه بر شرکت هرچه فعال تر در مسابقات، مطالعه بیشتر الگوریتم ها ، کتاب خانه های زبان های برنامه نویسی و حل مسائل مفهومی و دشوار به تعداد بیشتر است. بدیهی است که هیچ کدام از شرکت کنندگان کنکور با تکنیک های تست زنی از پس تست های مبحث ای مثل انتگرال بر نیامده اند و قطعا برای پیشرفت قطعی و مداوم بجز خود مسابقه دادن نیاز به مطالعات بیشتری هم میباشد.

ادامه مطلب

مقدمه
 بعد از اینکه Dynamic Programming را به صورت کلی مورد بازبینی قرار دادیم. طبق قراری که گذاشته شد در این مطلب و مطالب بعدی به توضیح بیشتر در این زمینه میپردازیم.
بد نیست بدانید که برنامه نویسی پویا دارای یک سری مسئله کلیشه مانند:

  • کولپشتی صفر و یک 01 Knapsack
  • کوله پشتی Knapsack
  • طولانی ترین زیر آرایه همسان Longest Common Sequence
  • طولانی ترین زیر آرایه صعودی Longest Increasing Sequence

می باشد. برای این مسائل به حد کافی آموزش در اینترنت وجود دارد توصیه میشود که این مطالب را به عنوان تمرین بیشتر مطالعه کنید.
این مطلب در مورد حل مسئله RNA Molecules مسابقه ملی اینترنتی 2013 سایت شریف  با استفاده از تکنیک برنامه نویسی پویا میباشد. 

ادامه مطلب

سلام دوستان ، همونطوری که تو نظرات خواسته بودن که سوالات ACM ICPC سایت شریف رو حل کنیم امروز به حل یک سوال نسبتا ساده مسابقه Tehran, Asia Region - Regional 2011 میپردازیم

Mobile SMS Keys

لینک ShareCode.ir

خب قبل از ادامه حل سوال ابتدا سوال رو کامل مطالعه بفرمایید و سعی کنید خودتان حل کنید این سوال فقط نیازمند پیاده سازی است و نیاز به الگوریتم پیچیده خاصی ندارد توصیه من این است که حدافل نیم ساعت وقت برای حل این سوال بگذارید و بعد کد نمونه را چک کنید. 

ادامه مطلب

سلام
امروز یک مسئله خوب ACM به نام حل مسئله محیط تصاویر Image Perimeters Solotion را برای حل انتخاب کرده ایم این سوال را با استفاده از توابع بازگشتی حل کرده ایم.
این مسئله از مسابقه Mid-Central USA 2001 انتخاب شده است
لینک سوال در ICPC Live Archive
لینک سوال در ShareCode.ir

حل مسئله محیط تصاویر Image Perimeters Solotion
خب قبل اینکه ادامه مطلب را بخوانید ابتدا متن سوال را مطالعه فرماید و سعی کنید که خودتان حل کنید .

ادامه مطلب

امروز میخواهیم یک مسئله سطح متوسط ACM را حل کنیم اینگونه سوال ها دارای یک نکته یا یک ابتکار کوچک میباشند که اگر آنرا متوجه شوید به راحتی میتوانید سوال را حل کنید.

این سوال دوباره به شکل بهتر و سریعتر حل شده و میتوانید از لینک زیر برای مشاهده آن استفاده کنید.

حل بهتر مسئله کارتهای برابر

این سوال از مسابقه Southeast USA 2000 انتخاب شده است.

در مورد سوال را از سایت ShareCode.ir مسئله 1003 بخوانید.

ادامه مطلب

خب قرار است یک شروع آزمایشی داشته باشیم به هیج وجه با دیدن این سوال راجب ACM قضاوت عجولانه نکنید!

برنامه‌ای بنویسید که دو عدد صحیح را خوانده و حاصل جمعشان را چاپ کند و اینکار را تا زمانی که ورودی تمام نشده است ادامه دهد.


ادامه مطلب


برای برنامه نویسی ACM و یا به عبارت بهتر حل سوالات ACM شما نیاز به آشنایی با موارد زیر دارید، این موارد به طور کلی بیان شده است:

1. برنامه نویسی به زبان ++C یا جاوا ( ترجیحا ++C)

2. طراحی الگوریتم (بیشتر سوالات نیاز به دانستن اطلاعات بالایی از یک زبان برنامه نویسی ندارند و دانستن در حد ورودی و خروجی خواندن و کار با عناصر یک آرایه کافیست.)

3. ساختمان داده (برای حل برخی سوالات)

4. هوش مصنوعی (برای حل برخی سوالات)


اگر فکر میکنید که در برخی از موارد بالا از مهارت کافی برخوردار نیستید به هیج وجه عقب نشینی نکنید میتوانید از سوال های خیلی ساده شروع کنید. و نقاط ضعفتان را به مرور برطرف کنید.

ACM International Collegiate Programming Contest یک مسابقه بین المللی بین دانشگاهی میباشد که توسط نهاد جهانی ACM اداره میشود.

این مسابقات در سایت تهران از حدود 10 سال گذشته (اطلاعات دقیق تاریخی را از ویکی پدیا و acmwiki می‌توانید پیدا کنید) با استقبال خوب دانشگاه های کشور برگزار می‌شود.

من حدود 3 سال در این زمینه فعالیت می‌کنم و دوره گذشته مسابقات سایت شریف شرکت کرده‌ام.

در این وبلاگ اطلاعات مختلف در زمینه برنامه‌نویسی اختیار شما می‌گذارم که کمکی شود به دوستانی که علاقه‌مند به برنامه‌نویسی و الگوریتم هستند.

منتظر مطالب آموزشی باشید.