I have been working on this for a while and can't figure it out. It has been really troublesome for me. Any help would be appreciated.
Suppose that n people numbered 1 to n are lined up with their backs to a wall. Starting at the end of the line, eliminate every other person until only 1 survives. Reverse directions when you reach the end of the line. For example, for n=10, the elimination order is 2,4,6,8,10,7,3,5,1 so the survivor is 9. Let s(n) denote the survivor's number (hence S(10)=9). Find a recursive definition for S(n). You should have a base case and 2 recursive cases-- one for S(2k) and S(2k+1).
2007-10-17
14:15:21
·
1 answers
·
asked by
A A
2