المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۶

جایگشتی از اعداد ۱ تا $n$ داده شده است. $Swap(i,j)$ عملی است که عنصر $i$ ام و عنصر $j$ ام جایگشت را با هم عوض می‌کند. ثابت کنید برای تبدیل جایگشت به جایشگشت مرتب $1,2,…,n$ در هر حالت $n-1$ بار عمل $Swap$ کاف و در بدترین حالت حداقل این تعداد بار لازم است.


ابزار صفحه