Josephus problem: Difference between revisions
m
→{{header|Fōrmulæ}}
| (14 intermediate revisions by 9 users not shown) | |||
Line 1,107:
{{out}}
<pre>Same as FreeBASIC entry.</pre>
==={{header|Craft Basic}}===
<syntaxhighlight lang="basic">'using 1 to n
define prisoners = 0, step = 0, killcount = 0, survivor = 0
define fn (josephus) as ( survivor + step ) % killcount
do
input "Prisoners", prisoners
input "Step", step
gosub executioner
loop
sub executioner
let killcount = 1
do
let killcount = killcount + 1
let survivor = (josephus)
loop killcount < prisoners
print "survivor = ", survivor
return</syntaxhighlight>
{{out| Output}}<pre>prisoners? 41
step? 3
survivor = 30</pre>
==={{header|FreeBASIC}}===
<syntaxhighlight lang="freebasic">
Function Josephus (n As Integer, k As Integer, m As Integer) As Integer
Dim As Integer lm = m
For i As Integer = m + 1 To n
lm = (lm + k) Mod i
Next i
Josephus = lm
End Function
Dim As Integer n = 41 'prisioneros
Dim As Integer k = 3 'orden de ejecución
Print "n ="; n, "k ="; k, "superviviente = "; Josephus(n, k, 0)
</syntaxhighlight>
{{out}}
<pre>
n = 41 k = 3 superviviente = 30
</pre>
==={{header|FTCBASIC}}===
<syntaxhighlight lang="basic">define prisoners = 0, step = 0, killcount = 0
define survivor = 0, remainder = 0
do
print "Prisoners: " \
input prisoners
print "Step: " \
input step
gosub executioner
loop
sub executioner
let killcount = 1
do
let killcount = killcount + 1
let survivor = survivor + step
let survivor = survivor / killcount
carry survivor
loop killcount < prisoners
print "survivor = " \
print survivor
return</syntaxhighlight>
==={{header|Gambas}}===
Line 1,192 ⟶ 1,279:
==={{header|MSX Basic}}===
The [[#GW-BASIC|GW-BASIC]] solution works without any changes.
==={{header|Palo Alto Tiny BASIC}}===
{{trans|ANSI BASIC}}
<syntaxhighlight lang="basic">
10 REM JOSEPHUS PROBLEM
20 LET N=41,K=3,M=0
30 GOSUB 100
40 PRINT #1,"N =",N,", K =",K,", FINAL SURVIVOR =",L
50 STOP
90 REM ** JOSEPHUS
100 LET L=M
110 FOR A=M+1 TO N
120 LET L=L+K-((L+K)/A)*A
130 NEXT A
140 RETURN
</syntaxhighlight>
{{out}}
<pre>
N = 41, K = 3, FINAL SURVIVOR = 30
</pre>
==={{header|PureBasic}}===
<syntaxhighlight lang="purebasic">NewList prisoners.i()
Procedure f2l(List p.i())
FirstElement(p()) : tmp.i=p()
DeleteElement(p(),1) : LastElement(p())
AddElement(p()) : p()=tmp
EndProcedure
Procedure l2f(List p.i())
LastElement(p()) : tmp.i=p()
DeleteElement(p()) : FirstElement(p())
InsertElement(p()) : p()=tmp
EndProcedure
OpenConsole()
Repeat
Print(#LF$+#LF$)
Print("Josephus problem - input prisoners : ") : n=Val(Input())
If n=0 : Break : EndIf
Print(" - input steps : ") : k=Val(Input())
Print(" - input survivors : ") : s=Val(Input()) : If s<1 : s=1 : EndIf
ClearList(prisoners()) : For i=0 To n-1 : AddElement(prisoners()) : prisoners()=i : Next
If n<100 : Print("Executed : ") : EndIf
While ListSize(prisoners())>s And n>0 And k>0 And k<n
For j=1 To k : f2l(prisoners()) : Next
l2f(prisoners()) : FirstElement(prisoners()) : If n<100 : Print(Str(prisoners())+Space(2)) : EndIf
DeleteElement(prisoners())
Wend
Print(#LF$+"Surviving: ")
ForEach prisoners()
Print(Str(prisoners())+Space(2))
Next
ForEver
End</syntaxhighlight>
{{out}}
<pre>Josephus problem - input prisoners : 5
- input steps : 2
- input survivors : 1
Executed : 1 3 0 4
Surviving: 2
Josephus problem - input prisoners : 41
- input steps : 3
- input survivors : 1
Executed : 2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27 31 36 40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3 34 15
Surviving: 30
Josephus problem - input prisoners : 41
- input steps : 3
- input survivors : 3
Executed : 2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27 31 36 40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3
Surviving: 15 30 34
Josephus problem - input prisoners : 71
- input steps : 47
- input survivors : 11
Executed : 46 22 70 48 26 5 56 36 17 0 54 38 23 9 66 55 43 33 25 16 11 6 2 69 68 1 4 10 15 24 32 42 53 65 20 40 60 19 47 8 44 13 52 31 12 62 57 50 51 61 7 30 59 34 18 3 21 37 67 63
Surviving: 64 14 27 28 29 35 39 41 45 49 58
Josephus problem - input prisoners :</pre>
==={{header|QBasic}}===
Line 1,223 ⟶ 1,392:
130 NEXT A
140 RETURN</syntaxhighlight>
==={{Header|Tiny BASIC}}===
<syntaxhighlight lang="qbasic"> REM Josephus problem
LET N = 41
LET K = 3
LET M = 0
GOSUB 10
PRINT "N = ", N
PRINT "K = ", K
PRINT "FINAL SURVIVOR = ", S
END
REM ** JOSEPHUS
10 LET S = M
LET I = M + 1
20 IF I = N THEN GOTO 30
LET S = S + K - ((S + K) / I) * I
LET I = I + 1
GOTO 20
30 RETURN
</syntaxhighlight>
==={{header|True BASIC}}===
Line 1,239 ⟶ 1,429:
{{out}}
<pre>Same as QBasic entry.</pre>
==={{header|VBScript}}===
<syntaxhighlight lang="vb">
Function josephus(n,k,s)
Set prisoner = CreateObject("System.Collections.ArrayList")
For i = 0 To n - 1
prisoner.Add(i)
Next
index = -1
Do Until prisoner.Count = s
step_count = 0
Do Until step_count = k
If index+1 <= prisoner.Count-1 Then
index = index+1
Else
index = (index+1)-(prisoner.Count)
End If
step_count = step_count+1
Loop
prisoner.RemoveAt(index)
index = index-1
Loop
For j = 0 To prisoner.Count-1
If j < prisoner.Count-1 Then
josephus = josephus & prisoner(j) & ","
Else
josephus = josephus & prisoner(j)
End If
Next
End Function
'testing the function
WScript.StdOut.WriteLine josephus(5,2,1)
WScript.StdOut.WriteLine josephus(41,3,1)
WScript.StdOut.WriteLine josephus(41,3,3)
</syntaxhighlight>
{{Out}}
<pre>
2
30
15,30,34
</pre>
==={{header|Visual Basic .NET}}===
{{trans|D}}
<syntaxhighlight lang="vbnet">Module Module1
'Determines the killing order numbering prisoners 1 to n
Sub Josephus(n As Integer, k As Integer, m As Integer)
Dim p = Enumerable.Range(1, n).ToList()
Dim i = 0
Console.Write("Prisoner killing order:")
While p.Count > 1
i = (i + k - 1) Mod p.Count
Console.Write(" {0}", p(i))
p.RemoveAt(i)
End While
Console.WriteLine()
Console.WriteLine("Survivor: {0}", p(0))
End Sub
Sub Main()
Josephus(5, 2, 1)
Console.WriteLine()
Josephus(41, 3, 1)
End Sub
End Module</syntaxhighlight>
{{out}}
<pre>Prisoner killing order: 2 4 1 5
Survivor: 3
Prisoner killing order: 3 6 9 12 15 18 21 24 27 30 33 36 39 1 5 10 14 19 23 28 32 37 41 7 13 20 26 34 40 8 17 29 38 11 25 2 22 4 35 16
Survivor: 31</pre>
==={{header|Yabasic}}===
Line 1,258 ⟶ 1,525:
{{out}}
<pre>Same as FreeBASIC entry.</pre>
==={{header|ZX Spectrum Basic}}===
{{trans|ANSI BASIC}}
<syntaxhighlight lang="zxbasic">10 LET n=41: LET k=3: LET m=0
20 GO SUB 100
30 PRINT "n= ";n;TAB (7);"k= ";k;TAB (13);"final survivor= ";lm
40 STOP
100 REM Josephus
110 REM Return m-th on the reversed kill list; m=0 is final survivor.
120 LET lm=m: REM Local copy of m
130 FOR a=m+1 TO n
140 LET lm=FN m(lm+k,a)
150 NEXT a
160 RETURN
200 DEF FN m(x,y)=x-INT (x/y)*y: REM MOD function
</syntaxhighlight>
=={{header|Batch File}}==
Line 1,616 ⟶ 1,899:
CL-USER > (kill 41 3)
30
=={{header|Crystal}}==
Line 1,806 ⟶ 2,059:
Josephus(41,2,1) -> 30 / 2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27 31 36 40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3 34 15
Josephus(23482,3342,3) -> 1087 1335 13317 / 3342 6685 10028 13371 16714 20057 23400 3261 6605 9949 13293 16637 19981 23325 3187 6532 9877 13222 16567 19912 23257 3120 6466 9812 13158 16504 19850 23196 3060 6407 9754 13101 16448 19795 23142 3007 6355 9703 13051 16399 19747 23095 2961 6310 9659 ...</pre>
=={{header|EasyLang}}==
<syntaxhighlight lang="easylang">
n = 41
k = 3
print "prisoners: " & n
print "step size: " & k
for i = 1 to n
lm = (lm + k) mod i
.
print "final survivor: " & lm
</syntaxhighlight>
=={{header|EchoLisp}}==
Line 1,850 ⟶ 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}}==
Line 2,103 ⟶ 2,496:
deallocate(next)
end program</syntaxhighlight>
=={{header|friendly interactive shell}}==
Line 2,185 ⟶ 2,558:
Alive: 30
</pre>
=={{header|Fōrmulæ}}==
Line 2,272 ⟶ 2,611:
[[File:Fōrmulæ - Josephus problem 10.png]]
'''Example 1.''' Drawing for the case
[[File:Fōrmulæ - Josephus problem 11.png]]
Line 2,278 ⟶ 2,617:
[[File:Fōrmulæ - Josephus problem 12.png]]
'''Example 2.''' Drawing for the case
[[File:Fōrmulæ - Josephus problem 13.png]]
Line 2,933 ⟶ 3,272:
end
</syntaxhighlight>
=={{header|Maxima}}==
<syntaxhighlight lang="maxima">
josephus_list(n,k):=(result:[],pos:1,ref:makelist(i,i,n),while ref#[] do (pos:mod(pos+k-2,length(ref))+1,push(ref[pos],result),ref:delete(ref[pos],ref)),
reverse(result));
/* Example */
/* last_survivor:last(josephus_list(41,3));
31
*/
</syntaxhighlight>
=={{header|Modula-2}}==
Line 3,335 ⟶ 3,685:
===iterative===
ALGOL 68, ANSI Standard BASIC, AppleScript[1,3(!!)], BASIC(*11), Batch File, C (but not ULL), Common Lisp[1], Craft Basic, Easylang, EDSAC (allegedly), Factor, Forth, FreeBASIC, FTCBASIC, Modula-2, Python[2], R, Racket, Ring, SequenceL, ZX Spectrum Basic<br>
Method: iterative mod maths madness - but hey, it will be extremely fast. Unlike recursive, it can also deliver >1 survivor, one at a time.
<!--<syntaxhighlight lang="phix">-->
Line 3,684 ⟶ 4,034:
return prisoners;
}</syntaxhighlight>
=={{header|Python}}==
Line 4,433 ⟶ 4,721:
remaining: 30
remaining 4: 3,34,15,30
</pre>
Line 4,515 ⟶ 4,760:
prisoner 34
</pre>
=={{header|V (Vlang)}}==
Line 4,643 ⟶ 4,854:
=={{header|Wren}}==
{{trans|Kotlin}}
<syntaxhighlight lang="
if (k <= 0 || m <= 0 || n <= k || n <= m) Fiber.abort("One or more parameters are invalid.")
var killed = []
Line 4,753 ⟶ 4,964:
Survivors: [15,30,34]
</pre>
{{omit from|GUISS}}
| |||