Implementando resolução do problema das 100 portas

Hoje mostrarei como implementar a resolução do problema das 100 portas em Visual Basic .NET. Enquanto navegava na grande rede de computadores internet, encontrei esse problema e achei que seria interessante mostrá-lo aqui.

O que é o problema das 100 portas

O problema das 100 portas cria a seguinte situação: você tem 100 portas em linha e todas as portas estão inicialmente fechadas. Você deve passar por cada porta 100 vezes. A cada vez que você passa pela porta, você deve fechá-la se estiver aberta, ou abri-la se estiver fechada. Na primeira vez você deve passar por todas as portas. Na segunda vez deve passar somente nas portas que são múltiplo de 2 (2, 4, 6, …). Na terceira vez, somente pelas portas que são múltiplos de 3 (3, 6, 9, …). Faça isso até a porta 100.

A pergunta: Ao final, quando passar por todas as portas, quais estarão abertas e quais estarão fechadas?

Resolvendo o problema

Nesse primeiro modelo que faremos para resolver o problema, levaremos o enunciado ao pé da letra e passaremos por todas as portas.

Para os exemplos, utilizarei uma Console Application do Visual Basic .NET.

Resolvendo com um For dentro de outro

    Sub Main()
        Dim portas(100) As Boolean

        For pass = 1 To 100
            For porta = pass - 1 To 99 Step pass
                portas(porta) = Not portas(porta)
            Next
        Next

        For porta = 0 To 99
            Console.WriteLine("Porta " & (porta + 1) & " está " & If(portas(porta), "Aberta", "Fechada"))
        Next
        Console.Read()
    End Sub

No código acima, temos a situação onde o código segue o que o enunciado pede.

Primeiro fazemos um laço de repetição For que passa por todas as portas e dentro do laço fazemos outro, que passa somente pelos múltiplos dessa porta; isso é possível porque cada interação do segundo For, “pula” os número das portas com o auxilio da variável pass, que é o número da porta do primeiro laço.

Dentro do segundo laço, falamos que cada porta deve ficar no status contrário ao que está, executando o código = Not portas(door).
No final fazemos um laço exibindo o status da porta ao fim das iterações. Aqui temos um trecho interessante, o condicional If está montado em linha (If(portas(porta), "Aberta", "Fechada")). Essa é uma ótima maneira de mostrarmos um valor mesmo que haja uma condição para a exibição. Essa forma segue a seguinte estrutura:

If (condição booleana, valor verdadeiro, valor falso)

Resolvendo o problema de outra forma

Quadrado PerfeitoNo próximo exemplo, o código é um pouco menor, porque só será necessário um laço de repetição. Dessa vez é utilizada a matemática para resolver o problema.

Segundo discursarão sobre a resolução do problema (ver fonte ao final do texto), somente as portas com números que são quadrados perfeitos ficam abertas.

Quadrado perfeito em matemática, é um número inteiro não negativo que pode ser expresso como o quadrado de um outro número inteiro.

Fonte: Wikipédia

Dito isso, vamos ao código:

    Sub Main()
        Dim portas(100) As Boolean

        For i = 1 To 10
            portas(i ^ 2 - 1) = True
        Next
        For porta = 0 To 99
            Console.WriteLine("Porta " & (porta + 1) & " está " & If(portas(porta), "Aberta", "Fechada"))
        Next

        Console.ReadLine()
    End Sub

Para conseguirmos somente os quadrados perfeitos, utilizamos a expressão i ^ 2, onde i é o número da iteração e o símbolo ^ (circunflexo) indica que o número (i) está sendo elevado a potencia (2). Seria o equivalente a i2.

Fazemos isso dentro do laço que vai de 1 a 10, porque a porta máxima é a 100 e 102. = 100. Para sabermos qual porta do array portas será aberta, devemos passar o índice do array, por isso a expressão i ^ 2 – 1. Como dito antes, sabemos o quadrado perfeito com o i ^2, o -1 da expressão é para ‘acertar’ o cálculo para o array que é baseado em zero (inicia em zero). Dessa forma quando i = 2, o resultado do quadrado seria 4, mas na verdade a porta 4 está na posição 3 do array.

Por hoje é só galera, espero que tenha gostado e entendido.

Fonte sobre problema das 100 portas.