Список факториалов в Прологе

У меня возникли проблемы с решением следующего упражнения...

Факториал можно описать на Прологе следующим образом:

factorial(0, 1).
factorial(N, F) :-
   N1 is N - 1,
   factorial(N1, F1),
   F is N * F1.

Мне нужно расширить этот код, чтобы вернуть список всех предыдущих факториалов до N. Но он возвращает только первый факториал (1), а затем ошибку: ERROR: Out of local stack. Вот мой код:

insertList(H, L, [H|L]) :-
   !.

factorial(0, 1, [1]).
factorial(N, F, L) :-
   N1 is N - 1,
   factorial(N1, F1, L),
   F is N * F1,
   insertList(F, L, [F|L]). 

list_factorial(X, L) :-
   factorial(X, F, L).

Что я делаю не так?


list factorial prolog
person Arthur Fortes    schedule 13.04.2015    source источник
comment
factorial(0,0) петель. Добавьте в правило не менее N > 0!   -  person false    schedule 13.04.2015

Ответы (4)


arrow_upward
0
arrow_downward

минимальная коррекция, указывающая на основную проблему

insertList(H, L, [H|L]):- !.

factorial(0, 1, [1]).
factorial(N, F, Fs):- N1 is N-1, factorial(N1, F1, L), F is N * F1, insertList(F, L, Fs). 

list_factorial(X, L):- factorial(X, F, L).

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

factorials(N, L) :-
    N > 0 -> L = [F,G|Fs], M is N-1, factorials(M, [G|Fs]), F is G*N ; L = [1].
person CapelliC    schedule 13.04.2015

arrow_upward
1
arrow_downward

Вот реализация на чистом prolog с clpfd:

:- use_module(library(clpfd)).

list_factorial([1], 0).
list_factorial(Zs0, N) :-
   length(Zs0, N),
   N #> 0,
   list_n_fac(Zs0, 1, 1).

list_n_fac([], _, _).
list_n_fac([Z1|Zs], N0, Z0) :-
   Z1 #= Z0 * N0,
   N1 #= N0 + 1,
   list_n_fac(Zs, N1, Z1).

Пример запроса:

?- list_factorial(Zs, 8).
Zs = [1,2,6,24,120,720,5040,40320].

Вот самый общий запрос:

?- list_factorial(Zs, N).
(  N = 0, Zs = [1]
;  N = 1, Zs = [1]
;  N = 2, Zs = [1,2]
;  N = 3, Zs = [1,2,6]
;  N = 4, Zs = [1,2,6,24]
;  N = 5, Zs = [1,2,6,24,120]
...
person repeat    schedule 14.04.2015

arrow_upward
0
arrow_downward

Другое решение:

factorial(0,1) :- !.
factorial(N,F) :- 
    N>0, N1 is N - 1, factorial(N1,F1), F is N * F1.

list_factorial(N,L) :-
    N>1, !, N2 is N-1, list_factorial(N2,L2), factorial(N,F), append(L2,[F],L). 
list_factorial(N,[F]) :- factorial(N,F).

Я изменил ваш factorial с проверкой, если N больше 0, потому что вы не можете сделать факториал отрицательного числа и с разрезом, чтобы получить только одно решение.

person RobotMan    schedule 15.04.2015

arrow_upward
-1
arrow_downward

Вы заставили меня установить SWI-prolog, ха-ха.

list_fact(N,M,A):- A is N * M.
list_fact(N,M,A):- N1 is N + 1, M1 is N * M, list_fact(N1,M1,A).

Позвонить как

list_fact(1,1,A).

Это довольно просто. Первое правило вычисляет следующий факториал как N * M. Второе правило выполняет рекурсивный вызов, где N = N + 1, а M = предыдущий факториал, рассчитанный в правиле 1.

person wvdz    schedule 13.04.2015
comment
@repeat Очевидно, я имел в виду факториал. Алгоритм по-прежнему правильный. - person wvdz; 14.04.2015
comment
@repeat Думаю, ты прав. Я не знал, что он ищет реальный список, поэтому я просто сделал функцию, которая продолжает генерировать факториалы, пока не завершится. - person wvdz; 14.04.2015