Exercise 2-8
Write a program to generate the product of the numbers in the range [1,10).
Solution
The question asks as to compute the product of the numbers within the asymmetric range [1,10). In other words, the product of numbers within the range of 1 to 10, excluding 10. i.e.
1 x 2 x 3 ... x 7 x 8 x 9
Observation: this is the same as 9 factorial (9!). This is the same logic as computing n factorial.
Here outlines my solution strategy at the top level.
Descriptions:
- Fact: the product of 3 x 4 x 5 (ascending syntax) is the same as 5 x 4 x 3 (descending syntax). So for simplicity, we restrict ourself by only writing in an ascending syntax. i.e. use [3,6), and avoid [5,1) . This is the same as making the assumption of n >= m.
- Fact: Case 1, if (n-m)=0, e.g. the asymmetric range is [3,3), this is equivalent of saying the range is between 3 and 3 (excluding 3). Because this range is null, the product is also null (zero). No loops required.
- Fact: Case 2, if (n-m)=1, e.g. the asymmetric range is [3,4), this is equivalent of saying the range is between 3 and 4 (excluding 4). The range is therefore just the number 3 (i.e. m). Likewise, the product is also 3 (i.e. m). No loops required.
- Fact: Case 3, if (n-m)>=1, e.g. the asymmetric range is [3,7), this is equivalent of saying the range is between 3 and 7 (excluding 7). i.e. we are looking for the product of 3 x 4 x 5 x 6. To compute this we must use loops. The main focus of this post is case 3.
Case 3 Solution Strategy
After spending an entire Sunday afternoon on this question, I eventually spotted a pattern which I believe is consistent and can be leveraged in the forming of our algorithm. To demonstrate this pattern, I have put together some diagrams in PowerPoint and presented as snapshot images below. For clarity, we are going to focus on this particular (arbitrary) asymmetric range as our core example: [3, 7).
Observations:
- The number of elements is always (n-m). there are 4 elements in this case.
- The number of loops required is always (n-m-1). We need 3 loops in this case. (numLoops = 3).
- The number of loops required also equals to the number of (multiplication) operator.
- Knowing the number of loops required enable us to form the loop invariant i [0,numLoops).
Now, let’s try and observe more patterns – what happens at each loop? (See diagram below)
Observations:
- 4 major variables are required.
- The integer invariant i that controls whether the loop is to go ahead or terminate.
- The integer variable a – the lower number of the product (a x b).
- The integer variable b – the higher number of the product (a x b).
- The integer variable c – the product of (a x b).
- At the beginning of the very first loop, initialise values of a and b.
- At the end of each loop, the re-initialise values of a and b.
The final product of [m,n) is the value of c at the end of the very last loop.
For completeness, let’s do a drill down into the loops in greater depth. Bear in mind that for [3,7), the numLoops is n-m-1=3. We need 3 loops. The loop go ahead if the invariant i has not reached numLoops – it starts at 0 (zero), and get increment by 1 at end of each loop.
Invariant i = 0 (Loop)
Invariant i = 1 (Loop)
Invariant i = 2 (Loop)
Invariant i = 3 (No Loop)
At the end of the loop, output the final result. The product of the numbers within the asymmetric range [m,n) is the value of c at the end of the very last loop. The following table summarises this looping process.
| Invariant i |
a |
b |
c |
| 0 |
3 |
4 |
12 |
| 1 |
12 |
5 |
60 |
| 2 |
60 |
6 |
360 |
Full Program
We should now have all the fundamentals in the making of our program. This is my version of the program. (There are many ways to do this however!)
#include <iostream>
using namespace std;
int main()
{
cout << "***********************************************************\n"
<< "*** This program computes the product of the numbers ***\n"
<< "*** in the asymmetric range [m,n). ***\n"
<< "*** (Limitation: please ensure m is not larger than n) ***\n"
<< "*** e.g. [3,7) contains elements 3, 4, 5, 6 (but not 7) ***\n"
<< "***********************************************************";
cout << endl;
// Ask user to supply the startNumber
cout << "Enter m: ";
int m;
cin >> m;
// Ask user to supply the endNumber
cout << "Enter n: ";
int n;
cin >> n;
// Algorithm to compute the product of numbers within the asymmetric range [m,n)
const int startNumber = m ;
const int endNumber = n;
const int numElements = endNumber - startNumber;
const int numLoops = numElements - 1;
int c;
if (numElements == 0)
{c = 0;}
else if (numElements == 1)
{c = startNumber;}
else
{
int a = startNumber;
int b = startNumber + 1;
cout << " i, a, b, c " << endl;
for (int i = 0; i != numLoops; ++i)
{
c = a * b;
cout << i << ", " << a << ", " << b << ", " << c << endl;
a = c;
++b;
}
}
cout << "Asymmetric range: [" << startNumber << "," << endNumber << ")" << endl;
cout << "Number of elements: " << numElements << endl;
cout << "Number of loops required: " << numLoops << endl;
cout << "Product of numbers within the asymmetric range = " << c << endl;
return 0;
}
Result
The program is meant to be robust and be able to deal with any asymmetric range [m,n) as long as (n>=m). Case 1-3 are mainly for prove of concepts. Case 4 is the solution to the question (find product of numbers within the range [1,10).
- Case 1 – when (n-m)=0. e.g. [3,3)
- Case 2 – when (n-m)=1. e.g. [3,4)
- Case 3 – when (n-m)>1. e.g. [3,7)
- Case 4 – when (n-m)>1. e.g. [1,10)
Case 1 – Asymmetric Range [3,3)
***********************************************************
*** This program computes the product of the numbers ***
*** in the asymmetric range [m,n). ***
*** (Limitation: please ensure m is not larger than n) ***
*** e.g. [3,7) contains elements 3, 4, 5, 6 (but not 7) ***
***********************************************************
Enter m: 3
Enter n: 3
Asymmetric range: [3,3)
Number of elements: 0
Number of loops required: 0
Product of numbers within the asymmetric range = 0
Case 2 – Asymmetric Range [3,4)
***********************************************************
*** This program computes the product of the numbers ***
*** in the asymmetric range [m,n). ***
*** (Limitation: please ensure m is not larger than n) ***
*** e.g. [3,7) contains elements 3, 4, 5, 6 (but not 7) ***
***********************************************************
Enter m: 3
Enter n: 4
Asymmetric range: [3,4)
Number of elements: 1
Number of loops required: 0
Product of numbers within the asymmetric range = 3
Case 3 – Asymmetric Range [3,7)
***********************************************************
*** This program computes the product of the numbers ***
*** in the asymmetric range [m,n). ***
*** (Limitation: please ensure m is not larger than n) ***
*** e.g. [3,7) contains elements 3, 4, 5, 6 (but not 7) ***
***********************************************************
Enter m: 3
Enter n: 7
i, a, b, c
0, 3, 4, 12
1, 12, 5, 60
2, 60, 6, 360
Asymmetric range: [3,7)
Number of elements: 4
Number of loops required: 3
Product of numbers within the asymmetric range = 360
Case 4- Asymmetric Range [1,10)
***********************************************************
*** This program computes the product of the numbers ***
*** in the asymmetric range [m,n). ***
*** (Limitation: please ensure m is not larger than n) ***
*** e.g. [3,7) contains elements 3, 4, 5, 6 (but not 7) ***
***********************************************************
Enter m: 1
Enter n: 10
i, a, b, c
0, 1, 2, 2
1, 2, 3, 6
2, 6, 4, 24
3, 24, 5, 120
4, 120, 6, 720
5, 720, 7, 5040
6, 5040, 8, 40320
7, 40320, 9, 362880
Asymmetric range: [1,10)
Number of elements: 9
Number of loops required: 8
Product of numbers within the asymmetric range = 362880
Compute the N factorial
Note that this program may also be used as a skeleton program for computing factorial. e.g. 5! = 1 x 2 x 3 x 4 x 5. In other words, to compute n! this is effectively the same as computing the internal product of the numbers within the asymmetric range (0, n+1).
Conclusion
The product of the numbers within the asymmetric range [0,10) is 362880, as computed by the program (and verified by calculators). This program might also be used as a skeleton program for computing factorial.
Reference
Koenig, Andrew & Moo, Barbara E., Accelerated C++, Addison-Wesley, 2000
