What have you found for these years?

2009-12-01

powerset (3) hanoi

看到老林在上篇 comment 裡提到的 hanoi,
我記得我那時候,有照著老林說的概念自己試過一次。
已經不記得那時候是試什麼,但概念倒是還記得,
走在路上時,就開始在想,是不是能重做一次看看?

結果還真的一試就成了...

只能說這個解釋確實很清楚好懂?大概是這樣的:
hanoi 的三個柱子,可以看成 source, buffer, 和 destination.
想像現在只有一個盤子要搬,那當然是 source => destination.
但如果現在要搬的盤子,上面還有其他盤子(n-1),那必須把上面的先搬到
buffer, 然後把自己搬到 dest, 最後再把 buffer 裡的搬到 dest.

全部也只有這個動作而已。因為我們可以互換每個柱子的角色。
當我們要把上面的盤子(n-1)搬到 buffer, 我們可以互換 buffer
與 dest 的角色,也就是說把 buffer 當 dest, 把 dest 當 buffer.

而因為你要搬 n 時,要先搬 n-1, 要搬 n-2 時,要先搬 n-1,
所以實際上只要不斷變換柱子的角色,就能把整個過程看成一種遞迴,
實際上真正的操作,只有 source => destination,
其餘都是讓 buffer 與 dest 互換,還有讓 buffer 與 source 互換。
後者是從 buffer 搬到 dest, 讓 source 變成 buffer 的意思。

寫成表大概像這樣:

(n-1) source => buffer (buffer 與 dest 互換)
(n) source => destination (唯一真正的移動)
(n-1) buffer => destination (buffer 與 source 互換)

翻譯成 Haskell, 一開始我是寫成這樣:
n 是盤子編號,f 是 from(source), b 是 buffer, t 是 to(dest),
而 r 則是 result, 所有步驟的 List.

ha :: Integer -> Char -> Char -> Char -> [(Integer, Char, Char)] -> [(Integer, Char, Char)]
ha 0 _ _ _ r = r
ha n f b t r = ha (n-1) f t b r ++ [(n, f, t)] ++ ha (n-1) b f t r

試了一下,看起來真的是對的。很少一寫就成過...
雖然我原本是想把柱子寫成 List, 像是:
hanoi :: List a -> List a -> List a -> ...

但想來想去,這樣做的話就不知道怎麼互換柱子了?
只好還是用代號表示柱子。或許要把這當成某種 flag, 才能做 List.

然後覺得 r 很多餘,可以改成:
ha' :: Integer -> Char -> Char -> Char -> [(Integer, Char, Char)]
ha' 0 _ _ _ = []
ha' n f b t = ha' (n-1) f t b ++ [(n, f, t)] ++ ha' (n-1) b f t

接著可以省掉一個 ++, 雖然我不知道有沒有意義...
ha'' :: Integer -> Char -> Char -> Char -> [(Integer, Char, Char)]
ha'' 0 _ _ _ = []
ha'' n f b t = ha'' (n-1) f t b ++ ((n, f, t) : ha'' (n-1) b f t)

我想這樣再來看這個(Zelda triangle(誤)),應該比較容易懂吧?
ICFP 2009 演講全程錄影上網

0 retries:

Post a Comment

All texts are licensed under CC Attribution 3.0