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 generic and separate from the rest of the program (i.e., there should be separate classes for DCLLs and DCLL elements, not part of the class definitions for this specific problem).
Set up your program so that you can read the numbers in from a console Scanner, and 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.
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