حسام حداد

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

حسام حداد

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

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

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

۱ مطلب در تیر ۱۳۹۴ ثبت شده است

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

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