Josephus problem: Difference between revisions
Added solution for EDSAC
(Added Tiny BASIC) |
(Added solution for EDSAC) |
||
Line 2,115:
</syntaxhighlight>
=={{header|EDSAC order code}}==
The algorithm is of the "increasing modulus" type. Though written independently of the Ring solution, it seems to be essentially the same. The (n,k) pairs used by the demo program are taken from solutions on this page. Running time totals 1.2 EDSAC minutes for the first eight examples, and 12.5 for the last two.
<syntaxhighlight lang="edsac">
[Jospehus problem - Rosetta Code
EDSAC program (Initial Orders 2)]
[Arrange the storage]
T45K P56F [H parameter: library subroutine R4 to read integer]
T46K P80F [N parameter: subroutine to print 17-bit non-neg integer]
T47K P160F [M parameter: main routine]
T51K P128F [G parameter: subroutine to find last survivor]
[Library subroutine M3, runs at load time and is then overwritten.
Prints header; here, last character sets teleprinter to figures.]
PF GK IF AF RD LF UF OF E@ A6F G@ E8F EZ PF
*!!!!N!!!!!K!!!!SURVIVOR@&#..PZ
[============== G parameter: Subroutine to find last survivor ==============
Input: 4F = n = number of prisoners
5F = k = executioner's step
Output: 0F = 0-based index of last survivor]
[Pascal equivalent:
z := 0; // solution when n = 1
for j := 2 to n do z := (z + k) mod j;
result := z;]
E25K TG GK
A3F T22@ [plant return link as usual]
T23@ [z := 0]
A2F T24@ [j := 2]
E16@ [jump to middle of loop]
[6] TF [clear acc]
A23@ A5F [acc := z + k]
[Get residue modulo j by repeatedly subtracting j.
The number of subtractions is usually small.]
[9] S24@ E9@ [subtract j till result < 0]
A24@ [add back the last j]
T23@ [update z]
A24@ A25@ T24@ [inc(j)]
[16] A4F S24@ [acc := n - j]
E6@ [loop back if j <= n]
TF [done: clear acc]
A23@ TF [return z (last survivor) to caller in 0F]
[22] ZF [(planted) jump back to caller]
[Storage]
[23] PF [Pascal z]
[24] PF [Pascal j]
[25] PD [constant 1]
[====================== M parameter: Main routine ======================]
E25K TM GK
[0] PF [negative data count]
[1] PF [number of prisoners]
[2] PF [executioner's step]
[3] !F [space]
[4] @F [carriage return]
[5] &F [line feed]
[6] K4096F [null character]
[Enter with acc = 0]
[7] A7@ GH [call subroutine R4, sets 0D := count of (n,k) pairs]
SF [acc := count negated; it's assumed that count < 2^16]
E46@ [exit if count = 0]
LD [shift count into address field]
[12] T@ [update negative loop counter]
A13@ GH [call library subroutine R4, 0D := number of prisoners]
AF T1@ [store number of prisoners, assumed < 2^16]
A17@ GH [call library subroutine R4, 0D := executioner's step]
AF T2@ [store executioner's step, assumed < 2^16]
A3@ T1F [to print leading 0's as spaces]
A1@ TF [pass number of prisoners to print subroutine]
A25@ GN O3@ [print number of prisoners, plus space]
A2@ TF [same for executioner's step]
A30@ GN O3@
A1@ T4F [pass number of prisoners to "last survivor" subroutine]
A2@ T5F [same for executioner's step]
A37@ GG [call subroutine, 0F := 0-based index of last survivor]
A39@ GN O4@ O5@ [print last survivor, plus CR,LF]
A@ A2F [increment negative counter]
G12@ [loop back if still negative]
[46] O6@ [print null to flush printer buffer]
ZF [halt the machine]
[The next 3 lines put the entry address into location 50,
so that it can be accessed via the X parameter (see end of program).]
T50K
P7@
T7Z
[================== H parameter: Library subroutine R4 ==================
Input of one signed integer, returned in 0D.
22 locations.]
E25K TH GK
GKA3FT21@T4DH6@E11@P5DJFT6FVDL4FA4DTDI4FA4FS5@G7@S5@G20@SDTDT6FEF
[============================= N parameter ==============================
Subroutine to print non-negative 17-bit integer.
Input: 0F = integer to be printed (not preserved)
1F = character for leading zero (preserved)
Workspace: 4F..7F, 38 locations]
E25K TN
GKA3FT34@A1FT7FS35@T6FT4#FAFT4FH36@V4FRDA4#FR1024FH37@E23@O7FA2F
T6FT5FV4#FYFL8FT4#FA5FL1024FUFA6FG16@OFTFT7FA6FG17@ZFP4FZ219DTF
[==========================================================================
On the original EDSAC, the following (without the whitespace and comments)
might have been input on a separate tape.]
E25K TX GK
EZ [define entry point]
PF [acc = 0 on entry]
[Count of (n,k) pairs, then the pairs, to be read by library subroutine R4.
Note that sign comes *after* value.]
10+5+2+12+4+41+3+50+2+60+3+71+47+123+3+123+47+10201+17+23482+3343+
</syntaxhighlight>
{{out}}
<pre>
N K SURVIVOR
5 2 2
12 4 0
41 3 30
50 2 36
60 3 40
71 47 29
123 3 54
123 47 101
10201 17 7449
23482 3343 1335
</pre>
=={{header|Eiffel}}==
| |||