علی یک انبار دارد که در آن عدد ذخیره کرده است. این انبار به شکلی است که او فقط می تواند اعداد خود را در دو نقطه از آن به صورت دو ستون روی هم قرار داده و ذخیره کند. علی تاکنون اعداد <۷٫۳٫۵٫۱٫۲٫۶٫۴> را در انبار ذخیره کرده و آن ها را در ستون اول به ترتیب از چپ به راست روی هم قرار داده است؛ یعنی عدد ۷ پایین ترین و عدد ۴ بالاترین عدد این ستون شده اند. ستون دوم در حال حاضر خالی است.
علی برای جابه جا کردن این اعداد یک دستگاه حمل عدد دارد که در هر بار استفاده از آن می تواند تعداد دلخواهی از اعداد بالای یک ستون را برداشته و با همان ترتیب به بالای ستون دیگر انتقال دهد. برای مثال علی اگر بخواهد با این دستگاه ۳ عدد از ستون اول را به ستون دوم انتقال دهد٬ اعداد ستون اول به ترتیب <۷٫۳٫۵٫۱> و اعداد ستون دوم به ترتیب <۲٫۶٫۴> خواهند شد.
حداقل چند مرحله لازم است تا علی بتواند از وضعیت اولیه‌ي داده شده به وضعیتی برسد که همه‌ي اعداد در یکی از دو ستون به ترتیب صعودی از پایین به بالا قرار گرفته باشند؟
پاسخ
گزینه ی «۵» درست است.
با شش مرحله ی زیر دنباله مرتب میشود :
$(7,3,5,1,2,6,4) /() \rightarrow (7,3,5)/(1,2,6,4)\rightarrow (7,3)/(1,2,6,4,5)\rightarrow (7,3,4,5)/(1,2,6)$
$$(7,3,4,5,6)/(1,2) \rightarrow (7)/(1,2,3,4,5,6)\rightarrow ()/(1,2,3,4,5,6,7)$$