Rozwiązanie problemu Józefa Flawiusza w PowerShell

Józef Flawiusz walczył w powstaniu żydowskim przeciwko rzymianom. Pewnego razu, żołnierze żydowscy zostali otoczeni przez wojsko rzymskie i 40 powstańców wolało popełnić samobójstwo niż oddać się w niewolę. Żeby nie było łatwo w przewidzeniu kto będzie ostatni w tym czynie, postanowiono, że powstańcy staną w okręgu i co 3 osoba będzie dokonywać samobójstwa. Pomysł samobójstwa nie podobał się Józefowi i chciał stanąć w takim miejscu, aby jako ostatni mógł oddać się do niewoli i przeżyć. Wyznaczenie tego ostatniego miejsca nazywa się problemem Józefa Flawiusza.

Symulację graficzną algorytmu można zobaczyć na tej stronie.

Dla uproszczenia numeracja miejsc jest od 0. Poniżej jest rozwiązanie iteracyjne:

function Solve-JosephusProblem
{
    param(
        [ValidateRange(1,1000)]
        [int]$killEvery = 3,
        [ValidateRange(1,1000)]        
        [int]$soldiers = 40
      )
      $i=1
      $rest=0
      while($i -le $soldiers)
      {
        $rest = ($rest + $killEvery ) % $i 
        $i++
      }
      return $rest
}

Sprawdzenie miejsca dla 10 żołnierzy:

Solve-JosephusProblem -soldiers 10 -killEvery 3
#3

Gdyby samobójca był wybierany co 1 osobę to ostatnia osoba dokona samobójstwa.

Solve-JosephusProblem -soldiers 41 -killEvery 1

Poniżej jest rozwiązanie rekurencyjne:

function Solve-JosephusProblemRec
{
    param(
        [ValidateRange(1,1000)]
        [int]$killEvery = 3,
        [ValidateRange(1,1000)]
        [int]$soldiers = 40
      )

    if($soldiers -eq 1)
    { 
        return 0 
    }
    else
    {
        [int]$recSolve = Solve-JosephusProblemRec -killEvery $killEvery -soldiers ($soldiers-1)
        return (($recSolve +$killEvery  ) % $soldiers )  
    }
}

Nie ukrywam, że dużo pomogła mi strona na wiki opisująca ogólny problem.

Sprawdzamy na którym miejscu powinien Józef Flawiusz się ustawić:

$soldiers =41
$killEvery =3
Solve-JosephusProblem -soldiers $soldiers -killEvery $killEvery  #30
Solve-JosephusProblemRec -soldiers $soldiers -killEvery $killEvery #30