Problem 5: Consider the following Euclid algorithm to compute the greatest commo
ID: 3878196 • Letter: P
Question
Problem 5: Consider the following Euclid algorithm to compute the greatest common divisor of two integers A and B: algorithm Euclid GCD; var A, B, Q, M, N: integer; begin read(A, B); if A >= B then begin M:= A; N:= B; end; else begin M:= B; N:= A; end; Q:= MIN; R:= M-N* Q; while Ro0 do begin not guay begin M:= N; N:= R; Q:= MIN; R:= M-N* Q; end; CouTwrite(“The GCD of "A," and "B," is ", N); end. 1. What are the values taken by each variable during the execution of Euclid algorithm each of the following pairs of values read in A and B? 18 and 6; 28 and 12; 15 and 25; 32 and 21. Write the correspondino C+program.Explanation / Answer
As per Chegg policy, I am answering only first 4 subparts of Question 1. In need to get answer of remaining questions please upload them again:
1.) i.) A = 18, B = 6; Since, A>=B, therefore, M = 18 and N = 6, Q = 18/6 = 3, R = 18-6*3=0.
Since R = 0, GCD of 18 and 6 is 6.
ii.) A=28, B = 12. Since, A>=B, therefore, M = 28 and N = 12, Q = 28/12 = 2, R = 28-12*2=4.
in while loop:
M = 12, N = 4, Q = 12/4 = 3; R = 12-4*3 =0.
Since R = 0, GCD of 28 and 12 is 4.
iii.) A=15, B = 25. Since, A<B, therefore, M = 25 and N = 15, Q = 25/15 = 1, R = 25-15*1=10.
in while loop:
a.) M = 15, N = 10, Q = 15/10 = 1; R = 15-10*1 =5.
b.) M = 10, N = 5, Q =10/5 = 2, R = 10 - 5*2 =0
Since R = 0, GCD of 15 and 25 is 5.
iv.) A=32, B = 21. Since, A>=B, therefore, M = 32 and N = 21, Q = 32/21 = 1, R = 32-21*1=11.
in while loop:
a.) M = 21, N = 11, Q = 21/11 = 1; R = 21-11*1 =6.
b.) M = 11, N = 6, Q =11/6 = 1, R = 11 - 6*1 =5
c.) M = 6, N = 5, Q = 6/5 = 1; R = 6-5*1 = 1
d.) M = 5, N = 1, Q = 5/1 = 5, R = 5-1*5 = 0
Since R = 0, GCD of 32 and 21 is 1.
Hope it helps, do give your valuable response.