79 lines
2.0 KiB
Plaintext
79 lines
2.0 KiB
Plaintext
O = 50
|
|
N = 2*O
|
|
iterations = 10000
|
|
|
|
REM From the numbers 0 to N-1 inclusive, pick O of them.
|
|
function shuffle(N, O)
|
|
dim array(N)
|
|
for i = 0 to N-1
|
|
array[i] = i
|
|
next i
|
|
for i = 0 to O-1
|
|
swapindex = i + rand*(N-i)
|
|
swapvalue = array[swapindex]
|
|
array[swapindex] = array[i]
|
|
array[i] = swapvalue
|
|
next i
|
|
return array
|
|
end function
|
|
|
|
REM given N drawers with O to open, prisoner P chooses randomly: does he choose well?
|
|
function chooserandom(drawers, N, O, p)
|
|
choices = shuffle(N, O)
|
|
for i = 0 to O-1
|
|
if drawers[choices[i]] = p then return true
|
|
next i
|
|
return false
|
|
end function
|
|
|
|
REM N prisoners randomly choose O drawers to open: do they all choose well?
|
|
function allchooserandom(N, O)
|
|
drawers = shuffle(N, N)
|
|
for p = 0 to N-1
|
|
goodchoice = chooserandom(drawers, N, O, p)
|
|
if not goodchoice then return false
|
|
next p
|
|
return true
|
|
end function
|
|
|
|
REM given N drawers with O to open, prisoner P chooses smartly: does he choose well?
|
|
function choosesmart(drawers, N, O, p)
|
|
numopened = 0
|
|
i = p
|
|
while numopened < O
|
|
numopened += 1
|
|
if drawers[i] = p then return true
|
|
i = drawers[i]
|
|
end while
|
|
return false
|
|
end function
|
|
|
|
REM N prisoners smartly choose O drawers to open: do they all choose well?
|
|
function allchoosesmart(N, O)
|
|
drawers = shuffle(N, N)
|
|
for p = 0 to N-1
|
|
goodchoice = choosesmart(drawers, N, O, p)
|
|
if not goodchoice then return false
|
|
next p
|
|
return true
|
|
end function
|
|
|
|
cls
|
|
print N; " prisoners choosing ";O;" drawers, ";iterations;" iterations:"
|
|
|
|
total = 0
|
|
for iteration = 1 to iterations
|
|
if allchooserandom(N, O) then total += 1
|
|
next iteration
|
|
|
|
print "Random choices: "; total;" out of ";iterations
|
|
print "Observed ratio: "; total/iterations; ", expected ratio: "; (O/N)^N
|
|
|
|
total = 0
|
|
for iteration = 1 to iterations
|
|
if allchoosesmart(N, O) then total += 1
|
|
next iteration
|
|
|
|
print "Smart choices: "; total;" out of ";iterations
|
|
print "Observed ratio: "; total/iterations; ", expected ratio with N=2*O: greater than about 0.30685": REM for N=100, O=50 particularly, about 0.3118
|