Survivor of the Josephus Problem
>function countAndRemove (i,k,v) ...
loop 1 to k
repeat
i=i+1;
if i>cols(v) then i=1; endif;
until v[i];
end;
end;
v[i]=0;
return i;
endfunction
>format(4,0); v=ones(1,10)
1 1 1 1 1 1 1 1 1 1
>i=0; loop 1 to 9; i=countAndRemove(i,7,v), v, end;
7
1 1 1 1 1 1 0 1 1 1
4
1 1 1 0 1 1 0 1 1 1
2
1 0 1 0 1 1 0 1 1 1
1
0 0 1 0 1 1 0 1 1 1
3
0 0 0 0 1 1 0 1 1 1
6
0 0 0 0 1 0 0 1 1 1
10
0 0 0 0 1 0 0 1 1 0
5
0 0 0 0 0 0 0 1 1 0
8
0 0 0 0 0 0 0 0 1 0
>function map determineSurvivor (k,n) ...
v=ones(1,n);
i=0;
loop 1 to n-1;
i=countAndRemove(i,k,v);
end;
return nonzeros(v)
endfunction
>determineSurvivor(7,10)
9
>determineSurvivor(1:10,(1:10)')
1 1 1 1 1 1 1 1 1 1
2 1 2 1 2 1 2 1 2 1
3 3 2 2 1 1 3 3 2 2
4 1 1 2 2 3 2 3 3 4
5 3 4 1 2 4 4 1 2 4
6 5 1 5 1 4 5 3 5 2
7 7 4 2 6 3 5 4 7 5
8 1 7 6 3 1 4 4 8 7
9 3 1 1 8 7 2 3 8 8
10 5 4 5 3 3 9 1 7 8
>function determineLastTwoSurvivors (k,n) ...
v=ones(1,n);
i=0;
loop 1 to n-2;
i=countAndRemove(i,k,v);
end;
return nonzeros(v)
endfunction
>shortformat; determineLastTwoSurvivors(3,40)
[ 13 28 ]
Examples Homepage