Project Euler 17

O problema 17 do Project Euler propõe como desafio somar o número de letras dos números de 1 a 1000 escritos por extenso. Vamos adaptar o problema para o português do Brasil, mantendo-se a mesma proposta.

[int]$sum = 0

Function decompPTBR([int]$num) {
    $unidade = @("dez","um","dois","três","quatro","cinco","seis","sete","oito","nove")
    $dez_nove = @("onze","doze","treze","quatorze","quinze","dezesseis","dezessete","dezoito","dezenove")
    $dezena = @("vinte","trinta","quarenta","cinquenta","sessenta","setenta","oitenta","noventa","cem")
    $centena = @("cento","duzentos","trezentos","quatrocentos","quinhentos","seiscentos","setecentos","oitocentos","novecentos","mil")

    If ($num -le 10) {
        Write-Host $num":" $unidade[$num % 10]
        Return $unidade[$num % 10].Length
    }
    If (($num -gt 10) -and ($num -lt 20)) {
        Write-Host $num":" $dez_nove[($num % 10)-1]
        Return $dez_nove[($num % 10)-1].Length
    }
    If (($num -ge 20) -and ($num -le 100)) {
        $u = $num % 10
        $d = [Math]::Truncate($num / 10) - 2
        If ($u -eq 0) { 
            Write-Host $num":" $dezena[$d] 
            Return $dezena[$d].Length
        }
        Else { 
            Write-Host $num":" $dezena[$d] "e" $unidade[$u]
            Return ($dezena[$d].Length + 1 + $unidade[$u].Length)
        } 
    }
    If (($num -gt 100) -and ($num -le 1000)) {
        $u = $num % 10
        $d = [Math]::Truncate(($num / 10) % 10) ## - 2
        $c = [Math]::Truncate($num / 100) ## - 1

        If (($d*10+$u) -eq 0) { 
            Write-Host $num":" $centena[($c-1)] 
            Return $centena[($c-1)].Length
        }
        Else {
            If (($d*10+$u) -le 10) {
                Write-Host $num":" $centena[($c-1)] "e" $unidade[$u]
                Return ($centena[($c-1)].Length + 1 + $unidade[$u].Length)
            }
            If ( (($d*10+$u) -gt 10) -and (($d*10+$u) -lt 20) ) {
                Write-Host $num":" $centena[($c-1)] "e" $dez_nove[($u-1)]
                Return ($centena[($c-1)].Length + 1 + $dez_nove[($u-1)].Length)
            }
            If ((($d*10+$u) -ge 20) -and ($u -eq 0)) {
                Write-Host $num":" $centena[($c-1)] "e" $dezena[($d-2)]
                Return ($centena[($c-1)].Length + 1 + $dezena[($d-2)].Length)
            }
            If ((($d*10+$u) -ge 20) -and ($u -gt 0)) {
                Write-Host $num":" $centena[($c-1)] "e" $dezena[($d-2)] "e" $unidade[$u]
                Return ($centena[($c-1)].Length + 1 + $dezena[($d-2)].Length + 1 + $unidade[$u].Length)
            }
        }
    }
}

For ([int]$num=1; $num -le 1000; $num++) {
    $sum += decompPTBR($num)
}

Write-Host "=========================================="
Write-Host "Número de letras dos números de 1 a 1000:" $sum
Write-Host "=========================================="

Estamos imprimindo os números por extenso:

1: um
2: dois
3: três
4: quatro
5: cinco
6: seis
7: sete
8: oito
9: nove
10: dez
11: onze
12: doze
13: treze
14: quatorze
15: quinze
16: dezesseis
17: dezessete
18: dezoito
19: dezenove
20: vinte
21: vinte e um
22: vinte e dois
23: vinte e três
24: vinte e quatro

989: novecentos e oitenta e nove
990: novecentos e noventa
991: novecentos e noventa e um
992: novecentos e noventa e dois
993: novecentos e noventa e três
994: novecentos e noventa e quatro
995: novecentos e noventa e cinco
996: novecentos e noventa e seis
997: novecentos e noventa e sete
998: novecentos e noventa e oito
999: novecentos e noventa e nove
1000: mil
==========================================
Número de letras dos números de 1 a 1000: 19672
==========================================

Project Euler 12

Esse problema tem como tema números triangulares e seus respectivos divisores. No caso, é preciso encontrar o número triangular que tenha mais do que 500 divisores.

### Calcula a quantidade de divisores de um número
Function Divisores([int]$n) {
    [int] $count = 2
    [int] $i = 2;
 
    While (($i * $i) -lt $n) { 
        If ( $n % $i -eq 0 ) { $count+=2 }
        $i++
    } 
    If (($i*$i) -eq $n) { $count++ }
 
    Return $count
}


## enesimo número triangular é dado pela fórmula ntri*(ntri+1)/2
[int]$ndiv = 1
For ([int]$ntri=2; $ndiv -lt 500; $ntri++) {
    $ndiv = Divisores($ntri*($ntri+1)/2)
}
$ntri-=1
$ntri = ($ntri*($ntri+1)/2)
Clear-Host
Write-Host "O valor do primeiro número triangular com mais de 500 divisores é:" $ntri

O valor do primeiro número triangular com mais de 500 divisores é: 76576500

Project Euler - 6

Duas soluções para o problema 6 do Project Euler.

Function SomaQuadrados([Int32]$Num) {
    [Int32]$soma=0
    For ([int32]$i=1;$i -le $Num;$i++) {
        $soma += $i * $i
    }
    Return $soma
}

Function QuadradoSomas([Int32]$Num) {
    [Int32]$soma=0
    For ([int32]$i=1;$i -le $Num;$i++) {
        $soma += $i
    }
    Return ($soma * $soma)
}

[Int32]$s = SomaQuadrados 100
[Int32]$q = QuadradoSomas 100

Clear-Host
Write-Host -ForeGroundColor Yellow "SOLUÇÃO 1: Força Bruta"
Write-Host "A diferença entre o quadrado da soma dos 100 primeiros números [$q]"
Write-Host "e a soma dos quadrados dos números de 1 a 100 [$s] é: $q-$s ="($q-$s)
Write-Host "---------------------------------------------------------------------"
Write-Host -ForeGroundColor Yellow "SOLUÇÃO 2: Enfoque Matemático"
Write-Host "A soma dos números de 1 a N pode ser calculada com:"
Write-Host "Sn = n * (n + 1) / 2"
Write-Host "Se n = 100"
[Int32]$S100 = 100 * (100 + 1) / 2
Write-Host "S100 = 100 * (100 + 1) / 2 = " $S100
Write-Host "Logo, o quadrado da soma é: " ($S100 * $S100)
Write-Host "A soma dos quadrados de 1 a N pode ser calculada com:"
Write-Host "SQn = n * (n + 1) * (2n + 1) / 6"
Write-Host "Para n = 100"
$SQ100 = 100 * (100 + 1) * (2 * 100 + 1) / 6
Write-Host "SQ100 = 100 * (100 + 1) * (2 * 100 + 1) / 6 = " $SQ100
Write-Host "A diferença entre o quadrado da soma dos 100 primeiros números"
Write-Host "e a soma dos quadrados dos números de 1 a 100 é: "($S100*$S100-$SQ100)

SOLUÇÃO 1: Força Bruta
A diferença entre o quadrado da soma dos 100 primeiros números [25502500]
e a soma dos quadrados dos números de 1 a 100 [338350] é: 25502500-338350 = 25164150
---------------------------------------------------------------------
SOLUÇÃO 2: Enfoque Matemático
A soma dos números de 1 a N pode ser calculada com:
Sn = n * (n + 1) / 2
Se n = 100
S100 = 100 * (100 + 1) / 2 =  5050
Logo, o quadrado da soma é:  25502500
A soma dos quadrados de 1 a N pode ser calculada com:
SQn = n * (n + 1) * (2n + 1) / 6
Para n = 100
SQ100 = 100 * (100 + 1) * (2 * 100 + 1) / 6 =  338350
A diferença entre o quadrado da soma dos 100 primeiros números
e a soma dos quadrados dos números de 1 a 100 é:  25164150

Project - Euler 4

O enunciado do problema de nº 4 pede que se encontre o maior palíndromo da multiplicação de 2 números de 3 dígitos.

O enfoque aqui será o de implementar a solução tendo por base o método de busca de palíndromos que utilizamos no post Invertendo String e Palíndromos. Também, utilizaremos o fato de que estamos a procura do maior palíndromo, logo faz mais sentido começarmos a busca pelos números mais altos, dividindo a busca em intervalos [999-900], [899-700], etc. Assim sendo, quando encontrarmos um palíndromo, certamente será o maior, pois estamos multiplicando números maiores do que os intervalos que se seguirão. A busca então pode ser interrompida, acelerando a resposta.

Function ehPalindromo($pal) {
    $reversePal = -join([System.Linq.Enumerable]::Reverse($pal))
    if ($pal -eq $reversePal) {
        Return $true
    }
    else {
        Return $false
    }
}

Function VerPalNoIntervalo([Int32]$int1, [Int32]$int2) {
    [Int32]$max = 0
    For ($i=$int1; $i -gt $int2; $i--) {
        For ($j=$int1; $j -gt $int2; $j--) {
            If (ehPalindromo ([String]($i*$j))) {
                If (($i * $j) -gt $max) {
                    $max = $i * $j
                    Write-Host "Palíndromo entre $i * $j = $max"
                    Return $max
                }
            }
        } ## for $j
    } ## for $i
    Return 0
}

Clear-Host
[Int32]$i=999
For ([Int32]$j=899; $j -gt 100; $j-=100) {
    $i = $j + 100
    If (VerPalNoIntervalo $i $j) {
        Write-Host "O maior palíndromo encontrado de 3 dígitos foi: $max"
        Break
    }
}

Na implementação, a função ehPalindromo retorna $true se o número em questão é palíndromo. A função VerPalNoIntervalo recebe um intervalo, por exemplo [999-900], e verifica se há um palíndromo nesse intervalo - a verificação é feita chamando a função ehPalindromo.
No corpo principal, foi construído um loop que chama a função VerPalNoIntervalo passando os intervalos de busca. Conforme dito, como a busca está sendo feita a partir dos números maiores, em bloco, ao ser encontrado um palíndromo é seguro deduzir que é o maior.

Palíndromo entre 993 * 913 = 906609
O maior palíndromo encontrado de 3 dígitos foi: 906609

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

Soma dos Ímpares de um Intervalo

Aqui vamos criar uma função que seja capaz de somar todos os números ímpares de um determinado intervalo.

Em powershell, um intervalo pode ser especificado da seguinte forma, supondo que seja [3..9]:

$intervalo = 3..9

Cálculo de um número ímpar pode ser feito assim:

{ $numero % 2 -ne 0 }

Assim, podemos criar a função que efetua a soma de todos os números ímpares de um determinado intervalo, que é passado como parâmetro:

Function SomaImpares([Int32]$ini, [Int32]$fim) {
    $soma = 0
    $ini..$fim | Where {$_ % 2 -ne 0} | ForEach { $soma += $_ }

    return $soma
}