Catalan numbers/Pascal's triangle: Difference between revisions
Added solution for EDSAC.
(Added Wren) |
(Added solution for EDSAC.) |
||
Line 491:
→ 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845
</lang>
=={{header|EDSAC order code}}==
Rather than store a triangular array, this solution stores the right-hand half of the current row and updates it in place. It uses the third method in the link, e.g. once we have the half row (70, 56, 28, 8, 1), the Catalan number 42 appears as 70 - 28.
<lang edsac>
[Catalan numbers from Pascal triangle, Rosetta Code website.
EDSAC program, Initial Orders 2]
..PZ [blank tape and terminator]
T54K [refer to working array with 'C']
P300F [address of working array]
T46K [to call print subroutine with 'G N']
P56F [address of print subroutine]
[Modification of library subroutine P7.
Prints non-negative integer, up to 10 digits, right-justified.
55 locations, load at even address.]
E25KTN
GKA3FT42@A47@T31@ADE10@T31@A48@T31@SDTDH44#@NDYFLDT4DS43@
TFH17@S17@A43@G23@UFS43@T1FV4DAFG50@SFLDUFXFOFFFSFL4FT4DA49@
T31@A1FA43@G20@XFP1024FP610D@524D!FO46@O26@XFO46@SFL8FT4DE39@
[Main program]
PK T200K GK
[Constants]
[0] PD [short constant 1]
[1] P2F [to inc address by 2]
[2] T#C [used in manufacturing EDSAC orders]
[3] MF [add to T order to make A order with same address]
[4] #F [set figures]
[5] &F [line feed]
[6] @F [carriage return]
[7] P7D [maximum n = 15]
[Variable]
[8] PF [n]
[Enter with acc = 0]
[9] O4@ [set teleprinter to figures]
T4#C T2#C T#C A@ TC [initialize first 3 terms to 1, 0, 0]
T8@ E58@ [set n := 0; jump to inc n and print C_n]
[Outer loop; here with n updated]
[17] TF A8@ [acc := latest n]
L1F A2@ T22@ [make and store order 'T 2n #C']
[22] T#C [sets term := 0; also used to test for end of loop]
A2@ [load 'T#C', initial value of order 31]
[Loop to convert e.g. (20, 15, 6, 1) to (35, 21, 7, 1); works left to right]
[24] U31@ A3@ U29@ A1@ T30@ [set up orders on next line]
[29] A#C A#C T#C [replaced by manufactured orders]
A31@ A1@ S22@ E38@ [inc address in order 31, jump out if done]
A22@ E24@ [not done, loop back]
[38] A22@ T48@ [initialize order 48]
[Loop to convert e.g. (35, 21, 7, 1) to (70, 56, 28, 8, 1); works right to left]
[40] TF A48@ A3@ U46@ S1@ T47@ [set up orders on next line]
[46] A#C A#C T#C [replaced by manufactured orders]
A48@ S1@ T48@ [dec address in order 48]
A2@ S48@ G40@ [test for done, loop back if not]
A#C LD T#C [double first term, e.g. 35 -> 70 (not done in loop)]
[Increment n and print Catalan number C_n]
[58] TD [clear 0D, ensures sandwich bit = 0]
A8@ A@ U8@ TF [inc n; set 0D := n by setting 0F := n]
A63@ GN [print n]
A#C S4#C TD A68@ GN [print Catalan number C_n, e.g. C_5 = 70 - 28 = 42]
O6@ O5@ [print CR, LF]
A8@ S7@ G17@ [test for maximum n, loop back if not]
[75] O4@ ZF [flush printer buffer; stop]
E9Z PF [define entry point; enter with acc = 0]
</lang>
{{out}}
<pre>
1 1
2 2
3 5
4 14
5 42
6 132
7 429
8 1430
9 4862
10 16796
11 58786
12 208012
13 742900
14 2674440
15 9694845
</pre>
=={{header|Elixir}}==
| |||