Есть несколько вопросов, выраженных в постановке задачи:
В Прологе , есть предикаты и условия, но не функции. Думая о них как функции приводит к тому, что вы можете написать такие термины, как foo(bar(3), X*2))
, и ожидать, что Prolog вызовет bar(3)
и оценит X*2
, а затем передаст эти результаты в качестве двух аргументов в foo
. Но то, что делает Пролог, передает их так же, как и их имена (на самом деле, X*2
внутренне это термин, *(X,2)
).И если были вызваны bar(3)
, он не возвращает значение, а скорее либо сбой, либо сбой.
is/2
не является оператором присваивания переменных, а скорее оценщиком арифметических выражений. Он оценивает выражение во втором аргументе, а объединяет с переменной или атомом слева. Это удается, если оно может объединиться и не получилось иначе.
Хотя такие выражения, как 0 is N mod 2, N1 is round(N/2)
будут работать, вы можете взять больше преимуществ целочисленной арифметики в Прологе и записать его более соответствующим образом, как, 0 =:= N mod 2, N1 is N // 2
где =:=
является арифметическим оператором сравнения. Вы также можете использовать битовые операции: N /\ 1 =:= 0, N1 is N // 2
.
Вы не определили последовательное определение того, что такое град шторма дерево выглядит. Например, иногда ваш аргумент hs
имеет один аргумент, а иногда он имеет три. Это приведет к сбоям объединения, если вы явно не сортируете его в своем предикате 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).
Или в более компактной форме, используя Пролог если-иначе картина:
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
. Если вы хотите использовать var
и nonvar
, я оставлю это как упражнение для преобразования обратно. :)
Теперь к последовательности. Во-первых, я бы сделал четкое определение того, как выглядит дерево. Так как это бинарное дерево, общее представление будет:
hs(N, Left, Right)
Где Left
и Right
являются Филиалы (суб-деревья), которые могут иметь значение nul
, n
, nil
или любой другой атом вы хотите, чтобы представить пустое дерево. Теперь у нас есть последовательный, 3-аргументный термин для представления дерева.
Тогда предикат может быть легко определено с получением града:
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
hailSequence (1, [1]): -!. был отредактирован/исправлен? Я читаю град. Оценка (1,1): -!. previoulsy, которые приводят к тому, чтобы потребовать эту выборку градиента (5, [5,16,8,4,2 | 1]). –
@philippelhardy Это всегда было 'hailSequence (1, [1])' в сообщении, но поскольку он был отформатирован как цитата вместо кода, StackOverflow думал, что '[1]' означал ссылку сноски и отображал ее как '1' (обратите внимание, что он отображается как синий и можно щелкнуть, если вы посмотрите на предыдущую версию). –
@PhilippWendler благодарит за ваше редактирование, это помогает сосредоточиться на реальной проблеме. –