2007年6月28日

CMClass: 微軟徵才試題 in Prolog

一開始是在 thinker 那邊偶然看到這個題目,正文如下:
永源拿了兩個不同數字...
這兩個數字分別大於 1 ,也分別小於 50
永源只把這兩個數字的乘積告訴了亞譚 ...
永源再只把這兩個數字的和告訴了明歆 ...
永源問, 這兩個數字是什麼 ?

以下是亞譚和明歆的對話... (小強, 小毛, 小燕在旁坐陪)
亞譚: 我不知道這兩個數字是什麼!
明歆: 但我也還是不知道這兩個數字是什麼!
亞譚: 喔!那我知道那兩個數字是什麼了 !
明歆: 喔!那我也知道那兩個數字是什麼了 !
突然間 ....聰明的三位陪客同時也說: 我們也知道那兩個數字是什麼了 !
聰明的你, 告訴我....那兩個數字是什麼 ?
大家已經做出了 PythonC 的解法,但這題目感覺起來可以用 Prolog 解,自從修完 programming language 之後就再也沒碰過了(還被教授用一個很混蛋的理由當掉),正好複習一下。
solution(Set) :-
stage3(Set).

values(Set, S) :-
findall(V, (member(X, S), V is X), Set),
sort0(Set).

duplicate_values(Set, S) :-
values(Values, S),
findall(X, (member(X, Values), sublist([X,X], Values)), Set),
sort(Set).

single_values(Set, S) :-
values(Values, S),
findall(X, (member(X, Values), \+ sublist([X,X], Values)), Set),
sort(Set).

range(Set) :-
findall(I, for(I, 2, 49), Set).

solution_space(Set) :-
range(Range),
findall([A,B], (member(A, Range), member(B, Range), A < B), Set).

stage1(Set) :-
solution_space(S),
findall(A*B, member([A,B], S), S1),
duplicate_values(Values, S1),
findall([A,B], (member([A,B], S), V is A*B, member(V, Values)), Set).

stage2(Set) :-
stage1(S),
findall(A+B, member([A,B], S), S1),
duplicate_values(Values, S1),
findall([A,B], (member([A,B], S), V is A+B, member(V, Values)), Set).

stage3(Set) :-
stage2(S),
findall(A*B, member([A,B], S), S1),
single_values(Values, S1),
findall([A,B], (member([A,B], S), V is A*B, member(V, Values)), Set).
餵給 Prolog 之後打 ?- solution(Set). 就可以算出答案啦。

2 則留言 :

  1. 多謝誇獎。不過你知道怎麼把 geek 換成錢嗎?我肚子好餓。

    回覆刪除