Context
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.Pascal's triangle looks like
1One 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.
1 1
1 2 1
1 3 3 1
1 4 6 4 1
...
Given that, let's see how we can generate the Nth row of Pascal's triangle
Initial state
- Memory: N 0 0 0
- Cursor: on third cell
- Input: any
Process
- First, let's initialize the first row of the triangle
- Set third cell to 1
- Then, while our counter N is not null
- Decrease counter
- Generate next row
- Go to array's last cell
- Move current cell twice on the right (next 2 cells)
- Go to previous cell and loop
- This will generate next row. Actually, move is a "decrease here / increase there" process, so the first moves will transform
- ... A B C 0 into ... A B 0 C C
- then into ... A 0 B (B+C) C
- then into ... 0 A (A+B) (B+C) C
- Finally, move the whole new row one cell to the left (because of an extra 0 introduced by steps above)
- Go back to counter
Code - try it
initialize first row
>>+<<
[
decrease counter
-
go to last cell
>>[>]<
[
move twice
[->+>+<<]
go to previous cell
<
]
move whole array to the left
>>[[-<+>]>]
back to counter
<<[<]<
]
Final state
- Memory: 0 0 Nth row of Pascal's triangle
- Cursor: first cell
- Input: unchanged
- Output: unchanged
Note: because of cell size limitation, the row is computed modulo 256.
And because of that and 'one-cell' array implementation, this algorithm will fail as soon as one cell equals 0 modulo 256.
And because of that and 'one-cell' array implementation, this algorithm will fail as soon as one cell equals 0 modulo 256.
Anyway, this should not occur until counter = 256, meaning that it would overflow the cell limit for counter itself.
Any triangle row generated through this algorithm is therefore valid as long as it can be generated.
Aucun commentaire:
Enregistrer un commentaire