algorithm - Prolog:高效实现Luhn算法

Question

我尝试在 SWI-Prolog 中应用 Luhn 算法。但是我在运行时遇到了一些问题。当我用像 123 这样的简单数字进行测试时，它会很快给出结果。如果我用 5379173895860200 这样更长的数字进行测试，它运行的时间太长了，我只能中止这次执行。需要帮助才能找到问题。代码:

luhn(N):-
    spliter(N,Y),
    reverse(Y, Z),
    check(Z,X),
    sum_all(X, Res),
    T is Res mod 10,
    T is 0.

spliter(0,[]).
spliter(N,L):-
    N1 is floor(N/10),
    X is N mod 10,
    spliter(N1, L2),
    L = [X|L2].

check(A,B):-
    double(A,B,_).

double([],[],0).
double([H|T], [H1|T1], C):-
    double(T,T1, C1),
    C is C1 +1,
    H1 is H*(1+ C mod 2).

sum_all([],0).
sum_all([H|T],Sum):-
    sum_all(T,Subsum),
    X is floor(H/10),
    Y is H mod 10,
    Sum is (Subsum + X + Y).

Answer 1

不需要取很大的数字就能看出你代码的问题。考虑同样循环的 luhn(1) 和“高效”的 luhn(0) 就足够了。

您遇到的问题不是效率问题，而是终止问题。终止在 Prolog 中是一个非常微妙的概念。如果您通过顶层循环使用 Prolog，许多系统只会向您显示第一个答案。如果查询不包含变量，有些甚至不会显示任何进一步的答案。通过这种方式，您很容易产生错误的印象，认为您的程序可以正常运行并终止，而实际上却没有。

有一种非常简单的方法，您可以在任何系统中测试终止。只需将目标 false 添加到您的查询中。现在甚至 luhn(0),false 循环。

您可以更进一步，将此类 false 目标添加到您的程序中¹，从而减少您必须理解的文本的大小.在你的情况下，考虑就足够了:

luhn(N):-    spliter(N,Y), false,    reverse(Y, Z),    check(Z,X),    sum_all(X, Res),    T is Res mod 10,    T is 0.spliter(0,[]) :- false.spliter(N,L):-    N1 is floor(N/10),    X is N mod 10,    spliter(N1, L2), false,    L = [X|L2].

程序的这一小部分(称为 failure-slice)足以理解非终止。事实上，任何整数 N 都会导致循环。您需要的是直接添加 N > 0 作为 spliter/2 的第一个目标。

有关更多信息，请参阅 failure-slice

^{细则
1 实际上，这只适用于像您的程序这样的纯粹、单调的程序。}