去年在Imperial College学习中我选修了非常有趣的Prolog课程。从名字(Pro gramming in Log ic)不难看出这是一个专门为人工智能设计的语言;而且跟传统的过程式语言(如C++)和函数式编程语言(如Haskell)思考的方式完全不同,Prolog是一种声明式的逻辑编程语言。
如Wiki中所说,”有别于一般的过编程语言,prolog的程式是基于谓词逻辑的理论。最基本的写法是定立物件与物件之间的关系,之后可以用询问目标的方式来查询各种物件之间的关系。系统会自动进行匹配及回溯,找出所询问的答案。 ” 这句话很好,我直接复制过来了。 Prolog解决问题的方式非常巧妙。鉴于篇幅问题,读者有兴趣可以去查找其他更详尽的学习资料查看Prolog具体的编程写法。
这里举一个很简单的例子,修改自wiki:
我预先定义5个事实(fact)
human ( kate ).
human ( bill ).
human ( xp ).
likes ( kate , bill ).
likes ( bill , kate ).
likes ( xp , kate ).
这几个事实告诉了当前上下文环境:kate, bill 和 xp 是 human;kate 喜欢 bill,bill 也喜欢 kate,而 xp 单恋 kate。
我们再添加一条规则(rule)
friend ( X , Y ):-
X \ = Y ,
likes ( X , Y ),
likes ( Y , X ).
这个规则的意思是如果给定的X和Y满足三个条件(这三个条件分别是,X和Y不同,X和Y相互喜欢),那么X和Y满足friend这个条件。
这样的话,如果我在解释器中输入friend(A, B)
的话,Prolog会自动列出所有的满足这个规则的A和B的组合。
比如根据这个事实,我会得到
A = kate , B = bill ?
A = bill , A = kate .
这里没有顺序差别,所以我们会得到2个组合。
言归正传。greplin challange是greplin公司设计的几个编程挑战,共计3关。
去年看到这个的时候,我正好在学习Prolog,而且我发现每个题目用Prolog来做都很简单,所以就心血来潮的实现了一下^^,同时也为Prolog语言抛砖引玉。
问题一 :
给定一段连续的字符,找出其中最长的对称子字符串。(如 I like racecars that go fast 这句话中的racecar)
:- use_module ( library ( lists )).
%%%% Question 1
ws ( "你的字符串" ). % 把问题给的长字符串贴到这里
get_all ( Lists ):-
ws ( WS ), % WS 是题目给的字符串
reverse ( WS , RWS ), % RWS 是 WS 的反转字符串
findall ( Sublist , % 找出所有满足以下条件的子字符串,放入 Lists 中
( segment ( WS , Sublist ), % Sublist 是 WS 的子字符串,
length ( Sublist , L ), % Sublist 的长度是 L
L < 15 , L > 2 , % L 长度小于 15 ,但大于 2 (减少计算量)
reverse ( Sublist , Sublist ), % Sublist 的反转是 Sublist
segment ( RWS , Sublist )), % Sublist 是 RWS 的子字符串
Lists ).
run ( String ):-
get_all ( Lists ), % 得到所有的对称的子字符串
member ( S , Lists ), % S 一个对称的子字符串
\ + ( % 对于所有以下条件的组合,必须至少有一条为假
member ( OS , Lists ), % OS 是不同于 S 的另一个字符串
S \ = OS ,
length ( S , L1 ), % 得到 OS 和 S 的长度
length ( OS , L2 ),
L1 =< L2 ), % OS 的长度大于或等于 S
name ( String , S ). % 把 S 保存成可识别的字符串
问题二 :
i. 给定一个数字,找到第一个比它大的斐波那契质数 X (prime fibonacci number)
ii. 找出所有 X + 1 的质数约数。
% i , 求出 X
prime_fibo ( Target , Fib ):- % 给定 T ,找出比第一比 T 大的斐波那契质数
fibo ( Target , Fib ), % Fib 是比 T 大的一个斐波那契数字
prime ( Fib ). % Fib 是质数
prime_fibo ( Target , PFib ):-
fibo ( Target , Fib ),
\ + prime ( Fib ), % Fib 不是质数
prime_fibo ( Fib , PFib ). % 从 Fib 开始找结果
% ii ,给定 X + 1 ,求出所有 X + 1 的质数约数。
all_div ( Target , List ):- % 找出所有能整除 Target 的质数,放到 List 中
findall ( D ,
prime_div ( Target , D ),
List ).
% utility rules
fibo ( T , Fib ):- % Fib 是一个比 T 大的第一个斐波那契数字
fibo ( 1 , 1 , T , Fib ). % 从 1 , 1 开始算斐波那契数列
fibo ( Fib , _ , T , Fib ):-
Fib > T .
fibo ( Fib , LastFib , T , FFib ):- % Fib 是当前的 Fib 数, LastFib 是上次的 Fib 数
Fib =< T ,
NFib is Fib + LastFib ,
fibo ( NFib , Fib , T , FFib ). % 计算新的斐波那契数
prime ( N ):- % 判定 N 是否为质数
prime ( N , 2 ). % 从不能被 2 整除开始累加
prime ( N , D ):- % N 不能被 D 整除
0 = \ = N mod D , % N 不被 D 整除
D =< sqrt ( N ), % D 小于等于 N 的平方根(缩小 D 的取值范围)
ND is D + 1 , % ND 为 D + 1
prime ( N , ND ). % ND 也不能被 ND 整除
prime ( N , D ):- % 如果 D 大于 N 的平方根,则直接判定 N 不能被 D 整除
D > sqrt ( N ).
gen ( [ N | List ], N ):- % 生成一个 N 到 2 的数组
N > 2 ,
NN is N - 1 ,
gen ( List , NN ).
gen ( [ 2 ], 2 ).
prime_div ( Target , Diviser ):-
gen ( List , Target ),
member ( Diviser , List ),
is_div ( Target , Diviser ). % 只保留 gen生成的数组中的能整除Target的
is_div ( T , D ):- % T 能被质数 D 整除
prime ( D ),
0 =:= T mod D .
问题三 :
给定一个数列,找出所有子数列,使得子数列里最大的值是其余数字之和。
这个问题用Prolog很直接,直接按要求枚举出所有结果就好了~
% 手动复制给定的数列
l ( [ 3 , 4 , 9 , 14 , 15 , 19 , 28 , 37 , 47 , 50 , 54 , 56 , 59 , 61 , 70 , 73 , 78 , 81 , 92 , 95 , 97 , 99 ]).
fin ( Lists ):-
l ( W ),
findall (
List , (
subseq0 ( W , List ),
last ( Fore , Last , List ),
sumlist ( Fore , Last )
), Lists ).
我非常喜欢Prolog的编程方式:思考直接、代码精简。但是对于此类语言的初学者来说可能理解起来有些吃力。
相信我,如果你明白了Prolog的好处后,你会像我一样喜欢上这个语言的~