0

Hi, I'm studying for a final exam and I just wanted to ask if you could be so kind to explain how you get these answers from these questions. I'm really confused on them. Thanks!

1) What is the output of the following program?
def f(x, y):
    if y == 0: 
return x
    else: 
return f(y, x%y)
print(f(240, 150))

Answer: 30

2) What is the output of the following program?
num = 0
for i in range(0,10,1):
    if (i%2 == i%3):
        num = num + 1
print(num)

Answer: 4
5
Contributors
4
Replies
7
Views
4 Years
Discussion Span
Last Post by Xantipius
0

The first one is not properly indented, does not run.
The question was: How we get the answers.
Solution 1: You run the code, look at the output.
Solution 2: You run the code with paper and pencil, and look at the result.

The second one:
We take the numbers from 0 to 9. If a number gives the same reminder divided by 2 and 3 then we increase a counter. The result is the counter.

The first one:
This is a recursive function, because the function is called inside the function.
You can evaluate it, by enumerate the inputs.
0: 240,150
1: 150,90
2: 90,60
3: 60,30
4: 30:0
5: print 30
Try this with other numbers.

If you look at the code, you can see that the equations are:
a = q0 b + r0
b = q1 r0 + r1
r0 = q2 r1 + r2
r1 = q3 r2 + r3
where r(i)= r(i-1)%r(i-2) and r(-1)=b and r(-2)=a
The last equation is:
r(n)=q(n+2)r(n-1)+0
So the result is r(n-1). If you are smart, you can proove that the last not null remainder -the result- divides a and b, and if something divides a and b, then the result is divided by it.

It is called the euclidean algorithm, look up at the wikipedia.

Edited by slate

0

Slate is right, a little test print within the function allows you to follow what is going on:

def f(x, y):
    print(x, y)  # test print to check progress
    if y == 0:
        return x
    else:
        return f(y, x%y)

print(f(240, 150))

Or:

num = 0
for i in range(0,10,1):
    if (i%2 == i%3):
        num = num + 1
    print(i%2, i%3, num)  # test print to check progress

print(num)

Later you can comment out the test print when done.

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.