-
May 1st, 2014, 07:26 PM
#1
Pascal Triangle Problem - Please help
Pascal’s triangle looks as follows:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
...
The first entry in a row is 1 and the last entry is 1 (except for the first row which contains only 1), and every other entry in Pascal’s triangle is equal to the sum of the two entries: the entry that is in the previous row and the same column, and the entry that is in the previous row and previous column.
(a) Give a recursive definition for the entry C[i, j] at row i and column j of Pascal’s triangle. Make sure that you distinguish the base case(s).
(b) Give a recursive algorithm to compute C[i, j], i > j > 1. Illustrate by drawing a diagram (tree) the steps that your algorithm performs to compute C[6, 4]. Does your algorithm perform overlapping computations?
(c) Use dynamic programming to design an O(n2) time algorithm that computes the first n rows in Pascal’s triangle. Does the dynamic programming algorithm performs better than the recursive
algorithm? Explain.
-
May 2nd, 2014, 04:06 AM
#2
Re: Pascal Triangle Problem - Please help
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
May 2nd, 2014, 04:46 AM
#3
Re: Pascal Triangle Problem - Please help
Originally Posted by BlueBir86
Pascal’s triangle looks as follows:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
...
The first entry in a row is 1 and the last entry is 1 (except for the first row which contains only 1), and every other entry in Pascal’s triangle is equal to the sum of the two entries: the entry that is in the previous row and the same column, and the entry that is in the previous row and previous column.
(a) Give a recursive definition for the entry C[i, j] at row i and column j of Pascal’s triangle. Make sure that you distinguish the base case(s).
(b) Give a recursive algorithm to compute C[i, j], i > j > 1. Illustrate by drawing a diagram (tree) the steps that your algorithm performs to compute C[6, 4].
You could start from wiki to solve (a) and (b)
Victor Nijegorodov
-
May 2nd, 2014, 02:42 PM
#4
Re: Pascal Triangle Problem - Please help
Originally Posted by BlueBir86
(c) Use dynamic programming to design an O(n2) time algorithm that computes the first n rows in Pascal’s triangle. Does the dynamic programming algorithm performs better than the recursive
algorithm? Explain.
Being presented with the question it strikes me that,
recursion + memoization == dynamic programming
Remember you read it here first
Last edited by zizz; May 2nd, 2014 at 04:29 PM.
Tags for this Thread
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|