Project Euler 2

Implementaremos 2 soluções para o problema de nº 2 do Project Euler:

Estamos implementando uma solução através do uso de recursividade (RecursiveFibonacciEvenSum) e outra utilizando um loop (FibonacciEvenSum).

Function RecursiveFibonacciEvenSum([Long]$pre, [Long]$cur, [Long]$evenSum) {
    If ($cur -gt 4000000) { Return $evenSum}
    If ($cur %2 -eq 0) { $evenSum = $evenSum + $cur }
    [Long]$tmp = $pre + $cur
    $pre = $cur
    $cur = $tmp
    RecursiveFibonacciEvenSum $pre $cur $evenSum
}
 
Function FibonacciEvenSum([Long]$pre, [Long]$cur) {
    [Long]$tmp = 0
    [Long]$evenSum = 0
 
    While($tmp -lt 4000000) {
        $tmp = $pre + $cur
        If ($tmp % 2 -eq 0) { $evenSum = $evenSum + $tmp }
        $pre = $cur
        $cur = $tmp
    }
    Return $evenSum
}
 
Clear-Host
$time = New-Object System.Diagnostics.Stopwatch
$time.Start()
RecursiveFibonacciEvenSum 1 1 0
$time.Stop()
$ts = $time.Elapsed
Write-Host "Tempo calculado com Recursividade:"
Write-Host $ts.Seconds "segundos e" $ts.Milliseconds "milisegundos"
 
$time2 = New-Object System.Diagnostics.Stopwatch
$time2.Start()
FibonacciEvenSum 1 1
$time2.Stop()
$ts2 = $time2.Elapsed
Write-Host "Tempo calculado com Loop:"
Write-Host $ts2.Seconds "segundos e" $ts2.Milliseconds "milisegundos"

Calculamos a soma dos números pares na Série de Fibonacci, obtendo 4613732 como resultado. Com relação ao tempo gasto, observamos que a implementação através de loop teve melhor desempenho do que a solução que utiliza recursividade.

4613732
Tempo calculado com Recursividade:
0 segundos e 157 milisegundos

4613732
Tempo calculado com Loop:
0 segundos e 28 milisegundos

Séries de Taylor - Cosseno

Neste post, vamos implementar o cálculo do cosseno de um ângulo através de um série de Taylor.

Function Fatorial([Int32]$num) {
    if ($num -eq 0) { return 1 }
    return $num * (Fatorial($num-1))
}

Function Cosseno($x,$max) {
    $CossenoX = 1 - ([math]::Pow($x,2) / (Fatorial 2))
    For ($n=2;$n -lt $max;$n++) {
        $CossenoX = $CossenoX + [math]::Pow(-1,$n)*[math]::Pow($x,(2*$n)) / (Fatorial (2*$n))
    }
    Return $CossenoX 
}

Clear-Host
$angulo = Read-Host "Digite um ângulo para calcular o Cosseno"
$rad = $angulo / 180 * [math]::PI
$Cosseno = [math]::Round((Cosseno $rad 20),10)
Write-Host -ForeGroundColor Yellow "Cos($angulo°)=$Cosseno"

Séries de Taylor - Seno

Aqui um exercício de implementação de um algoritmo para o cálculo do Seno de um ângulo através de uma série de Taylor.

Na implementação, estamos fixando as iterações em 20 e o arredondamento em 10 casas decimais. Observa-se a função de apoio Fatorial, a mesma que implementamos no post sobre recursividade.

Function Fatorial([Int32]$num) {
    if ($num -eq 0) { return 1 }
    return $num * (Fatorial($num-1))
}

Function Seno($x,$max) {
    $senoX = $x - ([math]::Pow($x,3) / (Fatorial 3))
    For ($n=2;$n -lt $max;$n++) {
        $senoX = $senoX + [math]::Pow(-1,$n)*[math]::Pow($x,(2*$n+1)) / (Fatorial (2*$n+1))
    }
    Return $senoX 
}

Clear-Host
$angulo = Read-Host "Digite um ângulo para calcular o Seno"
$rad = $angulo / 180 * [math]::PI
$seno = [math]::Round((Seno $rad 20),10)
Write-Host -ForeGroundColor Yellow "Seno($angulo°)=$seno"

Decimal para Binário

Este é um post bem simples, onde o objetivo é de apenas ilustrar como poderia ser implementado com o Powershell a conversão de um número decimal para binário através de um função recursiva. Não se quer, com isso, demonstrar o melhor método, nem tão pouco o mais otimizado.

$Global:Bin=""
Function Dec2Bin([Int32]$Num) {
    If ($Num -lt 0) {Return "Número a converter deve ser positivo"}
    If ($Num -lt 2) {Return (($Global:Bin+=$Num)|%{-join $_[$_.Length..0]})}
    $Global:Bin += ($Num % 2)
    If ($Num -eq 2) {Return (($Global:Bin+=1)|%{-join $_[$_.Length..0]})}
    Return Dec2Bin ([math]::Truncate($Num/2))
}

Clear-Host
[Int32]$Dec = Read-Host "Insira um número para converter em binário"
Write-Host "O equivalente em binário de $Dec é:" (Dec2Bin $Dec)

Sabemos que uma maneira de ser realizada a conversão é através dos restos sucessivos da divisão por 2. Por exemplo, na conversão do número 19.

Se bem observarmos na implementação proposta, são utilizadas chamadas recursivas à função Dec2Bin. Ainda (usando uma função recursiva), os valores de resto são empilhados em uma variável global do tipo String. Assim sendo, no teste de parada da recursividade, efetuamos uma inversão da pilha, ou seja, da String que armazena os restos.

Se colocarmos como entrada o número 19 no script, o resultado será:

Insira um número para converter em binário: 19
O equivalente em binário de 19 é: 10011

Desenhando com Pixels - parte 2

Na parte 1 de Desenhando com Pixels, criou-se funções para o desenho de pontos, retas, triângulos e quadrados. Ainda, naquele código usou-se o artifício de carregar um bitmap de fundo.

Agora, vamos acrescentar novas funções, como o desenho de círculos, bem como o desenho de figuras geométricas com preenchimento. Para o desenho dessa característica, usaremos o que foi aprendido no post sobre recursividade, ou seja, o preenchimento de uma figura pode ser obtido através de chamadas recursivas à própria função de desenho.

Na plotagem, criamos um novo atributo "espessura", possibilitando a geração de pontos maiores e, como todas as demais figuras são baseadas em pontos, a consequente geração de retas, quadrados, triângulos e círculos mais espessos.

Outra melhoria foi a alteração no modo de compor o fundo de desenho, sem a necessidade da carga de um bitmap gerado externamente, seja de um arquivo ou de uma string base64. Agora, o fundo foi implementado assim:

$img = New-Object System.Drawing.Bitmap($form.Width, $form.Height)
$form.BackgroundImage = $img
$form.BackgroundImageLayout = "None"

A implementação completa é demonstrada abaixo:

Add-Type -AssemblyName System.Windows.Forms
Add-Type -AssemblyName System.Drawing
##########################################################
Function plot([Int32]$x, [Int32] $y, [String] $cor, [Int32] $espessura) {
    for ([Int32]$ey=0;$ey -le $espessura;$ey++) {
        for ([Int32]$ex=0;$ex -le $espessura;$ex++) {
             $img.SetPixel($x+$ex, $y+$ey, $cor)
        }
    }
}
##########################################################
Function retaBresenham ([Int32]$x1, [Int32]$y1, [Int32]$x2, [Int32]$y2, [String]$cor, [Int32]$espessura) {
    [Int32] $dx = $x2 - $x1
    [Int32] $dy = $y2 - $y1
    [Int32] $stepx, $stepy

    if ($dy -lt 0) { 
        $dy = -$dy 
        $stepy = -1
    }
    else { $stepy = 1 }

    if ($dx -lt 0) { 
        $dx = -$dx 
        $stepx = -1
    }
    else { $stepx = 1 }

    $dy = $dy -shl 1
    $dx = $dx -shl 1

    plot $x1 $y1 $cor $espessura

    if ($dx -gt $dy) {
        [Int32] $fraction = $dy - ($dx -shr 1)
        while ($x1 -ne $x2) {
            if ($fraction -ge 0) {
                $y1 += $stepy
                $fraction -= $dx
            }
            $x1 += $stepx
            $fraction += $dy
            plot $x1 $y1 $cor $espessura
        }
    }
    else {
        [Int32] $fraction = $dx - ($dy -shr 1)
        while ($y1 -ne $y2) {
            if ($fraction -ge 0) {
                $x1 += $stepx
                $fraction -= $dy
            }
            $y1 += $stepy
            $fraction += $dx
            plot $x1 $y1 $cor $espessura
        }
    }
    
}

##########################################################
Function triangulo([Int32]$x1, [Int32]$y1, [Int32]$h, [String]$cor, [Int32]$espessura) {
    [Int32] $lado = ([math]::Sqrt(4*$h*$h/3))
    retaBresenham $x1 $y1 ($x1-($lado/2)) ($y1+$h) $cor $espessura
    retaBresenham $x1 $y1 ($x1+($lado/2)) ($y1+$h) $cor $espessura
    retaBresenham ($x1-($lado/2)) ($y1+$h) ($x1+($lado/2)) ($y1+$h) $cor $espessura
}

##########################################################
Function trianguloSolido([Int32]$x1, [Int32]$y1, [Int32]$h, [String]$cor) {
    ## Caso Base - Triângulo mínimo alcançado
    if ($h -lt 3) {
        triangulo $x1 $y1 $h $cor 2 
        return 
    }
    triangulo $x1 $y1 $h $cor 2
    return trianguloSolido $x1 ($y1+3) ($h-6) $cor
}

##########################################################
Function quadrado([Int32]$x1, [Int32]$y1, [Int32]$tam, [String]$cor, [Int32]$espessura) {
    retaBresenham $x1 $y1 ($x1+$tam) $y1 $cor $espessura
    retaBresenham $x1 $y1 $x1 ($y1+$tam) $cor $espessura
    retaBresenham $x1 ($y1+$tam) ($x1+$tam) ($y1+$tam) $cor $espessura
    retaBresenham ($x1+$tam) $y1 ($x1+$tam) ($y1+$tam) $cor $espessura
}

##########################################################
Function quadradoSolido([Int32]$x1, [Int32]$y1, [Int32]$tam, [String]$cor) {
    ## Caso Base - Quadrado mínimo alcançado
    if ($tam -lt 5) {
        quadrado $x1 $y1 $tam $cor 5
        return 
    }
    quadrado $x1 $y1 $tam $cor 5
    return quadradoSolido ($x1+5) ($y1+5) ($tam-10) $cor
}

##########################################################
Function circuloSolido([Int32]$xC, [Int32]$yC, [Int32]$r, [String]$cor) {
    ## Caso Base - Quadrado mínimo alcançado
    if ($r -lt 5) {
        plot $xC $yC $cor 5
        return
    }
    circulo $xC $yC $r $cor 5
    return circuloSolido $xC $yC ($r-5) $cor
}

##########################################################
Function circulo([Int32]$xC, [Int32]$yC, [Int32]$r, [String]$cor, [Int32]$espessura) {
    [Int32] $x = 0
    [Int32] $y = $r
    [Int32] $u = 1
    [Int32] $v = 2*$r-1
    [Int32] $E = 0

    while ($x -lt $y) {
        plot ($xC + $x) ($yC + $y) $cor $espessura ## NNE
        plot ($xC + $y) ($yC - $x) $cor $espessura ## ESE
        plot ($xC - $x) ($yC - $y) $cor $espessura ## SSW
        plot ($xC - $y) ($yC + $x) $cor $espessura ## WNW
        $x++
        $E += $u
        $u += 2
        if ($v -lt (2*$E)) {
            $y--
            $E -= $v
            $v -= 2
        }
        if ($x -gt $y) { return }
        plot ($xC + $y) ($yC + $x) $cor $espessura ## ENE
        plot ($xC + $x) ($yC - $y) $cor $espessura ## SSE
        plot ($xC - $y) ($yC - $x) $cor $espessura ## WSW
        plot ($xC - $x) ($yC + $y) $cor $espessura ## NNW
    }
}


Function bmpRefresh([System.Drawing.Bitmap]$img){
    $formGraphics.DrawImage($img,0,0,$img.Width,$img.Height)    
}

##########################################################
[Windows.Forms.Application]::EnableVisualStyles()
$form = New-Object Windows.Forms.Form
$form.Width = 600;
$form.Height = 480;
$img = New-Object System.Drawing.Bitmap($form.Width, $form.Height)
$form.BackgroundImage = $img
$form.BackgroundImageLayout = "None"
$formGraphics = $form.CreateGraphics()

$form.Add_Shown({

        ### Pontos
        for ([Int32]$x=30;$x -lt 55;$x+=5) {
            plot $x 50 'Red' 0
            plot $x 60 'Red' 1
            plot $x 70 'Red' 2
        }
        bmpRefresh($img)

        ### Reta
        retaBresenham 50 0 535 440 'Orange' 2
        retaBresenham 0 0 585 440 'Blue' 1
        bmpRefresh($img)

        ### Triângulo
        triangulo 100 100 100 'Green' 3
        triangulo 100 120 70 'Gray' 2
        bmpRefresh($img)

        ### Triângulo Sólido
        trianguloSolido 100 220 100 'Red'
        bmpRefresh($img)

        ### Quadrado
        quadrado 370 70 100 'Red' 5
        quadrado 390 90 60 'Black' 3
        quadrado 410 110 20 'blue' 2
        bmpRefresh($img)

        ### Quadrado Sólido
        quadradoSolido 250 70 100 'Green'
        bmpRefresh($img)

        ### Círculo
        circulo 200 380 40 'Black' 2
        bmpRefresh($img)

        circuloSolido 340 370 60 'Blue'
        bmpRefresh($img)
        
})

$form.ShowDialog()

O resultado:

Recursividade

Se tivermos um algoritmo para resolver um problema solucionando uma instância menor do mesmo problema, podemos usar funções recursivas. Reduz-se o problema até uma parte em que a recursividade cessa.

Quando se implementa recursividade, o exemplo clássico que nos vem à mente é o do cálculo do fatorial de um número. Se bem observarmos, o fatorial de um número é calculado multiplicando-o pelos números que o antecedem. Assim, fatorial de 6! = 6x5x4x3x2x1. E, por definição, o fatorial de 0! = 1.

Desse modo, é possível implementar facilmente uma função recursiva que calcule o fatorial de um número. Por exemplo:

Function fatorial([Int32]$num) {
    if ($num -eq 0) { return 1 }
    return $num * (fatorial($num-1))
}

Clear-Host
do {
    try {
        $numOk = $true
        [Int32]$num = Read-host `
        "Digite um número entre 0-100 para calcular o fatorial e pressione [ENTER]"
    }
    catch {$numOK = $false}
}
until (($num -ge 0 -and $num -le 100) -and $numOK)

Write-Host -NoNewline "O fatorial de $num é: "
fatorial($num)

Um exemplo de execução para o cálculo do fatorial de 7!

Digite um número entre 0-100 para calcular o fatorial e pressione [ENTER]: 7
O fatorial de 7 é: 5040

No post Invertendo Strings e Palíndromos, demonstramos uma maneira de implementar uma função que verifica se uma string é um palíndromo, ou seja, sua forma inversa tem escrita idêntica. É possível implementar uma função recursiva que verifica se uma string é palíndromo, mas fica apenas como exercício de programação, dado que a implementação no post anterior é bem mais simples.

Seguindo a ideia para funções recursivas de dividir um problema em instâncias menores, observamos que palavras são palíndromos quando a letra inicial e final são as mesmas. Assim, podemos usar esse algoritmo de testar se são iguais as letras inicial e final, removê-las e repetir a mesma lógica, até que não restem letras ou reste uma letra central. Se isso acontecer, a palavra é um palíndromo. Cada iteração seria uma chamada à função recursiva. O código poderia ser escrito assim:

Function trimFirstLast($pal) {
    $pal = $pal.TrimStart($pal[0])
    $pal = $pal.TrimEnd($pal[$pal.Length-1])
    return $pal
}

Function ehPalindromo([String]$pal) {
    if ($pal.Length -lt 2) { return $true }
    if ($pal[0] -ne $pal[$pal.Length-1]) { return $false }
    return ehPalindromo(trimFirstLast($pal))
}

$palavras = @("RELER","REVIVER","RADAR","ARARA","AMORA","SALAS",`
"ANILINA","MUSSUM","CASACA","MOTOR","OSSO","RIR","MIRIM","ROTOR")

Clear-Host

ForEach ($pal in $palavras) {
    Write-Host -NoNewLine "$pal é palíndromo? "
    ehPalindromo $pal
}

Com o seguinte resultado de execução:

RELER é palíndromo? True
REVIVER é palíndromo? True
RADAR é palíndromo? True
ARARA é palíndromo? True
AMORA é palíndromo? False
SALAS é palíndromo? True
ANILINA é palíndromo? True
MUSSUM é palíndromo? True
CASACA é palíndromo? False
MOTOR é palíndromo? False
OSSO é palíndromo? True
RIR é palíndromo? True
MIRIM é palíndromo? True
ROTOR é palíndromo? True

Referência: KHANACADEMY - Recursividade