Outline for October 31, 2012

Reading: None
Assignment Due: Friday, November 9, 2012 at 5:00 PM

  1. How to solve problem #2 of Homework #2
  2. Recursion
    1. n factorial [nfact.py]
    2. Fibonacci numbers [rfib .py]
    3. Sum of digits [sumdigits.py]
  3. Speed: compare iterative and recursive Fibonacci programs [timefibs.py]

Problem #2, Homework #2

Write a function gcd(m, n) that calculates the greatest common divisor of m and n. The greatest divisor of m and n is the largest positive integer k that evenly divides m and n (that is, divides both of them giving a remainder of 0). Use Euclid’s algorithm to calculate this. Here is one very succinct way to describe the algorithm (as usual in Python, m % n is the remainder of m when divided by n):

Repeatedly replace m with n, and n with m % n, until n is 0

When n is 0, the value m is the greatest common divisor of m and n. Then write a program that calls your function repeatedly, until the user enters 0 for n. Here is an example run of such a program. What the user types is in italics and the symbol “↵” means to type a return or enter. Please do not try to make the input in italics and show the return symbol in your output, of course! 

First number (0 to stop): 113↵
Second number: 293↵
The greatest common divisor of 293 and 113 is 1
First number (0 to stop): 14↵
Second number: 18↵
The greatest common divisor of 18 and 14 is 2
First number (0 to stop): -30↵
Second number: -66↵
The greatest common divisor of -66 and -30 is 6
First number (0 to stop): 7↵
Second number: 0↵
The greatest common divisor of 0 and 7 is 7
First number (0 to stop): 0↵

Please call your program “gcd.py”.

A PDF version is available here.
ECS 10, Basic Concepts of Computing
Fall Quarter 2012