1. Engineering
  2. Computer Science
  3. imagine a row of n lights numbered 1 to n...

Question: imagine a row of n lights numbered 1 to n...

Question details

Imagine a row of n lights, numbered 1 to n, that can be turned on or off only under certain conditions as follows. The first light can be turned on or off anytime. Each of the other lights can be turned on or off only when the preceding light is on and all other lights before it are off. If all the lights are on initially, how can you turn them all off For three lights numbered 1 to 3, you can take the following steps, where 1 indicates a light that is ON and 0 indicates OFF 111 011 010 110 100 3 lights ON initially Turn OFF light 1 Turn OFF light 3 Turn ON light 1 Turn OFF light 2 Turn OFF light 1 We can solve this problem by indirect recursion using the two methods turnOff) and turnOn() that mutually call each other. The algorithm in pseudo-code for turnOff(n) is shown below: Algorithm turnOff( n) // Pre-Condition: Lights 1. n are all currently on // Post-Condition: Lights 1. n are all turned off 1. if (n 1) then Turn OFF light 1 2. else IIn 2 2 3 4 if (n> 2) then turnOff( n 2) Turn OFF light n if (n > 2) then turnOn( n 2) trunOff( n - 1) 7. end // trunOff

a) b) Write a similar algorithm in pseudo-code for turnOn(n). Implement these algorithms in Java. Use the results in a program to display the sequence of steps to turn off n lights that are initially on. Show the output for a few values of n. The output format should be similar to the 3-lights example shown above. c) Obtain, with sufficient explanation, an accurate estimate of the number of times lights are turned off or on during the entire process. Express the answer as a function of n. Combine the two algorithms turnOff(n) and turnOn(n) and replace them with a single recursive two parameter algorithm flipSwitches(n, s) written in pseudo-code. The boolean parameter s indicates which version is intended: switching n lights ON or OFF. Note: turnoff) and turnOn() methods should no longer be used/invoked in your new algorithm-use only FlipSwitches() instead.] d)

Solution by an expert tutor
Blurred Solution
This question has been solved
Subscribe to see this solution