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

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۲۲:سوال یک

مرتب سازی

دنباله‌ی A شامل n2 عدد طبیعی، داده شده است. می‌دانیم هر یک از اعداد ۱ تا n دقیقا n بار در این دنباله آمده‌اند. می‌خواهیم این دنباله را به صورت صعودی مرتب کنیم. در هر مرحله می‌توان n عضو این دنباله را انتخاب کرده و آن‌ها را به یک ترتیب دلخواه در مکان‌های قبلی‌شان نوشت. می‌خواهیم در کم‌ترین تعداد مرحله، دنباله را مرتب کنیم. به عنوان مثال، دنباله‌ی زیر در دو مرحله مرتب می شود:<1,1,2_,3_,2,3,2,3,1_>⇒<1,1,1,2,2,3_,2_,3,3_>⇒<1,1,1,2,2,2,3,3,3>

ثابت کنید هر دنباله‌ی دلخواه A را می‌توان حداکثر در n+1 مرحله مرتب کرد.


ابزار صفحه