Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۸:الگوریتم ها:سوال ۱۰

سوال ۱۰

مسائل A و B به ترتیب زیر می‌باشند:

مسئله‌ی A:

ورودی: مجموعه‌ی A={x1,x2,,xn} از اعداد طبیعی.

سوال: آیا این مجموعه، زیرمجموعه‌ای مانند S دارد که جمع اعضای آن دقیقا نصف جمع اعضای A باشد؟

مسئله‌ی B:

ورودی: مجموعه‌ی A={x1,x2,,xn} از اعداد طبیعی و عدد طبیعی M.

سوال: آیا این مجموعه، زیرمجموعه‌ای مانند S دارد که جمع اعضای آن دقیقا M باشد؟

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


ابزار صفحه