CS171 (Spring 2012)
Assignment 4: Circular List and Josephus Problem
Due: Friday, March 9, 11:59pm
Goals
1. Implement a Circular
List
2. Use Circular List to solve
the Josephus problem.
Circular List
The
first part of this assignment is to implement a circular list class. A circular list, or circularly linked list, is
a linked list where the last element in the list points to the first element,
thus completing a cycle (circle) of links. A common representation for the
circular list is based on the use of a tail variable which points to the last
element in the list. This strategy is very convenient, since inserting and
removing elements from the head of the list can be done without traversing the
entire list of elements.
1.
Each element in the circular list is of type ListElem. ListElem.java is
provided as starter code. You do not need to change it. An object of type
ListElem has 2 properties: an integer value storing the numerical value
associated with the element, and a variable of type ListElem,
that points to the next element in the list.
2.
The circular list is implemented in CircularList.java. Your task is to
implement the following required methods for the CircularList
class:
·
public
boolean isEmpty()
This method returns true if the list is
empty, false otherwise.
·
public
int getSize()
This method returns the size of the circular
list.
·
public
Integer remove()
This method removes an element from the head
of list. It returns the value of the element removed, or null if the list is
empty.
·
public
void insert(ListElem newElem)
This method inserts the newElem at the head
of the circular list, and it has no returning value.
·
public
void rotate()
This method rotates the circular list. In
other words, the first element in the list is moved to the end of the list, and
all other elements in the list are moved forward one position.
·
public
void printList()
This method prints the value of each element in
the list starting from the head.
The Josephus problem
The
second part of this assignment is to use your CircularList
to solve the Josephus problem. The
problem can be summarized as follows: "given a group of n men arranged in
a circle under the edict that every m-th man will be executed going around the
circle until only one remains". For example, if 6, 5, 4, 3, 2, 1, 0 are
arranged in circle, with m = 3, then the order of removal is
4, 1, 5, 0, 2, 6, with 3 remaining as the survivor. You can read more about
this problem on Wikipedia: http://en.wikipedia.org/wiki/Josephus_problem
Your
task is to implement the solve() method in
Josephus.java class to solve the problem given a list of values and m. The list represents the n men. Each execution
should be simulated by removing an element from the list. The detailed
specification for this method is as follows:
·
public
static int solve (CircularList
cl, int m)
This method takes 2 parameters: a circular
list cl representing the men in the circle and an integer m which tells how
many men are skipped before each execution. Your method should remove the m-th element, starting at the head element, and the process
repeats, starting from the next element. You can use the rotation method in your
circular list to find the element to be executed. This repetition continues until one element
is left (i.e. only one man survived). The method should return the value of the
survived element in the circular list.
Starter Code:
The
starter code consists of 3 classes: ListElem.java, CircularList.java and Josephus.java.
The class ListElem contains the definitions of the
elements used to build the circular list, so you do not need to change this
class. Your task is to implement the required methods in the CircularList.java
and the solve() method in Josephus.java. You can edit
the main() method in Josephus to test your CircularList implementation as well as the solve() method.
In particular, you can use the printList() method of the CircularList
class to ensure things are working correctly.
Honor code
The
assignment is governed by the College Honor Code and Departmental Policy.
Please remember to have the following comment included at the top of the file.
/*
THIS CODE IS MY OWN WORK, IT WAS WRITTEN
WITHOUT CONSULTING
CODE WRITTEN BY OTHER
STUDENTS. _Your_Name_Here_
*/
Submission:
Your
completed CircularList.java, Josephus.java and ListElm.java should be placed in
your ~/cs171/hw4
Grading:
·
Note
that, each method will be tested separately.
·
If
your program does not compile, you will get 0 points
·
If
your program does not contain the honor code, you will get 0 points
·
Correctness
1.
Your
insert and remove methods work properly (30 pts).
1.
Your
getSize and isEmpty methods work properly (10 pts).
2.
Your
rotation method works properly (15 pts).
3.
Your
printList method works properly (10 pts).
4.
Your
program solves the Josephus problem correctly with any circular list of size up
to 15 and m up to 15 (20 pts).
·
Robustness
(your program never crashes for any reasonable size of circular list and m) (10
pts).
·
Code
clarity and style: 5 points
Enjoy!