Erlang寫過橋問題

過橋問題是像這樣 http://www.coolmath4kids.com/math_puzzles/Logic-bridgecrossing/index.html

最近找到解決步驟,然後可以用 Erlang 實現。先用人腦找解,然後用程式實現,還蠻輕鬆的。

以下程式, bridge_crossing:go/1 求行走步驟, bridge_crossing:cost/1 求行走步驟的成本。例如, bridge_crossing:cost(bridge_crossing:go([1,3,6,8,12])) 得 29 ,bridge_crossing:cost(bridge_crossing:go([1,2,3,5,8,10,15])) 得 39 。

-module(bridge_crossing).
-export([go/1, cost/1]).

largest([A]) ->
    A;
largest([A|Rest]) ->
    B = largest(Rest),
    if
	A > B ->
	    A;
	true ->
	    B
    end.

largest_two(List) ->
    L = largest(List),
    {L, largest(List--[L])}.

smallest([A]) ->
    A;
smallest([A|Rest]) ->
    B = smallest(Rest),
    if
	A < B ->
	    A;
	true ->
	    B
    end.

smallest_two(List) ->
    S = smallest(List),
    {S, smallest(List--[S])}.

go(List = [_,_,_|_]) ->
    {S,S1} = smallest_two(List),
    case (List--[S1]) of
	[A,B] ->
	    [{S,S1},S,{A,B}];
	Rest ->
	    {L,L1} = largest_two(Rest),
	    [{S,S1},S,{L,L1},S1] ++ go(List--[L,L1])
    end;
go([A,B]) ->
    [{A,B}];
go(List) ->
    List.

cost([]) ->
    0;
cost([{A,B}|Rest]) ->
    C = if
	A > B ->
	    A;
	true ->
	    B
    end,
    C + cost(Rest);
cost([C|Rest]) ->
    C + cost(Rest).
廣告

About 黃耀賢 (Yau-Hsien Huang)

熱愛 Erlang ,並且有相關工作經驗。喜歡程式語言。喜歡邏輯。目前用 Python 工作。
本篇發表於 Erlang, Problem。將永久鏈結加入書籤。

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s