Lab: Measuring Cups

In this lab, you will develop a program to determine which measuring cups to use to measure a specified quantity.

Instructions

You should complete this lab individually.

Background

In class, we proved it is possible to measure out any number of cups greater than or equal to 11 using 4-cup, 9-cup, 11-cup, and 14-cup measures. We used n to refer to the total quantity being measured.

Step 1: Manual Calculation

First, rewrite the base cases for n=11,12,13,14.

Next, use the insight from our induction proof to determine which cups to use to measure n=15,16,17,18.

Step 2: Python Program

You should develop a Python program to determine which measuring cups to use to measure a specified quantity. Name your program cups.py. The program should accept one argument, n≥11. Your program should print a JSON dictionary representing how many times each measuring cup should be used. For example:

> python cups.py 11
{"4": 0, "9": 0, "11": 1, "14": 0}
> python thue.py 12
{"4": 3, "9": 0, "11": 0, "14": 0}
> python cups.py 42
{"4": 7, "9": 0, "11": 0, "14": 1}

Hint: Write a recursive method with base cases and a recursive case.

Hint: Use a dictionary to keep track of how many times each cup is used. Use json.dumps to print the dictionary as JSON.

Optional: Use Fewer Cups

The algorithm used in our induction proof will use the 4-cup more times than is strictly necessary. By using larger cups, it is often possible to use fewer cups.

Modify your program to use fewer cups. Consider using a greedy algorithm, or using dynamic programming to implement an optimal algorithm.

Submit

Upload cups.py to Gradescope.

Learning Goals