python漢諾塔問題-有解無憂

python漢諾塔問題

實作python漢諾塔影片，需要分成兩個部分來進行：

（1）繪制塔和圓盤

（2）移動繪制后的形狀

這里需要用到遞回

1、遞回的定義：間接或直接呼叫自身的函式被稱為遞回函式，

2、遞回三原則：

（1）要有個基礎條件，來退出遞回

（2）遞回程序要向1靠攏

（3）要不斷的呼叫自身

一、思路分析

移動程序

設 A塔是圓盤出發的塔，稱之為起點塔
C塔是圓盤最終要達到的塔，稱之為目標塔
B塔起輔助中轉作用，稱之為中轉塔

當n=1時，只需要將盤1從起點塔A移動到目標塔C即可，

當n=2時，需要將盤1從起點塔A移動到中轉塔B，

再將盤2從起點塔A移動到目標塔C，

最后將盤1從中轉塔B移動到目標塔C即可，

當n=3時，先將盤12看做一個整體從起點塔A移動到中轉塔B，

再將盤3從起點塔A移動到目標塔C，

最后將盤12作為一個整體從中轉塔B移動到目標塔C即可，

（參照n=2）

當n=k時，先將盤1到k-1看做一個整體從起點塔A移動到中轉塔B，

再將盤k從起點塔A移動到目標塔C，

最后將盤1到k-1作為一個整體從中轉塔B移動到目標塔C即可，

以下以三層漢諾塔為例，

1、首先，定義一個moveDisk(diskIndex,fromPole,toPole) 函式：移動指定層圓盤diskIndex，從fromPole出發，到達toPole

def moveDisk(diskIndex, fromPole, toPole):
	print_str = 'Move disk %s form %s to %s' % (diskIndex,fromPole,toPole)
	print(print_str)

2、接下來，定義一個movetower函式，其中，WithPole表示中轉塔B

def moveDisk(diskIndex,fromPole,toPole):
	print_str = 'Move disk %s form %s to %s' % (diskIndex, fromPole,,toPole)
	print(print_str)

def moveTower(height, fromPole, withPole,,toPole):
	if height == 1 :
		moveDisk(1,fromPole,,toPole)
	else:
		moveTower(height-1,fromPole,,toPole, withPole)
		moveDisk(height,fromPole,,toPole)
		moveTower(height-1, withPole,fromPole,,toPole)

if __name__ == '__main__':
	moveTower(3, "A", "B", "C")

3、繪制塔和圓盤

turtle函式	作用
turtle.begin_poly()	開始記錄多邊形的頂點，當前的烏龜位置是多邊形的第一個頂點，
turtle.end_poly()	停止記錄多邊形的頂點，當前的烏龜位置是多邊形的最后一個頂點，將與第一個頂點相連，
turtle.get_poly()	回傳最后記錄的多邊形，
turtle.hideturtle()	隱藏畫筆的turtle形狀

register函式用于注冊程式退出時的回呼函式，然后在回呼函式中做一些資源清理的操作

import turtle

size = 20
TowerP=5    # Tower的線寬
TowerW=100  # Tower的底座寬度
TowerH=200  # Tower的高度
TowerSpace=260  # Tower的之間的距離，從中心到中心
HORIZON=-100    # Tower的底座高度，用于定位
towerD = 250
towerA = -100

 
# 設定圓盤形狀
def set_plate(i):
    l = size * (i+2) 
    t = turtle.Turtle()
    t.hideturtle()
    t.penup()
    t.begin_poly()
    t.left(90)
    t.forward(l)
    t.circle(size, 180)
    t.forward(l * 2)
    t.circle(size, 180)
    t.forward(l)
    t.end_poly()
    p = t.get_poly()
    turtle.register_shape("plate_%s"%i, p)
 
 
# 設定塔柱形狀
def set_tower():
    t = turtle.Turtle()
    t.hideturtle()
    t.penup()
    t.begin_poly()
    t.left(90)
    t.forward(TowerW)
    t.circle(-TowerP, 180)
    t.forward(TowerW)
    t.forward(TowerW)
    t.circle(-TowerP, 180)
    t.forward(TowerW-TowerP/2)
 
    t.left(90)
    t.forward(TowerH)
    t.circle(-TowerP, 180)
    t.forward(TowerH)
    t.end_poly()
    p = t.get_poly()
    SCR.register_shape('tower', p)
 
 
# 繪制塔柱
def draw_towers():
    set_tower()
    tower = turtle.Turtle("tower")
    tower.penup()
    tower.goto(-towerD,towerA)
    tower.stamp()
    tower.goto(0,towerA)
    tower.stamp()
    tower.goto(towerD,towerA)
 
 
# 繪制圓盤
def draw_plates(pn):
    plates=[]
    for i in range(pn):
        set_plate(i)
        _plate='plate_%s'%i
        pi=turtle.Turtle(_plate)
        pi.penup()
        plates.append(pi)
    return plates

最后，將繪制函式和移動函式結合起來

import turtle

size = 20
TowerP=5    # Tower的線寬
TowerW=100  # Tower的底座寬度
TowerH=200  # Tower的高度
TowerSpace=260  # Tower的之間的距離，從中心到中心
HORIZON=-100    # Tower的底座高度，用于定位
towerD = 250
towerA = -100

#記錄塔的位置
tower_loc = {
    "A":-1,
    "B":0,
    "C":1,
}

#記錄塔上有幾個圓盤
tower_poles = {
    "A":[],
    "B":[],
    "C":[],
}

# 建立表單
SCR=turtle.Screen()
# SCR.tracer()
SCR.setup(800,600) #設定表單大小
 
 
# 設定圓盤形狀
def set_plate(i):
    l = size * (i+2) 
    t = turtle.Turtle()
    t.hideturtle()
    t.penup()
    t.begin_poly()
    t.left(90)
    t.forward(l)
    t.circle(size, 180)
    t.forward(l * 2)
    t.circle(size, 180)
    t.forward(l)
    t.end_poly()
    p = t.get_poly()
    turtle.register_shape("plate_%s"%i, p)
 
 
# 設定塔柱形狀
def set_tower():
    t = turtle.Turtle()
    t.hideturtle()
    t.penup()
    t.begin_poly()
    t.left(90)
    t.forward(TowerW)
    t.circle(-TowerP, 180)
    t.forward(TowerW)
    t.forward(TowerW)
    t.circle(-TowerP, 180)
    t.forward(TowerW-TowerP/2)
 
    t.left(90)
    t.forward(TowerH)
    t.circle(-TowerP, 180)
    t.forward(TowerH)
    t.end_poly()
    p = t.get_poly()
    SCR.register_shape('tower', p)
 
 
# 繪制塔柱
def draw_towers():
    set_tower()
    tower = turtle.Turtle("tower")
    tower.penup()
    tower.goto(-towerD,towerA)
    tower.stamp()
    tower.goto(0,towerA)
    tower.stamp()
    tower.goto(towerD,towerA)
 
 
# 繪制圓盤
def draw_plates(pn):
    plates=[]
    for i in range(pn):
        set_plate(i)
        _plate='plate_%s'%i
        pi=turtle.Turtle(_plate)
        pi.penup()
        plates.append(pi)
    return plates

 
# 繪制移動程序
def draw_move(plate,fromPole,toPole):
    to_x = tower_loc[toPole] * towerD
    toPole_count = len(tower_poles[toPole])
    to_y = towerA +2 * TowerP + toPole_count * size * 2
    if fromPole:
        tower_poles[fromPole].remove(plate)
    plate.goto(to_x,to_y)
    tower_poles[toPole].append(plate)
    
 
 
# 移動指定層圓盤diskIndex，從fromPole出發，到達toPole
def moveDisk(diskIndex,fromPole,toPole):

    draw_move(diskIndex, fromPole, toPole)
 
 
# 核心函式，入口
def moveTower(height,fromPole, withPole, toPole,plates):
    if height == 1:
        draw_move(plates[0],fromPole, toPole)
    else:
        moveTower(height-1,fromPole,toPole,withPole,plates)
        draw_move(plates[height-1],fromPole,toPole)
        moveTower(height-1,withPole,fromPole,toPole,plates)
 
 
if __name__ == '__main__':
    draw_towers()
    n=3
    plates=draw_plates(n)
    for i in range(n):
        draw_move(plates[n-1-i],'','A')
    moveTower(n,"A","B","C",plates)
    turtle.done()

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/162479.html

標籤：Python

上一篇：python+opencv實作機器視徑訓礎技術(邊緣提取，影像濾波，邊緣檢測算子，投影，車牌字符分割)

下一篇：python的自學之路2