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> triangle; //global

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 row;

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