Evolving Software

Question: You have two light bulbs and a 100-story building. You want to find the floor at which the bulbs will break when dropped. Find the floor using the least number of drops.

Hopefully your mind has immediately kicked into gear … and you start thinking of solutions and estimating the Big-O. Good for you these are the kinds of problems that I just can’t resist.

In this article I’ll take a look at several different solutions to this problem.

Linear Search:Linear Search

Of course we are going to start with linear search, and why not it is the most obvious solution. Start at the first floor and just start dropping bulbs.

How does this algorithm perform? Well as you might expect pretty poorly. In the worst case you have to go all the way up to the top floor in order to find out that the bulbs break … however using this solution you can determine the breaking floor using only one bulb.

Additionally this algorithm has a pretty good travel time. Considering how much time you will spend traveling between floors, this algorithm is pretty good, in the sense that the number of trips up and down the stairs is equal to the number of floors in the building in the worst case.

public void getNumberOfDrops(DropScenerio dropManager) {
for (int i = dropManager.getCurrentFloor();
i <= dropManager.getNumFloors(); i++) {
dropManager.setCurrentFloor(i);
if (dropManager.dropTest()) {
return;
}
}
}

linearperformance

Worst Case # of Drops = n (where n = the height of the building)

Average Case # of Drops = n/2 (where n = the height of the building)

Worst Case Travel Time = n (where n = the height of the building)

Average Case Travel Time = n/2 (where n = the height of the building)

This is a pretty standard linear function and we can use this as a baseline for analyzing other searching methods.

Pages: 1 2 3 4 5

Categories: Computer Science