حسام حداد

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

حسام حداد

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

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

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

۱۴ مطلب با کلمه‌ی کلیدی «آموزش ACM» ثبت شده است

مقدمه
سوال «چگونه کار کنیم تا در مسابقات برنامه نویسی موفق شویم؟» به تعداد افراد شرکت کننده در این مسابقات جواب مختلف دارد ولی تعدادی ضدالگو وجود دارد که همه با مشکل ساز بودن این ضدالگو ها موافق هستند. یک مثال ساده این است که مثلا تشخیص روشهای افزایش ده سال طول عمر، سخت تر از تشخیص روشهای کاهش ده سال طول عمر هست و اگر شما از این ضد الگوها یا کارهای اشتباه دوری کنید میتوان امیدوار بود که در کل نتیجه بهتری بگیرید. بد نیست از کتاب «چگونه در C++ برنامه ننویسیم؟» نام ببرم که در انتخاب عنوان از این کتاب الگو گرفتم.
  • حسام حداد

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

  • حسام حداد
مقدمه
پیش از این برنامه نویسی پویا را مطرح کرده بودیم، امروز یک سبک از برنامه نویسی پویا به اسم Bitmask را به همراه حل مسئله شماره 10911 از UVA مطرح میکنیم، که به نسبت مسئله ساده ای هست. وقتی که بحث پیاده سازی مجموعه ها در میان باشد Bit Mask ها مطرح میشوند.

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

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

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

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

  • حسام حداد

در مطالب گذشته سوال کارت های برابر را حل کردیم حل اول کارت های برابر

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

دوم اینکه دارای پیچیدگی زمانی O(N2M4) بود که با توجه به N کمتر از 100 و M=5 این کد Accept شد اما برای مسئله مشابه با M های بزرگتر ، برای مثال M=100 برنامه ما در محدوده زمانی مورد نظر به جواب نمیرسید و نتیجه ارسال کد Time Limit Executed میشد.

برای حل این سوال اینبار از یکی از Data Structure های C++ Standard Library به نام Bitset استفاده میکنیم که میتوان از این Solution به عنوان مثالی برای یادگیری Bitset نیز استفاده کرد.

میشود Bitset را به عنوان یک آرایه ای از متغیر Boolean تعریف کرد، اما این تعریف بسیار ناقص میباشد زیرا برای یک آرایه Boolean توابعی مانند شیفت به چپ ، شیفت به راست ، نقیض ، مساوی بودن ، OR , AND , XOR با یک آرایه Boolean دیگر وجود ندارد و برای پیاده سازی هریک نیاز به تابع نویسی داریم. اما در Bitset تمام این امکانات گنجانده شده است.

  • حسام حداد

مقدمه

بسیاری از مسائل برنامه نویسی تنها با استفاده از Dynamic Programming حل میشوند در این نوشتار سعی شده که طرح کلی برنامه نویسی پویا و دلیل و مزایای استفاده از آن با چندین پیاده سازی برای تابع Fibonacci بیان شود. در مطالب آینده مثال های مهم تر و به نسبت پیچیده تری قرار میگیرد.


برنامه نویسی پویا یا Dynamic Programming چیست ؟

همه شما کم و بیش با الگوریتم ها یا برنامه هایی که به صورت بازگشتی عمل میکنند اطلاع دارید. حل یک مسئله با حل کردن یک یا چندین زیر مسئله .

در استفاده از تکنیک برنامه نویسی پویا ما حل مسئله را توسط حل مسئله های کوچکتر بیان میکنیم با این تفاوت که با ذخیره سازی از محاسبه دوباره اجتناب میکنیم.

  • حسام حداد

Guilan Faculty of Engineering
Hesam Haddad

Today we are going to be talking about the Importance of Algorithms in Programming and providing their usage, optimization after definitions.
The main propose of this is to help you have a clear view of algorithms or some basic knowledge.


What’s An Algorithm?
Algorithms are sets of rules to be followed in calculation or other problem solving by computer.


Runtime Analysis
After The correctness of an algorithm to solve all the test cases, the most important thing is runtime.
Computer Scientists typically talk about the runtime relative to the size of input. If the input consists of N integers, an algorithm witch has a runtime proportion to N2 represent as O(N2) means that this algorithm terminate and complete after doing N2 operations.

  • حسام حداد

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

کجا نمیتوان از الگوریتم حریصانه استفاده کرد؟

گراف بدون جهت زیر را در نظر بگیرید.

گراف نمونه

برای پیدا کردن کوتاه ترین مسیر بین گره A   و D اگر به صورت حریصانه عمل کنیم  یال A-C از یال A-B  دارای وزن کمتری میباشد پس یال A-C  را در نظر میگیریم ولی در ادامه مجبوریم از تنها انتخاب یعنی C-D استفاده کنیم و به گره  D برسیم. طول مسیر 9 + 15 یعنی 24 میباشد اما در صورتی که در ابتدا یال A-B را انتخاب کرده بودیم  با اینکه نسبت به A-C در مرحله اول انتخاب بدتری بود اما در ادامه مسیر بهینه تر و کوتاه تری را داشتیم.
پس نمیتوان از الگوریتم حریصانه در پیدا کردن کوتاه ترین میسر بین دو گره استفاده کرد برای اینکار میتوان از الگوریتم هایی مثل Dijkstra استفاده کرد که به این مقاله مربوط نمیشود.
اما باید بدانیم که اگر در مسئله ای الگوریتم حریصانه درست باشد بی شک بهترین راه حل برای آن مسئله حریصانه است چون نسبت به بقییه الگوریتم ها دارای پیچیده گی زمانی کمتری میباشد.
ما بنا بر روال همیشگی امروز یک مسئله ICPC – ACM را برای مثال انتخاب کرده ایم که در حل آن از الگوریتم حریصانه میتوان استفاده کرد.
ابتدا متن سوال را مرور میکنیم

  • حسام حداد

سلام دوستان

امروز به جای حل و بررسی مسائل برنامه نویسی به معرفی منابع و شفاف سازی در زمینه الگوریتم نویسی میپردازیم

قالبا دوستانی که با تگ کلیدی "آموزش الگوریتم نویسی" وارد این تارنما ( بقول پاسداران زبان پارسی ) میشوند را میتوان به دو گروه تقیسم کرد.


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


گروه دوم که به دنبال اموزش Fllowchart فلوچارت یا pseudocode شبه کد به صورت پایه هستند.

  • حسام حداد

سلام دوستان

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

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

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

  • حسام حداد