piątek, 14 marca 2014

Problem Józefa Flawiusza w PowerShell cz.2

Już wcześniej pisałem o problemie Józefa Flawiusz. W tamtych czasach nie miałem rozwiązania przedstawiającego wszystkie iteracje tylko rozwiązanie zwracało ostatni element. Napisałem od nowa algorytm do wyświetlenia wszystkich elementów.
Poniżej jest funkcja iteracyjna do wyświetlenia kolejności elementów:
function Iterate-JosephusFlavius(
        [ValidateRange(1,1000)]
        [int]$killEvery = 3,
        [ValidateRange(1,1000)]        
        [int]$soldiers = 41
      )
{
    [bool[]]$bools = @($false)*$soldiers
    $indexOfKilledSoldiers=@()
    $soldiersToKill = $soldiers
    $rest = 0
    $setps=0
    while($soldiersToKill  -gt 0)
    {
        for($i=$rest; $i -lt $bools.Length;$i++)
        {
            if($bools[$i] -eq $false)
            {
                $setps++
                if($setps -eq $killEvery)
                {
                    $bools[$i] = $true
                    $indexOfKilledSoldiers += $i
                    $soldiersToKill--
                    $setps=0
                }
            }
        }
        $rest = $i -$bools.Length
    }
    return $indexOfKilledSoldiers
}
A tutaj jest funkcja rekurencyjna. Z tą funkcją miałem więcej problemów. Niestety argumenty funkcji są inne dla iteracji jak i dla rekurencji. Jak będę miał chwilkę czasu to poprawię tą różnicę.
function Recursive-JosephusFlavius(
        [ValidateRange(1,1000)]
        [int]$killEvery = 3,
        [int[]]$soldiers,
        [int[]]$killedSoldiers=@(),
        [int]$prevRest = 0
      )
{
    if($soldiers.Length -eq 0 )
    {
        return $killedSoldiers
    }
    $aliveSoldiers=@()
    
    if($soldiers.Length - $killEvery -lt 0)
    {
        $soldierToKill = (($killEvery + $prevRest) -1) % $soldiers.Length 
        for($i=0; $i -lt $soldiers.Length; $i++)
        {
            if($soldierToKill -eq $i)
            {
                $killedSoldiers += $soldiers[$i]
            }else
            {
                $aliveSoldiers += $soldiers[$i] 
            }
        }  
    }
    else
    {
        for($i=0; $i -lt $soldiers.Length; $i++)
        {
            if(($i+1)  % $killEvery -ne 0)
            {
                $aliveSoldiers +=   $soldiers[($i-$prevRest)]  
            }else
            {
                $killedSoldiers +=  $soldiers[($i-$prevRest)]
            }
        }
        $soldierToKill = $soldiers.Length % $killEvery
    }
   return  Recursive-JosephusFlavius -soldiers $aliveSoldiers -killEvery $killEvery -killedSoldiers $killedSoldiers  -prevRest $soldierToKill 
}

Wywołanie tych funkcji oraz sprawdzenie działania wygląda następująco:
$soldiers = 0..40 #41 soldiers
$killEvery = 3

$res1= Recursive-JosephusFlavius -soldiers $soldiers -killEvery $killEvery
$res2 = Iterate-JosephusFlavius  -soldiers ($soldiers.Length) -killEvery $killEvery

for($i=0; $i -lt [math]::Max($res1.Length,$res2.Length); $i++)
{
    if($res1[$i] -ne  $res2[$i])
    {
        throw "not the same"
    }
    else
    {
        Write-Host $res1[$i]
    }
}

Brak komentarzy:

Prześlij komentarz