12  Exercícios com vetores

Os vetores permitem que sejam realizados algoritmos bem mais complexos, nesse capítulo veremos algums exercícios.

12.1 Permutação

Dado um vetor com inteiros, queremos verificar se esse vetor contém uma permutação. Para isso, temos que verificar em um vetor de tamanho n, se ele contém os números de 1 a n exatamente uma vez cada 1. O vetor [3, 1, 2] é uma permutação, pois tem tamanho 3 e os elementos de 1 a 3 aparecem uma vez.

Uma forma de se resolver esse problema é por meio de um indicador de passagem. Inicialmente vamos supor que o vetor é uma permutação, em seguida verificamos se todos os números entre 1 e n estão no vetor. Isso pode ser feito com comando in, que verifica se um elemento pertence ao vetor.

function permutação(l)
    perm = true
    tamanho = length(l)
    i = 1
    while i <= tamanho
        if !(i in l)
            perm = false
        end    
        i += 1
    end
    return perm
end

permutação (generic function with 1 method)

Uma outra alternativa é verificar se para cada elemento do vetor, se ele está entre 1 e n, e é unico. Ou seja, verificamos se o primeiro elemento está entre 1 e n, e depois percorremos o vetor para ver se ele é único. Em seguida fazemos isso para os elementos seguintes. O código fica:

function permutação(l)
    perm = true
    tamanho = length(l)
    i = 1
    while i <= tamanho
        if (l[i] > tamanho || l[i] <= 0)
            perm = false
        end
        j = i +1
        while j <= tamanho
            if l[j] == l[i]
                perm = false
            end
            j += 1
        end
        i += 1
    end
    return perm
end

permutação (generic function with 1 method)

Uma outra alternativa é ter um vetor auxiliar onde contamos as ocorrências de cada número entre 1 e n. Ao final, todos os elementos desse vetor auxiliar tem que valer 1. Dessa vez, aproveitamos e já colocamos os testes automatizados.

using Test
function permutação(l)
    perm = true
    tamanho = length(l)
    aux = zeros(Int8, tamanho)
    for i in l
      if i < 1 || i > tamanho
        perm = false
      else
        aux[i] += 1
      end
    end
    for i in aux
      if i != 1
        perm = false
      end
    end  
    return perm
end

@testset "Verifica Permutação" begin
    @test permutação([1,2,3])
    @test permutação([3, 2, 1])
    @test permutação([1])
    @test permutação([2, 1])
    @test permutação([4, 2, 3, 1])
    @test !permutação([1, 1])
    @test !permutação([1, 3])
    @test !permutação([4, 2, 3, -1])
    @test !permutação([5, 2, 3, 1])
    @test permutação([])
    @test !permutação([0, 3, 3])
    @test !permutação([2, 2, 2])
end

Test Summary:       | Pass  Total  Time
Verifica Permutação |   12     12  0.1s

Test.DefaultTestSet("Verifica Permutação", Any[], 12, false, false, true, 1.737500420375648e9, 1.737500420476822e9, false, "/Users/lucas/ws/livro-alfredo/chapters/12.qmd")

12.2 Histograma

Já que vimos o exemplo anterior onde “contamos” o número, podemos ir um pouco além e calcular o histograma de um vetor com números entre 1 e 10.

using Test

function histograma(l)
    result = [0,0,0,0,0,0,0,0,0,0]
    i = 1
    while i <= length(l)
        valor_atual = l[i]
        if valor_atual >= 1 && valor_atual <= 10
           result[valor_atual] += 1
        end
        i += 1
    end
    return result
end

@testset "Verifica Histograma" begin
    @test [1,0,0,0,0,0,0,0,0,0] == histograma([1])
    @test [0,0,0,0,0,0,0,0,0,0] == histograma([-1])
    @test [0,0,1,0,0,0,0,0,0,0] == histograma([3])
    @test [0,0,0,0,0,0,0,0,0,1] == histograma([10])
    @test [0,0,0,0,0,0,0,0,0,0] == histograma([11])
    @test [1,4,0,2,5,1,0,1,0,0] == histograma([5,6,5,4,5,5,4,2,8,2,1,2,5,2])
    @test [0,0,0,0,0,0,0,0,0,0] == histograma([])
    end

Test Summary:       | Pass  Total  Time
Verifica Histograma |    7      7  0.0s

Test.DefaultTestSet("Verifica Histograma", Any[], 7, false, false, true, 1.737500420717199e9, 1.737500420758469e9, false, "/Users/lucas/ws/livro-alfredo/chapters/12.qmd")

12.3 Modelando problemas com o computador

O computador pode ser uma ferramenta bem poderosa para a modelagem de problemas reais. Para isso vamos pegar o caso do problema dos aniversários. Esse problema também é conhecido pelo paradoxo do aniversário: Calcular a probabilidade de que em uma sala com n pessoas, pelo menos duas possuam a mesma data de aniversário. Esse problema pode ser resolvido usando probabilidade, por meio da qual se descobre que se a sala tem 23 pessoas a chance de duas terem a mesma data é de pouco mais de 50%.

Mas, também podemos modelar esse problema computacionalmente. Para isso, o primeiro passo é simplificar as datas, ao invés de mês e ano, podemos codificar os dias em um número entre 1 e 365, sendo que 1 corresponderia a primeiro de janeiro. Para resolver o problema, podemos sortear n datas, e ver se há alguma repetição, se houver encontramos duas pessoas com a mesma data.

Isso está representado na função experimento_niver abaixo. Mas, para saber a chance real, temos que repetr o experimento várias vezes. Na função main() abaixo, pedimos a quantidade de experimentos e o número de pessoas para executar a simulação.

function experimento_niver(n)
    repetiu = false
    i = 1
    nivers = []
    while i <= n && (repetiu == false)
        niver = rand(1:365)
        if niver in nivers
            repetiu = true
        end
        push!(nivers, niver)
        i += 1
    end
    return repetiu
end

function main()
    print("Quantos experimentos? ")
    quantas = readline()
    print("Quantas pessoas? ")
    npessoas = readline()
    quantas = parse(Int64, quantas)
    npessoas = parse(Int64, npessoas)
    sucessos = 0
    i = 1
    while i <= quantas
        if experimento_niver(npessoas)
            sucessos += 1
        end
        i += 1
    end
    println("A probabilidade estimada é ", 100*sucessos/quantas, "%")
end
main()

A parte interessante é que podemos com pequenas variações ter outros experimentos, como verificar se mais do que duas pessoas fazem aniversário na mesma data. Para isso, abaixo, contamos o número de repetições.

function experimento_niver(n)
    repetiu = 0
    i = 1
    nivers = []
    while i <= n
        niver = rand(1:365)
        if niver in nivers
            repetiu += 1
        end
        push!(nivers, niver)
        i += 1
    end
    return repetiu >= 2
end

experimento_niver (generic function with 1 method)