Реализовать счетчик на прологе Ханойских башен - PullRequest
Новая
       39

Реализовать счетчик на прологе Ханойских башен

3 голосов
/ 16 ноября 2011

У меня есть программа на утро, использующая Пролог.

Я реализую Ханойские башни.

Мне нужна помощь каждый раз, когда он печатает Move disc number # from _ to _. Мне нужно увеличить счетчик, говоря Move X: "String" Строка, являющаяся предыдущим утверждением того, что нужно переместить.

В конце программы мне нужно распечатать общее количество ходов, выполненных для выполнения головоломки. В настоящее время моя программа рекурсивно настроена снизу вверх.

Ответы [ 3 ]

1 голос
/ 16 ноября 2011

вместо написания предиката "сделай все" разбейте его на предикаты "сделай одно":

  1. написать предикат, который получает количество дисков и возвращает список ходов, которые решают проблему (т. Е. [1->2, 3->1, ...])
  2. стандартный предикат length/2 уже позволяет подсчитывать количество ходов в списке.
  3. написать предикат для печати списка ходов в удобном для пользователя формате.
  4. написать предикат для вызова предыдущих предикатов по порядку.
1 голос
/ 14 марта 2016

Используя этот вариант, можно вызвать 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).
1 голос
/ 16 ноября 2011

Одной из распространенных проблем является смешивание ввода-вывода с расчетом. Лучше изолировать ввод-вывод, используя предикат-обертку с аргументом, экземпляр которого создается с результатом.

Учтите это (код предназначен для демонстрации добавления счетчика, а не для решения проблемы): 

% 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('.').

Даже если приведенный выше код не относится к тому, что у вас есть, применяется та же процедура: добавьте аргументы для передачи счетчика и используйте рекурсию для его увеличения.

В качестве альтернативы, есть глобальные переменные , но, как правило, их осуждают, поскольку их легко использовать и писать процедурные программы.

...