1
Write an iterative function
iterPower(base, exp)
that calculates the exponential baseexp by
simply using successive multiplication. For example,
iterPower(base, exp)
should compute baseexp by
multiplying
base
exp
times. Write such a function below.
This function should take in two values -
base
exp
will be an integer ≥ 0.
It should return one numerical value. Your code must be iterative - use of the
**
def iterPower(base, exp):
result = base
while exp > 1:
result = result * base
exp = exp - 1
if exp == 0:
return 1
else:
return result 2
In Problem 1, we computed an exponential by iteratively executing successive multiplications. We can use the same idea, but in a recursive function.
Write a function
recurPower(base, exp)
which computes baseexp by
recursively calling itself to solve a smaller version of the same problem, and then multiplying the result by
base
to solve the initial problem.
base
exp
will be an integer ≥0.
It should return one numerical value. Your code must be recursive - use of the
**
operator or looping constructs is not allowed.
def recurPower(base, exp):
if exp > 1:
return base * recurPower(base, exp-1)
elif exp == 0:
return 1
else:
return base 3
The function
recurPower(base, exp)
from Problem 2 computed baseexp by
decomposing the problem into one recursive case and one base case:
baseexpbaseexp==base⋅baseexp−11ifexp>0ifexp=0
Another way to solve this problem just using multiplication (and remainder) is to note that
baseexpbaseexpbaseexp===(base2)exp2base⋅baseexp−11ifexp>0andexpisevenifexp>0andexpisoddifexp=0
Write a procedure
recurPowerNew
which recursively computes exponentials using this idea.
def recurPowerNew(base, exp):
if exp > 0 and exp % 2 == 0:
return recurPowerNew((base * base),exp/2)
elif exp > 0 and exp % 2 != 0:
return base * recurPowerNew(base, exp-1)
else:
return 1 4
The greatest common divisor of two positive integers is the largest integer that divides each of them without remainder. For example,
- gcd(2, 12) = 2
- gcd(6, 12) = 6
- gcd(9, 12) = 3
- gcd(17, 12) = 1
Write an iterative function,
gcdIter(a, b)
, that implements this idea. One easy way to do this is to begin with a test value equal to the smaller of the two input arguments, and iteratively reduce this test value by 1 until
you either reach a case where the test divides both
a
and
b
without remainder, or you reach 1.
def gcdIter(a, b):
if a > b:
t = a
a = b
b = t
t = a
while t > 1:
if b % t == 0 and a % t == 0:
return t
t = t - 1 5
A clever mathematical trick (due to Euclid) makes it easy to find greatest common divisors. Suppose that
a
b
are two positive integers:
- If b = 0, then the answer is a
- Otherwise, gcd(a, b) is the same as gcd(b, a % b)
gcdRecur(a, b)
that implements this idea recursively. This function takes in two positive integers and returns one integer.
def gcdRecur(a, b):
if b == 0:
return a
else:
return gcdRecur(b, a%b)
6
Although Python provides a built-in function for computing the length of a string, we can write our own.
lenIter
, which computes the length of an input argument (a string), by counting up the number of characters in the string.
def lenIter(aStr):
cnt = 0
for x in aStr:
cnt = cnt + 1
return cnt
7
For this problem, write a recursive function,
lenRecur
Hint:
String slicingmay be useful in this problem...
def lenRecur(aStr):
if aStr == '':
return 0
else:
a = aStr[1:]
return 1+lenRecur(a) 8
We can use the idea of bisection search to determine if a character is in a string, so long as the string is sorted in alphabetical order.
First, test the middle character of a string against the character you're looking for (the "test character"). If they are the same, we are done - we've found the character we're looking for!
If they're not the same, check if the test character is "smaller" than the middle character. If so, we need only consider the lower half of the string; otherwise, we only consider the upper half of the string. (Note that you can compare characters
using Python's
<
function.)
Implement the function
isIn(char, aStr)
which implements the above idea recursively to test if
char
is in
aStr
.
char
will be a single character and
aStr
will
be a string that is in alphabetical order. The function should return a boolean value.
As you design the function, think very carefully about what the base cases should be.
def isIn(char, aStr):
'''
char: a single character
aStr: an alphabetized string
returns: True if char is in aStr; False otherwise
'''
# Base case: If aStr is empty, we did not find the char.
if aStr == '':
return False
# Base case: if aStr is of length 1, just see if the chars are equal
if len (aStr) == 1:
return aStr == char
# Base case: See if the character in the middle of aStr equals the
# test character
midIndex = len (aStr) / 2
midChar = aStr[midIndex]
if char == midChar:
# We found the character!
return True
# Recursive case: If the test character is smaller than the middle
# character, recursively search on the first half of aStr
elif char < midChar:
return isIn (char, aStr[:midIndex])
# Otherwise the test character is larger than the middle character,
# so recursively search on the last half of aStr
else:
return isIn (char, aStr[midIndex + 1:]) 9
A semordnilap is a word or a phrase that spells a different word when backwards ("semordnilap" is a semordnilap of "palindromes"). Here are some examples:
- nametag / gateman
- dog / god
- live / evil
- desserts / stressed
Write a recursive program,
semordnilap
, that takes in two words and says if they are semordnilap.
This recursive function is not entirely straightforward. There are a few things that you need to check the first time you look at the inputs that you should not check on subsequent recursive calls: you need to make sure that the strings are not
single characters, and also you need to be sure that the strings are not equal. If you do this check every time you call your function, though, this will end up interfering with the recursive base case (which we don't want!).
There's a few different ways you can perform checks on the inputs the first time. The first way would be to use keyword arguments. The second way would be to use a global variable, which you'll see in
the next lecture video; however, using global variables is always a bit risky and thus not the best way to do this.
The third way to perform checks on the inputs the first time you see them, but not any subsequent time, is to use a wrapper function. This wrapper function performs some checks, then makes a call to the recursive function.
The idea of a wrapper function is really important. You'll see more wrapper functions later. To introduce you to the idea, we are providing you with the wrapper function; your job is to write the recursive function
semordnilap
that
the wrapper function calls. Here is the wrapper function:
def semordnilapWrapper(str1, str2):
# A single-length string cannot be semordnilap
if len(str1) == 1 or len(str2) == 1:
return False
# Equal strings cannot be semordnilap
if str1 == str2:
return False
return semordnilap(str1, str2) def semordnilapWrapper(str1, str2):
# A single-length string cannot be semordnilap
if len(str1) == 1 or len(str2) == 1:
return False
# Equal strings cannot be semordnilap
if str1 == str2:
return False
if len(str1) != len(str2):
return False
#other situation
return semordnilap(str1, str2)
def semordnilap(str1, str2):
if (len(str1) == 2) & (str1[0] == str2[-1]) & (str1[-1] == str2[0]):
return True
if str1[0] == str2[-1]:
return semordnilap(str1[1:], str2[:-1]) 10
Write a procedure called
oddTuples
,
which takes a tuple as input, and returns a new tuple as output, where every other element of the input tuple is copied, starting with the first one. So if test is the tuple
('I', 'am', 'a', 'test', 'tuple')
then evaluating
oddTuples
on this input would return the tuple
('I', 'a', 'tuple')
.
def oddTuples(aTup):
Out=()
n = 0
for i in aTup:
n = n + 1
if n % 2 == 1:
Out += (aTup[n-1],)
return Out
11
Here is the code for a function
applyToEach
:
def applyToEach(L, f):
for i in range(len(L)):
L[i] = f(L[i])
Assume that
testList = [1, -4, 8, -9]
For each of the following questions (which you may assume is evaluated independently of the previous questions, so that testList has the value indicated above), provide an expression using
applyToEach
, so that after evaluation
testList
has
the indicated value. You may need to write a simple procedure in each question to help with this process.
Example Question:
>>> print testList
[5, -20, 40, -45]
>>> print testList
[1, 4, 8, 9] def fabs(a):
if a < 0:
return -a
else:
return a
applyToEach(testList, fabs) >>> print testList
[2, -3, 9, -8] # Your Code Here
def fabs(a):
return a + 1
applyToEach(testList, fabs) >>> print testList
[1, 16, 64, 81] # Your Code Here
def fabs(a):
return a * a
applyToEach(testList, fabs) 13
Consider the following sequence of expressions:
animals = { 'a': ['aardvark'], 'b': ['baboon'], 'c': ['coati']}
animals['d'] = ['donkey']
animals['d'].append('dog')
animals['d'].append('dingo')
We want to write some simple procedures that work on dictionaries to return information.
First, write a procedure, called
howMany
, which returns the sum of the number of values associated with a dictionary. For example:
>>> print howMany(animals)
6 def howMany(animals):
s = 0
for e in animals:
s += len(animals[e])
return s 14
animals = { 'a': ['aardvark'], 'b': ['baboon'], 'c': ['coati']}
animals['d'] = ['donkey']
animals['d'].append('dog')
animals['d'].append('dingo')
This time, write a procedure, called
biggest
, which returns the key corresponding to the entry with the largest number of values associated with it. If there is more than one such entry, return any one of the matching keys.
Example usage:
>>> biggest(animals)
'd'
If there are no values in the dictionary,
biggest
should return
None
def biggest(aDict):
result = None
biggestValue = 0
for key in aDict.keys():
if len(aDict[key]) >= biggestValue:
result = key
biggestValue = len(aDict[key])
return result ![Network Architecture Search Survey[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)