say_hi
, which takes no arguments and prints the stringHello, world!
when called.
def say_hi():
print('Hello, world!')
goat_pad
, which takes a string as its only argument, and prints that string, prepended and appended with the string goat
. So, goat_pad('bird')
should produce the outputdef goat_pad(s):
print('goat' + s + 'goat')
print_n
, which takes two arguments, a string s
and an integer n
(in that order), and prints the string n
times, each on a separate line. You may assume that s
is a string and that the integer n
is non-negative.def print_n(s, n):
for _ in range(n):
print(s)
Euclid's algorithm (https://en.wikipedia.org/wiki/Euclidean_algorithm) is a method for finding the greatest common divisor (GCD) of two numbers. Recall that the GCD of two numbers m and n is the largest number that divides both m and n.
gcd
, which takes two integers as its arguments and returns their GCD. You may assume that both inputs are integers, so there is no need to include any error checking in your function.def gcd(a, b):
while b != 0:
t = b
b = a % b
a = t
return(a)
A = gcd(2018, 2019)
B = gcd(1200, 300)
C = gcd(5040, 60)
A, B, C
(1, 300, 60)
# Testing gcd(a, b) with numbers different signs
gcd(8, -12), gcd(-8, 12), gcd(-8, -12)
(-4, 4, -4)
return(abs(a))
to avoid the output from being negative.The base of the natural logarithm, $e$, is typically defined as the infinite sum
def euler_limit(n):
approx_E = (1 + 1/n) ** n
return(approx_E)
euler_infinite_sum
that takes a single non-negative integer argument $n$, and returns an approximation to $e$ based on the first $n$ terms of the sum in Equation (1). Your function should return a float. You may assume that the input will be a non-negative integer, so you do not need to include error checking in your function. As an example, euler_infinite_sum(4)
should return the sum of the first four terms in Equation 1, so that ~euler_infinite_sum(4)~ returns $1+1+\frac{1}{2}+\frac{1}{6}\approx2.667$.def euler_infinite_sum(n):
# Initials
approxSum = 0 # keeps track of the running sum
factorialTerm = 1 # keeps track of the product of integers for the factorial term
# Looping through each term in the sum of e
for i in range(n):
if i == 0:
approxSum += 1
else:
factorialTerm *= i
approxSum += (1 / factorialTerm)
return(approxSum)
euler_infinite_sum(0)
0
euler_approx
that takes a single argument, a float epsilon
, and uses the sum in (1) to obtain an approximation of $e$ that is within epsilon
of the true value of $e$.def euler_approx(epsilon):
# Returns: a tuple with the approximate value of e within epsilon, and the number of terms
# needed to achieve this estimate i.e. (approx, n).
# Initials
factorialTerm = 1 # keeps track of the product of integers for the factorial term
absError = 1 # keeps track of the error bound
# The first if statement guards against values of epsilon larger than 1
if absError < epsilon:
return(absError, 0)
# Here we use the fact that the error bound is given by the next term in the taylor polynomial,
# which we check inside of the while loop
else:
i = 1
while( absError >= epsilon ):
factorialTerm *= i
absError = 1 / factorialTerm
i += 1
return(euler_infinite_sum(i - 1), (i - 1))
euler_approx(0.0001)
(2.7182539682539684, 8)
import math
# Alternate Solution
def euler_approx(epsilon):
# Returns: a tuple with the approximate value of e within epsilon, and the number of terms
# needed to achieve this estimate i.e. (approx, n).
# Initials
factorialTerm = 1 # keeps track of the product of integers for the factorial term
absError = math.e
i = 0
while(absError > epsilon):
if i != 0:
factorialTerm *= i
absError -= 1 / factorialTerm
i += 1
return(euler_infinite_sum(i), i)
euler_approx(0.0000000000000000000000000000000000000000000001)
(2.7182818284590455, 19)
print_euler_sum_table
that takes a single positive integer $n$ as an argument and prints the successive values obtained from euler_infinite_sum(k)
as $k$ ranges from $1$ to $n$, one per line.def print_euler_sum_table(n):
# Initials
approxSum = 0 # keeps track of the running sum
factorialTerm = 1 # keeps track of the product of integers for the factorial term
# Looping through each term in the sum of e
for i in range(n):
if i == 0:
approxSum += 1
print(approxSum)
else:
factorialTerm *= i
approxSum += (1 / factorialTerm)
print(approxSum)
euler_infinite_sum
is the better approximation. For a more concrete proof, see below.Using the binomial formula, \begin{align*} \left(1+\frac{1}{n}\right)^{n}= & \sum_{k=0}^{n}\binom{n}{k}\left(\frac{1}{n}\right)^{k}\\ = & \sum_{k=0}^{n}\left(\frac{n(n-1)\cdots(n-k+1)}{k!}\right)\left(\frac{1}{n}\right)^{k}\\ = & \sum_{k=0}^{n}\left(\frac{1}{k!}\right)\left(1-\frac{1}{n}\right)\left(1-\frac{2}{n}\right)\cdots\left(1-\frac{k-1}{n}\right)\\ < & \sum_{k=0}^{n}\left(\frac{1}{k!}\right) \end{align*} The last summation is the $n$-th Taylor expansion of $e$ and the strict inequality holds for any $n>1$.
In this problem, you'll get a bit more practice working with conditionals, and a first exposure to the kind of thinking that is required in a typical "coding interview" question. A positive integer $n$ is a power of $2$ if $n = 2^p$ for some integer $p \geq 0$
is_power_of_2
that takes a positive integer as its only argument and returns a Boolean indicating whether or not the input is a power of $2$. Youmay assume that the input is a positive integer. You may not use the built-in math.sqrt function in your solution. You should need only the division and modulus (%) operations. Hint: the simplest solution to this problem makes use of recursion, though recursion is not necessary.
def is_power_of_2(num):
if (num == 1):
return(True)
elif (num % 2) != 0:
return(False)
else:
return(is_power_of_2(num / 2))
is_power
that takes two positive integers as its arguments, $b$ and $n$, in that order, and returns a Boolean. is_power(b,n)
should return True if $n$ is a power of $b$ and False
otherwise.def is_power(b, n):
if (n == 1):
return(True)
elif (n % b) != 0:
return(False)
else:
return(is_power(b, n / b))