-
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))
-
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()
-
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()
-
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()
-
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()
-
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()