Loops are fundamental in programming. The ability to write loops is essential in learning programming.
If you can write programs using loops, you know how to program! For this reason, this section presents four additional examples of solving problems using loops.
1. Case Study: Finding the Greatest Common Divisor
The greatest common divisor (GCD) of the two integers 4 and 2 is 2. The GCD of the two GCD integers 16 and 24 is 8. How do you determine the GCD? Let the two input integers be n1 and n2 . You know that number 1 is a common divisor, but it may not be the greatest one. So, you can check whether k (for k = 2, 3, 4, and so on) is a common divisor for n1 and n2, until k is greater than n1 or n2. Store the common divisor in a variable named gcd. Initially, gcd is 1. Whenever a new common divisor is found, it becomes the new GCD. When you have checked all the possible common divisors from 2 up to n1 or n2, the value in variable gcd is the GCD. The idea can be translated into the following loop:
int gcd = 1; // Initial gcd is 1
int k = 2; // Possible gcd
while (k <= n1 && k <= n2)
{
if (n1 % k == 0 && n2 % k == 0)
gcd = k; // Update gcd
k++; // Next possible gcd
}
// After the loop, gcd is the greatest common divisor for n1 and n2
Listing 5.10 presents the program that prompts the user to enter two positive integers and finds their GCD.
Listing 5.10 GreatestCommonDivisor.cpp
1 #include <iostream>
2 using namespace std;
3
4 int main()
5 {
6 // Prompt the user to enter two integers
7 cout << “Enter first integer: “;
8 int n1;
9 cin >> n1;
10
11 cout << “Enter second integer: “;
12 int n2;
13 cin >> n2;
14
15 int gcd = 1;
16 int k = 2;
17 while (k <= n1 && k <= n2)
18 {
19 if (n1 % k == 0 && n2 % k == 0)
20 gcd = k;
21 k++;
22 }
23
24 cout << “The greatest common divisor for ” << n1 << ” and “
25 << n2 << ” is ” << gcd << endl;
26
27 return 0;
28 }
How would you write this program? Would you immediately begin to write the code? No. It is important to think before you type. Thinking enables you to generate a logical solution for the problem before writing the code. Once you have a logical solution, type the code to translate the solution into a program. The translation is not unique. For example, you could use a for loop to rewrite the code as follows:
for (int k = 2; k <= n1 && k <= n2; k++)
{
if (n1 % k == 0 && n2 % k == 0)
gcd = k;
}
A problem often has multiple solutions, and the gcd problem can be solved in many ways. Programming Exercise 5.16 suggests another solution. A more efficient solution is to use the classic Euclidean algorithm (see www.cut-the-knot.org/blue/Euclid.shtml for more information).
You might think that a divisor for a number n1 cannot be greater than n1 / 2, prompting you to try to improve the program using the following loop:
for (int k = 2; k <= n1 / 2 && k <= n2 / 2; k++)
{
if (n1 % k == 0 && n2 % k == 0)
gcd = k;
}
This revision is wrong. Can you find the reason? See Check Point 5.23 for the answer.
2. Case Study: Predicting the Future Tuition
Suppose that the tuition for a university is $10,000 this year and tuition increases 7% every year. In how many years will the tuition be doubled?
Before you can write a program to solve this problem, first consider how to solve it by hand. The tuition for the second year is the tuition for the first year * 1.07. The tuition for a future year is the tuition of its preceding year * 1.07. Thus, the tuition for each year can be computed as follows:
double tuition = 10000; int year = 0; // Year 0
tuition = tuition * 1.07; year++; // Year 1
tuition = tuition * 1.07; year++; // Year 2
tuition = tuition * 1.07; year++; // Year 3
…
Keep computing the tuition for a new year until it is at least 20000. By then you will know how many years it will take for the tuition to be doubled. You can now translate the logic into the following loop:
double tuition = 10000; // Year 0
int year = 0;
while (tuition < 20000)
{
tuition = tuition * 1.07;
year++;
}
The complete program is shown in Listing 5.11.
Listing 5.11 FutureTuition.cpp
1 #include <iostream>
2 #include <iomanip>
3 using namespace std;
4
5 int main()
6 {
7 double tuition = 10000; // Year 1
8 int year = 1;
9 while (tuition < 20000)
10 {
11 tuition = tuition * 1.07;
12 year++;
13 }
14
15 cout << “Tuition will be doubled in ” << year << ” years” << endl;
16 cout << setprecision(2) << fixed << showpoint <<
17 “Tuition will be $” << tuition << ” in “
18 << year << ” years” << endl;
19
20 return 0;
21 }
The while loop (lines 9-13) is used to repeatedly compute the tuition for a new year. The loop terminates when tuition is greater than or equal to 20000.
3. Case Study: Monte Carlo Simulation
Monte Carlo simulation uses random numbers and probability to solve problems. This method has a wide range of applications in computational mathematics, physics, chemistry, and finance. This section gives an example of using Monte Carlo simulation for estimating π.
To estimate π using the Monte Carlo method, draw a circle with its bounding square as shown below:
Assume the radius of the circle is 1. Therefore, the circle area is p and the square area is 4. Randomly generate a point in the square. The probability for the point to fall in the circle is circleArea / squareArea =π / 4.
Write a program that randomly generates 1,000,000 points in the square and let numberOfHits denote the number of points that fall in the circle. Thus, numberOfHits is approximately 1000000 * (π / 4). p can be approximated as 4 * numberOfHits / 1000000. The complete program is shown in Listing 5.12.
Listing 5.12 MonteCarloSimulation.cpp
1 #include <iostream>
2 #include <cstdlib>
3 #include <ctime>
4 using namespace std;
5
6 int main()
7 {
8 const int NUMBER_OF_TRIALS = 1000000;
9 int numberOfHits = 0;
10 srand(time(0));
11
12 for (int i = 0; i < NUMBER_OF_TRIALS; i++)
13 {
14 double x = rand() * 2.0 / RAND_MAX – 1;
15 double y = rand() * 2.0 / RAND_MAX – 1;
16 if (x * x + y * y <= 1)
17 numberOfHits++;
18 }
19
20 double pi = 4.0 * numberOfHits / NUMBER_OF_TRIALS;
21 cout << “PI is ” << pi << endl;
22
23 return 0;
24 }
The program repeatedly generates a random point (x, y) in the square in lines 14-15. Note that RAND_MAX is the maximum number that may be returned from invoking the rand() function. So, rand() * 1.0 / RAND_MAX is a random number between 0.0 and 1.0, and 2.0 * rand() / RAND_MAX is a random number between 0.0 and 2.0. Therefore, 2.0 * rand() / RAND_MAX – 1 is a random number between -1.0 and 1.0.
If x2 + y2 < 1, the point is inside the circle and numberOfHits is incremented by 1. p is approximately 4 * numberOfHits / NUMBER_OF_TRIALS (line 20).
4. Case Study: Converting Decimals to Hexadecimals
Hexadecimals are often used in computer systems programming (see Appendix D for an introduction to number systems). How do you convert a decimal number to a hexadecimal number? To convert a decimal number d to a hexadecimal number is to find the hexadecimal digits hn, hn-1, hn–2, … , h2, h1, and h0 such that
d = hn X 16n + hn -1 X 16n –1 + hn – 2 X 16n – 2 + …
+ h2 X 162 + hi X 161 + h0 X 160
These hexadecimal digits can be found by successively dividing d by 16 until the quotient is 0. The remainders are h0, h1, h2, … , hn–2, hn–1, and hn. The hexadecimal digits include the decimal digits 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9, plus A, which is the decimal value 10; B, which is the decimal value 11; C, which is 12; D, which is 13; E, which is 14; and F, which is 15.
For example, the decimal number 123 is 7B in hexadecimal. The conversion is done as follows. Divide 123 by 16. The remainder is 11 (B in hexadecimal) and the quotient is 7. Continue divide 7 by 16. The remainder is 7 and the quotient is 0. Therefore, 7B is the hexadecimal number for 123 .
Listing 5.13 gives a program that prompts the user to enter a decimal number and converts it into a hex number as a string.
Listing 5.13 Dec2Hex.cpp
1 #include <iostream>
2 #include <string>
3 using namespace std;
4
5 int main()
6 {
7 // Prompt the user to enter a decimal integer
8 cout << “Enter a decimal number: “;
9 int decimal;
10 cin >> decimal;
11
12 // Convert decimal to hex
13 string hex = “”;
14
15 while (decimal != 0)
16 {
17 int hexValue = decimal % 16;
18
19 // Convert a decimal value to a hex digit
20 char hexChar = (hexValue <= 9 && hexValue >= 0) ?
21 static_cast<char>(hexValue + ‘0’) :
22 static_cast<char>(hexValue – 10 + ‘A’);
23
24 hex = hexChar + hex;
25 decimal = decimal / 16;
26 }
27
28 cout << “The hex number is ” << hex << endl;
29
30 return 0;
31 }
The program prompts the user to enter a decimal integer (line 10), converts it to a hex number as a string (lines 13-26), and displays the result (line 28). To convert a decimal to a hex number, the program uses a loop to successively divide the decimal number by 16 and obtain its remainder (line 17). The remainder is converted into a hex character (lines 20-22). The character is then appended to the hex string (line 24). The hex string is initially empty (line 13). Divide the decimal number by 16 to remove a hex digit from the number (line 25). The loop ends when the remaining decimal number becomes 0.
The program converts a hexValue between 0 and 15 into a hex character. If hexValue is between 0 and 9, it is converted to static_cast<char>(hexValue + ‘0’) (line 21). Recall that when adding a character with an integer, the character’s ASCII code is used in the evaluation. For example, if hexValue is 5, static_cast<char>(hexValue + ‘0’) returns character 5 (line 21). Similarly, if hexValue is between 10 and 15, it is converted to static_cast<char>(hexValue – 10 + ‘A’) (line 22). For instance, if hexValue is 11, static_cast<char>(hexValue – 10 + ‘A’) returns character B.
Source: Liang Y. Daniel (2013), Introduction to programming with C++, Pearson; 3rd edition.