subject

The greatest common divisor (GCD) of two integers a and b is defined as the largest integer that can divide both a and b without a remainder. For example, the GCD of 30 and 54 is 6, whereas the GCD of 7 and 5 is 1. The following procedure was developed by Euclid to compute the greatest common divisor of two positive integers a and b. In this exercise, we will prove the correctness of this algorithm. procedure Euclidean(a, b) 1 x ← a 2 y ← b 3 while x 6= y do 4 if x > y then 5 x ← x − y 6 else 7 y ← y − x 8 return x (a) State the loop invariant for the while loop in this procedure.
(b) Prove the loop invariant.
(c) Prove that procedure Euclidean always terminates provided that a and b are positive integers.
(d) Using the termination property of your loop invariant, prove that procedure Euclidean computes and returns the greatest common divisor of a and b.

ansver
Answers: 3

Another question on Computers and Technology

question
Computers and Technology, 21.06.2019 23:00
The animal classthis class represents a an animal residing at a zoo. it has a weight (in pounds),height (in inches), a name, and a color. the methods in the class include constructors,getters, and a tostring. you will finish the implementation of these methods. referto the code documentation.1.getters: you will need to implement getter methods. these get a value (froma member variable) in the animal class. you will make a getter method toreturn each variable (weight, height, name, color). reference getname if youare having issues.2.tostring: you will need to finish the tostring method. this returns a stringcontaining information about an animal. the output string should be of theformat: ” (name) , a ( color )â’colored animal . ( weight ) pounds , ( height ) inches .\n”the height and weight are formatted to 1 decimal place. recall from lab 1how to format strings neatly using string. see the reference sectionfor more about string.format.
Answers: 2
question
Computers and Technology, 22.06.2019 11:00
Technician a says that the radiator usually cools better if the front air dam is removed. technician b says that when a condenser has a leak it can be repaired easily with epoxy. who is correct?
Answers: 1
question
Computers and Technology, 22.06.2019 12:40
In a response of approximately 50 words, explain why it would be essential for the successful a/v technician to participate in additional coursework, presentations and seminars offered by equipment manufacturers as well as annual conferences attended by colleagues in the industry.
Answers: 1
question
Computers and Technology, 22.06.2019 13:30
1. technician a says horsepower information can be used by consumers to compare the power of different automobile engines. technician b says that manufacturers will often list the horsepower output of their engines in the online service information. who is right?
Answers: 2
You know the right answer?
The greatest common divisor (GCD) of two integers a and b is defined as the largest integer that can...
Questions
question
History, 01.12.2020 23:30
question
History, 01.12.2020 23:30
Questions on the website: 13722362