\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2015年12月30日 星期三

[ round-off error eps ] 浮點數誤差模板

有些計算幾何的過程中會產生捨位誤差,這時候就需要決定一個很小的數,去避開這個捨位誤差問題,我們稱那個很小的數為EPS
  • A < B ....... A - B < - EPS
  • A > B ....... A - B > EPS
  • A == B ....... abs(A - B) <= EPS
  • A <= B ....... A - B <= EPS
  • A >= B ....... A - B >= - EPS
因為我的計算幾何模板在實作時是用template實作的,所以如果需要處理浮點數誤差時,需要傳入一個新的資料結構,所以寫了這份模板

[ long long multiply long long mod long long ] long long 乘 long long 模 long long不溢位算法

這標題有點長,不過也很清楚的顯示了這篇的重點,所以就直接附模板吧
如果a,b<m的話a%=m,b%=m;可以拿掉沒關係

code(參考自morris):

code(比較慢,但適用範圍更大,算法取自維基百科:同餘):

2015年12月27日 星期日

[ Maze generation-Randomized Kruskal's algorithm ] 迷宮生成-隨機Kruskal算法

說得通俗點,就是"隨機拆牆"。
一開始假設所有牆都在,也就是圖的每個點都不連通。如果當前不滿足“任意兩個格子間都有唯一路徑”,那麼就隨機選擇一堵牆,要求牆兩端的格子不連通,即它們對應的兩個頂點在兩個不同的連通分量。把這堵牆拆掉,即在後牆兩端的格子對應的頂點間建立一條邊。重複作下去,直到所有的點都在同一個連通分量裡面。
會發現這就是隨機合併點的Kruskal演算法,需要用到並查集

範例生成圖:
#########################
#   #       #   #       #
### # # # ### ####### ###
#     # #   #   # #     #
######### ### # # ##### #
#       # #   #   #     #
### ### # # # ### ### ###
#   #   #   #   #       #
### # ##### ### ##### ###
#   #       # #     # # #
####### # ### # ####### #
#   # # #   #       # # #
# ### ### ### # ##### # #
# #     # #   # # # # # #
# # ### # ### ### # # # #
# # #     #   #         #
# # ### ######### # #####
#   #   # # #     #   # #
####### # # # # ### ### #
#     #       #   #     #
# # ##### ######### # ###
# #               # #   #
### # # ### # ####### ###
#   # #   # #   #       #
#########################

code(n,m必須是奇數):

2015年12月21日 星期一

[ min-max heap ] 最小-最大堆

最小-最大堆(Min-Max Heaps)是一個完整二元樹。此二元樹是交替的階層方式呈現,分別為最小階層 ( min level ) 和最大階層 ( max level ) ,這裡實作樹根為最大鍵值。

這裡最小-最大堆的建立規則為:
階度1的鍵值 > 階度3的鍵值 > 階度5的鍵值…> 階度n的鍵值(n為奇數)
階度2的鍵值 < 階度4的鍵值 < 階度6的鍵值…< 階度n的鍵值(n為偶數)

最小-最大堆是一種堆積支援以下幾種操作:
  1. 求最大值 - max()
  2. 求最小值 - min()
  3. 刪除最大值 - pop_max()
  4. 刪除最小值 - pop_min()
  5. 元素入堆 - push()
求最大最小的做法很容易理解,這裡就不再多講了。
現在先來講入堆(以最大階層為例):
  1. 因為它是一顆完滿二元樹,所以直接將入堆的元素加在最尾端即可
  2. 因為要滿足最小-最大堆的建立規則,所以如果他的值比他父母小就把他跟他父母的值交換
  3. 之後一直跟祖父母節點的值做比較,如果他的值比祖父母節點的值還大就把他跟祖父母節點交換(類似於維護一般的最大堆,只是不跟父母比較),值到祖父母不存在
再來是講刪除節點(以最大階層為例):
  1. 因為它是一顆完滿二元樹,所以把尾端元素換到要刪除元素的位置再將尾端刪除(現在要刪除元素的位置的值是尾端元素)
  2. 如果要刪除元素有孫節點(下下層),就把他跟最大的孫節點交換
  3. 如果要刪除元素沒有孫節點但有子節點,就把他跟最大的子節點交換
  4. 如果比較後最大的節點比要刪除元素小,就不交換
  5. 如果沒有子節點就結束程式
如果不懂敘述就看code吧
以下提供模板: