1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
MariettaO [177]
2 years ago
11

5. The recursive algorithm given below can be used to compute gcd(a, b) where a and b are non-negative integer, not both zero.

Mathematics
1 answer:
s2008m [1.1K]2 years ago
6 0

Implementating the given algorithm in python 3, the greatest common divisors of <em>(</em><em>124</em><em> </em><em>and</em><em> </em><em>244</em><em>)</em><em> </em>and <em>(</em><em>4424</em><em> </em><em>and</em><em> </em><em>2111</em><em>)</em><em> </em>are 4 and 1 respectively.

The program implementation is given below and the output of the sample run is attached.

def gcd(a, b):

<em>#initialize</em><em> </em><em>a</em><em> </em><em>function</em><em> </em><em>named</em><em> </em><em>gcd</em><em> </em><em>which</em><em> </em><em>takes</em><em> </em><em>in</em><em> </em><em>two</em><em> </em><em>parameters</em><em> </em>

if a>b:

<em>#checks</em><em> </em><em>if</em><em> </em><em>a</em><em> </em><em>is</em><em> </em><em>greater</em><em> </em><em>than</em><em> </em><em>b</em>

return gcd (b, a)

<em>#if</em><em> </em><em>true</em><em> </em><em>interchange</em><em> </em><em>the</em><em> </em><em>Parameters</em><em> </em><em>and</em><em> </em><em>Recall</em><em> </em><em>the</em><em> </em><em>function</em><em> </em>

elif a == 0:

return b

elif a == 1:

return 1

elif((a%2 == 0)and(b%2==0)):

<em>#even</em><em> </em><em>numbers</em><em> </em><em>leave</em><em> </em><em>no</em><em> </em><em>remainder</em><em> </em><em>when</em><em> </em><em>divided</em><em> </em><em>by</em><em> </em><em>2</em><em>,</em><em> </em><em>checks</em><em> </em><em>if</em><em> </em><em>a</em><em> </em><em>and</em><em> </em><em>b</em><em> </em><em>are</em><em> </em><em>even</em><em> </em>

return 2 * gcd(a/2, b/2)

elif((a%2 !=0) and (b%2==0)):

<em>#checks</em><em> </em><em>if</em><em> </em><em>a</em><em> </em><em>is</em><em> </em><em>odd</em><em> </em><em>and</em><em> </em><em>B</em><em> </em><em>is</em><em> </em><em>even</em><em> </em>

return gcd(a, b/2)

else :

return gcd(a, b-a)

<em>#since</em><em> </em><em>it's</em><em> </em><em>a</em><em> </em><em>recursive</em><em> </em><em>function</em><em>,</em><em> </em><em>it</em><em> </em><em>recalls</em><em> </em><em>the function</em><em> </em><em>with </em><em>new</em><em> </em><em>parameters</em><em> </em><em>until</em><em> </em><em>a</em><em> </em><em>certain</em><em> </em><em>condition</em><em> </em><em>is</em><em> </em><em>satisfied</em><em> </em>

print(gcd(124, 244))

print()

<em>#leaves</em><em> </em><em>a</em><em> </em><em>space</em><em> </em><em>after</em><em> </em><em>the</em><em> </em><em>first</em><em> </em><em>output</em><em> </em>

print(gcd(4424, 2111))

Learn more :brainly.com/question/25506437

You might be interested in
Teresa bought 16 roses for $20.64. How much did she pay for each rose
jeka94
Roses: 16
Total Cost: $20.64

Divide:
$20.64 ÷ 16
=  $1.29

Each Rose cost $1.29

Hope This Helped! :3
6 0
3 years ago
Read 2 more answers
Find values of a and b that make the statement |a+b|= |a|+|b| false.
jok3333 [9.3K]

The values that make this statement falser are any in which a and b do not have the same sign.

For instance, if a was equal to 3 and b was equal to -3 than see the results.

|a+b|=

|3+-3|=

|0|= 0

Then see the next equation with the same selections

|a|+|b|

|3|+|-3|

3 + 3 = 6

And this would be true no matter which is the negative, as long as there is one negative and one positive.

3 0
3 years ago
An item is priced at $13.13. If the sales tax is 5%, what does the item cost including sales tax?
V125BC [204]

Answer:

$13.79

Step-by-step explanation:

13.13x0.05=0.6565

Tax=0.66

13.13+0.66=13.79

8 0
2 years ago
List the 3-membered subsets of the set {1,2,3,4,5,6).
Alexxandr [17]
Look at the attachment. Hope it helps!

8 0
3 years ago
Whoever needed help with this MATH question I got it for you...<br> Answer: F(x)= 4,800(1.5)^X
Ganezh [65]

Answer:

1+2=3

Step-by-step explanation:

8 0
2 years ago
Read 2 more answers
Other questions:
  • What is the answer for -7 +4
    6·1 answer
  • TOO Roberto<br> 05.03 MC)What is the area, in square units, of the polygon shown here?
    15·1 answer
  • Which of the following best describes the equation below?
    10·2 answers
  • Dan invests £11000 into his bank account.
    13·1 answer
  • Hi, this is for a poll
    8·1 answer
  • Find the inverse of the function f(x) = 4x-1
    14·2 answers
  • Number square adding up to middle number<br>​
    8·1 answer
  • The product of two integers is -8. What are the two<br>integers?​
    9·1 answer
  • Find the unknown sides and angles of this triangle using the Law of Cosines.
    8·1 answer
  • Answer choices are 9,-9,4,-4 for both spots PLEASE HELP FAST!!!
    14·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!