Information Technology Reference
In-Depth Information
Figure 5.7.
A program for n!
factorial.pl
% factorial(N,M) holds when M=Nx(N-1)x...x2x1.
factorial(1,1).
factorial(N,M) :-N>1,N1isN-1, factorial(N1,K), M is N*K.
?- age(andy,N).
N=25
Yes
Although they are not the focus of this topic, one can also write more traditional
numerical programs in Prolog, for example, a program to compute the value of
n
!, defined as
n
×
(
−
)
×
(
−
)
×···×
×
n
1
n
2
2
1
. What is needed is a predicate
factorial
(
)
=
n
,
m
that holds when
n
!
m
. This can be written as a recursive pred-
=
×
(
−
)
icate, observing that for
n
>
1
, the factorial
n
!
n
n
1
!. The entire program for
the factorial is shown in figure 5.7.
5.3.2 Cryptarithmetic as constraint satisfaction
Let us now return to the cryptarithmetic problem. The solution to this problem uses
arithmetic expressions that deal with integers, in particular,
//
(integer quotient) and
mod
(integer remainder). For instance,
?- X is 11/3,
Y is 11//3,
Z is 11 mod 3.
X = 3.66667, Y = 3, Z = 2
Whereas
/
does full division, the
//
operation produces the integer part of a division,
and
mod
produces the remainder after an integer division. When these two operations
are used with
10
, the result is the sum and carry digits of an addition:
?- S is (2+5) mod 10,
C is (2+5) // 10,
S=7, C=0
Yes
?- S is (8+5) mod 10,
C is (8+5) // 10,
S=3, C=1
Yes
(
+
)
In the first case, the sum digit for
is
7
with a carry digit of
0
(that is, the sum
is
7
), and in the second, the sum digit for
2
5
(
+
)
8
5
is
3
with a carry digit of
1
(that is,
the sum is 13).
