3

我有一个使用 Prolog 的程序在早上到期。

我正在实施河内塔。

我需要帮助的是每次打印Move disc number # from _ to _。我需要增加一个计数器，说Move X: "String"String 是要移动的前一个语句。

在程序结束时，我需要打印完成拼图所采取的移动总数。我目前有我的程序设置递归自下而上。

4

3 回答 3

1

与其写一个全能的谓词，不如把它分解成一个做一件事的谓词：

  1. 编写一个谓词，获取光盘的数量并返回解决问题的移动列表（即[1->2, 3->1, ...]）
  2. 标准length/2谓词已经允许您计算列表中的移动次数。
  3. 编写谓词以用户友好的格式打印移动列表。
  4. 写一个谓词按顺序调用前面的谓词。
于 2011-11-16T08:49:06.637 回答
1

一个常见问题是将 IO 与计算混合在一起。最好通过使用带有参数的包装谓词来隔离 IO，该参数会随结果实例化。

考虑一下（代码旨在演示添加计数器，而不是解决问题）：

% one move
move(1,X,Y,_,_,1) :-                           
    write('Move top disk from '), 
    write(X), write(' to '), write(Y), nl.

move(N,X,Y,Z,Count,Counter) :- 
    N>1, 
    M is N-1,
    Countplus is Count*2,        % binary recursion tree
    move(M,X,Z,Y,Countplus,C1), 
    move(1,X,Y,_,Countplus,C2),
    move(M,Z,Y,X,Countplus,C3),
    Counter is C1+C2+C3.         % sum of moves

towers(N,X,Y,Z) :-
    Count is N*N-1,
    move(N,X,Y,Z,Count,Counter),                       
    % you can now do whatever you want with Counter, e.g. print it:
    write('The number of steps required with '),
    write(N), write(' disks is '), write(Count), write('.').

即使上面的代码与你所拥有的无关，同样的过程也适用：添加参数来传输计数器并使用递归来增加它。

或者，有全局变量，但通常不受欢迎，因为它们很容易误用和编写程序程序。

于 2011-11-16T08:21:15.050 回答
1

使用此变体，可以调用hanoi(3,left,middle,right,Moves-NMoves)，并将移动列表实例化为Moves，并将采取的移动次数实例化为NMoves。可以很容易地编写一个谓词来将每个列表成员格式化为输入/输出。

注意这里如何使用差异列表来避免昂贵的append/3. 谓词中的length/2调用hanoi/5作为一种证明，结果移动列表的大小是正确的。

hanoi(N, Src, Aux, Dest, Moves-NMoves) :-
  NMoves is 2^N - 1,
  length(Moves, NMoves),
  move(N, Src, Aux, Dest, Moves-_).


move(1, Src, _, Dest, [Src->Dest|Rest]-Rest) :- !.
move(2, Src, Aux, Dest, [Src->Aux,Src->Dest,Aux->Dest|Rest]-Rest) :- !.
move(N, Src, Aux, Dest, Moves-Rest) :-
  N0 is N-1,
  move(N0, Src, Dest, Aux, Moves-M1),
  move(1, Src, Aux, Dest, M1-M2),
  move(N0, Aux, Src, Dest, M2-Rest).

更易读的方法可能涉及使用 DCG 来隐藏管道：

hanoi(N, Src, Aux, Dest, Moves-NMoves) :-
  NMoves is 2^N - 1,
  length(Moves, NMoves),
  phrase(move(N, Src, Aux, Dest), Moves).


move(1, Src, _, Dest) --> !,
  [Src->Dest].

move(2, Src, Aux, Dest) --> !,
  [Src->Aux,Src->Dest,Aux->Dest].

move(N, Src, Aux, Dest) -->
  { succ(N0, N) },
  move(N0, Src, Dest, Aux),
  move(1, Src, Aux, Dest),
  move(N0, Aux, Src, Dest).
于 2016-03-14T01:29:39.757 回答