Transcript Chapter 4 Part 3

Chapter 4 Loops
Case Studies
Liang, Introduction to Programming with C++, Second Edition, (c) 2010 Pearson Education, Inc. All rights reserved. 10136097200
Problem:
Finding the Greatest Common Divisor
Problem: Write a program that prompts the user to enter two positive
integers and finds their greatest common divisor.
Solution: Suppose you enter two integers 4 and 2, their greatest
common divisor is 2. Suppose you enter two integers 16 and 24, their
greatest common divisor is 8. So, how do you find the greatest
common divisor? Let the two input integers be n1 and n2. You know
number 1 is a common divisor, but it may not be the greatest commons
divisor. 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.
GreatestCommonDivisor.cpp
Liang, Introduction to Programming with C++, Second Edition, (c) 2010 Pearson Education, Inc.
All rights reserved. 0136097200
2
Finding the Greatest Common Divisor
GreatestCommonDivisor.cpp
#include <iostream>
using namespace std;
int main()
{
// Prompt the user to enter two integers
cout << "Enter first integer: ";
int n1;
cin >> n1;
cout << "Enter second integer: ";
int n2;
cin >> n2;
Liang, Introduction to Programming with C++, Second Edition, (c) 2010 Pearson Education, Inc.
All rights reserved. 0136097200
3
Finding the Greatest Common Divisor
GreatestCommonDivisor.cpp
int gcd = 1;
int k = 1;
while (k <= n1 && k <= n2)
{
if (n1 % k == 0 && n2 % k == 0)
gcd = k;
k++;
}
cout << "The greatest common divisor for " << n1 << " and "
<< n2 << " is " << gcd<<endl;
system("PAUSE");
return 0;
}
Liang, Introduction to Programming with C++, Second Edition, (c) 2010 Pearson Education, Inc.
All rights reserved. 0136097200
4
Finding the Greatest Common Divisor
You could use for loop to rewrite the code as follows:
for(int k=1; k<=n1 && k<=n2 ; k++)
{
if (n1%k==0 && n2%k==0)
gcd=k;
}
Liang, Introduction to Programming with C++, Second Edition, (c) 2010 Pearson Education, Inc.
All rights reserved. 0136097200
5
Problem: Print Pyramid
Write a program that prompts the user to enter an integer from 1 to
15 and displays a pyramid. If the input integer is 12, for example, the
output is shown as follows:
PrintPyramid.cpp
Liang, Introduction to Programming with C++, Second Edition, (c) 2010 Pearson Education, Inc.
All rights reserved. 0136097200
6
Problem: Print Pyramid
PrintPyramid.cpp
Algorithm:
Input number0fLines;
for (int row; row<=number0fLines; row++)
{
print(number0fLines – row)*3 leading spaces;
print leading numbers row, row-1, …,1;
print ending numbers 2, 3, …,row-1,row;
}
Liang, Introduction to Programming with C++, Second Edition, (c) 2010 Pearson Education, Inc.
All rights reserved. 0136097200
7
Problem: Print Pyramid
PrintPyramid.cpp
#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
// Prompt the user to enter the number of lines
cout << "Enter the number of lines: ";
int numberOfLines;
cin >> numberOfLines;
if (numberOfLines < 1 || numberOfLines > 15)
{
cout << "You must enter a number from 1 to 15";
return 0;
}
Liang, Introduction to Programming with C++, Second Edition, (c) 2010 Pearson Education, Inc.
All rights reserved. 0136097200
8
// Print lines
for (int row = 1; row <= numberOfLines; row++)
{
// Print NUMBER_OF_LINES – row) leading spaces
for (int column = 1; column <= numberOfLines - row; column++)
cout << " ";
// Print leading numbers row, row – 1, ..., 1
for (int num = row; num >= 1; num--)
cout << setw(3) << num;
// Print ending numbers 2, 3, ..., row – 1, row
for (int num = 2; num <= row; num++)
cout << setw(3) << num;
// Start a new line
cout << endl;
PrintPyramid.cpp
}
return 0; }
Liang, Introduction to Programming with C++, Second Edition, (c) 2010 Pearson Education, Inc.
All rights reserved. 0136097200
9
Problem: Displaying Prime Numbers
Problem: Write a program that displays the first 50 prime numbers
in five lines, each of which contains 10 numbers. An integer
greater than 1 is prime if its only positive divisor is 1 or itself. For
example, 2, 3, 5, and 7 are prime numbers, but 4, 6, 8, and 9 are
not.
PrimeNumber.cpp
Liang, Introduction to Programming with C++, Second Edition, (c) 2010 Pearson Education, Inc.
All rights reserved. 0136097200
10
Displaying Prime Numbers
PrimeNumber.cpp
#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
const int NUMBER_OF_PRIMES = 50; // Number of primes to display
const int NUMBER_OF_PRIMES_PER_LINE = 10; // Display 10 per line
int count = 0; // Count the number of prime numbers
int number = 2; // A number to be tested for primeness
cout << "The first 50 prime numbers are \n";
Liang, Introduction to Programming with C++, Second Edition, (c) 2010 Pearson Education, Inc.
All rights reserved. 0136097200
11
Displaying Prime Numbers
PrimeNumber.cpp
// Repeatedly find prime numbers
while (count < NUMBER_OF_PRIMES)
{
// Assume the number is prime
bool isPrime = true; // Is the current number prime?
// Test if number is prime
for (int divisor = 2; divisor <= number / 2; divisor++)
{
if (number % divisor == 0)
{
// If true, the number is not prime
isPrime = false; // Set isPrime to false
break; // Exit the for loop
}
}
Liang, Introduction to Programming with C++, Second Edition, (c) 2010 Pearson Education, Inc.
All rights reserved. 0136097200
12
// Print the prime number and increase the count
if (isPrime)
PrimeNumber.cpp
{
count++; // Increase the count
if (count % NUMBER_OF_PRIMES_PER_LINE == 0)
{
// Print the number and advance to the new line
cout << setw(4)<< number << endl;
}
else
cout << setw(4)<< number << " ";
}
// Check if the next number is prime
number++;
} // brace of while loop
system("PAUSE");
return 0;}
Liang, Introduction to Programming with C++, Second Edition, (c) 2010 Pearson Education, Inc.
All rights reserved. 0136097200
13
Displaying Prime Numbers
PrimeNumber.cpp
Liang, Introduction to Programming with C++, Second Edition, (c) 2010 Pearson Education, Inc.
All rights reserved. 0136097200
14