Разделение двух целых чисел альтернативным способом

Question

Давайте рассмотрим, что n=s(s(...s(0)...)) (просто n= s^n(0)). Как можно написать программу, вычисляющую деление двух целых чисел? Я имею в виду s^(n//m) (это определение деления). Есть идеи? Например, если у нас возник вопрос:

?-divide(s(s(s(s(0)))),s(0),D). 

я написал следующий код:

 nat(0).
 nat(s(X)) :- nat(X).
 divide(0,_,D) :- D is 0.
 divide(s(X),s(Y),D) :- divide(X,Y,D). 

Answer 1

Ваш предикат divide/3 ошибочно предполагает, что следующее уравнение выполняется, когда x и y являются числами: (x-1) / (y-1) = x / y
Контрпример: (16-1) / (4-1) = 5 отличается от 16/4 = 4

Кажется, вы пытаетесь основать свой предикат на хорошо известном предикате сложения:

add(0,Y,Y).
add(s(X),Y,s(Z)) :- add(X,Y,Z).

но деление является мультипликативной, а не аддитивной операцией. Возможный способ решения вашей проблемы - представить деление как повторное вычитание (так как умножение - это повторное сложение). Поскольку ваш предикат находится на натуральных числах, он должен реализовывать интегральное деление, как вы написали в вопросе.

Answer 2

s(0).
s(X):- X.

plus(0, Y, Y).
plus(s(X), Y, s(Z)):- plus(X , Y , Z).

minus(A, B, C) :- plus(C, B, A).

divide(_, 0, 0).
divide(0, _ , 0).
divide(X, s(0), X).
divide(A, B, s(N)) :- minus(A, B, R), divide(R, B, N).

Пример:

| ?- divide(s(s(s(0))), s(0), N).

N = s(s(s(0))) ?

yes
| ?- divide(s(s(s(s(0)))), s(s(0)), N).

N = s(s(0)) ?

yes

Это решение, очевидно, работает только для совершенных делений, таких как 4/2 или 6/3 и т. Д. Поскольку мы можем представлять только натуральные числа с использованием чисел Пеано.

Answer 3

Старый пост, но у меня такое же назначение. Так что ответ:

%nat:Is X natural?,nat2:Is X,Y naturals?
nat(0).
nat(s(X)) :- nat(X).
nat2(0,s(Y)) :- nat(Y).
nat2(s(X),s(Y)) :- nat2(X,Y). 

%Summary of X+Y=Z
sum(X,0,X) :- nat(X).
sum(X,s(Y),s(Z)) :- sum(X,Y,Z).

%Minus of X-Y=Z is same as Y+Z=X
minus(X,Y,Z) :- sum(Y,Z,X). 

%Multiplication of X*Y,add X+0(Z) Y times(recursive)
mult(X,0,0).
mult(X,s(Y),D):-mult(X,Y,Z), sum(X,Z,D).

%Divide,check special occasions,add to W the s(0)(1) recursive.
divide(X,Y,D) :- div(X,Y,D,_).
div(s(X),0,undefined,_).
div(0,s(Y),0,_).
div(0,0,undefined,_).
div(X,Y,0,X) :- X \== 0,Y \== 0,nat2(X,Y).
div(X,Y,D,L) :- X \== 0,Y \== 0,minus(X,Y,Z),div(Z,Y,W,L),sum(W,s(0),D).