Цамхаг нь гурван багана, мөн дундаа нүх бүхий төрөл бүрийн хэмжээтэй хэд хэдэн дискнүүдээс бүрдэнэ. Анх цамхагийн аль нэг баганын суурь хэсэгт хамгийн том дискийг байрлуулж, дээшлэх тусам дискний хэмжээ буурах дараалалтайгаар бүх дискийг байрлуулна.

Бодлогын зорилго нь дисктэй баганаас бүх дискийг өөр нэг сул багана руу шилжүүлэх явдал юм. Ингэхдээ дараах дүрмийг баримтална.

Дискийг нэг нэгээр шилжүүлнэ Дискийг шилжүүлэхдээ өөөрөөс нь жижиг дискний дээр тавихыг хориглоно. Даалгавар. Нэг баганаас нөгөө баганад хамгийн цөөн үйлдлээр шилжүүлэх үйлдлийн дарааллыг ол. Багана эхнээсээ, диск жижгээсээ том руу натурал тоогоор дугаарлагдсан байна. Бүх диск 1-р баганад байгаа.

Даалгаврыг шууд биелүүлэхэд амархан байсан тул Ханойн цамхгийн 1-р дискийг 2-р шон дээр шилжүүлж болохгүй гэсэн шударга бус дүрэм гаргажээ. Энэ дүрмийг баримтлан шилжүүлнэ үү.

Оролт:

• Дискний n тоо байна.

Гаралт:

3 натурал тоонууд нэг нэг мөрөнд нэг хоосон зайтай байна. Эхний тоо дискний дугаар, хоёр дахь тоо нь диск авах баганын дугаар, гурав дахь тоо нь диск шилжүүлэх баганын дугаар.

Хязгаарлалтууд:

• (n<=10)

Дэд бодлого

Жишээ:

Оролт-1

2

Гаралт-1

1 1 3
2 1 2
1 3 1
2 2 3
1 1 3