Small Steps III — Thinking with Programs
Challenges (Optional)
Challenges (Optional)
Explore one topic in small steps. Try the examples one at a time and take a break whenever you need. Choose how many extra exercises you want to try.
Finding the second-largest value
What you will learn
Before solving a new problem, define what counts as the answer and what assumptions hold about the input. Here we remember two candidates.
Try it
void small_main()
{
Array<int> numbers = {8, 3, 12, 5, 10};
int largest = numbers[0];
int second = numbers[1];
if (second > largest)
{
int temp = largest;
largest = second;
second = temp;
}
for (int i = 2; i < numbers.length(); i = i + 1)
{
if (numbers[i] > largest)
{
second = largest;
largest = numbers[i];
}
else if (numbers[i] > second)
{
second = numbers[i];
}
}
print("Second largest: ", second);
}
The example assumes at least two elements and includes duplicates in the ranking. For {9, 9, 3}, the answer is 9. It does not mean the second distinct value.
When a new maximum appears, move the previous maximum into second. For 8, 3, 12, 5, 10, the answer is 10.
Counting occurrences of the largest value
What you will learn
Combining two procedures you already know can solve a new problem.
Try it
void small_main()
{
Array<int> numbers = {4, 9, 2, 9, 7};
int largest = numbers[0];
int count_largest = 0;
for (int i = 0; i < numbers.length(); i = i + 1)
if (numbers[i] > largest)
largest = numbers[i];
for (int i = 0; i < numbers.length(); i = i + 1)
if (numbers[i] == largest)
count_largest = count_largest + 1;
print("Largest: ", largest);
print("How many: ", count_largest);
}
First find the maximum, then use a second loop to count elements equal to it. The output is Largest: 9 and How many: 2.
Make each step's responsibility clear before trying to combine the two loops. The array must contain at least one element.
Exercise
Assume there are at least two distinct values and find the second-smallest value.
void small_main()
{
Array<int> numbers = {8, 3, 12, 5, 10};
// find the second smallest value.
}
Hint
Remember smallest and second. When a value is smaller than smallest, update both values together.
show solution
void small_main()
{
Array<int> numbers = {8, 3, 12, 5, 10};
int smallest = numbers[0];
int second = numbers[1];
if (second < smallest)
{
int temp = smallest;
smallest = second;
second = temp;
}
for (int i = 2; i < numbers.length(); i = i + 1)
{
if (numbers[i] < smallest)
{
second = smallest;
smallest = numbers[i];
}
else if (numbers[i] < second)
{
second = numbers[i];
}
}
print(second);
}
Try More (Optional)
Exercise
First find the Array's largest value, then count how often it occurs in a second loop.
void small_main()
{
Array<int> numbers = {5, 9, 2, 9, 9, 4};
// find largest, then count it.
}
Hint
The first loop finds largest; the second counts occurrences of numbers[i] == largest.
show solution
void small_main()
{
Array<int> numbers = {5, 9, 2, 9, 9, 4};
int largest = numbers[0];
for (int i = 1; i < numbers.length(); i = i + 1)
if (numbers[i] > largest)
largest = numbers[i];
int count = 0;
for (int i = 0; i < numbers.length(); i = i + 1)
if (numbers[i] == largest)
count = count + 1;
print("Largest: ", largest);
print("Count: ", count);
}