المپدیا

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

ابزار کاربر

ابزار سایت


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

جدول تقریباً مرتب

یک جدول ‎$2 \times n$‎ که اعداد ‎$1‎, ‎2‎, ‎\dots‎, ‎2n$‎ در آن نوشته شده است را تقریباً مرتب می‌گوییم هرگاه عدد هر خانه‌ی آن از دو عدد موجود در خانه‌های پایینی و سمت راستی‌اش (در صورت وجود) کوچک‌تر باشد. می‌خواهیم باقی‌مانده‌ی تعداد چنین جدول‌هایی را بر عدد ‎۱۰۰۰۰۰۰۰۱‎ به‌دست آوریم. برای این کار الگوریتمی از ‎${\cal O}(n^2)$‎ ارائه کنید.

الگوریتم خود را تحلیل و اثبات کنید.


ابزار صفحه