An insightful YouTube video explaining the idea of factorial, zero factorial, and in-between factorial.
Tag Archives: Mathematics
Accelerated C++ Solution to Exercise 3-2
Exercise 3-2
Write a program to compute and print the quartiles (that is, the quarter of the numbers with the largest values, the next highest quarter, and so on) of a set of integers.
Solution
According to this Wikipedia page, for discrete distributions, there is no universal agreement on selecting the quartiles values – there are 3 major computing methods.
I will apply Method 1 in my solution which has the following definitions:
- Use the median to divide the ordered data set into two halves. Do not include the median in either half.
- The lower quartile value is the median of the lower half of the data. The upper quartile value is the median of the upper half of the data.
This rule is employed by the TI-83 calculator boxplot and “1-Var Stats” functions (according to Wikipedia)
It is also very important to note that there are two types of medians:
- Datum median – the middle data point of an ordered vector.
- Non-datum median – the mean of the middle two data points of an ordered dataset.
The computation of the lower quartile, median, and upper quartile can be either a datum or non-datum. It depends on the dataset dataset pattern which I shall expand on more shortly.
The 6 distinctive dataset patterns
After 3 hours of sketching and iterations, I am pleased to say that I have found “the dataset pattern” which I believe is consistent for all types of input datasets, and robust to implement. I summarise this pattern in the following table:
ID | Pattern | Condition | Quartiles (Q1, Q2, Q3) |
1 | NULL dataset | N = 0 | (Cannot compute) |
2 | 1 Number only | N = 1 | Quartiles all resolve to that 1 number provided. |
3 | Datum Profile [0 0 0] | N % 4 == 0 | |
4 | Datum Profile [0 1 0] | N % 4 == 1 | |
5 | Datum Profile [1 0 1] | N % 4 == 2 | |
6 | Datum Profile [1 1 1] | N % 4 == 3 |
Note
- I use Q1, Q2, and Q3 to denote Quartile 1, 2, and 3. (i.e. end of quarter 1, 2, and 3)
- If the dataset is empty (Null), it is not possible to compute the quartiles for that dataset.
- If the dataset contains only 1 number, it is quite natural to assume that there is no variation (or no range). i.e. all quartiles correspond to that number.
- If there are at least 2 numbers provided, the pattern is determined by the Datum Profile [Q1 Q2 Q3]. There are four possible types of Datum Profiles: [0 0 0], [0 1 0], [1 0 1], and [1 1 1].
- For example, a datum profile of [1 0 1] means: lower quartile is a datum, median is a non-datum, upper quartile is a datum. i.e. 1 represents datum. 0 represents non-datum.
- N is the total number of elements within the dataset.
- The % (percent) sign is used to compute remainder. e.g. N % 4 gives the remainder of N divided by 4.
Nomenclature
I use the following short-form letters to make the formula easier to understand, and program easier to code.
Symbol | Meaning |
v | Represents the vector. e.g. v[M] resolves the value of the element locating at index M of the vector v. |
N | Number of elements of the vector (i.e. the input dataset) |
ML | An index value for computing the lower quartile. (Think Median of the Lower-halve). |
M | An index value for computing the median. |
MU | An index value for computing the upper quartile. (Think Median of the Upper-halve). |
ml | The computed value of lower quartile. |
m | The computed value of median |
mu | The computed value of upper quartile. |
Solution Strategy
At a high level, this is what the program should do:
- Read the list of numbers from the user and store in a vector.
- Pattern 1: If vector contains no elements (i.e. NULL), output an error message (mentioning the program requires at least 1 number to compute quartiles), then exit the program peacefully.
- Pattern 2: If vector contains just 1 number, output a message saying that all quartiles values are the same as that number provided, then exit the program peacefully.
- Sort the vector so it become non-descending – this is required for the median computation.
- Determine whether the dataset belongs to pattern 3, 4, 5, or 6, execute the corresponding algorithms, display the quartile summary at the end.
Before walking through this solution strategy I think it is worth expand a bit more on how I derive the algorithms for pattern 3, 4, 5, and 6 in the first place.
Derivation of Algorithms
Pattern 1 (null dataset) and patter 2 (1 number only) are very straight forward and have already been explained above. So I’m not going to expand further on these first two patterns.
Pattern 3, 4, 5 and 6, however, are much more interesting in comparison. These patterns require a bit more intelligence to solve – so I will focus on these one-by-one and summarise this at the end.
The Repeating Cycles
The first thing that I did in terms of trying to spot a pattern was to sketch out around a number vectors with sizes ranging from N=2 to N=11 (could have been more but the patter had become quite obvious at that point!), circle out the datum profile, and hope to see some sort of pattern. Through the exercise I observed that the datum profile changes every time I increase N by 1. I also observed the profile change follows a cycle of 4 increments. e.g. the profile is the same at N=2, N=6, N=10, etc…. The following table is that “sketch” that I produced which led me to the discovery of algorithms.
N | N % 4 | Profile | Sketch |
2 | 2 | [101] | |
3 | 3 | [111] | |
4 | 0 | [000] | |
5 | 1 | [010] | |
6 | 2 | [101] | |
7 | 3 | [111] | |
8 | 0 | [000] | |
9 | 1 | [010] | |
10 | 2 | [101] | |
11 | 3 | [111] |
The pattern can therefore be summarised as follows:
Pattern ID | Datum Profile | N % 4 |
3 | [000] | 0 |
4 | [010] | 1 |
5 | [101] | 2 |
6 | [111] | 3 |
We now have this core table, let’s derive the equations.
Equations and Examples
These diagrams summarise the equations, examples, and code implementations for each of the four datum patterns.
Profile [000] – Equations and Examples
Profile [010] – Equations and Examples
Profile [101] – Equations and Examples
Profile [111] – Equations and Examples
The Program
Now that we have our algorithms, let’s put everything together into a final program. I am purely using the skeleton program from chapter 3 of the book (which has an in-depth explanation of the various components). I merely implement the algorithms into this skeleton program, with some extra enhancements for user-friendly output.
#include <algorithm> #include <iomanip> #include <ios> #include <iostream> #include <string> #include <vector> using std::cin; // <iostream> using std::cout; // <iostream> using std::endl; // <iostream> using std::setprecision; // <iomanip> using std::sort; // <algorithm> using std::streamsize; // <ios> using std::string; // <string> using std::vector; // <string> int main() { // display header message cout << "***************************************************************\n" "*** This program computes quartiles given a list of numbers ***\n" "***************************************************************\n"; cout << endl; // ask for a list of numbers and store the list as a vector cout << "Enter all a list of numbers: "; vector<double> v; double x; while (cin >> x) v.push_back(x); // check vector size and action accordingly cout << endl; typedef vector<double>::size_type vecSize; vecSize N = v.size(); if (N ==0 ) { cout << "You must enter some numbers! " << endl; return 1; } else if (N ==1 ) { cout << " Only 1 number supplied. Q1, Q2, and Q3 all equate to " << v[0] << endl; return 0; } else { // sort the homework grades; sort(v.begin(),v.end()); } // declare new variables vecSize NMod4 = (N % 4); // identification of 1 of the 4 known datum distribution profiles string datumDistr = ""; // datum distribution profile vecSize M, ML, MU; // core vector indices for quartile computation double m, ml, mu; // quartile values are store here // compute quartiles for the 4 known patterns if ( NMod4 == 0 ) { // Q1-Q3 datum distribution: [0 0 0] datumDistr = "[0 0 0]"; M = N / 2; ML = M / 2; MU = M + ML; // grab quartile values ml= (v[ML] + v[ML-1]) / 2; // datum: 0 m = (v[M] + v[M-1]) / 2; // datum: 0 mu = (v[MU] + v[MU-1]) / 2; // datum: 0 } else if ( NMod4 == 1 ) { // Q1-Q3 datum distribution: [0 1 0] datumDistr = "[0 1 0]"; M = N / 2; ML = M / 2; MU = M + ML + 1; // grab quartile values datumDistr = "[0 0 0]"; ml= (v[ML] + v[ML-1]) / 2; // datum: 0 m = v[M]; // datum: 1 mu = (v[MU] + v[MU-1]) / 2; // datum: 0 } else if ( NMod4 == 2 ) { // Q1-Q3 datum distribution: [1 0 1] datumDistr = "[1 0 1]"; M = N / 2; ML = M / 2; MU = M + ML; // grab quartile values ml= v[ML]; // datum: 1 m = (v[M] + v[M-1]) / 2; // datum: 0 mu = v[MU]; // datum: 1 } else if ( NMod4 == 3 ) { // Q1-Q3 datum distribution: [1 1 1] datumDistr = "[1 1 1]"; M = N / 2; ML = M / 2; MU = M + ML + 1; // grab quartile values ml= v[ML]; // datum: 1 m = v[M]; // datum: 0 mu = v[MU]; // datum: 1 } else { cout << "Unknown pattern discovered - new algorithm may be required."; } // Display results streamsize prec = cout.precision(); cout << "Display the sorted (non-descending) vector below." << endl; cout << "Index: Number" << endl; for (vecSize i = 0; i != N; ++i) { cout << i << ": " << v[i] << endl; } cout << endl; cout << "Vector size: " << N << endl; cout << "Datum Distribution: " << datumDistr << endl; cout << setprecision(3) << endl << " Q1: " << ml << endl << " Q2: " << m << endl << " Q3: " << mu << endl << setprecision(prec); }
Result
i’m going to run the program a number of times – each with different input dataset. (e.g. incrementing N by 1, try out the Wikipedia example and compare, etc.)
N = 0
*************************************************************** *** This program computes quartiles given a list of numbers *** *************************************************************** Enter all a list of numbers: ^Z You must enter some numbers! Process returned 1 (0x1) execution time : 9.804 s
N = 1
*************************************************************** *** This program computes quartiles given a list of numbers *** *************************************************************** Enter all a list of numbers: 5 ^Z Only 1 number supplied. Q1, Q2, and Q3 all equate to 5 Process returned 0 (0x0) execution time : 8.430 s
N = 2
*************************************************************** *** This program computes quartiles given a list of numbers *** *************************************************************** Enter all a list of numbers: 10 20 ^Z Display the sorted (non-descending) vector below. Index: Number 0: 10 1: 20 Vector size: 2 Datum Distribution: [1 0 1] Q1: 10 Q2: 15 Q3: 20
N = 3
*************************************************************** *** This program computes quartiles given a list of numbers *** *************************************************************** Enter all a list of numbers: 10 20 30 ^Z Display the sorted (non-descending) vector below. Index: Number 0: 10 1: 20 2: 30 Vector size: 3 Datum Distribution: [1 1 1] Q1: 10 Q2: 20 Q3: 30
N = 4
*************************************************************** *** This program computes quartiles given a list of numbers *** *************************************************************** Enter all a list of numbers: 6 2 4 9 ^Z Display the sorted (non-descending) vector below. Index: Number 0: 2 1: 4 2: 6 3: 9 Vector size: 4 Datum Distribution: [0 0 0] Q1: 3 Q2: 5 Q3: 7.5
N = 5
Enter all a list of numbers: 9 4 20 39 44 ^Z Display the sorted (non-descending) vector below. Index: Number 0: 4 1: 9 2: 20 3: 39 4: 44 Vector size: 5 Datum Distribution: [0 0 0] Q1: 6.5 Q2: 20 Q3: 41.5
Wikipedia example (even size vector)
The results match!
************************************************************** *** This program computes quartiles given a list of numbers ** ************************************************************** Enter all a list of numbers: 41 39 15 7 36 40 ^Z Display the sorted (non-descending) vector below. Index: Number 0: 7 1: 15 2: 36 3: 39 4: 40 5: 41 Vector size: 6 Datum Distribution: [1 0 1] Q1: 15 Q2: 37.5 Q3: 40
Wikipedia example (odd size vector)
The results match!
*************************************************************** *** This program computes quartiles given a list of numbers *** *************************************************************** Enter all a list of numbers: 49 43 41 39 15 6 7 36 40 42 47 ^Z Display the sorted (non-descending) vector below. Index: Number 0: 6 1: 7 2: 15 3: 36 4: 39 5: 40 6: 41 7: 42 8: 43 9: 47 10: 49 Vector size: 11 Datum Distribution: [1 1 1] Q1: 15 Q2: 40 Q3: 43
Reference
Koenig, Andrew & Moo, Barbara E., Accelerated C++, Addison-Wesley, 2000Accelerated C++ Solution to Exercise 3-1
Exercise 3-1
Suppose we wish to find the median of a collection of values. Assume that the we have read some values so far, and that we have no idea how many values remain to be read. Prove that we cannot afford to discard any of the values that we have read. Hint: One proof strategy is to assume that we can discard a value, and then find values for the unread–and therefore unknown–part of our collection that would cause the median to be the value that we discarded.
Solution
I must admit that I find this question very difficult to understand. When I first read it I wasn’t sure whether it is meant to be a very simple and straight forward question, or some kind of trick question which has a definite answer.
I decided to google this and found this very interesting forum on this topic (including some comments from the original author A.Koenig!). After spending an hour going through the thread I decided the question and answer might get a bit too mathematical / theatrical, which I am not prepared to spend my next hours or days researching it. For this reason, I will stick to my motto KISS – Keep It Simple and Stupid. i.e. I will just give a couple of examples showing that, the true median value of a full set “without discarding” may be different to the (distorted) median of the same full set “with discarding“. Hence demonstrating why we cannot afford to discard any numbers.
Example 1
Assume we have read the numbers 1, 2, 3, 4 so far, and imagine that the next number is 5.
Scenario | The eventual “full set” | The Median | Observation |
No Discarding | 1, 2, 3, 4, 5 | 3 | True median |
We discard 1 | 2, 3, 4, 5 | 3.5 | Larger than true median |
We discard 2 | 1, 3, 4, 5 | 3.5 | Larger than true median |
We discard 3 | 1, 2, 4, 5 | 3 | Identical to true median |
We discard 4 | 1, 2, 3, 5 | 2.5 | Smaller than true median |
Example 2
Assume we have read the numbers 1, 2, 3, 4 so far, and imagine that the next number is 5, 6.
Scenario | The eventual “full set” | The Median | Observation |
No Discarding | 1, 2, 3, 4, 5, 6 | 3.5 | True median |
We discard 1 | 2, 3, 4, 5, 6 | 4 | Larger than true median |
We discard 2 | 1, 3, 4, 5, 6 | 4 | Larger than true median |
We discard 3 | 1, 2, 4, 5, 6 | 4 | Larger than true median |
We discard 4 | 1, 2, 3, 5, 6 | 3 | Smaller than true median |
Conclusion
The two examples above have demonstrated that we cannot afford to discard any numbers from the number set, should we wish to identify the true median. By discarding any numbers from the (read) set, we essentially distort the median.
Reference
Koenig, Andrew & Moo, Barbara E., Accelerated C++, Addison-Wesley, 2000Accelerated C++ Solution to Exercise 2-8
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, 2000Accelerated C++ Solution to Exercise 2-5
Exercise 2-5
Write the set of “*” characters so that they form a square, a rectangle, and a triangle.
Solution
This is a fun one! To make this an even more interesting problem to solve, I’m going to add one more requirement – hollow and solid shapes. This diagram outlines my solution strategy:
In this post I will:
- Walk through the solution strategy step-by-step, with explanation of the code snippets that I have created using logics.
- Put all the snippets together and form one complete program.
- Run the complete program and record the results – seeing is believing!
I will start from step one of my solution strategy.
1 – Choose Shape Type
The program first asks the user to select the int inputShapeType 1 (Square), 2 (Rectangle), or 3 (Triangle). This is stored as the const int shapeType which has global scope. I’ve also added a for loop for the extra effect that, in the case that the user type in a number outside the selected range (e.g. 9), the program would keep re-asking the question until the user eventually type in the valid range of 1, 2, or 3. Note that if we really want we could add extra controls such as preventing the user from entering letters (instead of numbers). But for the sake of this exercise.
// ask for the Shape Type int inputShapeType; for (int keepAsking = 1; keepAsking == 1; ) { cout << "Select the Shape Type." << endl; cout << " (1) - Square " << endl; cout << " (2) - Rectangle " << endl; cout << " (3) - Triangle " << endl; cout << "Shape Type (enter 1/2/3): "; cin >> inputShapeType; // Make sure the user input is within range. If not, ask again! if (inputShapeType == 1 || inputShapeType == 2 || inputShapeType == 3) {keepAsking = 0;} } const int shapeType = inputShapeType;
2 – Define Shape Height
We ask the user to supply the desirable height (in number of columns). This integer height is stored as a int const numRows and has global scope.
// ask for the shape height cout << "Enter Shape Height: "; int shapeHeight; cin >> shapeHeight; // set the total number of rows to write (as a constant) int const numRows = shapeHeight;
3 – Define or Compute Shape Width
- If the shape is a square, the width is computed as the same as height.
- If the shape is a rectangle, the user will need to explicitly supply the width (in number of columns).
- If the shape is a triangle, the width is computed as: width = (2*numRows)-1.
We store the width as const string:size_type numCols.
// Only need to ask for a width if the shape is a a rectangle // For square and triangle, the width is computed instead. int shapeWidth; if (shapeType == 2) { // ask for the shape width cout << "Enter Shape Width: "; cin >> shapeWidth; } // compute the number of columns to write (as a constant) based on shape type int finalShapeWidth; if (shapeType == 1) {finalShapeWidth = shapeHeight; } // Compute square width else if (shapeType == 2) {finalShapeWidth = shapeWidth; } // Define rectangle width else {finalShapeWidth = (2*numRows)-1; } // Compute triangle width const string::size_type numCols = finalShapeWidth; // define constant here
4 – Choose Fill Style (Hollow / Solid)
To make the problem more interesting I have added the option to either output a hollow or solid shape. We ask user to choose option 1 (Hollow), or 2 (Solid) and store the value as int inputFillStyle. We eventually store this value as a const int fillSyle. Depending on the shapeType and fillStyle we may apply different algorithm accordingly later on.
// ask for the Shape Fill Style int inputFillStyle; for (int keepAsking = 1; keepAsking == 1; ) { cout << "Select Fill Style." << endl; cout << " (1) - Hollow " << endl; cout << " (2) - Solid " << endl; cout << "Select Fill Style (enter 1/2): "; cin >> inputFillStyle; // Make sure the user input is within range. If not, ask again! if (inputFillStyle == 1 || inputFillStyle == 2) {keepAsking = 0;} } const int fillStyle = inputFillStyle;
5 – Apply Algorithms
All algorithms follow the same “looping” procedure. We have two loops (like in the previous exercises):
- a for loop with the invariant r (increment of 1), and an asymmetric range of [0, numRows). Denote this as r[0,numRows].
- a nested while loop with the invariant c, and an asymmetric range of [0, numCols). Denote this as c[0,numCols].
Just to refresh memory, asymmetric range of [0,numRows) means the range is betwen 0 and numRows, and excludeding numRows from the range. The looping procedure looks like this:
// invariant: we have written r rows so far for ( int r = 0; r != numRows; ++r ) { string::size_type c = 0; // invariant: we have written c characters so far in the current row while ( c != numCols) { // Algorithms go here (where the invariant c gets incremented accordingly) } }
Rectangle (and Square) Algorithm
If rectangle and square, use the solid/hollow rectangle algorithm (as square is a form of rectangle).
// If Square or Rectangle Option if (shapeType == 1 or shapeType == 2) { // hollow option if (fillStyle == 1) { // Are we at the exact position to output asterisk (border)? if ( ( c == 0 ) // the left edge || ( c == numCols-1) // the right edge || ( r == 0 ) // the top edge || ( r == numRows-1) // or the bottom edge ) { cout << "*"; ++c; } else { cout << ' '; ++c; } } // If solid option else if (fillStyle == 2) { cout << "*"; ++c; } }
Triangle Algorithm
If triangle, use the solid/hollow triangle algorithm.
// If Triangle Option if (shapeType == 3) { // If Triangle hollow option if (fillStyle == 1) { // Are we at the exact position to output asterisk (border)? if ( ( c == ((numCols-1)/2)-r ) // the triangle left edge || ( c == ((numCols-1)/2)+r ) // or the triangle right edge || ( r == numRows-1) // or the triangle bottom edge ) { cout << "*"; ++c; } else { cout << ' '; ++c; } } // If triangle solid option else if (fillStyle == 2) { // Are we at the exact position to output asterisk (solid fill)? if ( ( c >= ((numCols-1)/2)-r ) // between the triangle left edge && ( c <= ((numCols-1)/2)+r ) // and the triangle right edge ) { cout << "*"; ++c; } else { cout << ' '; ++c; } } }
6 – Extras
To make the problem more robust I have also added the following features:
A banner at the top to make the console output prettier.
cout << endl; cout << "*********************************" << endl; cout << "*** The Shape Making Program ***" << endl; cout << "*********************************" << endl; cout << endl;
Display the height and width values for clarification.
// display the shape specification cout << endl; cout << "Height = " << numRows << " rows." << endl; cout << "Width = " << numCols << " columns." << endl; cout << endl;
At the end of the program, offer the user an option to re-start the program (from the top) by entering the y button on the keyboard (whereas entering any other keys will cause the program to terminate peacefully). To do this, we wrap the entire main program with a while loop.
int main() { string tryAgain = "y"; while (tryAgain == "y") { // The core program components go here // at the end of the program we ask user if he would like to re-run program // depending on the user input then this program may either re-run or terminate cout << "Again? (y/n): "; cin >> tryAgain; } return 0; }
}
[/code]
The Complete Program
Putting this all together, we now have our complete program.
#include <iostream> #include <string> // say what standard-library names we use using std::cin; using std::endl; using std::cout; using std::string; int main() { // at the end of the program we ask user if he would like to re-run program // depending on the user input then this program may either re-run or terminate string tryAgain = "y"; while (tryAgain == "y") { cout << endl; cout << "*********************************" << endl; cout << "*** The Shape Making Program ***" << endl; cout << "*********************************" << endl; cout << endl; // ask for the Shape Type int shapeType; for (int keepAsking = 1; keepAsking == 1; ) { cout << "Select the Shape Type." << endl; cout << " (1) - Square " << endl; cout << " (2) - Rectangle " << endl; cout << " (3) - Triangle " << endl; cout << "Shape Type (enter 1/2/3): "; cin >> shapeType; // Make sure the user input is within range. If not, ask again! if (shapeType == 1 || shapeType == 2 || shapeType == 3) {keepAsking = 0;} } // ask for the shape height cout << "Enter Shape Height: "; int shapeHeight; cin >> shapeHeight; // set the total number of rows to write (as a constant) int const numRows = shapeHeight; // Only need to ask for a width if the shape is a a rectangle // For square and triangle, the width is computed instead. int shapeWidth; if (shapeType == 2) { // ask for the shape width cout << "Enter Shape Width: "; cin >> shapeWidth; } // compute the number of columns to write (as a constant) based on shape type int finalShapeWidth; if (shapeType == 1) {finalShapeWidth = shapeHeight; } // Compute square width else if (shapeType == 2) {finalShapeWidth = shapeWidth; } // Define rectangle width else {finalShapeWidth = (2*numRows)-1; } // Compute triangle width const string::size_type numCols = finalShapeWidth; // define constant here // ask for the Shape Fill Style int fillStyle; for (int keepAsking = 1; keepAsking == 1; ) { cout << "Select Fill Style." << endl; cout << " (1) - Hollow " << endl; cout << " (2) - Solid " << endl; cout << "Select Fill Style (enter 1/2): "; cin >> fillStyle; // Make sure the user input is within range. If not, ask again! if (fillStyle == 1 || fillStyle == 2) {keepAsking = 0;} } // display the shape specification cout << endl; cout << "Height = " << numRows << " rows." << endl; cout << "Width = " << numCols << " columns." << endl; cout << endl; // invariant: we have written r rows so far for ( int r = 0; r != numRows; ++r ) { string::size_type c = 0; // invariant: we have written c characters so far in the current row while ( c != numCols) { // If Square or Rectangle Option if (shapeType == 1 or shapeType == 2) { // hollow option if (fillStyle == 1) { // Are we at the exact position to output asterisk (border)? if ( ( c == 0 ) // the left edge || ( c == numCols-1) // the right edge || ( r == 0 ) // the top edge || ( r == numRows-1) // or the bottom edge ) { cout << "*"; ++c; } else { cout << ' '; ++c; } } // If solid option else if (fillStyle == 2) { cout << "*"; ++c; } } // If Triangle Option if (shapeType == 3) { // Triangle hollow option if (fillStyle == 1) { // Are we at the exact position to output asterisk (border)? if ( ( c == ((numCols-1)/2)-r ) // the triangle left edge || ( c == ((numCols-1)/2)+r ) // or the triangle right edge || ( r == numRows-1) // or the triangle bottom edge ) { cout << "*"; ++c; } else { cout << ' '; ++c; } } // If triangle solid option else if (fillStyle == 2) { // Are we at the exact position to output asterisk (solid fill)? if ( ( c >= ((numCols-1)/2)-r ) // between the triangle left edge && ( c <= ((numCols-1)/2)+r ) // and the triangle right edge ) { cout << "*"; ++c; } else { cout << ' '; ++c; } } } } cout << endl; } // ask user if he would like to start the program again cout << "Again? (y/n): "; cin >> tryAgain; } return 0; }
Result
********************************* *** The Shape Making Program *** ********************************* Select the Shape Type. (1) - Square (2) - Rectangle (3) - Triangle Shape Type (enter 1/2/3): 1 Enter Shape Height: 5 Select Fill Style. (1) - Hollow (2) - Solid Select Fill Style (enter 1/2): 1 Height = 5 rows. Width = 5 columns. ***** * * * * * * ***** Again? (y/n): y ********************************* *** The Shape Making Program *** ********************************* Select the Shape Type. (1) - Square (2) - Rectangle (3) - Triangle Shape Type (enter 1/2/3): 1 Enter Shape Height: 5 Select Fill Style. (1) - Hollow (2) - Solid Select Fill Style (enter 1/2): 2 Height = 5 rows. Width = 5 columns. ***** ***** ***** ***** ***** Again? (y/n): y ********************************* *** The Shape Making Program *** ********************************* Select the Shape Type. (1) - Square (2) - Rectangle (3) - Triangle Shape Type (enter 1/2/3): 2 Enter Shape Height: 5 Enter Shape Width: 10 Select Fill Style. (1) - Hollow (2) - Solid Select Fill Style (enter 1/2): 1 Height = 5 rows. Width = 10 columns. ********** * * * * * * ********** Again? (y/n): y ********************************* *** The Shape Making Program *** ********************************* Select the Shape Type. (1) - Square (2) - Rectangle (3) - Triangle Shape Type (enter 1/2/3): 2 Enter Shape Height: 5 Enter Shape Width: 10 Select Fill Style. (1) - Hollow (2) - Solid Select Fill Style (enter 1/2): 2 Height = 5 rows. Width = 10 columns. ********** ********** ********** ********** ********** Again? (y/n): y ********************************* *** The Shape Making Program *** ********************************* Select the Shape Type. (1) - Square (2) - Rectangle (3) - Triangle Shape Type (enter 1/2/3): 3 Enter Shape Height: 5 Select Fill Style. (1) - Hollow (2) - Solid Select Fill Style (enter 1/2): 1 Height = 5 rows. Width = 9 columns. * * * * * * * ********* Again? (y/n): y ********************************* *** The Shape Making Program *** ********************************* Select the Shape Type. (1) - Square (2) - Rectangle (3) - Triangle Shape Type (enter 1/2/3): 3 Enter Shape Height: 5 Select Fill Style. (1) - Hollow (2) - Solid Select Fill Style (enter 1/2): 2 Height = 5 rows. Width = 9 columns. * *** ***** ******* ********* Again? (y/n): n Process returned 0 (0x0) execution time : 245.384 s Press any key to continue.
Remarks
This (procedural) program works fine when the problem is fairly simple. When things get more complicated (e.g. if we are asked to produce hundreds or even thousands of different types of shapes, a procedural code might become harder and harder to write and maintain. In that case, I wonder if an object-orientated approach may help simplifying this? Something to come back to in future I guess. i.e. to rewrite the above program in an object oriented manner.
Reference
Koenig, Andrew & Moo, Barbara E., Accelerated C++, Addison-Wesley, 2000WordPress Plugin: LaTex for WordPress
Decided to have a go writing equations in the WordPress editor today. After some Google searches found this pretty promising WordPress Plugin called LaTex for WordPress. So I’ve decided to download and have a go at it. The plugin is built on the following concepts / tools:
MathJax – an open source JavaScript display engine for mathematics that works in all browsers.
LaTex – the de facto standard for the communication and publication of scientific documents
i.e. one may build an equation within the WordPress editor by typing in LaTex syntax (in conjunction with the rules specified by the plugin). The MathJax engine “knows” what the LaTex syntax means and would display the equation onto the browser accordingly.
Well, something to try out in future posts!