Please attempt these only after you finished the main notebook!
Write a recursive function gcd(a, b)
that:
a
and b
as input.a
and b
.For example:
gcd(15, 10) == 5 # nothing bigger than 5 divides 15 and 10.
gcd(24, 36) == 12
gcd(72, 180) == 36
gcd(101, 197) == 1 # 101 and 197 do not share any common factors.
gcd(39793, 1) == 1 # gcd(a, 1) == 1 for all positive a.
gcd(22, 0) == 22 # gcd(a, 0) == a for all positive a.
To implement gcd()
, we will use a recursive algorithm that Euclid discovered in Alexandria, Egypt in 300BC. Here it is:
If $b > 0$,
gcd(a, b) == gcd(b, a % b)
gcd(a, 0) == a
Here is an example of Euclid's algorithm for gcd(180, 72)
:
# Recursive case: 180 % 72 == 36
gcd(180, 72) == gcd(72, 36)
# Recursive case: 72 % 36 == 0
gcd(72, 36) == gcd(36, 0)
# Base case (b == 0)
gcd(36, 0) == 36
Result: the greatest common divisor of 180 and 72 is 36.
Here is another example, of gcd(45, 210)
:
# Recursive case: 45 % 210 == 45
gcd(45, 210) == gcd(210, 45)
# Recursive case: 210 % 45 == 30
gcd(210, 45) == gcd(45, 20)
# Recursive case: 45 % 30 == 15
gcd(45, 30) == gcd(30, 15)
# Recursive case: 30 % 15 = 0
gcd(30, 15) == gcd(15, 0)
# Base case (b == 0)
gcd(15, 0) == 15
Result: the greatest common divisor of 45 and 210 is 15.
Task: Implement gcd()
using Euclid's algorithm described above.
def gcd(a, b):
# YOUR ANSWER HERE
pass
# After you finish, these should all print True
print(gcd(15, 10) == 5)
print(gcd(24, 36) == 12)
print(gcd(72, 180) == 36)
print(gcd(101, 197) == 1)
print(gcd(39793, 1) == 1)
print(gcd(22, 0) == 22)
False False False False False False
A permutation of a list is the same list, but in a different order.
For example, [0, 2, 1]
and [2, 0, 1]
are both permutations of [0, 1, 2]
.
Write a recursive function permutations(n)
that takes an integer, n
, as input, and returns a sorted list of all permutations of integers between 0
and n
. Examples:
permutations(0) == [[0]]
permutations(1) == [[0, 1], [1, 0]]
permutations(2) == [[0, 1, 2], [0, 2, 1],
[1, 0, 2], [1, 2, 0],
[2, 0, 1], [2, 1, 0]]
Hints
myList.insert(5, 'myItem')
will insert 'myItem'
at position 5
in myList
.myList.sort()
to put myList
in sorted order. Note: sort()
returns None
, so use it on its own line of code.# Example code to illustrate `insert()` and `sort()`
myList = [2, 0, 3, 1]
myList.insert(2, 77) # insert 77 at position 2 in myList
print("myList hasn't been sorted yet:", myList)
myList.sort()
print("Now myList is sorted:", myList)
myList hasn't been sorted yet: [2, 0, 77, 3, 1] Now myList is sorted: [0, 1, 2, 3, 77]
Task: Write a recursive permutations(n)
function.
Remember: it is OK to use loops as part of your recursive solution!
def permutations(n):
# YOUR ANSWER HERE
pass
# If your code is correct, these should all print True
print(permutations(0) == [[0]])
print(permutations(1) == [[0, 1], [1, 0]])
print(permutations(2) == [[0, 1, 2], [0, 2, 1],
[1, 0, 2], [1, 2, 0],
[2, 0, 1], [2, 1, 0]])
if permutations(0) != None:
print(len(permutations(6)) == 5040)
print(permutations(6)[3791] == [5, 1, 3, 6, 4, 2, 0])
else:
print(False)
False False False False
Consider a recursive function called combinations
.
Combinations of size k refer to the subsets or groupings of elements taken from a given set, where each combination consists of exactly k elements. In other words, it represents the selection of k distinct elements from a larger set, without considering the order of the elements.
For example:
combinations([1, 2, 3], 2) == [[1, 2], [1, 3], [2, 3]]
combinations([4, 5, 6], 3) == [[4, 5, 6]]
combinations([1, 2, 3, 4], 5) == []
Think about:
combinations()
? Describe your answer using English.combinations()
? Describe your answer using English.Implement combinations()
.
def combinations(lst, k):
if len(lst) < k:
return []
if k == 0:
return []
if k == 1:
return [[i] for i in lst]
prev_com = combinations(lst, k - 1)
new_com = list()
for sub in prev_com:
for m in lst:
if m not in sub:
new_add = sorted(sub + [m])
if new_add not in new_com:
new_com.append(new_add)
return new_com
#Test cases
print('Test passed:', combinations([1, 2, 3], 2) == [[1, 2], [1, 3], [2, 3]])
print('Test passed:', combinations([4, 5, 6], 3) == [[4, 5, 6]])
print('Test passed:', combinations([4, 5, 6], 2) == [[4, 5], [4, 6], [5, 6]])
print('Test passed:', combinations([1, 2, 3, 4], 5) == [])
# print(combinations([1, 2, 3], 2))
Test passed: True Test passed: True Test passed: True Test passed: True
You may have heard of the game "Tower of Hanoi" (see figure below):
The goal of the game is to move all the disks from the leftmost peg to the rightmost peg. The middle peg can be used as a helper peg to temporarily hold the disks.
There are only two simple rules:
The puzzle starts with n
disks on the leftmost peg, and the disks are sorted from smallest to largest, with the largest disk on the bottom.
Your task is to write a recursive function called hanoi(n, source, helper, target)
that prints out the steps to solve the Tower of Hanoi puzzle.
For example:
hanoi(1, "A", "B", "C")
# ---> prints "Move disk 1 from peg A to peg C"
hanoi(2, "A", "B", "C")
# ---> prints "Move disk 1 from peg A to peg B"
"Move disk 2 from peg A to peg C"
"Move disk 1 from peg B to peg C"
hanoi(3, "A", "B", "C")
# ---> prints "Move disk 1 from peg A to peg C"
"Move disk 2 from peg A to peg B"
"Move disk 1 from peg C to peg B"
"Move disk 3 from peg A to peg C"
"Move disk 1 from peg B to peg A"
"Move disk 2 from peg B to peg C"
"Move disk 1 from peg A to peg C"
Hint: Think about what the base case and recursive case would be; the recursive case should reduce the problem to a smaller version of itself (in this problem, a Tower of Hanoi with fewer disks).
def hanoi(n, source, helper, target):
# Hint: the base case is implemented below for you
if n == 0:
return
# TODO: your code for the recursive here
# NOTE: you don't need to return anything from the function;
# just print out the individual moves
# Test cases
for tower_height in range(1, 4):
print('For', tower_height, 'disks:')
hanoi(tower_height, 'A', 'B', 'C')
print()
For 1 disks: For 2 disks: For 3 disks:
Write a recursive function, permuteString(s)
, that returns all possible permutations of the string s
.
For example:
permuteString("ab") == ["ab", "ba"]
permuteString("abc") == ["abc", "acb", "bac", "bca", "cab", "cba"]
Implement permuteString(s)
recursively.
def permuteString(s):
# your code here
return []
# after you finish, these all should print true
print('Test passed:', set(permuteString("ab")) == set(["ab", "ba"]))
print('Test passed:', set(permuteString("abc")) == set(["abc", "acb", "bac", "bca", "cab", "cba"]))
print('Test passed:', set(permuteString("aaa")) == set(["aaa"]))
Test passed: False Test passed: False Test passed: False