Recall the design paradigm of stepwise refinement:
1 | 2 | 3 | ... | n |
2 | 3 | 4 | ... | n+1 |
... | ||||
n | n+1 | n+2 | ... | 2n-1 |
Enter value n, where n < 50: 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
Think about what you're going to have to do in order to ensure that the columns line up correctly, given that you have single and double digit numbers!
The key to solving this problem effortlessly is to gradually develop a solution. If you click the forward and backward arrows below, you'll see one way of following stepwise refinement for the Hankel matrix problem.
#include <iostream>
using namespace std;
int main()
{
// Read in the parameter n
// Write Hankel matrix
return 0;
}
#include <iostream>
using namespace std;
int main()
{
// Read in the parameter n
// Write Hankel matrix
for(int row = 1; row <= n; row++)
{
// Write row entries row, ..., row + n
}
return 0;
}
#include <iostream>
using namespace std;
int main()
{
// Read in the parameter n
// Write Hankel matrix
for(int row = 1; row <= n; row++)
{
// Write row entries row, ..., row + n
for(int col = 1; col <= n; col++)
{
// Write entry (row,col) in two spaces
}
}
return 0;
}
#include <iostream>
using namespace std;
int main()
{
// Read in the parameter n
// Write Hankel matrix
for(int row = 1; row <= n; row++)
{
// Write row entries row, ..., row + n
for(int col = 1; col <= n; col++)
{
// Write entry (row,col) in two spaces
int val = row + (col - 1);
if (val < 10)
cout << ' ';
cout << val << ' ';
}
cout << endl;
}
return 0;
}
#include <iostream>
using namespace std;
int main()
{
// Read in the parameter n
int n;
cout << "Enter value n, where n < 50: ";
cin >> n;
// Write Hankel matrix
for(int row = 1; row <= n; row++)
{
// Write row entries row, ..., row + n
for(int col = 1; col <= n; col++)
{
// Write entry (row,col) in two spaces
int val = row + (col - 1);
if (val < 10)
cout << ' ';
cout << val << ' ';
}
cout << endl;
}
return 0;
}
This is what step-wise refinement is about. We've been doing it all along, in a sense, but it's much more interesting when you have nested structures like loops and if statements, as opposed to a simple sequence of flat steps.
1.1*x^2 - 3.0*x^1 + 2.1*x^0instead of 1.1*x^2 - 3.0*x + 2.1. The user will show that he's done entering the polynomial by typing an equals sign. A typical run of the program might look like this:
Enter value for x: 3.1
Enter polynomial to be evaluated (e.g. 3.1*x^2 - 2.0*x^1 + 1.1*x^0 = )
0.75*x^5 - 1.8*x^3 + 0.3*x^2 + 1.1*x^1 =
Result is 167.388
In essence this problem is not much different from the "simple calculator"
problem we looked at in Class 10. The main
difference is that instead of sums and differences of simple numbers, we
have sums and differences of terms in a polynomial. Once again, a nice
way to attack this problem is by stepwise refinement, where we gradually
develop a solution by specifying in deeper and deeper detail how we'll
solve the problem, until our detail is so great we actually have a
complete C++ program. Clicking through the arrows below will show you one
way of solving this one through stepwise refinement.
#include <iostream>
using namespace std;
int main()
{
// Read in x value
// Read and evaluate polynomial
// Write result
return 0;
}
#include <iostream>
using namespace std;
int main()
{
// Read in x value
/************************************/
/*** Read and evaluate polynomial ***/
/************************************/
while()
{
// Read next term c*x^n
// Evaluate next term c*x^n
// Update value of total
}
// Write result
return 0;
}
#include <iostream>
using namespace std;
int main()
{
// Read in x value
/************************************/
/*** Read and evaluate polynomial ***/
/************************************/
while()
{
// Read next term c*x^n
/******************************/
/** Evaluate next term c*x^n **/
/******************************/
// - Compute x^n
// - multiply by c
// Add value of term to total
}
// Write result
return 0;
}
#include <iostream>
using namespace std;
int main()
{
// Read in x value
double x;
cout << "Enter value for x: ";
cin >> x;
/************************************/
/*** Read and evaluate polynomial ***/
/************************************/
while()
{
// Read next term c*x^n
/******************************/
/** Evaluate next term c*x^n **/
/******************************/
// - Compute x^n
double xn = 1;
for(int i = 0; i < n; i++)
xn = xn*x;
// - multiply by c
double term = xn*c;
/******************************/
/** Add value of term to total*/
/******************************/
if (op == '+')
total = total + term;
else
total = total - term;
}
// Write result
cout << "Result is " << total << endl;
return 0;
}
#include <iostream>
using namespace std;
int main()
{
// Read in x value
double x;
cout << "Enter value for x: ";
cin >> x;
/************************************/
/*** Read and evaluate polynomial ***/
/************************************/
cout << "Enter polynomial to be evaluated "
<< "(e.g. 3.1*x^2 - 2.0*x^1 + 1.1*x^0 = )"
<< endl;
while(op != '=')
{
/******************************/
/** Read next term c*x^n *****/
/******************************/
double c;
int n;
char t;
cin >> c >> t >> t >> t >> n;
/******************************/
/** Evaluate next term c*x^n **/
/******************************/
// - Compute x^n
double xn = 1;
for(int i = 0; i < n; i++)
xn = xn*x;
// - multiply by c
double term = xn*c;
/******************************/
/** Add value of term to total*/
/******************************/
if (op == '+')
total = total + term;
else
total = total - term;
}
// Write result
cout << "Result is " << total << endl;
return 0;
}
#include <iostream>
using namespace std;
int main()
{
// Read in x value
double x;
cout << "Enter value for x: ";
cin >> x;
/************************************/
/*** Read and evaluate polynomial ***/
/************************************/
cout << "Enter polynomial to be evaluated "
<< "(e.g. 3.1*x^2 - 2.0*x^1 + 1.1*x^0 = )"
<< endl;
// Initialization for loop
char op;
double total;
op = '+';
total = 0;
while(op != '=')
{
/******************************/
/** Read next term c*x^n *****/
/******************************/
double c;
int n;
char t;
cin >> c >> t >> t >> t >> n;
/******************************/
/** Evaluate next term c*x^n **/
/******************************/
// - Compute x^n
double xn = 1;
for(int i = 0; i < n; i++)
xn = xn*x;
// - multiply by c
double term = xn*c;
/******************************/
/** Add value of term to total*/
/******************************/
if (op == '+')
total = total + term;
else
total = total - term;
// Read next op
cin >> op;
}
// Write result
cout << "Result is " << total << endl;
return 0;
}
The formula for n choose k is $$\frac{n\cdot(n-1)\cdot(n-2)\cdots(n-k+1)}{k\cdot(k-1)\cdot(k-2)\cdots 1}$$
So, for example 7 choose 3 is (7*6*5)/(3*2*1) = 35.
Notice that this number will always be an integer! So do all of your
computations using type int
, and don’t do anvy division
unless you're sure you'll get exact results, i.e. no remainder. Take a
look at this solution to the problem.
Please enter the table size: 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2 4 6 8 10 12 14 16 18 20 22 24 26 28 30
3 6 9 12 15 18 21 24 27 30 33 36 39 42 45
4 8 12 16 20 24 28 32 36 40 44 48 52 56 60
5 10 15 20 25 30 35 40 45 50 55 60 65 70 75
6 12 18 24 30 36 42 48 54 60 66 72 78 84 90
7 14 21 28 35 42 49 56 63 70 77 84 91 98 105
8 16 24 32 40 48 56 64 72 80 88 96 104 112 120
9 18 27 36 45 54 63 72 81 90 99 108 117 126 135
10 20 30 40 50 60 70 80 90 100 110 120 130 140 150
11 22 33 44 55 66 77 88 99 110 121 132 143 154 165
12 24 36 48 60 72 84 96 108 120 132 144 156 168 180
13 26 39 52 65 78 91 104 117 130 143 156 169 182 195
14 28 42 56 70 84 98 112 126 140 154 168 182 196 210
15 30 45 60 75 90 105 120 135 150 165 180 195 210 225
Take a look at this solution to this problem.