3

1000未満の3と5のすべての正の倍数の合計を見つけようとしています。5の倍数の合計から3の倍数を削除することになっている部分を追加した後、gprologはクエリ?- sigma(1000,N).

問題は明らかにsigma5にありますが、私はそれを完全に見つけることができません。

sigma(Num, Result) :- sigma3(Num, 3, Result3),
                      sigma5(Num, 5, Result5),
                      Result is Result3 + Result5.

sigma3(Num, A, Result) :- A < Num,
                          Ax is A+3,
                          sigma3(Num, Ax, ResultX),
                          Result is ResultX + A.
sigma3(Num, A, Result) :- A >= Num,
                          Result is 0.

sigma5(Num, A, Result) :- A < Num,
                          mod3 is A mod 3,
                          0 \= mod3,
                          Ax is A+5,
                          sigma5(Num, Ax, ResultX),
                          Result is ResultX + A.
sigma5(Num, A, Result) :- A < Num,
                          mod3 is A mod 3,
                          0 == mod3,
                          Ax is A+5,
                          sigma5(Num, Ax, ResultX),
                          Result is ResultX.
sigma5(Num, A, Result) :- A >= Num,
                          Result is 0.

私のコードの何が問題になっていますか？

4

4 に答える 4

4

整数が含まれるため、有限領域制約の使用を検討してください。たとえば、SWI-Prolog の場合:

?- use_module(library(clpfd)).
true.

?- findall(N, (N mod 3 #= 0 #\/ N mod 5 #= 0, N in 0..999, indomain(N)), Ns),
   sum(Ns, #=, Sum).
Ns = [0, 3, 5, 6, 9, 10, 12, 15, 18|...],
Sum = 233168.
于 2012-02-07T18:33:03.160 に答える
2

Prolog は、その算術機能のために人気がありませんでした。

これは、過度の評価を行わずにシンボリック処理の「項コンストラクター」を表す必要があるためです。そのため、実際の算術演算が必要な場合は、式を「渡す」代わりに、結果に「スペース」(変数) を明示的に割り当てる必要があります。 . これにより、かなり冗長で不快なコードが作成されます。

しかし、GProlog や SWI-Prolog で利用できる CLP(FD) のような一般的な拡張機能を使用すると、他の言語ではすぐに利用できない、はるかに優れた結果が得られます。つまり、通常の算術演算に対する整数ドメインのクロージャです。たとえば、SWI-Prolog CLP(FD) ライブラリから、「双方向」階乗

n_factorial(0, 1).
n_factorial(N, F) :- N #> 0, N1 #= N - 1, F #= N * F1, n_factorial(N1, F1).

?- n_factorial(X, 3628800).
X = 10 .

とにかく、これは元の問題に対する単純な解決策です。これは、試みたものと似ていますが、アキュムレータを使用して結果を計算します。この単純なトリックにより、末尾再帰プロシージャを記述できるようになり、効率が向上します。

sigma(Num, Result) :-
    sigma(1, Num, 0, Result).

sigma(N, M, Acc, Tot) :-
    (   N < M, !,
        (   (0 is N mod 3 ; 0 is N mod 5)
        ->  Sum is Acc + N
        ;   Sum is Acc
        ),
        N1 is N + 1,
        sigma(N1, M, Sum, Tot)
    ;   Tot is Acc
    ).

テスト：

?- sigma(1000, X).
X = 233168 .
于 2012-02-08T08:20:13.797 に答える
1 
mod3 is A mod 3,

(mod3 の他のすべての出現と同様に) Mod3 は変数であるため、Mod3 である必要があります。その修正により、プログラムは正しく実行されます (少なくとも N=1000 の場合)

ところで、ここに私の解決策があります（高次の述語を使用）：

sum(S):-
    findall(X,between(1,999,X),L),       % create a list with all numbers between 1 and 999
    include(div(3),L,L3),                % get the numbers of list L which are divisible by 3
    include(div(5),L,L5),                % get the numbers of list L which are divisible by 5
    append(L3,L5,LF),                    % merge the two lists
    list_to_set(LF,SF),                  % eliminate double elements
    sumlist(SF,S).                       % find the sum of the members of the list

div(N,M):-
    0 is M mod N.

もちろん効率は劣りますが、入力が小さすぎて顕著な違いはありません

于 2012-02-07T18:19:47.483 に答える
0

これはすべて私には非常に複雑に思えます。

sum_of( L , S ) :-
  L > 0 ,
  sum_of( 0 , L , 0 , S )
  .

sum_of( X , X , S , S ) .    % if we hit the upper bound, we're done.
sum_of( X , L , T , S ) :-   % if not, look at it.
  X < L ,                    % - backtracking once we succeeded.
  add_mult35( X , T , T1 ) , % - add any multiple of 3 or 5 to the accumulator
  X1 is X + 1 ,              % - next X
  sum_of( X1 , L , T1 , S )  % - recurse
  . 

add_mult35( X , T , T ) :-  % no-op if X is
  X mod 3 =\= 0 ,           % - not a multiple of 3, and
  X mod 5 =\= 0 ,           % - not a multiple of 5
  !.                        %
add_mult35( X , T , T1 ) :- % otherwise,
  T1 is T + X               % increment the accumulator by X
  .

これは、実際よりもさらに簡潔になる可能性があります。

私のコードはおそらく非常に恐ろしいものです (実際には私の C ソリューションよりも長く、それ自体はかなりの偉業です)。

ANSI C:

int sum_multiples_of_three_and_five( int lower_bound , int upper_bound )
{
  int sum = 0 ;

  for ( int i = lower_bound ; i <= upper_bound ; ++i )
  {
    if ( 0 == i % 3 || 0 == i % 5 )
    {
      sum += i ;
    }
  }

  return sum ;
}
于 2012-02-08T18:27:58.550 に答える