CS 223 In-lab 5
Week of 2/27

For CS 223, in-labs will consist of a mix of exercises and problems and short programming assignments.  These will be due at the end of the lab period.  You may occasionally be assigned homework problems as well.  Homework will always be due at the beginning of the next lab.

Counting Coconuts

The following is an interesting math problem that can be solved elegantly with dynamic programming.

On a desert island, five students and a monkey gather coconuts all day, then sleep. The first student awakens and decides to gather her share. She divides the coconuts into 5 equal shares with one left over, gives the extra one to the monkey, hides her share, and goes to sleep. Later, the second student awakens and takes his fifth from the remaining pile. He, too, finds one extra and gives it to the monkey. Each of the three remaining students does likewise in turn. Find the minimum number of coconuts originally present.

For this in-lab, your job is to write a dynamic programming based program that computes the answer to the above question.  To do this you will first need a recurrence relation.  The following analysis will provide one.

Let s[n] be the number of students that can visit a coconut pile whose original size is n.  Each time a new student visits they will divide the pile into five groups with a remainder of 1 and remove one of the groups.  So, n mod 5 must equal 1, otherwise s(n) = 0; no students can come.  So we can now express a recurrence relation for s[n]:

s[n]    = 0                , if n mod 5 != 1,
        = s[4*(n-1)/5] + 1 , otherwise

The idea of this recurrence is that if a student can visit the pile, we can find out how many more students can come by computing the size of the remaining pile and looking up that value in the s array.

What to do:

  • Write a short program that uses dynamic programming to find s[n] using the above recurrence.
  • You may assume that s[1] = 0, so just use the recurrence to compute s[n] for n > 1.
  • Compute s[n] for n up to 5000.
  • Answer the original problem based on the results.

Extra credit:

  • Print out the number of coconuts remaining after each student visits the coconut pile (with starting size found above).

What to Turn In

  • Source code and sample run showing the answer to the original problem.