Биномиальный коэффициент [Пролог]

Question

bc(0,N,R,R):- N>0,R is 1,!.
bc(M,0,R,R):- M>0,R is 1,!.
bc(N,N,R,R):- R is 1,!.
bc(M,N,R,R1):- 
    M1 is M - 1, 
    N1 is N - 1, 
    bc(M1,N1,R,R2),
    bc(M1,N,R,R3),
    R1 is R2+R3.

Почему он возвращает ложь?

Задача: написать рекурсивную процедуру C(M,N) (0 ≤ m ≤ n ) чтобы узнать биномиальный коэффициент по этой формуле:

C(m,0)=C(0,n)=C(n,n)=1
C(m,n)=C(m−1,n−1)+C(m−1,n)

PS: я пользуюсь онлайн-компилятором SWISH.

Answer 1

Во-первых, давайте получим формулу для биномиальных коэффициентов, сформулированных правильно. Общепринятое определение c(M, N) будет иметь M >= N >= 0не N >= M >= 0 как указано. Это важно, потому что формула дана:

C(m,0)=C(0,n)=C(n,n)=1 C(m,n)=C(m−1,n−1)+C(m−1,n)

предполагает, что 0 ≤ n ≤ mне то что было сказано (0 ≤ m ≤ n). Так что это неверно (либо оно было дано неправильно, либо вы, возможно, записали его неправильно). Также, C(0, n) не является действительным коэффициентом, если n = 0, Так что этот случай не имеет смысла и может быть опущен. Это уже покрыто C(m, 0),

Неправильная формулировка проблемы может быть основной причиной, по которой вы получаете "ложные" результаты.

C(n, 0) = C(n, n) = 1 будет охватываться следующими базовыми (не рекурсивными) случаями:

bc(N, 0, 1) :- N #>= 0.
bc(N, N, 1) :- N #> 0.    % The N = 0 case is already covered in the first base case

Тогда более общий случай будет обрабатываться рекурсивно по заданной формуле:

bc(M, N, R) :-
    N #> 0,        % The N = 0 case is already covered in the first base case
    M #> N,        % The M = N case is already covered in the second base case
    R #>= M,       % This constraint prevents unbounded search in non-solution space
    M1 #= M - 1,   % The rest of this is just the given formula
    N1 #= N - 1,
    bc(M1, N1, R1),
    bc(M1, N, R2),
    R #= R1 + R2.

Несколько принципов при написании предикатов Пролога:

• Убедитесь, что ваша проблема сформулирована точно и правильно. Это звучит очевидно, но в данном случае это была проблема.

• Используйте CLP(FD) для рассуждений с целыми числами. Это более реляционный, чем является то, о чем Пролог. С помощью is/2 является более необходимым. Например, X is Y * 2 сгенерирует ошибку инстанции, если Y не связан. Но X #= Y * 2 будет генерировать потенциальные решения. Если вы должны использовать is/2 из-за произвольного требования, вы можете заменить его обратно в.

• Примените ограничения в своих предложениях предикатов, которые делают их взаимоисключающими. То есть, если это не то, чего вы хотите, не позволяйте вашему предикату успешно выполнять более одного способа для данного решения. В частности, сделайте ваши различные пункты не перекрывающимися. Например, если у вас есть предикат, где первый аргумент является натуральным числом (неотрицательное целое число), и у вас есть базовый случай foo(0, 1).тогда в вашем рекурсивном случае foo(N, R) :- Вы хотели бы ограничение N > 0 или же N #> 0при условии, что в рекурсивном случае нет других побочных эффектов или других аргументов, которые могут понадобиться и / или измениться.

• Чем больше вы можете ограничить или связать переменные в пространстве решения, которое вы хотите, тем меньше ваш код будет отклоняться от попыток опций, которые не являются допустимыми решениями, и, в худшем случае, не завершаться из-за отсутствия привязки к таким опциям, не относящимся к решению., Например, в этой задаче мы добавили ограничение R #>= M что верно, когда N > 0 а также N < M, Без этого ограничения Пролог будет исследовать случаи, когда R < M которые безграничны и приводят к не прекращению в некоторых случаях.

Выполнение запроса:

| ?- bc(3,2,R).

R = 3 ? ;

no
| ?- bc(4,2,R).

R = 6 ? ;

no
| ?-

Так далее...

Используя операторы CLP(FD), вы также можете запускать такие запросы:

| ?- bc(4,X,6).

X = 2 ? ;

no
| ?-

А также...

| ?- bc(N, K, 6).

N = 6
K = 1 ? ;

N = 4
K = 2 ? ;

N = 6
K = 5 ? ;

no
| ?- ;