Open Source Your Knowledge, Become a Contributor
Technology knowledge has to be shared and made accessible for free. Join the movement.
Pascal's triangle is a triangular array of binomial coefficients: cell k of row n indicates how many combinations exist of n things taken k at a time. It looks like this
- 1 1
- 1 2 1
- 1 3 3 1
- 1 4 6 4 1
One can prove that a given cell is the sum of 2 cells from previous row: the one just above and the one on top left.
Given that, let's see how we can generate the Nth row of Pascal's triangle
- Memory: empty
- Cursor: first cell
- Input: a decimal number N (greater than 0)
- Read a decimal number
- Init line 0 : just 1
- While counter is not null
- Decrease counter
- Generate next line
- Go to row last cell (e.g. mem : A B C D 0 0 0
- Move it to the next 2 cells (e.g. mem : A B C 0 D D)
- Go to previous cell and loop
- mem : A B 0 C C+D D
- then A 0 B B+C C+D D
- and finally 0 A A+B B+C C+D D
- Move all values back on the left
- Print last line, comma separated. Line is symetric : can be print from right to left as well
- Print '1' and ignore first value (it's always 1)
- While there is an item
- Print comma
- Move / Print item
- Go left
>,[>++++++[-<-------->]>+++++++++[- read an integer <<<[->+>+<<]>>[-<<+>>]>]<<[-<+>],] ** part 2 ** >+ Initialize first row <<[ while counter is not null - decrease counter >>[>]< go to last cell [[->+>+<<]<] while there is a cell: move to the next 2 ones on the left and repeat >>[[-<+>]>] Move whole array to the left <<[<]< back to counter ] loop >+++++++[-<+++++++>]<.----- print 49 (='1') and change into comma (44) >>[>]<-< go to last cell (1) then reset; then go to previous cell [ for each cell in the row [<]<.>>[>]< print comma (first memory cell) then go back to the current cell [->+<]> move to the right (at least one 0 needed to print a decimal value) [>>>>++++++++++<<<<[->+>>+>-[<-]<[- Print decimal value >>+<<<<[->>>+<<<]>]<<]>+[-<+>]>>>[- ** part 2 ** ]>[-<<<<+>>>>]<<<<]<[>++++++[<+++++ ** part 3 ** +++>-]<-.[-]<] ** part 4 ** <]
>,[>++++++[-<-------->]>+++++++++[-<<<[-> +>+<<]>>[-<<+>>]>]<<[-<+>],]>+<<[->>[>]<[ [->+>+<<]<]>>[[-<+>]>]<<[<]<]>+++++++[-<+ ++++++>]<.----->>[>]<-<[[<]<.>>[>]<[->+<] >[>>>>++++++++++<<<<[->+>>+>-[<-]<[->>+<< <<[->>>+<<<]>]<<]>+[-<+>]>>>[-]>[-<<<<+>> >>]<<<<]<[>++++++[<++++++++>-]<-.[-]<]<]
- Memory: 44, 0, 0, 0
- Cursor: on second cell
- Input: read (empty)
- Output: Nth row from Pascal's triangle (modulo 256)
Note: because of the nature of the algorithm, if a cell equals 0 on a row it will break the loop. And modulo 256, a cell can actually be null.
However, the first cell that will be a multiple of 256 in standard Pascal's triangle appears on row 256, and the counter itself, from user input, cannot be more than 255.
In other words: this algorithm is valid as long as we rely on a counter. Having an infinite loop to generate more than 255 rows will fail. We can of course introduce 2-cell-long arrays but it's not really important here.