C++ : Algorithm and Program Interatif and Recursive Function forCalculating the GCD of 2 Bilanga Round Positive

download

ANALYSIS
If n is not equal to 0 and m non-negative integers, we can write m =qn + r for a non-negative integers q and r with 0 less the same withsmaller r n

For example:
if n = 3, m = 16 then 16 = 5 (3) + 1, ie q = 5 and r = 1
if n = 10, m = 3 then 3 = 0 (10) + 3, ie q = 0 and r = 3

To find the GCD of two integers, we can use the way of writing theabove. Suppose we want to find the GCD (190, 34)
34 | 190 -> 190 = 5 (34) + 20, r = 20
20 | 34 -> 34 = 1 (20) + 14, r = 14
14 | 20 -> 20 = 1 (14) + 6, r = 6
6 | 14 -> 14 = 2 (6) + 2, r = 2
2 | 6 -> 6 = 3 (2) + 0, r = o stop!

Harge r is not equal to 0 last in reach is r = 2. This is the result darGCD (190.34). Vesi recursive GCD is defined as follows:
gcd (c, d) = c, if d = 0
= gcd (c-d, d), if d> 0 and c> d
Commutative law applies, gcd (c, d) = gcd (d, c)

ALGORITHM
function gcd (c, d: integer): integer

VERSION INTERATIF
DSKRIPSI
while (d> 0) do
r <- c mod dc <- d {save the price of the last r}d <- r {r final price to stop the loop}endwhilegcd <- cRECURSIVE VERSIONDESCRIPTIONif (d = 0) then gcd <- celse if (c < d ) tehen gcd <- gcd (d, c)else gcd <- gcd (c-d, d)download

Posted in: Pemrograman C++