Делители натурального числа

В этой теме 1 ответ, 2 участника, последнее обновление  Васильев Владимир Сергеевич 2 года/лет, 8 мес. назад.

  • Автор
    Сообщения
  • #1977

    questioner
    Участник

    Помогите решить две задачи на Prolog:

    • Указать все делители натурального числа n.
    • Найти сумму делителей данного натурального числа.
  • #1979

    Делители будут выводиться на экран, поэтому разумно будет передавать нашей функции лишь число, для которого нужно посчитать делители. Однако, на каждом шаге функция должна увеличивать счетчик и пытаться вычислить остаток от деления на него, поэтому основная функция будет вызывать вспомогательную, передавая единицу в качестве начального значения счетчика:

    all_factors(Number):-
      all_factors(Number, 1).

    Вспомогательная функция:

    • завершает работу если счетчик больше числа:
    • выводит счетчик на экран если число делится на него без остатка (остаток получается встроенным оператором mod);
    • увеличивает счетчик и обрабатывает новое значение рекурсивно

    all_factors(Number, Factor):-
     Factor > Number, !.
    all_factors(Number, Factor):-
     0 is Number mod Factor,
     write(Factor), nl, 
     fail.
    all_factors(Number, Factor):-
     NextFactor is Factor + 1,
     all_factors(Number, NextFactor).

    В приведенном примере правило, обрабатывающее удачно найденный делитель завершается неудачей, в результате управление будет передано на следующее правило. Такой трюк позволяет не дублировать код увеличения счетчика и рекурсивного вызова и возможен лишь потому, что результат выполнения не нужен (он выводится на экран, что является побочным эффектом, side effect). Мы не сможем использовать такой трюк при вычислении суммы делителей.

    sum_factors(Number, Sum):-
     sum_factors(Number, 1, Sum).
    
    sum_factors(Number, Factor, 0):-
     Factor > Number, !.
    sum_factors(Number, Factor, Sum):-
     0 is Number mod Factor, !,
     NextFactor is Factor + 1, sum_factors(Number, NextFactor, NextSum),
     Sum is NextSum + Factor.
    sum_factors(Number, Factor, Sum):-
     NextFactor is Factor + 1, sum_factors(Number, NextFactor, Sum).

    Если счетчик стал больше числа, значит дальше искать делители смысла нет, функция возвращает ноль в качестве суммы. В противном случае счетчик увеличивается и обрабатывается рекурсивно, при этом к результату может быть добавлено старое значение счетчика если число делится на него нацело.

Для ответа в этой теме необходимо авторизоваться.