Project Euler - 19

No problema 19 do Project Euler, vamos assim dizer, há uma "pegadinha", principalmente para quem, como eu, deseja solucionar por força bruta.

O problema é assim proposto:

Observamos que no problema é dito que 1/jan/1900 caiu em uma segunda-feira, entretanto o problema pede para calcular o número de domingos que caíram no primeiro dia do mês, entre 1901 e 2000. Logo, o ano 1900 deve ser desconsiderado. Como 1900 não foi um ano bissexto, no ano seguinte o dia 1 de janeiro cairá no dia da semana subseqüente, ou seja, se em 1900 foi em uma segunda-feira, em 1901 será em uma terça-feira.

Esta informação é importante para a inicialização das variáveis...

Inicialmente, vamos precisar de uma função que indique se determinado ano é bissexto ou não.

Foi implementado assim:

Function is_bissexto([int]$a) {
    [int]$f = 0

    If (($a % 4) -eq 0) { 
        $f = 1 
        If (($a % 100) -eq 0) { $f = 0 }
    }
    Else { $f = 0 }
    If (($a % 400) -eq 0) { $f = 1 }
    Return $f
}

A função is_bissexto recebe um ano como argumento e retorna 1 se o ano é bissexto, ou zero se não é.

Assim, bastará somar 28 ao mês de fevereiro do ano correspondente, ou seja, se o ano for bissexto a função retorna 1 e o mês de fevereiro terá 29 dias, caso contrário, permanece com 28.

Vamos utilizar arrays para armazenar o número de dias de cada mês $mes e para representar qual o dia do mês é determinado dia da semana $dia.

$mes = @(31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)
$dia = @(0, 0, 0, 0, 0, 0, 0)

No caso, $mes[1] é que armazenará os dias do mês de fevereiro, que irá variar conforme o ano em questão for bissexto. O array $dia é inicializado com zero, mas no código receberá os dias do mês que estiver sendo calculado.

A implementação terá 3 laços For (um para o ano, outro para o mês e outro para os dias do mês, preenchendo os dias da semana no array $dia). Sendo que $dia[0] irá representar o domingo e cada vez que $dia[0] = 1, iremos incrementar uma variável que acumulará o somatório de domingos que caem no primeiro dia do mês.

O código completo ficou assim:

Function is_bissexto([int]$a) {
    [int]$f = 0

    If (($a % 4) -eq 0) { 
        $f = 1 
        If (($a % 100) -eq 0) { $f = 0 }
    }
    Else { $f = 0 }
    If (($a % 400) -eq 0) { $f = 1 }
    Return $f
}

$mes = @(31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)
$dia = @(0, 0, 0, 0, 0, 0, 0)
[int]$sun_sum = 0
[int]$ds = 2

For ([int]$ano=1901;$ano -le 2000;$ano++) {
    If (is_bissexto($ano) -eq 1) { $mes[1] = 29 }
    Else { $mes[1] = 28 }

    For ([int]$m=0; $m -lt 12; $m++) {
        For ([int]$d=1; $d -le $mes[$m]; $d++) {
            $dia[$ds] = $d
            If (($ds -eq 0) -and ($dia[$ds] -eq 1)) { 
                $sun_sum++ 
                Write-Host "Encontrou Domingo em: " $d "/"($m+1)"/"$ano
            }
            If ($ds -ge 6) { $ds = 0 }
            else { $ds++ }
        }
    }
}
write-Host "----------------------------------------------"
Write-Host "Há $sun_sum Domingos no primeiro dia do mês entre [1901-2000]"

.
.
.
Encontrou Domingo em:  1 / 3 / 1992
Encontrou Domingo em:  1 / 11 / 1992
Encontrou Domingo em:  1 / 8 / 1993
Encontrou Domingo em:  1 / 5 / 1994
Encontrou Domingo em:  1 / 1 / 1995
Encontrou Domingo em:  1 / 10 / 1995
Encontrou Domingo em:  1 / 9 / 1996
Encontrou Domingo em:  1 / 12 / 1996
Encontrou Domingo em:  1 / 6 / 1997
Encontrou Domingo em:  1 / 2 / 1998
Encontrou Domingo em:  1 / 3 / 1998
Encontrou Domingo em:  1 / 11 / 1998
Encontrou Domingo em:  1 / 8 / 1999
Encontrou Domingo em:  1 / 10 / 2000
----------------------------------------------
Há 171 Domingos no primeiro dia do mês entre [1901-2000]

Calculando Pi

O número Pi (π) há muito tempo encanta não apenas matemáticos, e há uma procura constante por métodos otimizados para obtê-lo com maior precisão. Em 1995, David Harold Bailey, em colaboração com Peter Borwein e Simon Plouffe, descobriu uma fórmula de cálculo de π, uma soma infinita (frequentemente chamada fórmula BBP):

Aqui um exemplo de implementação em Powershell. A fórmula converge rapidamente, com poucas iterações.

$PI = 0
For ([long]$k=0;$k -lt 12;$k++) {
   $PI += 1/[Math]::Pow(16,$k) * ( 4/(8*$k+1) - (2/(8*$k+4)) - 1/(8*$k+5) - 1/(8*$k+6) )
   Write-Host "Para k=$k, PI é ~" $PI 
}

Para k=0, PI é ~ 3,13333333333333
Para k=1, PI é ~ 3,14142246642247
Para k=2, PI é ~ 3,14158739034658
Para k=3, PI é ~ 3,14159245756744
Para k=4, PI é ~ 3,14159264546034
Para k=5, PI é ~ 3,14159265322809
Para k=6, PI é ~ 3,14159265357288
Para k=7, PI é ~ 3,14159265358897
Para k=8, PI é ~ 3,14159265358975
Para k=9, PI é ~ 3,14159265358979
Para k=10, PI é ~ 3,14159265358979
Para k=11, PI é ~ 3,14159265358979

Cálculo de Exponencial de X

Implementando o cálculo de Exponencial de X através da Série de Maclaurin:

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

Function ExpX([Double]$x, [Int32]$max) {
    $eX = 1
    For ($n=1;$n -lt $max;$n++) {
        $eX = $eX + [math]::Pow($x,$n) / (Fatorial $n)
    }
    Return $eX 
}

Clear-Host
$x = Read-Host "Calcula e^x com serie de Maclaurin. Qual o valor de x? "
$eX = [math]::Round((ExpX $x 40),10)
Write-Host -ForeGroundColor Yellow "e^$x=$eX"

Calcula e^x com serie de Maclaurin. Qual o valor de x? : 7
e^7=1096.6331584285

Problema do Relógio Digital

Supondo um relógio digital de 24 horas, quantas vezes um determinado dígito aparece durante 1 dia?

Esse interessante problema li em NRICH enriching mathematics.
Lá o problema é apresentado fazendo a pergunta sobre o dígito 5.
Se bem observarmos, o dígito 5 aparece 16 vezes em cada hora normal.

00:05 - 1
00:15 - 2
00:25 - 3
00:35 - 4
00:45 - 5
00:50 - 6
00:51 - 7
00:52 - 8
00:53 - 9
00:54 - 10
00:55 - 11
00:55 - 12
00:56 - 13
00:57 - 14
00:58 - 15
00:59 - 16

E aparece 76 vezes às 05:mm e às 15:mm, pois nesses horários há repetição em 05:05, 05:15,... e também em 05:55.
Assim, o cálculo é feito somando-se:

• 22 horas em que o 5 aparece 16 vezes
MAIS
• 2 horas em que o 5 aparece 76 vezes
Ou seja, (22x16) + (2x76) = 352 + 152 = 504

O dígito 5 aparece 504 vezes em um relógio digital de 24 horas durante 1 dia.

Então, tive a ideia de escrever um programinha em Powershell que calcule quantas vezes cada dígito 0,1,2,3,... aparece no relógio digital durante 1 dia e ao final exiba um relatório.

Function QuantoApareceEm24Horas([Int32] $digito) {
    [Int32] $dig1, $dig2, $dig3, $dig4, $contador=0

    ## Primeiro Horários 0h:mm e 1h:mm
    For ($dig1=0; $dig1 -le 1; $dig1++) { ## 0,1
        ########## $dig2 ############
        For ($dig2=0; $dig2 -le 9; $dig2++) { ## 0,1,2,3,4,5,6,7,8,9
            ########## $dig3 ############
            For ($dig3=0; $dig3 -lt 6; $dig3++) { ## 0,1,2,3,4,5
                ########## $dig4 ############
                For ($dig4=0; $dig4 -le 9; $dig4++) { ## 0,1,2,3,4,5,6,7,8,9
                    If ($dig1 -eq $digito) { 
                        $contador++
                        Write-Host $dig1$dig2":"$dig3$dig4" - "$contador
                    }
                    If ($dig2 -eq $digito) { 
                        $contador++
                        Write-Host $dig1$dig2":"$dig3$dig4" - "$contador
                    }
                    If ($dig3 -eq $digito) {
                        $contador++ 
                        Write-Host $dig1$dig2":"$dig3$dig4" - "$contador
                    }
                    If ($dig4 -eq $digito) {
                        $contador++ 
                        Write-Host $dig1$dig2":"$dig3$dig4" - "$contador
                    }
                } ##$dig4
            } ## dig3
        } ## dig2
    } ## dig1


    ## Horários 20, 21, 22, 23
    $dig1=2
    For ($dig2=0; $dig2 -le 3; $dig2++) { ## 0,1,2,3
        For ($dig3=0; $dig3 -le 5; $dig3++) { ## 0,1,2,3,4,5
            For ($dig4=0; $dig4 -le 9; $dig4++) { ## 0,1,2,3,4,5,6,7,8,9
                If ($dig1 -eq $digito) {
                    $contador++ 
                    Write-Host $dig1$dig2":"$dig3$dig4" - "$contador
                }
                If ($dig2 -eq $digito) {
                    $contador++ 
                    Write-Host $dig1$dig2":"$dig3$dig4" - "$contador
                }
                If ($dig3 -eq $digito) {
                    $contador++ 
                    Write-Host $dig1$dig2":"$dig3$dig4" - "$contador
                }
                If ($dig4 -eq $digito) {
                    $contador++ 
                    Write-Host $dig1$dig2":"$dig3$dig4" - "$contador
                }
            } ## $dig4
        } ## $dig3
    } ## $dig2

    Return $contador
} ##Function

Clear-Host
$Numeros=@()
[Int32] $i

For ($i=0; $i -le 9; $i++) {
    Write-Host -ForegroundColor Yellow "######################################"
    Write-Host -ForegroundColor Yellow "Calculando quantas vezes o dígito"$i
    Write-Host -ForegroundColor Yellow "aparece em relógio digital em 1 dia"
    Write-Host -ForegroundColor Yellow "######################################"
    $Numeros += QuantoApareceEm24Horas $i
}
Write-Host -ForegroundColor Green "######################################"
Write-Host -ForegroundColor Green "Relatório de Execução:"
For ($i=0; $i -le 9; $i++) {
    Write-Host -ForegroundColor Cyan "O dígito" $i "aparece" $Numeros[$i]"vezes em 24 horas."
}