Topic J - Looping Structures

Overview

LOGs

General Programming Concepts and Terms

Identify the C# statements that correspond to Do-While and Do-Until logical structures
Translate Do-While structures into code
Translate Do-Until structures into code
Identify and distinguish the parts of the for statement in code
Describe the common situations in which the for statement is used
Demonstrate how the various looping statements can be interchanged with slight alterations of the logical structures to maintain the overall logic of a given routine.

Code Samples

Aggregator – The Aggregator class supports static methods for doing various types of aggregation on Numbers. (Numbers is a supplied class that stores a series of real values that can be obtained by calling getNext().) The common aggregations of totalItems(), averageItems(), maxValue() are given as examples of simple looping.
Math – fibonnacciNumber() and isPerfect()
Fraction – The fraction example is now enhanced to simplify the fractional value by finding the greatest common denominator of the fraction’s numerator and denominator.
GuessingGame – This example uses a supplied class called SecretNumber, which picks a random whole number between a specific range. An instance of the SecretNumber is passed to the constructor of the GuessingGame, and the GuessingGame’s guess() method attempts to get the correct guess within a specified number of tries.

Aggregator

The Aggregator class supports static methods for doing various types of aggregation on Numbers. (Numbers is a supplied class that stores a series of real values that can be obtained by calling GetNext().) The common aggregations of TotalItems(), AverageItems(), MaxValue() are given as examples of simple looping.

The Numbers Class

The methods of the Aggregator class all take a single argument: a Numbers object. The Numbers object contains a bunch of real numbers and it has two methods that the Aggregator methods will use:

HasNext() – This returns a Boolean indicating that the object has another number available.
GetNext() – This returns a real number from the set of values in the Numbers object.

For example, if a Numbers object has a set of four values such as 1.0, 5.5, 3.2, and 5.3, then the GetNext() method can be called four times to retrieve each value. Any attempt to call GetNext() when the object’s HasNext() is false will cause an exception.

Note: This class is already coded for you in the samples.

Aggregator Methods

The following Aggregator methods will demonstrate looping logic and syntax. All of these examples demonstrate the while statement.

TotalItems() – This method loops through all the values inside of the Numbers object to calculate and return the total of the values.
AverageItems() – This method gets all the values inside of the Numbers object so as to calculate the average value. If no values exist in the Numbers object, then the method returns an average of zero.
MaxValue() – This method examines the Numbers object’s values to see which value is the largest. If there are no values inside of the Numbers object, then the method returns the smallest possible value that is supported by the programming language.

 1 public class Aggregator
 2 {
 3     public static double TotalItems(Numbers items)
 4     {
 5         double total = 0;
 6         while (items.HasNext())
 7             total += items.Next();
 8         return total;
 9     }
10 
11     public static double AverageItems(Numbers items)
12     {
13         double average, total = 0;
14         int count = 0;
15         while (items.HasNext())
16         {
17             total += items.Next();
18             count++;
19         }
20         if (count > 0)
21             average = total / count;
22         else
23             average = 0;
24         return average;
25     }
26 
27     public static double MaxValue(Numbers items)
28     {
29         double max = double.MinValue;
30         while (items.HasNext())
31         {
32             double value = items.Next();
33             if (max < value)
34                 max = value;
35         }
36         return max;
37     }
38 }

Math

The Math class provides methods for the following mathematical algorithms not found in the default Math class.

FibonacciNumber() – Returns a number from the Fibonacci sequence for a given position. If the given position is less than or equal to zero, then this method should throw an exception. This example demonstrates the for statement. An alternative version illustrates the do-while statement.
IsPerfect() – Indicates whether or not a number is a “perfect” number. A perfect number is a number where the sum of all the factors equals the number. By definition, any number less than 1 (including all negative numbers) are not perfect numbers. This example uses a while statement. An alternative version illustrates a do-while statement.

 1 public class Math
 2 {
 3     public static int FibonacciNumber(int i)
 4     {
 5         int current = 1, previous = 1, beforePrevious = 0;
 6         if (i >= 1)
 7         {
 8             for (int counter = 3; counter <= i; counter++)
 9             {
10                 beforePrevious = previous;
11                 previous = current;
12                 current = beforePrevious + previous;
13             }
14         }
15         else
16             throw new Exception("Can only create a fibonnaci number based on a p\
17 ositive non-zero position");
18         return current;
19     }
20 
21     public static bool IsPerfect(int number)
22     {
23         bool perfect = true;
24         if (number <= 1)
25             perfect = false;
26         else
27         {
28             // The following logic attempts to prove it is imperfect
29             int halfWay = number / 2;
30             int total = 0;
31             int count = 1;
32             while (total != number && total <= halfWay && total < number)
33             {
34                 if (number % count == 0) // Then count is a factor of number
35                     total += count;
36                 count++;
37             }
38             if (total != number)
39                 perfect = false;
40         }
41         return perfect;
42     }
43 }

Fraction

The fraction example is now enhanced to simplify the fractional value by finding the greatest common denominator of the fraction’s numerator and denominator.

The Fraction class represents a fraction as two integers: one for the numerator and one for the denominator. When a Fraction object is created, the class must now simplify the fractional values by calculating the greatest common denominator.

GreatestCommonDenominator() – This private method is used by the Simplify() method to get the greatest common denominator for the numerator and denominator. Remember to allow for dealing with negative fractions (in which case, the negative sign will be on the numerator). This example uses a while statement (though it is possible to re-work the logic to use a do-while statement).

 1     private int GreatestCommonDenominator()
 2     {
 3         int commonDenominator = 1;
 4         int count = 2, halfWay;
 5         int absoluteNumerator = System.Math.Abs(Numerator);
 6         if (absoluteNumerator > Denominator)
 7             halfWay = absoluteNumerator / 2;
 8         else
 9             halfWay = Denominator / 2;
10 
11         while (count <= halfWay)
12         {
13             if (absoluteNumerator % count == 0 && 
14                 Denominator % count == 0)
15                 commonDenominator = count;
16             count++;
17         }
18 
19         return commonDenominator;
20     }

GuessingGame

This example uses a supplied class called SecretNumber, which picks a random whole number between a specific range. An instance of the SecretNumber is passed to the constructor of the GuessingGame, and the GuessingGame’s Guess() method attempts to get the correct guess within a specified number of tries.

In a regular number guessing game between two people, one person asks another person to guess a whole number between a pair of values. In this example, two different classes take on the roles of the two people in the game: The SecretNumber class takes on the role of the person who has picked a value between some lower and upper limit, while the GuessingGame class takes on the role of the person who has to guess what that hidden number is.

Note: This class is already coded for you in the samples.

SecretNumber

Objects of this class will store a hidden value between some upper and lower limit (inclusive). The SecretNumber class supports three public methods:

GetLowerLimit() – Returns a number representing the lower end (inclusive) of the range of possible values for the hidden value.
GetUpperLimit() – Returns a number representing the upper end (inclusive) of the range of possible values for the hidden value.
Guess() – Returns true if the supplied value matches the hidden value, otherwise it returns false.

GuessingGame

This class simulates the action of guessing what hidden value is stored inside of a SecretNumber object. The SecretNumber is supplied to the constructor of the GuessingGame, and the following methods attempt to find out what that number is.

GuessNumber() – This first method simply tries to guess the hidden value of the SecretNumber. It has “unlimited” guesses, and it will return the number of attempts it took to find out what that hidden number is.
GuessNumber(MaxAttempts : Integer) – This method will also try to guess the SecretNumber’s hidden value, but it is limited to a maximum number of guesses. This method will return the actual number of attempts it took to find the hidden value, or it will return the GUESS_FAILED constant if it was unable to guess the secret number.

Try creating alternate versions of this GuessingGame that will use a while statement and a for statement in the GuessNumber methods.

 1 public class GuessingGame
 2 {
 3     private SecretNumber Number { get; set; }
 4     public const int GUESS_FAILED = -1;
 5 
 6     public GuessingGame(SecretNumber number)
 7     {
 8         if (number == null)
 9             throw new System.Exception("SecretNumber cannot be null");
10         this.Number = number;
11     }
12 
13     public int GuessNumber(int maxAttempts)
14     {
15         int numberOfAttempts = 0;
16         bool correct = false;
17         while (maxAttempts > 0 && !correct)
18         {
19             // Make a guess
20             int myBestGuess = Rnd.Next(Number.LowerLimit, Number.UpperLimit);
21             if (Number.Guess(myBestGuess))
22                 correct = true;
23             numberOfAttempts++;
24             maxAttempts--;
25         }
26         if (!correct)
27             numberOfAttempts = GUESS_FAILED; // a "flag" to say the guess was in\
28 correct
29         return numberOfAttempts;
30     }
31 
32     public int GuessNumber()
33     {
34         bool correct = false;
35         int numberOfAttempts = 0;
36         while (numberOfAttempts < int.MaxValue && !correct)
37         {
38             // Make a guess
39             int myBestGuess = Rnd.Next(Number.LowerLimit, Number.UpperLimit);
40             if (Number.Guess(myBestGuess))
41                 correct = true;
42             numberOfAttempts++;
43         }
44         if (!correct)
45             numberOfAttempts = GUESS_FAILED;
46         return numberOfAttempts;
47     }
48 }

Practice Exercises

Aggregator – countItems(), minValue()
Math – factorial(), isPrime(), power(), and greatestCommonDenominator()
GuessingGame – This example expands on the sample GuessingGame by 1) re-working the guess() method to make guessing more efficient by using the SecretNumber’s guessWithHint() method, and 2) overloading the guess() method to continue guessing until the correct answer is found (and returning the number of attempts it took to find the correct answer).

Aggregator

Expand on the sample Aggregator class to perform the following aggregations.

CountItems() – Return the count of the number of values in the Numbers object.
MinValue() – Return the smallest value in the set of values of the supplied Numbers object. If no values exist in the Numbers object, return the largest whole number supported by the programming language.

Math

Expand on the sample Math class by providing methods to perform the following.

Factorial() – Calculate the factorial of a given number. If the given number is negative, throw an exception. If the calculated value for the factorial will exceed the maximum integer value (int.MaxValue), then return zero (0) as a result.
IsPrime() – Identify if a number is or is not a prime number. A prime number is a number with only two divisors: 1 and the number itself. By definition for this problem, numbers less than one are not considered prime numbers.
Power() – Calculate the value of x to the power of y (as in xy). Use looping logic (addition) to get the result.
GreatestCommonDenominator() – Find the greatest common denominator between two whole numbers.

GuessingGame

This example expands on the sample GuessingGame by adding more guess methods to make guessing more efficient by using the SecretNumber’s guessWithHint() method.

SecretNumber

Objects of this class will store a hidden value between some upper and lower limit (inclusive). The SecretNumber class supports these public methods:

GetLowerLimit() – Returns a number representing the lower end (inclusive) of the range of possible values for the hidden value.
GetUpperLimit() – Returns a number representing the upper end (inclusive) of the range of possible values for the hidden value.
GuessWithHint() – Returns CORRECT if the supplied value matches the hidden value, otherwise it returns GUESS_HIGHER if the attempted guess was too low or GUESS_LOWER if the attempted guess was too high.

Note: This class is already coded for you in the samples.

GuessingGame

GuessUsingHints() – This first method simply tries to guess the hidden value of the SecretNumber. It has “unlimited” guesses, and it will return the number of attempts it took to find out what that hidden number is. Use the GuessWithHint method of the SecretNumber object.
GuessUsingHints(MaxAttempts : Integer) – This method will also try to guess the SecretNumber’s hidden value, but it is limited to a maximum number of guesses. This method will return the actual number of attempts it took to find the hidden value, or it will return the GUESS_FAILED constant if it was unable to guess the secret number. Use the GuessWithHint method of the SecretNumber object.
As an additional exercise, create a simple driver that instantiates a SecretNumber object and supplies it to a GuessingGame object. Show how many attempts it took to guess the hidden number when using hints.

Up next

Interlude 2 - A General-Purpose Driver