prolog - 查询将数字转换为数字失败

Question

split(0).
split(M,List) :-
    M > 0,
    MM is floor(M / 10),
    Z is M mod 10,
    append(List,[Z],SubList),
    nl,
    print(SubList),
    split(MM,SubList).

Answer 1

这可能是一个简单的拼写错误:你的 split/1事实的数量为一，而归纳案例的数量为第二。将第一行修改为:

split(0,[]).

你应该使用append/3相反的方式:

append(SubList,[Z],List),

所以谓词是这样的:

split(0,[]).
split(M,List) :-
    M > 0,
    MM is floor(M / 10),
    Z is M mod 10,
    append(SubList,[Z],List),
    split(MM,SubList).

将部分解决问题:它将返回一个正确答案。但随后陷入无限循环。原因是你调用append/3两者都有 List和SubList未实例化，例如:

append(A,[3],B).

将其运行到运行时环境中会生成:

?- append(A,[3],B).
A = [],
B = [3] ;
A = [_G218718],
B = [_G218718, 3] ;
A = [_G218718, _G218724],
B = [_G218718, _G218724, 3] ;
A = [_G218718, _G218724, _G218730],
B = [_G218718, _G218724, _G218730, 3] ;
A = [_G218718, _G218724, _G218730, _G218736],
B = [_G218718, _G218724, _G218730, _G218736, 3] ;
A = [_G218718, _G218724, _G218730, _G218736, _G218742],
B = [_G218718, _G218724, _G218730, _G218736, _G218742, 3];

(等)

因此有无限数量的列表，append/3谓词成功，所有这些列表都会失败，因为最终你调用 split/2与 0需要一个空列表，但事实并非如此。

使用累加器的更优雅的解决方案

使用append/3使用一个元素通常效率不高:每次插入都会导致 O(n) 时间复杂度，因此对于这个问题，您的 split/2谓词将在 O(n²) 中运行。解决方案是使用累加器:通过递归调用更新的变量。在这种情况下，您的第一个谓词链接 split/2与 split/3 :带有累加器的版本。

split(A,B) :-
    split(A,[],B).

现在是split/3的归纳案例又是 A == 0 的那个。在这种情况下，我们将累加器视为最终结果:

split(0,B,B).

归纳情况意味着我们查找数字，将其添加到累加器的头部，然后递归地传递它:

split(M,Acc,Res) :-
    M > 0,
    MM is floor(M / 10),
    Z is M mod 10,
    split(MM,[Z|Acc],Res).

所以把它们放在一起，我们的版本有以下代码:

split(A,B) :-
    split(A,[],B).

split(0,B,B).
split(M,Acc,Res) :-
    M > 0,
    MM is floor(M / 10),
    Z is M mod 10,
    split(MM,[Z|Acc],Res).