حسام حداد

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

حسام حداد

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

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

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

۳ مطلب با کلمه‌ی کلیدی «Dynamic Programming» ثبت شده است

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

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

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

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

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

  • حسام حداد

مقدمه

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


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

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

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

  • حسام حداد