Xanoy minorasi

Uchta qoziq ($1$, $2$, $3$) bor. $a$ qoziqda $n$ ta disk turibdi: pastda eng kattasi, yuqoriga qarab kichrayib boradi. Hamma disklarni $b$ qoziqqa o'tkazish kerak. Qoidalar: bir yurishda faqat bitta — biror qoziqning eng yuqoridagi diskini boshqa qoziqqa olinadi; katta disk kichigining ustiga qo'yilmaydi.

Eng kam yurishlar bilan o'tkazing va yurishlarni ketma-ket chiqaring.

Bitta qatorda $n$, $a$, $b$ ($1 \le n \le 10$; $a, b \in \{1, 2, 3\}$, $a \ne b$).

Birinchi qatorda yurishlar soni. Keyin har bir yurish alohida qatorda: disk olinadigan va qo'yiladigan qoziq raqami.

$n$ ta diskni $a$ dan $b$ ga o'tkazish uchun: yuqoridagi $n - 1$ ta diskni uchinchi qoziqqa ($6 - a - b$) o'tkazing, eng katta diskni $b$ ga qo'ying, so'ng $n - 1$ ta diskni uchinchi qoziqdan $b$ ga o'tkazing. Asos holat: $n = 0$ — hech narsa qilinmaydi. Yurishlar soni $2^n - 1$, eng kam yurishli ketma-ketlik esa yagona.

Birinchi misol: kichik disk $1 \to 2$, katta disk $1 \to 3$, kichik disk $2 \to 3$.