stack應用

• 二元樹走訪運算
• CPU中斷處裡
• DFS追蹤
• 堆疊計算機指令
• 遞迴呼叫與返回
• 算術式轉換

遞迴演算法

#用for計算0!-n!
sum=1
n=int(input('請輸入n='))
for i in range(0,n+1):
    for j in range(i,0,-1):
        sum*=j
    print(i,'!=',sum,'!')
    sum=1

#用遞迴計算0!-n!
def factorial(i):
    if(i==0):return 1
    else:product=i*factorial(i-1)
    return product

n=int(input('請輸入階程數'))
for i in range(n+1):
    print(i,'值為',factorial(i))

費伯納序列

• Fn=0 n=0
• Fn=1 n=1
• Fn-1+Fn-2 n≥2

#費伯納序列
def fib(n):
    if(n==0):return 0
    elif(n==1 or n==2):return 1
    else:return(fib(n-1)+fib(n-2))

盒內塔

步驟1:將n-1個盤子，由木樁1移動到木樁2

步驟2:將n個最大盤子，由木樁1移動到木樁3

步驟3:將n-1個盤子，由木樁2移動到木樁3

#盒內塔
def hanoi(n,p1,p2,p3):
    if(n==1):print('圓圈由',p1,'移到',p3)
    else:
        hanoi(n-1,p1,p3,p2)
        print('圓圈由',p1,'移到',p3)
        hanoi(n-1,p2,p1,p3)

g=int(input('移動圓圈數量'))
hanoi(g,1,2,3)

老鼠走迷宮

一次走一格

遇到強無法往前走，退一步看是否有其他方向

走過路不會重複走

maze[i][j]=1 表示有牆不能通過 maze[i][j]=0 表示牆 能通過 maze[0][0]是入口 maze[1][1]是出口

迷宮搜尋技巧:

if 上一格可走: 
加上方格標號到stack
往上走
判斷是否出口
elif 下一格可走: 
加下方格標號到stack
往下走
判斷是否出口

elif 左一格可走: 
加左方格標號到stack
往左走
判斷是否出口

elif 右一格可走: 
加右方格標號到stack
往右走
判斷是否出口

else 從stack刪除表格編號
從stack中取出一方格編號
往回走

八皇后問題

"""有瑕疵"""
global queen
global number
eight=8
queen=[None]*8
number=0#計算幾組解

def print_table():
    global number
    x=y=0
    number+=1
    print(' ')
    print('八皇后問題解',number,'\t')
    for x in range(8):
        for y in range(8):
            if(x==queen[y]):
                print('<q>',end='')
            else:
                print('<->',end='')
                print('\t')
            input('\n 按下任一鍵繼續..\n')

#測試皇后是否遭受攻擊，受攻擊為1，否則0
def attack(row,col):
    global queen
    i=0
    atk=0
    offset_row=offset_col=0
    while(atk!=1 and i<col):
        offset_col=abs(i-col)
        offset_row-abs(queen[i]-row)
        #判斷兩皇后是否同一條線
        if(queen[i]==row or offset_row==offset_col):
            atk=1
        i+=1
    return atk

def decide_position(value):
    global queen
    i=0
    while(i<8):
        if(attack(i,value)!=1):
            queen[value]=i
            if(value==7):
                print_table()
            else:
                decide_position(value+1)
        i+=1

decide_position(0)