序言中的帕斯卡三角形，递归且无切割

Question

我正在尝试在 prolog 中编写一个程序，其中 returns 是 Pascal 三角形的列表。该列表包含用户输入指示的行的所有元素。例如：

ptriangle(3,X).

returns: X = [1, 2, 1]

到目前为止我有：

sumC([X,Y],[Z]) :- Z is X + Y.
sumC([X,Y|L], Z):- H is X + Y,
                    sumC([Y|L],L2),
                    Z = [H|L2].

ptriangle(1,[1]) :- ! .
ptriangle(2,[1,1]) :- !.
ptriangle(N, L) :- Ant is N - 1,
                   ptriangle(Ant,L2),
                   sumC(L2,R),
                   append([1|R],[1],L), !.

但我正在尝试找到一种无需 ! 且使用递归的方法。你有什么建议吗？

Answer 1

您已经在 ptriangle 中使用递归。你可以避免削减 !，代价是一些不确定性。

看看这个，看看变化：

sumC([X,Y],[Z, 1]) :- Z is X + Y.
sumC([X,Y|L], Z):- H is X + Y,
                   sumC([Y|L],L2),
                   Z = [H|L2].

ptriangle(1,[1]).
ptriangle(2,[1,1]).
ptriangle(N, [1|R]) :- N > 2,
                       Ant is N - 1,
                       ptriangle(Ant,L2),
                       sumC(L2,R).

最后那个append可能会很贵，所以你可以让sumC自己在建表的时候给一个

尝试找出更改如何影响执行。

PS:

sumC([X,Y|L], [H|L2]):- H is X + Y,
                        sumC([Y|L],L2).

是一种惯用的写法：

sumC([X,Y|L], Z):- H is X + Y,
                   sumC([Y|L],L2),
                   Z = [H|L2].

序言中的帕斯卡三角形，递归且无切割

Pascal's triangle in prolog with recursion and without cuts

prolog

pascals-triangle