Description
1 R Change-making problem: greedy solution
Write a program that prompts the user for an amount, and outputs the minimal number of banknotes needed to yield that amount, as well as the detail of how many banknotes of each type value
are used. The available banknotes have a face value which is one of $1, $2, $5, $10, $20, $50, and
$100.
Here are examples of interactions:
$ python question_1.py
Input the desired amount: 10
1 banknote is needed.
The detail is:
$10: 1
$ python question_1.py
Input the desired amount: 739
12 banknotes are needed
The detail is:
$100: 7
$20: 1
$10: 1
$5: 1
$2: 2
$ python question_1.py
Input the desired amount: 35642
359 banknotes are needed
The detail is:
$100: 356
$20: 2
$2: 1
The natural solution implements a greedy approach: we always look for the largest possible face
value to deduct from what remains of the amount.
Suppose that the available banknotes had a face value which was one of $1, $20, and $50. For an
amount of $60, the greedy algorithm would not work, as it would yield one $50 banknote and ten
$1 banknotes, so eleven banknotes all together, whereas we only need three $20 banknotes.
1
2 R Change-making problem: general solution
Write a program that prompts the user for the face values of banknotes and their associated
quantities as well as for an amount, and if possible, outputs the minimal number of banknotes
needed to match that amount, as well as the detail of how many banknotes of each type value are
used.
Note: this question is flagged but in case it is used in the exam, only the minimal number of
banknotes needed to match the amount would have to be computed, not the various solutions.
Here are examples of interactions:
$ python question_2.py
Input pairs of the form ’value : number’
to indicate that you have ’number’ many banknotes of face value ’value’.
Input these pairs one per line, with a blank line to indicate end of input.
2 : 100
50: 100
Input the desired amount: 99
There is no solution.
$ python question_2.py
Input pairs of the form ’value : number’
to indicate that you have ’number’ many banknotes of face value ’value’.
Input these pairs one per line, with a blank line to indicate end of input.
1 : 30
20 : 30
50 : 30
Input the desired amount: 60
There is a unique solution:
$20: 3
2
$ python question_2.py
Input pairs of the form ’value : number’
to indicate that you have ’number’ many banknotes of face value ’value’.
Input these pairs one per line, with a blank line to indicate end of input.
1: 100
2: 5
3: 4
10:5
20:4
30:1
Input the desired amount: 107
There are 2 solutions:
$1: 1
$3: 2
$10: 1
$20: 3
$30: 1
$2: 2
$3: 1
$10: 1
$20: 3
$30: 1
The natural approach makes use of the linear programming technique exemplified in the computation of the Levenshtein distance between two words.
3 R A class to work exactly with fractions
Write a program that allows one to create fractions and work precisely with them, following this
kind of interaction:
$ python
…
>>> from question_3 import Fraction
>>> f = Fraction()
Provide exactly two arguments.
>>> f = Fraction(1, 5, 12)
Provide exactly two arguments.
>>> f = Fraction(1, ’hi’)
Provide an integer and a nonzero integer as arguments.
3
>>> f = Fraction(3, 0)
Provide an integer and a nonzero integer as arguments.
>>> f = Fraction(0, 3)
>>> f
Fraction(numerator = 0, denominator = 1)
>>> print(f)
0 / 1
>>> f = Fraction(120, -30)
>>> f
Fraction(numerator = -4, denominator = 1)
>>> print(f)
-4 / 1
>>> f = Fraction(-310532200, -46077863832)
>>> f
Fraction(numerator = 425, denominator = 63063)
>>> print(f)
425 / 63063
>>> f3 = f1 – f2
>>> print(f3)
-32743 / 11520
>>> f3 = f1 * f2
>>> print(f3)
739 / 5760
>>> f1 / Fraction(0, 35)
Cannot divide by 0.
>>> f1 < f2 True >>> f1 <= f2 True >>> f1 > f2
False
>>> f1 >= f2
False
>>> f1 == f2
False
>>> f1 != f2
True
To find out whether the correct number of arguments has been provided, pass an argument of the
form *args to __init__ (the name args is arbitrary; what matters is the leading star, which makes
args a tuple consisting of all positional arguments).
The implementation makes use of the following special methods (find out about them): __repr__,
__str__, __add__, __sub__, __mul__, __truediv__, __lt__, __le__, __gt__, __ge__, __eq__,
__ne__.
4
