NWD_c.pdf

Przykþad

Napiszprogramdoznajdowanianajwiększego

wspólnegodzielnikadwóchliczbnaturalnych

wykorzystujący rekurencyjny algorytm

Euklidesa.

210

/* program do wyznaczania najwiekszego wspolnego

podzielnika dwoch liczb naturalnych */

# include <stdio.h>

int NWD ( int , int );

int main ( void )

{

int w,x,y;

printf ("Program do wyznaczania najwiekszego dzielnika

dwoch liczb naturalnych\n\n");

printf ("Wpisz dwie liczby naturalne ");

scanf ("%d %d", &x, &y);

w = NWD (x,y);

printf ("Najwiekszyn dzielnikiem liczb %d i %d jest %d\n",

x,y,w);

return 0;

211

}

int NWD ( int x, int y) //najwiekszy wspolny dzielnik

{

int r, z;

r = x % y; // x / y = c*y + r

// {F: x>0 and y>0}

if (r == 0) z = y; else z = NWD (y,r);

// {G: z = NWD(x,y)}

return z;

}

212