2

我尝试在 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).
4

2 回答 2

2

无需花费大量时间来查看代码的问题。考虑luhn(1)哪些循环以及“高效”就足够了luhn(0)。

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

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

您可以更进一步，将这些false目标添加到您的程序1中，从而减少您必须理解的文本的大小。在您的情况下，考虑改为：

卢恩（N）：-
    spliter(N,Y), false ,
     reverse(Y, Z) ,
     check(Z,X) ,
     sum_all(X, Res) ,
     T 是 Res mod 10 ,
     T 是 0。

拆分器（0，[]）：-假。
分离器（N，L）：-
    N1 是楼层（N/10），
    X 是 N mod 10，
    拆分器（N1，L2），假，
     L = [X|L2]。

程序的这一小部分（称为）足以理解不终止。事实上，任何整数N都会导致循环。您需要的是N > 0直接添加作为spliter/2.

有关更多信息，请参见

Fine Print
1 实际上，这仅适用于像您的程序这样的纯单调程序。

于 2015-08-02T14:52:31.040 回答
1

这是我从维基百科翻译的 Python

is_luhn_valid(Card_number):-
    luhn_checksum(Card_number, 0).

luhn_checksum(Card_number, Checksum) :-
    digits_of(Card_number, Digits),
    findall(D, (nth0(I, Digits, D), I mod 2 =:= 0), Odd_digits),
    findall(D, (nth0(I, Digits, D), I mod 2 =:= 1), Even_digits),
    sum_list(Odd_digits, Checksum_t),
    findall(S, (
        member(T, Even_digits),
        T1 is T * 2,
        digits_of(T1, D1),
        sum_list(D1, S)
    ), St),
    sum_list(St, St1),
    Checksum is (Checksum_t + St1) mod 10.

digits_of(Number, Digits) :-
    number_codes(Number, Cs),
    maplist(code_digit, Cs, Digits).
code_digit(C, D) :- D is C - 0'0.

除了更冗长之外，上面页面中的测试用例似乎是正确的。但：

?- is_luhn_valid(123).
false.

而你的代码：

?- luhn(123).
true ;
true ;
...

而且当然

?- luhn(124).
....

不会终止。所以，你陷入了一个失败循环，每次都要求 Prolog 试图证明一个无法解决的目标......

痕迹片段：

?- leash(-all),trace.
true.

[trace] ?- luhn(124).
   Call: (7) so:luhn(124)
   Call: (8) so:spliter(124, _G9437)
...
   Exit: (8) 2 is 12 mod 10
   Call: (8) 2 is 0
   Fail: (8) 2 is 0
   Redo: (11) so:spliter(0, _G9461)
   Call: (12) _G9465 is floor(0/10)
...

问题似乎是 spliter/2 不断在序列前面添加 0，而它应该失败。

关于效率：我的片段可以重写为

luhn_checksum(Card_number, Checksum) :-
    digits_of(Card_number, Digits),
    aggregate_all(sum(V), (
        nth0(I, Digits, D),
        (   I mod 2 =:= 0
        ->  V = D           % Odd_digits
        ;   Dt is D * 2,    % Even_digits
            digits_of(Dt, Ds),
            sum_list(Ds, V)
        )),
        Checksum_t),
    Checksum is Checksum_t mod 10.

利用库（聚合）

编辑

我认为 spliter/2 应该检查 N > 0，否则它将永远递归......尝试

spliter(N,L):- N>0,
    N1 is floor(N/10),
    ...
于 2015-08-01T09:16:03.953 回答