我想尝试编写一个递归谓词 divide_by(X, D, I, R),它接收一个正整数 X 和一个除数 D 作为输入,并返回商的整数部分 I 和余数部分 R,但是我不太懂 Prolog。请问应该如何实现?
这方面有预定义的可求值函数。
(div)/2
和(mod)/2
总是向下取整。被LIA-1、Knuth等推荐。
(//)/2
和(rem)/2
向零舍入(实际上,这是由实现定义的,但所有当前实现都是这样做的)。您可以通过current_prolog_flag(integer_rounding_function, F)
询问此内容,在当前实现中返回toward_zero
。
这些对之间的区别只在涉及负数时才会显示出来。这是一种宗教战争,要优先考虑哪个。ISO/IEC 10967:2012独立于语言的算术运算(vl. LIA-1)仅提供向下舍入 "由于易于出错的使用"(C.5.1.2.2),而Fortran和像C这样的支持者则采用向零舍入并将其称为"代数的"(6.5.5)。也请参见: 利用向负无穷截断与向零截断的优势
divit(Dividend, Divisor, Q, R) :-
Dividend > 0, % Only allow positive dividend
Divisor \== 0, % Don't allow 0 divisor
% Use an accumulator (starts at 0) for the quotient, counting subtractions
% of the divisor from the dividend
divit(Dividend, Divisor, 0, Q, R).
% If Dividend < Divisor, then
% quotient accumulator is quotient and dividend is remainder, done!
divit(Dividend, Divisor, Qacc, Qacc, Dividend) :-
Dividend < Divisor.
% If Dividend >= Divisor, then
% subtract the divisor from the dividend
% increment the quotient accumulator
% recurs on updated dividend and quotient accumulator until dividend < divisor
divit(Dividend , Divisor, Qacc, Q, R) :-
Dividend >= Divisor,
D1 is Dividend - Divisor,
Qacc1 is Qacc + 1,
divit(D1, Divisor, Qacc1, Q, R).
0,s(0),...
这样的东西而不是整数,但他拒绝说出来,所以我们只能猜测。 - user1812457我假设你的老师正在教授递归。
除法是重复减法,就像乘法是重复加法一样,不是吗?
一个常见的Prolog惯用语,因为变量只能赋值一次,是拥有一个外部“公共”谓词,调用一个使用累加器执行实际工作的私有“工作人员”谓词。这使我们可以得到以下解决方案。
%
% divide M (the dividend) by N (the divisor),
%yielding the quotient (Q) and remainder (R).
integer_division( M , N , Q , R ) :-
M > 0 ,
N > 0 ,
div_rem( M , N , 0 , Q , R )
.
%
% internal worker predicate for integer division
% requires dividend and divisor both to be unsigned (positive).
%
div_rem( M , N , Q , Q , M ) :- % dividend M < divisor N? We're done.
M < N , % - unify the accumulator with the quotient
. % - and unify the divisor with the remainder
div_rem( M , N ,T , Q , R ) :- % dividend M >= divisor N?
M >= N , % - increment the accumulator T
T is T+1 , % - decrement the divisor by N
M1 is M-N , % - recurse down
div_rem( M1 , N , T1 , Q , R ) % - That's all.
. % Easy!
从这里开始,修改外部公共谓词以考虑有符号操作数应该相当容易,记住:
+/+
产生+
+/-
产生-
-/+
产生-
-/-
产生+
并且,在评估M/N
以获得商Q
和余数R
之后,具有以下属性:
M = N * Q + R
这是正确的。这应该告诉您商和余数所需的符号。不要忘记,负数的加法等同于减法:M + -N
等同于 M - N
。这将使您得到数学上正确的结果(可能与通过计算机的整数除法指令获得的结果不同)。值得注意的是,为了使上述属性成立,商的符号和余数的符号可能会不同。
I is X div D
将给你整数部分,而R is X rem D
将给你余数(http://gprolog.univ-paris1.fr/manual/html_node/gprolog030.html)。我不确定为什么你想编写一个递归谓词。 - user1812457