المپدیا

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

ابزار کاربر

ابزار سایت


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

مرتب‌سازی

یک جایگشت از اعداد ۱ تا $n$ داریم و هدف مرتب‌سازی آن در کم‌ترین تعداد حرکت است. در هر حرکت می‌توانیم یک زیردنباله از آن را انتخاب کنیم و با حفظ ترتیب به ابتدای جایگشت انتقال دهیم. به عنوان مثال این حرکت را در نظر بگیرید:

$$12\underline{4}53\underline{76} \longrightarrow \underline{476}1253$$

نشان دهید هر جایگشت $n$ تایی را می‌توان با حداکثر $lg(n+1)$ حرکت مرتب کرد.


ابزار صفحه