Sunday, February 28, 2010

Find2Largest Problem

Problem: Expand the problem from the preceding exercise "Find Largest" so that it finds both the largest and the second largest values in the list." (Robers ch 4, problem 13).

Basically, you start with two placeholder variables, "top" and "second." You set them initially to 0, but their values will change. As the user enters in new integers, you want a program that looks at each new input and says "If the input value is greater than the top, then replace the current top with the new input. If the input value is less than the current top AND greater than the current second, then reset second to equal the new input."

Renee's Code:
/*
* File: Find2ndLargest.java
* Name: Renee
* Section Leader:
* ------------------
This program uses three variables to find the two-largest values in an indefinite
list of integers entered by the user: "value", which is the variable given to the user
inputs, and "top" and "second," which are storage variables that start off at a value of 0. As the user
enters inputs, we compare the inputs to the current "top" and "second." Whenever the value
the user enters is greater or equal to the current "top," then we reassign the value
of "top" to the new input (but first we have to move the old "top" to "second" place).
This keeps going until the user enters the sentinel, when we end the inner loop and print the
reigning "top" and "second."
*/

import acm.program.*;

public class Find2ndLargest extends ConsoleProgram{
public void run () {
println ("This program finds the 2 largest of a list of integers.");
println("Enter integers, one per line, entering 0 to signify the end of the list.");

int top = 0;
int second = 0;

while (true){
int value = readInt("Enter integer: ");
if (value == SENTINEL) break;

if (value >= top) {
second = top;
top = value;
}else if (value >= second){
second = value;
}

}

println("The highest is " + top + ".");
println("The second highest is " + second + ".");
}
//private constants
private static final int SENTINEL = 0;


}

What it looks like:


Time it took: 35 min

What made it difficult: Not super-difficult this time. I did have a funny blooper. The first time I ran the code, I entered "7, 9, 6, 0" and got "The highest is 9. The second-highest is 6." What! The problem was, I had forgotten to state, "if you get a new 'top,' make the old 'top' equal to the 'second' and then make the new 'value' equal to the new 'top.'" Leaving out that line, then if your second-highest gets entered before your highest, you won't capture the second-highest.

This program also shows you the importance of "greater than" versus "greater than or equal to." At first I thought it was a wash whether I used ">=" or ">" as my operator, but running the program by hand with a couple test inputs clarified the difference.

Let's say the user enters "2, 2, 1, 0" as the inputs. What's the right answer? "The highest is 2. The second-highest is 1", right? However, if the operator is ">", which is wrong, here's how the program runs (going through it by hand):

Initial: top = 0, second = 0
1st loop: value = 2. The program thinks, "Is 2 greater than my current top, 0? Yes. Then top = 2, second = 0."
2nd loop: value = 2. The program thinks, "Is 2 greater than my current top, 2? NO! Well, is it greater than my current second, 0? Yes! Then reassign "second" to equal 2. top = 2, second = 2."
3rd: value = 1. The program thinks "1 is not greater than my current top or my current second, so keep the status as top = 2, second = 2."
4th: value = 0. Zero is the sentinel. Program stops, print "The highest is 2. The second-highest is 2."

This bug is solved by making the operator >=, because if the current top is 2 and the user enters 2, the program will replace the old 2 with the new 2, instead of moving it to the "second" variable.

1 comment:

  1. Meta-pedagogical comment: this problem is ill-posed. If someone gave me the list "2, 2, 1, 0" and asked me to pick the top two values I would pick 2 and 2 because I have two terms to choose from which are bigger than all the others. But there are applications where you'd like to discard repeated numbers, so it makes sense for you to use your solution too.

    Unrelated comment: you could solve my version of this problem using this code.

    ...
    if (value> second) second = value;
    if (second>top) {temp = top; top = second; second = temp}; //swaps second and first
    ...

    Your solution is better, I think and it's not trivial to extend this and exclude repeated numbers. The reason why I put this here is because this idea of swapping is the basis of a sorting algorithm, the bubble sort, which I think it's cool.

    ReplyDelete