Как изменить целое число в Прологе с помощью хвостовой рекурсии? - PullRequest
Новая
       30

Как изменить целое число в Прологе с помощью хвостовой рекурсии?

0 голосов
/ 03 июня 2018

Я хотел бы сделать обратный предикат (N, Результат) в Прологе.

Например:

  • реверс (12345, Результат).
  • Результат = 54321.

Я должен использовать хвостовую рекурсию.Я могу использовать *, +, - и divmod / 4, и это все. Я не могу использовать список.

Я могу перевернуть число <100, но я не могу найти, как закончить мой код, я могуНе завершите мой код для обратного целых чисел больше 100. </p> 

reverse(N,N):-
    N <10,
    N>0.

reverse(N,Result):-
    N > 9,
    iter(N,0,Result).

iter(N,Ac,Result):-
    N  < 100, !,
    divmod(N,10,Q,R),
    R1 is R*10,
    Result is Q + R1.

Могу ли я получить помощь, пожалуйста?

Заранее спасибо.

Ответы [ 2 ]

0 голосов
/ 04 июня 2018

Если по какой-то причине вам не нужно решение на основе ограничений, или если вы используете систему Prolog, не поддерживающую ограничения, альтернативное решение: 

reverse_digits(N, M) :-
    (   integer(N) ->
        reverse_digits(N, 0, M)
    ;   integer(M),
        reverse_digits(M, 0, N)
    ).

reverse_digits(0, M, M) :- !.
reverse_digits(N, M0, M) :-
    N > 0,
    R is N div 10,
    M1 is M0 * 10 + N mod 10,
    reverse_digits(R, M1, M).

Это решение можно использовать с любым аргументомсвязана с целым числом и не оставляет ложных точек выбора: 

?- reverse_digits(12345, M).
M = 54321.

?- reverse_digits(N, 12345).
N = 54321.

?- reverse_digits(12345, 54321).
true.

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

?- reverse_digits(N, M).
false.
0 голосов
/ 04 июня 2018

Я предлагаю использовать CLP (FD) , поскольку он предлагает декларативные рассуждения по целочисленной арифметике, и многие системы Prolog предоставляют его.Что касается обращения цифр, я рекомендую вам взглянуть на запись A004086 в Онлайн-энциклопедия целочисленных последовательностей .В абзаце, озаглавленном FORMULA , вы найдете, среди прочего, следующие формулы: 

a(n) = d(n,0) with d(n,r) = if n=0 then r else d(floor(n/10),r*10+(n mod 10))

Они могут быть переведены в предикаты путем добавления дополнительного аргумента для обратного числа.Сначала давайте дадим ему хорошее декларативное имя, скажем digits_reversed/2.Тогда отношение может быть выражено с использованием #>/2, #=/2, (/)/2, +/2, mod/2 и хвостовой рекурсии: 

:- use_module(library(clpfd)).

digits_reversed(N,X) :-
   digits_reversed_(N,X,0).

digits_reversed_(0,R,R).
digits_reversed_(N,X,R) :-
   N #> 0,
   N0 #= N/10,
   R1 #= R*10 + (N mod 10),
   digits_reversed_(N0,X,R1).

Обратите внимание, что digits_reversed/2 соответствует a(n)и digits_reversed_/3 соответствует d(n,r) в приведенных выше формулах.Теперь давайте запросим предикат с примером из вашего поста: 

?- digits_reversed(12345,R).
R = 54321 ;
false.

Предикат также можно использовать в другом направлении, то есть задайте Какое число было обращено для получения 54321? Однако, так как ведущие нули чисел опущены, одно обратное число имеет бесконечно много исходных чисел: 

?- digits_reversed(N,54321).
N = 12345 ;
N = 123450 ;
N = 1234500 ;
N = 12345000 ;
N = 123450000 ;
N = 1234500000 ;
N = 12345000000 ;
N = 123450000000 ;
.
.
.

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

?- digits_reversed(N,R).
N = R, R = 0 ;              % <- zero
N = R,
R in 1..9 ;                 % <- other one-digit numbers
N in 10..99,                % <- numbers with two digits
N mod 10#=_G3123,
N/10#=_G3135,
_G3123 in 0..9,
_G3123*10#=_G3159,
_G3159 in 0..90,
_G3159+_G3135#=R,
_G3135 in 1..9,
R in 1..99 ;
N in 100..999,              % <- numbers with three digits
N mod 10#=_G4782,
N/10#=_G4794,
_G4782 in 0..9,
_G4782*10#=_G4818,
_G4818 in 0..90,
_G4818+_G4845#=_G4842,
_G4845 in 0..9,
_G4794 mod 10#=_G4845,
_G4794 in 10..99,
_G4794/10#=_G4890,
_G4890 in 1..9,
_G4916+_G4890#=R,
_G4916 in 0..990,
_G4842*10#=_G4916,
_G4842 in 0..99,
R in 1..999 ;
.
.
.

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

?- N in 10..20, digits_reversed(N,R), label([N]).
N = 10,
R = 1 ;
N = R, R = 11 ;
N = 12,
R = 21 ;
N = 13,
R = 31 ;
N = 14,
R = 41 ;
N = 15,
R = 51 ;
N = 16,
R = 61 ;
N = 17,
R = 71 ;
N = 18,
R = 81 ;
N = 19,
R = 91 ;
N = 20,
R = 2 ;
false.
...