You will write the Euclidean algorithm with a count of its divisions, the extended algorithm that finds Bezout's and , and a test for whether can be solved.
The idea. Replace the pair by , where is the remainder of on division by , until is . The extended algorithm carries two numbers along so that each remainder stays a combination of the starting pair.
Your tasks.
hcf_steps(a, b). Return the pair (hcf, number of divisions).bezout(a, b). Return (g, x, y) with a * x + b * y == g, where g is the HCF. A recursive version is short.solvable(a, b, c). Return True when has a solution in integers.Run your code once to unlock the worked solution.
Have you tried it?
Do the tasks in the editor first, and run the checker after each one. Its hints help when a check fails. When you are ready, compare your code with this solution.
Log in to join the discussion.
Loading…