Prologの技芸 4.2節の練習問題

(1)

挿入ソート
sort([3,1,2],Ys)
    sort([1,2],Zs1)
        sort([2],Zs2)
            sort([],Zs3)        {Zs3=[]}
                true
            insert(2,[],Zs2)    {Zs2=[2]}
                true
        insert(1,[2],Zs1)       {Zs1=[2|Zs4]}
            1>2
                fail
        insert(1,[2],Zs1)       {Zs1=[1,2|[]]}
            1=<2
                true
    insert(3,[1,2],Ys)          {Ys=[1|Ys1]}
        3>1
            true
        insert(3,[2],Ys1)       {Ys1=[2|Ys2]}
            3>2
                true
            insert(3,[],Ys2)    {Ys2=[3]}
                true

クイックソート
sort([3,1,2],Ys)
    partition([1,2],3,Ls,Bs)        {Ls=[1|Ls1]}
        1 =< 3
            true
        partition([2],3,Ls1,Bs)     {Ls1=[2|Ls2]}
            2 =< 3
                true
            partition([],3,Ls2,Bs)  {Ls2=[], Bs=[]}
                true
    sort([1,2],Ls3)
        partition([2],1,Ls4,Bs1)    {Ls4=[2|Ls5]}
            2 =< 1
                fail
        partition([2],1,Ls4,Bs1)    {Bs1=[2|Bs2]}
            2 > 1
                true
            partition([],1,Ls4,Bs2) {Ls4=[], Bs2=[]}
                true
        sort([],Ls5)                {Ls5=[]}
            true
        sort([2],Bs3)
            partition([],2,Ls6,Bs4) {Ls6=[], Bs4=[]}
                true
            sort([],Ls7)            {Ls7=[]}
                true
            sort([],Bs5)            {Bs5=[]}
                true
            append([],[2],Bs3)      {Bs3=[2]}
                true
        append([],[1,2],Ls3)        {Ls3=[1,2]}
            true
    sort([],Bs6)                    {Bs6=[]}
        true
    append([1,2],[3],Ys)            {Ys=[1,2,3]}
        true

(2)

derivative(3*sin(x)-4*cos(x),x,D)   {D=0}
    constant(3*sin(x)-4*cos(x))
        integer(3*sin(x)-4*cos(x))
            fail
derivative(3*sin(x)-4*cos(x),x,D)   {D=DF-DG}
    derivative(3*sin(x),x,DF)       {DF=0}
        constant(3*sin(x))
            integer(3*sin(x))
                fail
    derivative(3*sin(x),x,DF)       {DF=3*DG1+DF1*sin(x)}
        derivative(3,x,DF1)         {DF1=0}
            constant(3)
                integer(3)
                    true
        derivative(sin(x),x,DG1)    {DG1=0}
            constant(sin(x))
                integer(sin(x))
                    fail
        derivative(sin(x),x,DG1)    {DG1=cos(x)}
            true
    derivative(4*cos(x),x,DG)       {DG=0}
        constant(4*cos(x))
            integer(4*cos(x))
                fail
    derivative(4*cos(x),x,DG)       {DG=4*DG1+DF1*cos(x)}
        derivative(4,x,DF1)         {DF1=0}
            constant(4)
                integer(4)
                    true
        derivative(cos(x),x,DG1)    {DG1=0}
            constant(cos(x))
                integer(cos(x))
                    fail
        derivative(cos(x),x,DG1)    {DG1=-sin(x)}
            true

Prologの技芸 4.1節の練習問題

(1)

X=b
Xs=[]
Ys=[c,d]
L=[b|Zs]

(2)

N=s(0)
A=a
B=b
C=c
Ms=Xs

Prologの技芸 3.5節の練習問題

(1)

% arithmetic_sum(A + B) :-
%  算術和A+Bは，正規化されている．すなわちAが定数で，
%  Bが算術和の正規表現となっている形式A+B．
:- op(600, xfy, +).
arithmetic_sum(A + B) :- atomic(A), arithmetic_sum(B).
arithmetic_sum(A) :- atomic(A).

演算子定義

:- op(500, fy,~).
:- op(550,xfy,&).
:- op(600,xfy,'|').

(2)

bool(true).
bool(false).
bool(X & Y) :- bool(X), bool(Y).
bool(X | Y) :- bool(X), bool(Y).
bool(~X) :- bool(X).

(3)

% 和積標準形(選言の連言)
cnf(F1 & F2) :- disjunctive(F1), cnf(F2).
cnf(F) :- disjunctive(F).
% 選言
disjunctive(F1 | F2) :- atomic_formula(F1), disjunctive(F2).
disjunctive(F) :- atomic_formula(F).
% 連言
conjunctive(F1 & F2) :- atomic_formula(F1), conjunctive(F2).
conjunctive(F) :- atomic_formula(F).
% リテラル
atomic_formula(X) :- atomic(X).
atomic_formula(~X) :- atomic(X).

(4)

% negation_inwards(F1,F2) :-
%  F2は，論理式F1に現れる否定を
%  全て連言や選言の内側に移し変えて得られる論理式である．
negation_inwards(F1 & F2,G1 & G2) :-
 negation_inwards(F1,G1), negation_inwards(F2,G2).
negation_inwards(F1 | F2,G1 | G2) :-
 negation_inwards(F1,G1), negation_inwards(F2,G2).
negation_inwards(~(F1 & F2),G1 | G2) :-
 negation_inwards(~F1,G1), negation_inwards(~F2,G2).
negation_inwards(~(F1 | F2),G1 & G2) :-
 negation_inwards(~F1,G1), negation_inwards(~F2,G2).
negation_inwards(~ ~F,G) :- negation_inwards(F,G).
negation_inwards(F,F) :- atomic_formula(F).

Project Euler

problem 70
1<n<10において，10進数で表したφ(n)がnの並び替えになっているものの内，n/φ(n)が最大となるnを求めよ，という問題．
φ(n)の計算が予想以上に遅く，苦戦．最後はマシンパワーに頼った．

problem 80
1≦n≦100において，√n(ただし√nは無理数)の上位100桁をそれぞれ足しあわせた合計を求めよ，という問題．
BigDecimalの精度をMathContext.UNLIMITED(無制限)に設定し，愚直なループで√nを求めた．

Prologの技芸 3.4節の練習問題

(1)

% subtree(S,T) :-
%  SはTの部分木である．
subtree(tree(X,L,R),tree(_,Left,_)) :-
 subtree(tree(X,L,R),Left).
subtree(tree(X,L,R),tree(_,_,Right)) :-
 subtree(tree(X,L,R),Right).
subtree(tree(X,Left,Right),tree(X,Left,Right)).

(2)

% sum_tree(TreeOfIntegers,Sum) :-
%  Sumは整数の木TreeOfIntegersの整数要素の和である．
sum_tree(tree(X,Left,Right),Sum) :-
 sum_tree(Left,SumLeft),
 sum_tree(Right,SumRight),
 Sum is SumLeft+SumRight+X.
sum_tree(void,0).

(3)

% ordered(TreeOfIntegers) :-
%  TreeOfIntegersは整数の順序木である．
% ordered_left(X,Tree) :-
%  XがTreeの根節点よりも小さく，かつTreeが順序木．
% ordered_right(X,Tree) :-
%  XがTreeの根節点よりも小さく，かつTreeが順序木．
ordered(tree(X,Left,Right)) :-
 ordered_left(X,Left),
 ordered(Left),
 ordered_right(X,Right),
 ordered(Right).
ordered(void).
ordered_left(X,tree(Y,Left,Right)) :-
 X > Y, ordered_left(Y,Left), ordered_right(Y,Right).
ordered_right(X,tree(Y,Left,Right)) :-
 X < Y, ordered_left(Y,Left), ordered_right(Y,Right).
ordered_left(_,void).
ordered_right(_,void).

(4)

% tree_insert(X,Tree,Tree1) :-
%  Tree1は順序木Tree中にXを挿入してできる順序木である．
tree_insert(X,tree(X,Left,Right),tree(X,Left,Right)).
tree_insert(X,tree(Y,Left,Right),tree(Y,Left1,Right)) :-
 X < Y, tree_insert(X,Left,Left1).
tree_insert(X,tree(Y,Left,Right),tree(Y,Left,Right1)) :-
 X > Y, tree_insert(X,Right,Right1).
tree_insert(X,void,tree(X,void,void)).

Project Euler

problem 72
problem 73

Prologの技芸 3.3節の練習問題

(1)

% substitute(X,Y,L1,L2) :-
%  L2はL1中に現れるすべてのXをYで置き換えた結果である．
substitute(X,Y,[],[]).
substitute(X,Y,[X|Xs],[Y|Ys]) :- substitute(X,Y,Xs,Ys).
substitute(X,Y,[Z|Xs],[Z|Ys]) :- X \= Z, substitute(X,Y,Xs,Ys).

(2)

% select(X,Xs,Ys) :-
%  Ysは，Xsの最先頭にあるXをXsから削除したリストである．
select(X,[X|Xs],Xs).
select(X,[Y|Ys],[Y|Zs]) :- X \= Y, select(X,Ys,Zs).

(3)

% no_doubles(L1,L2) :-
%  L2はL1から重複する要素をすべて取り除いた結果である．
no_doubles([],[]).
no_doubles([X|Xs],Ys) :- member(X,Xs), !, no_doubles(Xs,Ys).
no_doubles([X|Xs],[X|Ys]) :- no_doubles(Xs,Ys).

(4)

% even_permutation(Xs,Ys) :-
%  YsはリストXsの偶数順列である．
% odd_permutation(Xs,Ys) :-
%  YsはリストXsの奇数順列である．
even_permutation([],[]).
odd_permutation([],[]).
even_permutation([X|Xs],Ys) :- odd_permutation(Xs,Ys).
odd_permutation([X|Xs],[X|Ys]) :- even_permutation(Xs,Ys).

(5)

% margesort(Xs,Ys) :-
%  リストYsはリストXsの順序付けられた順列である．
margesort([],[]).
margesort([X],[X]).
margesort([X1,X2|Xs],Ys) :-
 partition([X1,X2|Xs],Lefts,Rights),
 margesort(Lefts,Ls),
 margesort(Rights,Rs),
 marge(Ls,Rs,Ys).

% partition(Xs,Lefts,Rights) :-
%  LeftsとRightsはXsを大体半分ずつに分けたものである．
partition(Xs,Lefts,Rights) :-
 length(Xs,Length),
 half(Length,L,R),
 prefix(Lefts,Xs),
 length(Lefts,L),
 append(Lefts,Rights,Xs),
 length(Rights,R).

half(X,L,R) :-
 X1 is X/2,
 integer(X1),
 L = X1,
 R = X1.
half(X,L,R) :-
 X1 is (X-1)/2,
 integer(X1),
 L = X1,
 R is X-X1.

% marge(Xs,Ys,Zs) :-
%  ZsはXsとYsを併合したものである．
marge([],Xs,Xs).
marge(Xs,[],Xs).
marge([X|Xs],[Y|Ys],[X|Zs]) :- X < Y, marge(Xs,[Y|Ys],Zs).
marge([X|Xs],[Y|Ys],[Y|Zs]) :- X >= Y, marge([X|Xs],Ys,Zs).

Prologの技芸 3.2節の練習問題

(2)

adjacent(X,Y,[X,Y|_]).
adjacent(X,Y,[_|Zs]) :- adjacent(X,Y,Zs).
last(X,[X]).
last(X,[_|Ys]) :- last(X,Ys).

(5)

% sum(Sum,ListOfIntegers) :-
%  Sumは整数のリストListOfIntegersの要素の和である．

(a) plus/3を使った定義

natural_number(0).
natural_number(s(X)) :- natural_number(X).
plus(0,X,X) :- natural_number(X).
plus(s(X),Y,s(Z)) :- plus(X,Y,Z).
sum_a(0,[]).
sum_a(X,[Y|Ys]) :- sum_a(Z,Ys), plus(Y,Z,X).

(b) 補助述語を使わない定義

sum_b(0,[]).
sum_b(s(X),[s(Y)|Ys]) :- sum_b(X,[Y|Ys]).
sum_b(X,[0|Ys]) :- sum_b(X,Ys).