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)
文章標籤
全站熱搜