The "Josephus" problem is to identify the position to stand in a circle of 41
men if every 3rd man will be successively eliminated around the circle and you
want to be the last remaining man.
In the following, n denotes the number of people in the initial circle, and k
denotes the count for each step, that is, k-1 people are skipped and the k-th
is executed. The people in the circle are numbered from 1 to n.
#include "crt.bi"
const N = 41
const K = 3
const S = !"The prisoner standing at position %2d is eliminated. %2d prisoner(S) eliminated.\n"
enum boolean
TRUE = (0 = 0)
FALSE = not TRUE
end enum
dim alive(1 to N) as boolean
for i as integer = 1 to N
alive(i) = TRUE
next i
dim as integer _
eliminated = 0, _ ' 0 to N
position = 1, _ ' 1 to N
fatal = 1 ' 1 to K
while eliminated < N
if alive(position) then
if fatal = K then
alive(position) = FALSE
eliminated += 1
printf(S, position, eliminated)
end if
fatal += 1
if fatal > K then fatal = 1
end if
position += 1
if position > N then position = 1
wend
print "Press a key..."
sleep
#include "crt.bi"
const N = 41
const K = 3
const S = !"The prisoner standing at position %2d is eliminated. %2d prisoner(S) eliminated.\n"
type TPrisoner
position as integer
next1 as TPrisoner ptr
next2 as TPrisoner ptr
end type
dim as TPrisoner ptr first, current, auxiliary
current = allocate(sizeof(TPrisoner))
current->position = 1
first = current
for i as integer = 2 to N
auxiliary = allocate(sizeof(TPrisoner))
auxiliary->position = i
current->next1 = auxiliary
current = auxiliary
next i
current->next1 = first
current = first
for i as integer = 1 to N
current->next2 = current->next1
current = current->next1
next i
dim as integer _
eliminated = 0, _ ' 0 to N
fatal = 1 ' 1 to K
current = first
while eliminated < N
if fatal = K then
auxiliary->next2 = current->next2
eliminated += 1
printf(S, current->position, eliminated)
endif
fatal += 1
if fatal > K then fatal = 1
auxiliary = current
current = current->next2
wend
current = first
for i as integer = 1 to N
auxiliary = current
current = current->next1
deallocate(auxiliary)
next i
print "Press a key..."
sleep
Last edited by Roland Chastain on May 14, 2015 9:47, edited 1 time in total.
Small variant of your linked list version (14 lines less):
- each object has one pointer to next
- each eliminated object is destructed in the same loop
#include "crt.bi"
const N = 41
const K = 3
const S = !"The prisoner standing at position %2d is eliminated. %2d prisoner(S) eliminated.\n"
type TPrisoner
position as integer
next1 as TPrisoner ptr
end type
dim as TPrisoner ptr first, current
current = allocate(sizeof(TPrisoner))
current->position = 1
first = current
for i as integer = 2 to N
current->next1 = allocate(sizeof(TPrisoner))
current->next1->position = i
current = current->next1
next i
current->next1 = first
dim as integer _
eliminated = 0, _ ' 0 to N
fatal = 1 ' 1 to K
while eliminated < N
if fatal = K then
dim as TPrisoner ptr p = current->next1
current->next1 = current->next1->next1
printf(S, p->position, eliminated)
deallocate p
eliminated += 1
else
current = current->next1
end if
fatal += 1
if fatal > K then fatal = 1
wend
print "Press a key..."
sleep
const N = 41
const K = 3
const S = "The prisoner standing at position ## is eliminated. ## prisoner(S) eliminated."
dim nextp(1 to N) as integer
for i as integer = 1 to N-1
nextp(i) = i + 1
next i
nextp(N) = 1
var eliminated = 0, skipped = 0
var p = 1, prevp = p
do while eliminated < N
if skipped < K-1 then
prevp = p
p = nextp(p)
skipped += 1
continue do
end if
nextp(prevp) = nextp(p)
prevp = p
p = nextp(p)
eliminated += 1
skipped = 0
print using S; prevp; eliminated
loop
print "Press a key..."
sleep
Nice examples using the C nomenclature possible now with FreeBasic and the use of memory allocation.
As an old BASIC programmer I know about linked lists but have never required them in any project.
It seems to me they need to be implemented as an object with a set of methods.
Last edited by BasicCoder2 on May 15, 2015 6:22, edited 1 time in total.
#include "lists.bi"
' http://www.freebasic.net/forum/viewtopic.php?p=207507#p207507
const N = 41
const K = 3
ListOfComparable(integer)
dim prisoners as ListOfInteger
for prisoner as integer = 1 to N
prisoners.Append prisoner
next prisoner
prisoners.First
do while prisoners.Count > 1
for i as integer = 1 to K - 1
prisoners.Succ
if prisoners.Index = 0 then prisoners.First
next i
print("exit prisoner " & prisoners.Value)
prisoners.CutCurrent
if prisoners.Index = 0 then prisoners.First
print(prisoners.Count & " prisoner(s) alive")
loop
print
print("prisoner " & prisoners.Value & " is the last prisoner alive")
print
print("Press a key...")
sleep
const N = 41 ' total number
const K = 3 - 1 ' selection interval
Dim p As String
Dim id As Integer
For i As Integer = 1 To N ' load up the string
p += Chr(i)
Next
While Len(p)
id = (id + K) Mod Len(p) ' find who's next
Print Using "_### eliminated. ## gone."; Asc(p, id+1); N - Len(p) + 1
p = Left(p, id) + Mid(p, id+2) ' remove selected
Wend
