حسام حداد

در مورد برنامه نویسی ، الگوریتم نویسی ، نکات ترفند ها

حسام حداد

در مورد برنامه نویسی ، الگوریتم نویسی ، نکات ترفند ها

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

آخرین نظرات
  • ۱۸ آبان ۹۵، ۱۲:۵۱ - سامان
    ای ول

۹ مطلب با کلمه‌ی کلیدی «مسابقه ACM شریف» ثبت شده است

مقدمه مترجم

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


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


مسئله استاندارد بیشینه جریان Maximoum 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 سال گذشته ( اطلاعات دقیق تاریخی را از ویکی پدیا بگیرید ) با استقبال خوب دانشگاه های کشور برگذار میشود .

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

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

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

  • حسام حداد