Question

Algorytm B Dla danych dodatnich liczb całkowitych u i v algorytm ten znajduje największy wspólny dzielnik.

B1 Przyjmij k <-- 0, a następnie powtarzaj operacje: k <-- k + 1, u <-- u/2, v <-- v/2 zero lub więcej razy do chwili gdy przynajmniej jedna z liczb u i v przestanie być parzysta

B2 Jeśli u jest nieparzyste to przyjmij t <-- -v i przejdź do kroku B4. w przeciwnym razie przyjmij t <-- u.

B3 (W tym miejscu t jest parzyste i różne od zera). Przyjmij t <-- t/2.

B4 Jeśli t jest parzyste to przejdź do B3.

B5 Jeśli t > 0, to przyjmij u <-- t, w przeciwnym razie przyjmij v <-- -t,

B6 Przyjmij t <-- u-v. Jeśli t ≠ 0to wróć do kroku B3. W przeciwnym razie algorytm zatrzymuje się z wynikiem u * 2^k.

Należy wykonać powyższy algorytm dla u = 455 i v = 712 dokumentując każdy krok

Answer 1

B1:

k=0

u=455

v=712

Jedna z liczb jest nieparzysta, więc nie powtarzamy, przechodzimy do punktu B2

 

B2:

u jest nieparzyste stąd

t=-712

przechodzimy do B4

 

B4:

t jest parzyste więc przechodzimy do B3

 

B3:

t=-712/2=-356

 

B4;

t jest nadal parzyste więc przechodzimy do B3

 

B3:

t=-356/2=-178

 

B4;

t jest nadal parzyste więc przechodzimy do B3

 

B3:

t=-178/2=-89

 

B4:

t jest nieparzyste, a więc w końcu przechodzimy do B5

 

B5:

t jest ujemne, więc

v=89

B6:

t=u-v=455-89=366

i wracamy z powrotem do B3:

 

B3:

t=366/2=183

 

B4:

t jest nieparzyste więc

 

B5:

u=183 (ponieważ t>0)

 

B6:

t=u-v=183-89=94

wracamy do B3

 

B3:

t=94/2=47

 

B4:

t jest nieparzyste

 

B5:

u=47 (ponieważ t>0)

 

B6:

t=47-89=-42

wracamy do B3

 

B3:

t=-42/2=-21

 

B4:

t jest nieparzyste

 

B5:

v=21 ( t jest <0)

 

B6:

t=47-21=26

wracamy do B3

 

B3:

t=26/2=13

 

B4:

t jest nieparzyste

 

B5:

u=13 (t>o)

 

B6:

t=13-21=-8

wracamy do B3

 

B3:

t=-8/2=-4

 

B4:

wracamy do B3

 

B3:

t=-4/2=-2

 

B4:

wracamy do B3

 

B3:

t=-2/2=-1

 

B4:

t jest nieparzyste

 

B5:

v=1 (t<0)

 

B6:

t=13-1=12

wracamy do B3

 

B3:

t=12/2=6

 

B4:

wracamy do B3

 

B3:

t=6/2=3

 

B4:

t jest nieparzyste

 

B5:

u=3 (t>0)

 

B6:

t=3-1=2

wracamy do B3

 

B3:

t=2/2=1 (uff w końcu)

 

B4:

t jest nieparzyste

 

B5:

u=1 (t>0)

 

B6:

t=1-1=0

 

 

Odp. Najwiekszym wspólnym dzielnikiem liczb 455 i 712 jest 1 ;).

Co się zgadza ponieważ:

455=5*7*13

712=2*2*89

Czyli liczby są względnie pierwszymi.