2

我试图在冰雹序列上实现各种形式的查询。

冰雹序列是具有以下属性的正整数序列：

  • 1 被认为是序列的终止值。
  • 对于任何偶数正整数 i，序列中 i 之后的值为 i/2。
  • 对于任何奇正整数 j > 1，序列中 j 之后的值为 3j+1

查询可以

  • hailSequence (Seed,Sequence)：其中 Sequence 是从给定的 Seed 生成的冰雹序列。

  • hailStone (M,N)：其中 N 是冰雹序列中 M 之后的数字。例如，如果 M 为 5，则 N 应为 16，如果 M 为 20，则 N 应为 10，以此类推。

  • hailStorm (Seed,Depth,HailTree)：其中 HailTree 是在指定深度的序列中可以在 Seed 之前的值树。

例子：

| ?- hailStorm(1,4,H).  
H = hs(1,hs(2,hs(4,hs(8)))) ?  
yes 

| ?- hailStorm(5,3,H).  
H = hs(5,hs(10,hs(3),hs(20))) ?  
yes

图示

现在我已经实现了前两个谓词：

hailSequence(1,[1]) :- !.  
hailSequence(N,[N|S]) :- 0 is N mod 2, N1 is round(N / 2), hailSequence(N1,S).  
hailSequence(N,[N|S]) :- 1 is N mod 2, N1 is (3 * N) + 1, hailSequence(N1, S).  

hailStone(X,Y) :- nonvar(X), 0 is X mod 2, Y is round(X / 2).  
hailStone(X,Y) :- nonvar(X), 1 is X mod 2, Y is (3 * X) + 1.  
hailStone(X,Y) :- nonvar(Y), 1 is Y mod 3, T is round( (Y - 1) / 3), 1 is T mod 2, X is T.

对于hailStorm/2谓词，我编写了以下代码，但它没有按预期工作：

make_hs1(S,hs(S)).  
make_hs2(S,R,hs(S,make_hs1(R,_))).  
make_hs3(S,L,R,hs(S,make_hs1(L,_),make_hs1(R,_))).  

hailStorm(S,1,hs(S)) :- !.  
hailStorm(S,D,H) :- nonvar(S), nonvar(D), 4 is S mod 6, S=\= 4, make_hs3(S,hailStorm(round((S-1)/3),D-1,_X),hailStorm(2*S,D-1,_Y),H).  

hailStorm(S,D,H) :- nonvar(S), nonvar(D), make_hs2(S,hailStorm(2*S,D-1,_X),H).

输出：

| ?- hailStorm(5,2,H).  
H = hs(5,make_hs1(hailStorm(2*5,2-1,_),_))  
yes

这不是所需的输出，即

H = hs(5,hs(10)) ?
4

1 回答 1

2

问题陈述中表达了几个问题：

  • 在 Prolog 中，有谓词和术语，但没有函数。将它们视为函数会让人相信您可以编写诸如此类的术语，foo(bar(3), X*2))并期望 Prolog 将调用bar(3)和评估X*2，然后将这些结果作为两个参数传递给foo. 但是 Prolog 所做的只是将这些作为您看到的术语传递（实际上，X*2内部是术语，*(X,2)）。如果bar(3)被调用，它不会返回值，而是成功或失败。

  • is/2不是变量赋值运算符，而是算术表达式求值器。它计算第二个参数中的表达式并将其与左侧的变量或原子统一。能统一就成功，否则失败。

  • 尽管诸如此类的表达式0 is N mod 2, N1 is round(N / 2)可以工作，但您可以在 Prolog 中充分利用整数算术并将其更恰当地编写为算术比较运算符0 =:= N mod 2, N1 is N // 2在哪里。=:=您还可以使用位操作：N /\ 1 =:= 0, N1 is N // 2.

  • 您还没有为冰雹风暴树的外观定义一致的定义。例如，有时您的hs术语有一个参数，有时它有三个。如果您没有在 predicate 中明确地对其进行排序，这将导致统一失败hailStorm。

所以你hailSequence在其他方面是正确的，但你不需要削减。我会将其重构为：

hail_sequence(1, [1]).
hail_sequence(Seed, [Seed|Seq]) :-
    Seed > 1,
    Seed /\ 1 =:= 0,
    S is Seed // 2,
    hail_sequence(S, Seq).
hail_sequence(Seed, [Seed|Seq]) :-
    Seed > 1,
    Seed /\ 1 =:= 1,
    S is Seed * 3 + 1,
    hail_sequence(S, Seq).

或者更简洁，使用 Prolog if-else模式：

hail_sequence(1, [1]).
hail_sequence(Seed, [Seed|Seq]) :-
    Seed > 1,
    (   Seed /\ 1 =:= 0
    ->  S is Seed // 2
    ;   S is Seed * 3 + 1
    ),
    hail_sequence(S, Seq).

您的描述hailStone并没有说它需要是“双向的”，但您的实现暗示这就是您想要的。因此，它似乎不完整，因为它缺少案例：

hailStone(X, Y) :- nonvar(Y), Y is X * 2.

我会使用一点 CLPFD 来重构它，因为它会给出“双向性”，而无需检查var和nonvar. 我还将进行区分hail_stone1，hail_stone2原因您稍后会看到。这些代表了可以生成冰雹的两种方式。

hail_stone(S, P) :-
    hail_stone1(S, P) ; hail_stone2(S, P).
hail_stone1(S, P) :-
    S #> 1,
    0 #= S rem 2,
    P #= S // 2.
hail_stone2(S, P) :-
    S #> 1,
    1 #= S rem 2,
    P #= S * 3 + 1.

请注意，S必须限制为，> 1因为没有冰雹之后1。如果你想要这些使用varand nonvar，我会把它作为一个练习来转换回来。:)

现在到序列。首先，我会对树的外观做出一个清晰的定义。由于它是二叉树，因此常见的表示形式是：

hs(N, Left, Right)

WhereLeft和Right是分支（子树），它的值可以是,nul或任何其他你希望表示空树的原子。现在我们有一个一致的、3 参数的术语来表示树。nnil

然后可以更容易地定义谓词以产生冰雹风暴：

hail_storm(S, 1, hs(S, nil, nil)).  % Depth of 1

hail_storm(S, N, hs(S, HSL, HSR)) :-
    N > 1,
    N1 is N - 1,

    % Left branch will be the first hail stone sequence method
    (   hail_stone1(S1, S)       % there may not be a sequence match
    ->  hail_storm(S1, N1, HSL)
    ;   HSL = nil
    ),

    % Right branch will be the second hail stone sequence method
    (   hail_stone2(S2, S)       % there may not be a sequence match
    ->  hail_storm(S2, N1, HSR)
    ;   HSR = nil
    ).

我们从中得到，例如：

| ?- hail_storm(10, 4, Storm).

Storm = hs(10,hs(20,hs(40,hs(80,nil,nil),hs(13,nil,nil)),nil),hs(3,hs(6,hs(12,nil,nil),nil),nil)) ? ;

(1 ms) no

如果您想使用不太对称且可以说是不太规范的二叉树定义：

hs(N)        % leaf node
hs(N, S)     % one sub tree
hs(N, L, R)  % two sub trees

然后hail_storm/3谓词变得稍微复杂但易于管理：

hail_storm(S, 1, hs(S)).
hail_storm(S, N, HS) :-
    N > 1,
    N1 is N - 1,
    (   hail_stone1(S1, S)
    ->  hail_storm(S1, N1, HSL),
        (   hail_stone2(S2, S)
        ->  hail_storm(S2, N1, HSR),
            HS = hs(S, HSL, HSR)
        ;   HS = hs(S, HSL)
        )
    ;   (   hail_stone2(S2, S)
        ->  hail_storm(S2, N1, HSR),
            HS = hs(S, HSR)
        ;   HS = hs(S)
        )
    ).

我们从中得到：

| ?- hail_storm1(10, 4, Storm).

Storm = hs(10,hs(20,hs(40,hs(80),hs(13))),hs(3,hs(6,hs(12)))) ? ;

no
于 2015-02-28T14:55:16.357 回答