Say we have a sequence of integer numbers: we can strike off the first one in the sequence, call it k, and then strike off every kth number following. This will give us a new sequence, and we can then repeat the process. Eventually, we will run out of numbers and be done: typically this happens when we reach a 1 at the front, so that every number is struck off. Here is an example:
What about zero or negative numbers? Well, we want to make some progress, so if we see a zero, let’s strike off at least the zero itself, but no other numbers. If we see a negative number, let’s strike it off, as usual, but let’s then strike off every kth number from the list going in the opposite direction, i.e., counting from the end of the list and going backward.
In other words, we can think of the numbers arranged not in a line, but rather in a circle, like this:
You should write a program which will read in such a sequence of numbers, all on one line. It should then print out the original sequence and each of the “stricken” versions, not with actual slashes through the numbers, of course, but with only the remaining values showing. For example (here I've added arrows for emphasis):
2 3 4 2 3 1 2 5 2 3 4 1 3 2
=> 3 2 1 5 3 1 2
=> 2 1 3 1
=> 1 1
You should use an implementation of doubly-circularly-linked lists (DCLLs), which you write yourself, as the basis for your implementation. Make sure that your DCLL implementation is separate from the rest of the program (i.e., there should be separate classes for DCLLs and DCLL nodes, not part of the class definitions for this specific problem).
Set up your program so that you can read the numbers in from user input, or use a GUI if you feel more comfortable with that. Try to come up with a few interesting test cases of your own (say, ones which require at least 5 passes before they finish). You may also want to test with the data shown below.
It would be nice if you could “pre-populate” your interface with some of these sample lists: this is especially easy with a GUI, but you could also just have your program run through some samples drawn from these and hard-coded in (or read from a file).
In order to help you understand and plan out your implementation, you may wish to refer to the following diagram, which shows how you can add (or insert) a new node into a DCLL just behind (prior or previous) to the head node:
Here are a few quick sample runs to show you the basic idea (again, I've added arrows to emphasize that the first line is the user’s input and that each subsequent line is a stricken version of the sequence on the previous line):
Sample one:
4 4 4 4 3 3 3 2 2 4 4 4 4 3 3 3 2 2 4 4 4 4 3 3 3 2 2
=> 4 4 4 3 3 2 4 4 4 3 3 3 2 4 4 4 3 3 2 2
=> 4 4 3 2 4 4 3 3 3 4 4 4 3 2 2
=> 4 3 2 4 3 3 4 4 4 2 2
=> 3 2 4 3 4 4 2 2
=> 2 4 4 4 2
=> 4 4
=> 4
Sample two:
2 3 4 5 -2 -3 -4 -5 2 3 4 5 -2 -3 -4 -5
=> 3 5 -3 -5 3 5 -3 -5
=> 5 -3 3 5 -5
=> -3 3 5 -5
=> 5 -5
=> -5
Sample three:
-2 -3 -4 -5 5 4 3 2 -2 -3 -4 -5 5 4 3 2 -2 -3 -4 -5 5 4 3 2
=> -3 -5 4 2 -3 -5 4 2 -3 -5 4 2
=> -5 4 -3 -5 2 -3 4 2
=> 4 -3 2 -3 4 2
=> -3 2 -3 2
=> -3 2
=> 2