Bagaimana untuk melaksanakan masalah Menara Hanoi menggunakan Python

Kata Pengantar

Masalah Menara Hanoi adalah masalah klasik. Menara Hanoi, juga dikenali sebagai Menara Hanoi, berasal dari legenda kuno di India. Apabila Brahma mencipta dunia, dia membuat tiga tiang berlian Pada satu tiang, 64 cakera emas disusun mengikut saiz dari bawah ke atas. Brahma mengarahkan Brahmin untuk menyusun semula cakera pada tiang lain mengikut saiz dari bawah. Ia juga ditetapkan bahawa pada bila-bila masa, cakera tidak boleh dibesarkan pada cakera kecil, dan hanya satu cakera boleh dipindahkan antara tiga tiang pada satu masa. Tanya bagaimana untuk beroperasi?

1. Mari kita bincangkan dahulu tentang apa itu rekursi?

Pemahaman saya sendiri ialah: teruskan kecilkan saiz masalah anda sendiri sehingga ia berkurangan sehingga tidak dapat dikurangkan. (Keadaan akhir rekursi tercapai) Kemudian mula selesaikan masalah kecil satu persatu, masalah besar akan selesai (rekursi kembali)

Pendek kata:

Asal Masalah dikurangkan kepada masalah asal yang lebih kecil, dan kemudian masalah asal yang lebih kecil diselesaikan, sekali gus menyelesaikan masalah besar asal!

3. Prosesnya ialah:

Kurangkan skala, selesaikan dari saiz kecil, ulang semula, dan selesaikan masalah asal! ! !

4. Kunci kepada rekursi ialah:

(1) Terdapat keadaan akhir rekursi.

(2) Berterusan memanggil dirinya untuk mengurangkan saiz masalah dan bergerak lebih dekat kepada keadaan akhir rekursi.

Masalah Menara Hanoi

1. Huraian masalah

Terdapat tiga tiang bernama A, B, dan C. Pada mulanya, terdapat n cakera pada tiang A, ia adalah dari bawah ke atas, dan saiz cakera adalah dari besar ke kecil. Semasa memindahkan dan meletakkan, plat kecil mesti berada di atas plat besar. Semasa memastikan peraturan, gerakkan semua plat pada tiang A ke tiang C. Anda boleh menggunakan tiang B semasa bergerak, tetapi anda mesti memastikan bahawa plat kecil mesti berada di atas pinggan besar semasa bergerak! ! ! Sila cetak proses pemindahan?

2. Analisis masalah proses rekursif:

(1) Gerakkan plat n-1 atas dari A ke B dengan bantuan C

(2) Gerakkan plat bawah dari A ke C

(3) Pindahkan plat n-1 atas dari B ke C

Keadaan akhir rekursi:

Skala masalah menjadi apabila bilangan plat adalah 0, kerana apabila bilangan plat adalah 0, tidak perlu bergerak! ! !

3. Kod (Python)

# coding:utf-8

"""
    n为初始时A柱上的盘子数
    a为起始盘子所在的柱子
    b为中转柱子
    c为目的地柱子
"""


def hanoi(n, a, b, c):
    if n > 0:
        hanoi(n-1, a, c, b)
        print("盘子从%s移动到%s" % (a, c))
        hanoi(n-1, b, a, c)



hanoi(3, "A", "B", "C")

4

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan masalah Menara Hanoi menggunakan Python. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!