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。これにより、理解しなければならないテキストのサイズを減らすことができます。あなたの場合、代わりに考慮するだけで十分です：

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

spliter(0,[]) :- false .
スプリッター(N、L):-
    N1は床(N/10)、
    X は N mod 10 です。
    spliter(N1, L2), false ,
     L = [X|L2] .

プログラムのこの小さな部分 ( と呼ばれます) だけで、非終了を十分に理解できます。実際、整数Nはループにつながります。必要なのはN > 0、 の最初のゴールとして直接追加することですspliter/2。

詳細については、

細字
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)
...

問題は、splitter/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 に答える