Java Reference
In-Depth Information
Program 2.4
Euclid's Greatest Common Divisor (GCD)
class
GCD
{
public static void
main( String [ ]
arg )
int
a;
int
b;
while
(a!=b)
if
(a
>
b) a=a
−
b;
else
b=b
−
a;
}
System . out . println (a) ;
// or b since a=b
}
}
Running this program for
a
=30and
b
= 105 yields GCD(
a, b
) = 15.
Euclid's algorithm has a nice
geometric
interpretation: Consider an initial
rectangle of width
a
and height
b
. Bisect this rectangle as follows: Choose
the smallest side, and remove a square of that side from the current rectangle.
Repeat this process until we get a square: The side length of that square is the
GCD of the initial numbers. Figure 2.2 depicts this “squaring” process.
Figure 2.2
Age-
ometric interpretation
of Euclid's algorithm.
Here, illustrated for
a
=65and
b
=25
(GCD(
a, b
)=5)
2.4.2 Loop statement:
do-while
Java provides another slightly different syntax for making iterations: the
do
loop statement. The difference with a
while
statement is that we execute at
least once the sequence of instructions in a
do
statement, whereas this might not
be the case of a
while
statement, depending on the evaluation of the boolean
predicate. The syntax of a
do
structure is as follows:
Search WWH ::
Custom Search