Начинающий - добавить кратные 3 и 5 - PullRequest
Новая
       3

Начинающий - добавить кратные 3 и 5

3 голосов
/ 07 февраля 2012

Я пытаюсь найти сумму всех положительных кратных 3 и 5 ниже 1000. После добавления части, которая должна удалить кратные 3 из суммы кратных 5, 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 голосов
/ 07 февраля 2012

Поскольку задействованы целые числа, рассмотрите возможность использования ограничений конечной области .Например, с помощью 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.
2 голосов
/ 08 февраля 2012

Пролог никогда не пользовался популярностью благодаря своим арифметическим возможностям.

Это связано с необходимостью представления «конструкторов терминов» для символьной обработки без ненужной оценки, поэтому, когда требуется фактическая арифметика, мы должны явно выделить «пробел» (переменную) для результата, вместо «передачи вниз» ' выражение. Это приводит к довольно многословному и неприятному коду.

Но используя некоторые популярные расширения, такие как CLP (FD), доступные в GProlog, а также SWI-Prolog, мы получаем гораздо лучшие результаты, которых нет на других языках: а именно, закрытие целочисленной области над обычной арифметикой операции. Например, из библиотеки 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 .
1 голос
/ 07 февраля 2012 
mod3 is A mod 3,

(а также все другие вхождения 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.

это, конечно, менее эффективно, новход слишком мал, чтобы сделать заметную разницу

0 голосов
/ 08 февраля 2012

Мне все кажется очень сложным. 

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 ;
}
...