# CMU 15-112 Spring 2016 Quiz 2 Practice (Due never)

• Edit how you wish (add imports, helper functions, etc), except:
• Do not use strings, lists, or recursion this week.
• Do not edit the test code.
• Do not hardcode the test cases in your solutions.
• Quiz2 will include a subset of the problems here.

1. Code Tracing
Quiz2 code tracing will be nearly identical to these. Practice these using slightly different constants each time.
# Code Tracing #1 of 2 def ct1(n): for i in range(n): for j in range(n): if ((j <= i) and ((i + j) % 2 == 0)): print("o", end="") elif ((i + j) % 3 == 0): print("x", end="") else: print(".", end="") print() ct1(5)

# Code Tracing #2 of 2 def ct2(n): result = 0 x = 0 y = 1 while (n > 0): temp = x x += y y = temp result = 10*result + (x%10) n -= 1 return result print(ct2(5))

2. digitCount(n)
Write the function digitCount that takes a possibly-negative int and returns the number of digits in it. So, digitCount(12323) returns 5, digitCount(0) returns 1, and digitCount(-111) returns 3. One way you could do this would be to return len(str(abs(n))), but you cannot do that, since you may not use strings here! This can be solved with logarithms, but seeing as this is "loops week", you should instead simply repeatedly remove the ones digit until you cannot.
def digitCount(n): return 42 # replace with your solution def testDigitCount(): print("Testing digitCount()...", end="") assert(digitCount(3) == 1) assert(digitCount(33) == 2) assert(digitCount(3030) == 4) assert(digitCount(-3030) == 4) assert(digitCount(0) == 1) print("Passed!") testDigitCount()

3. hasConsecutiveDigits(n)
Write the function hasConsecutiveDigits(n) that takes a possibly- negative int value n and returns True if that number contains two consecutive digits that are the same, and False otherwise.
def hasConsecutiveDigits(n): return 42 # replace with your solution def testHasConsecutiveDigits(): print("Testing hasConsecutiveDigits()...", end="") assert(hasConsecutiveDigits(0) == False) assert(hasConsecutiveDigits(123456789) == False) assert(hasConsecutiveDigits(1212) == False) assert(hasConsecutiveDigits(1212111212) == True) assert(hasConsecutiveDigits(33) == True) assert(hasConsecutiveDigits(-1212111212) == True) print("Passed!") testHasConsecutiveDigits()

4. nthPerfectNumber(n)
Write the function nthPerfectNumber that takes a non-negative integer n and returns the nth perfect number, starting at n=0, where a number is perfect if it is the sum of its positive divisors less than itself. For example, 6 is perfect because 6 = 1 + 2 + 3. Also, 28 is perfect because 28 = 1 + 2 + 4 + 7 + 14. The next one is 496, then 8128.
def nthPerfectNumber(n): return 42 # replace with your solution def testNthPerfectNumber(): print("Testing nthPerfectNumber()...", end="") assert(nthPerfectNumber(0) == 6) assert(nthPerfectNumber(1) == 28) # assert(nthPerfectNumber(2) == 496) # this can be slow in Brython # assert(nthPerfectNumber(3) == 8128) # this can be slow even in Standard Python! print("Passed!") testNthPerfectNumber()

5. gcd(m, n)
[Note: to receive any credit, you must solve this problem using Euclid's algorithm, and by no other means. In particular, do not just loop through all integers less than min(m,n) and find the common factors that way -- it is much too slow!]
According to Euclid, the greatest common divisor, or gcd, can be found like so:
gcd(x,y) == gcd(y, x%y)
We can use that to quickly find gcd's. For example:
gcd(270,250) == gcd(250, 20) # 270 % 250 == 20
== gcd(20, 10) # 250 % 20 == 10
== gcd(10, 0) # 20 % 10 == 0

When we get to gcd(x,0), the answer is x. So gcd(270, 250) is 10. With this in mind, write the function gcd(x,y) that takes two positive integers x and y and returns their gcd using Euclid's gcd algorithm.
def gcd(x, y): return 42 # replace with your solution def testGcd(): print("Testing gcd()...", end="") assert(gcd(3, 3) == 3) assert(gcd(3**6, 3**6) == 3**6) assert(gcd(3**6, 2**6) == 1) x = 1568160 # 2**5 * 3**4 * 5**1 * 11**2 y = 3143448 # 2**3 * 3**6 * 7**2 * 11**1 g = 7128 # 2**3 * 3**4 * 11**1 assert(gcd(x, y) == g) print("Passed!") testGcd()

6. cosineError(x, k)
Background: As explained here, we can use a Taylor Series to approximate cos(x), with x in radians, as:
cos(x) = 1 - x**2/2! + x**4/4! - x**6/6! + ...
With this in mind, write the function cosineError(x, k) that takes a float x (a value in radians) and a non-negative int k, and first computes the value of the series above including the first k terms (counting from 0), and then returns the absolute value of the difference between that and math.cos(x), which is a measure of the error after that many terms. Since we start at 0, cosineError(x, 0) should return |cos(x) - 1|. Note how the error quickly converges towards 0, especially for small x. Also, note that you may wish to use the math.factorial function.
def cosineError(x, k): return 42 # replace with your solution def almostEqual(d1, d2): epsilon = 10**-8 return abs(d1 - d2) < epsilon def testCosineError(): print("Testing cosineError()...", end="") assert(almostEqual(cosineError(0, 0), abs(math.cos(0) - 1))) assert(almostEqual(cosineError(1, 0), abs(math.cos(1) - 1))) x = 1.2 guess = 1 - x**2/2 + x**4/(4*3*2) error = abs(math.cos(x) - guess) assert(almostEqual(cosineError(x, 2), error)) x = 0.75 guess = 1 - x**2/2 + x**4/(4*3*2) - x**6/(6*5*4*3*2) error = abs(math.cos(x) - guess) assert(almostEqual(cosineError(x, 3), error)) print("Passed!") testCosineError()