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

المپدیا

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

ابزار کاربر

ابزار سایت


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

مرتب‌سازی با اعمال شاقه

روی جایگشت π از اعداد ۱، ۲، … و n، اعمال Move(i) و MoveReverse(i) به ترتیب زیر تعریف می‌شوند.

عمل Move(i) i عنصر انتهایی π را حذف و با حفظ ترتیب، به اول آن الحاق می‌کند. مثلا Move(3) جایگشت 1,2,4,3 را به جایگشت 2,4,3,1 تبدیل می‌کند.

عمل MoveReverse(i) i عنصر انتهایی π را حذف و با ترتیب عکس، به اول آن اضافه می‌کند. به عنوان مثال جایگشت 1,2,4,3 را به جایگشت 3,4,1,2 تبدیل می‌شود.

در مورد هر یک از دو عمل، تعداد حالت‌های ممکن برای جایگشت π برای آن‌که بتواند با استفاده از آن عمل به جایگشت 0,2,...,n تبدیل شود را محاسبه کنید.


ابزار صفحه