Question
Chapter 7 C++ HW Memoization We are going to compute a binomial coefficient again in a faster way. By saving intermediate results we can trade
Chapter 7 C++ HW Memoization
We are going to compute a binomial coefficient again in a faster way. By saving intermediate results we can trade storage space for computational time. This is called memoization.
Take the recursive calculation for 4 choose 2,
when n==k or k==0 then 1, else find C(n-1,k-1) + C(n-1,k)
C(4, 2)
/ \
C(3, 1) C(3, 2)
/ \ / \
C(2, 0) C(2, 1) C(2, 1) C(2, 2)
/ \ / \
C(1, 0) C(1, 1) C(1, 0) C(1, 1)
The answer is the sum of the base cases
(2,0) + (1,0) + (1,1) + (1,0) + (1,1) + (2,2)
= 1 + 1 + 1 + 1 + 1 + 1
= 6
But the intermediate step of C(2,1) is calculated twice.
So lets calculate all the intermediate results, row by row.
|
| k |
|
| ||
0 | 1 | 2 | 3 | 4 | ||
| 0 | 1 | ||||
| 1 | 1 | 1 | |||
n | 2 | 1 | 2 | 1 | ||
| 3 | 1 | 3 | 3 | 1 | |
| 4 | 1 | 4 | 6 | 4 | 1 |
So, we will build a 2-dimensional global vector:
vector
We will make it row by row, using nested for loops with counters i and j
with i going from i=0 to i <= n, and j going from j=0 to j<=i (if j went to k it would be a square instead of a triangle)
So i is the row and j is the column
Inside the outer for loop we will make a 1-dimensional vector:
vector
which we will add results in the following way
whenever j is 0 then triangle[i][j] is 1, this is the first column
when j equals i then triangle [i][j] is also 1, this is the diagonal
These are the 2 base cases, which can be added to the row with
row.push_back(1)
Otherwise, we use the sum of the number above plus above and to the left
So triangle[i][j] = triangle [i-1][j-1] + triangle[i-1][j]
Then add the row to the triangle
triangle.push_back(row)
When the for loops are done the triangle is complete.
The final answer to the coefficient is the result at triangle[n][k], in this case 6 which is 3+3
This triangle is called Pascals triangle.
Write a driver program that takes n and k, where n >= k>= 0. If the input does not meet those requirements print invalid input to standard error (cerr) then exit(-1). Run and print both the binomial coefficient which is triangle[n][k] and the whole triangle.
Example output:
Please enter n: 4
Please enter k: 6
invalid input
Example output:
Please enter n: 4
Please enter k: 2
Pascal's Triangle Coefficient: 6
Pascal's Triangle:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
Example output:
Please enter n: 10
Please enter k: 3
Pascal's Triangle Coefficient: 120
Pascal's Triangle:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
Example output:
Please enter n: 40
Please enter k: 4
Pascal's Triangle Coefficient: 91390
Pascal's Triangle:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
1 11 55 165 330 462 462 330 165 55 11 1
full triangle not shown
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started