Guia do Calouro para programação competitiva - Introdução a programação (Vetores)

calouros Fev 17, 2021

Demorei, férias acabaram, mas voltei.

Fim de ano perfeito, consegui terminar a Introdução a programação e continuar o semestre de cabeça limpa (sqn). Espero que todos estejam bem e se cuidando. Mas enfim, vamos continuar logo essa introdução, porque a produção parou de verdade durante as férias, e espero não ter prometido explicar vetores em algum tempo determinado.

Mas agora que voltei, espero voltar com tudo, mas antes disso, não custa nada fazer uma recapitulação do que passei.

Começamos vendo o básico do básico: o que são variáveis, como declarar variáveis, atribuir valores a elas, realizar operações aritméticas, ler entrada do usuário e escrever uma saída para o usuário; em seguida, vimos comparações e operações lógicas: E, OU, NEGAÇÃO, entre outros; e por último vimos sobre laços de repetição. Agora, vamos ver sobre vetores.

Vetores

Para explicar o que são vetores, vou usar de um exemplo simples para facilitar a explicação: suponha que você tenha diversas caixas, onde em cada caixa você guarda um determinado número de doces. Inicialmente, cada caixa possui um nome e tem a informação de quantos doces existem na respectiva caixa, e ficam espalhadas pela casa em lugares aleatórios. Agora, suponha que você deseja organizar essas caixas, de forma que você não precise mais nomear cada caixa, e todas fiquem juntas numa mesma caixa, só que maior. Dessa forma, ao invés de existirem várias caixas espalhadas aleatoriamente pela casa, você possui apenas uma caixa maior, contendo todas as caixas, e seus respectivos doces.

Agora, imagine que essa casa é a memória do seu computador, onde cada caixa de doce é uma variável. O vetor é essa caixa maior que contém a informação das outras caixas. Não vou explicar mais aprofundado que isso, pois com esse simples exemplo já é possível ter uma noção do que é um vetor, correto? Então eu te pergunto, o que vale mais a pena: deixar as caixas espalhadas pela casa, ou ter apenas uma caixa contendo todas as caixas?

Pois bem, naturalmente, acredito que sua resposta tenha sido: "usar vetores". Sinto informar, mas essa resposta está parcialmente errada, já que a resposta correta para essa questão (e muitas outras quando o assunto é escolher o que usar) é: depende. Existem diversos fatores a serem levados em conta sempre que for decidir entre usar um e outro, e não vou conseguir explicar cada fator aqui.

Porém, vamos supor um caso onde usar vetores seja de fato a melhor opção. Vamos continuar com o exemplo dos doces: temos uma pessoa que quer armazenar quantos doces existem em cada caixa, além de querer saber qual a diferença de doces entre a primeira e a última caixa, a segunda e a penúltima e assim por diante, porém o número de caixas varia de acordo com a vontade dessa pessoa cada vez que ela decide realizar essa operação.

Aqui nesse problema existem 2 fatores muito interessantes para ser levado em conta na hora de decidir entre variáveis e vetores: a quantidade de caixas (elementos) é variável a cada execução e as operações que vão revisitar cada elemento para gerar a resposta. Outro fator importante que vale destacar aqui, é a quantidade máxima de elementos que podem existir no problema (quando for resolver probleminhas cheque os limites, para ver se não é algo como $N \leq 200000$ ou coisa parecida).

Obviamente, esse programa dá para ser resolvido sem utilizar vetores, desde que você goste de sofrer bastante. Porém, como eu não sou uma pessoa que gosta tanto assim de sofrer (prefiro pegar exames finais a fazer trabalhos, não posso dizer que não gosto de sofrer), vou escrever inicialmente uma solução para esse problema utilizando vetores com o pseudocódigo BRUTE:

/// Isso aqui é um comentário e não é compilado / executado
/// Irei utilizar disso para explicar as partes do código a partir de agora
LEIA(n) /// LEIA é um comando para solicitar um valor do usuário
vetor := [n] /// Representamos o vetor por [], e indicamos seu tamanho por n

PARA i DE 0 A n-1 FAÇA
	LEIA(vetor[i])	/// Quando utilizamos variavel[indice], 
			/// indicamos que queremos fazer algo na caixa
			/// número indice.
			/// Vou explicar sobre índices adiante
FIMPARA

esquerda := 0
direita := n-1

ENQUANTO (esquerda <= direita) FAÇA
	ESCREVA(vetor[esquerda]-vetor[direita])
	esquerda := esquerda+1
	direta := direita-1
FIMENQUANTO

Certo, com esse programa simples somos capazes de resolver o problema proposto. Porém, como prometido nos comentários do código, existe algo que eu devo explicar para ajudar no entendimento da solução.

Índices

Lembra quando eu disse sobre colocar as caixas de doces, que tinham um nome cada uma, dentro de uma caixa maior, porém jogar fora o nome dessa caixa? Pois bem, como poderemos identificar qual caixa estamos mexendo agora?

Imagine novamente essa caixa maior (vetor) que contém as caixas menores. Agora, essa caixa vai ter um formato definido: ela será uma caixa cuja largura comporta somente 1 caixa, porém seu comprimento suporta n caixas. Dessa forma, você terá dentro dessa caixa maior uma única linha de n caixas. Assim, poderemos facilmente enumerar as caixas dentro do vetor, partindo da esquerda para direita. Sendo assim, teremos uma sequência de caixas $\{0,1,2,...,n-1\}$. A numeração da caixa é o índice da caixa (nesse caso elemento) do vetor.

Perceba outra coisa: quando nós enumeramos uma sequência, costumamos enumerar no formato $\{1,2,3,...,n\}$. Essa técnica de enumerar elementos é chamada de indexação. Você deve estar estranhando o fato de nós humanos indexarmos da forma $\{1,2,3,...,n\}$ e o computador indexar da forma $\{0,1,2,...,n-1\}$, certo? Pois bem, isso é o jeito como o computador trabalha, e não cabe a mim explicar o motivo, apenas se acostume com o fato de que quando for programar algo envolvendo indexação no computador, deverá usar a indexação em 0, ou seja, $\{0,1,2,...,n-1\}$. A indexação que nós, humanos utilizamos, é a indexação em 1.

Como funciona em Python

Agora que já expliquei sobre vetores e seus índices, além de ter exemplificado seu funcionamento em pseudocódigo BRUTE, agora me resta ensinar como que faz para programar vetores em Python. Porém, existe um pequeno problema com essa linguagem: ela não possui uma implementação de vetor.

É, é exatamente o que eu falei, Python não possui vetores, porém você não aprendeu tudo isso ali em cima pra nada (ainda mais pra quando for aprender sobre vetores em C/C++). Python não possui vetores, mas possui uma estrutura de dados chamada lista, e seu funcionamento é semelhante a um vetor. Para fins explicativos, irei utilizar o termo vetor, ainda que seja incorreto, para não causar confusão.

Vamos começar aprendendo a declarar um vetor em Python. Para isso, devemos utilizar o seguinte código:

vetor = []

Assim, teremos um vetor inicialmente vazio (sem nenhum elemento). Para inserir um novo elemento no vetor, utilizaremos o comando append, da seguinte forma:

vetor.append(valor)

Note que a função append é chamada de uma forma diferente das funções input() e print(). O motivo disso será explicado quando vocês verem orientação a objetos, por enquanto apenas aceitem. Agora, quando quisermos pegar um valor já inserido, iremos utilizar dos índices para acessarmos os elementos contidos no vetor, lembrando sempre que a indexação é em 0. Além disso, vale ressaltar que deve se tomar cuidado com relação aos índices, para não acessar um elemento inexistente no vetor. Para exemplificar o acesso aos elementos, vamos ao seguinte código de exemplo:

vetor = []
vetor.append(2)
vetor.append(5)
vetor.append(8)
print(vetor[2], vetor[0], vetor[1])

Esse código terá a saída $8\ 2\ 5$.

Agora que já expliquei como vetores funcionam em Python, vamos voltar para aquele exemplo das caixas de doces, que requerem um programa de certa forma um pouco mais robusto, com utilização de laços de repetições. Numa abordagem um pouco diferente, vou sugerir que você tente fazer o código primeiro. Caso não consiga, o código está disponível abaixo:

Solução em Python
n = int(input())
vetor = []
for i in range(0,n):
	vetor.append(int(input()))

esquerda = 0
direita = n-1
while esquerda <= direita:
	print(vetor[esquerda]-vetor[direita])
	esquerda += 1
	direita -= 1

E com isso, concluímos a explicação sobre vetores. Ela ficou um pouco longa de certa forma, mas é um assunto um pouco mais complexo que os anteriores. Sabendo utilizar agora os vetores, muitas possibilidades se abriram para o que é possível programar, e você já tem o domínio de quase toda a parte básica da programação. Na próxima postagem (se ela existir), irei explicar sobre funções e recursividade, e com isso terminarei essa série de postagens para vocês calouros (pelo menos até onde eu lembre) e isso permitirá que vocês possam estabelecer uma rotina de treino e buscar mais conhecimento sobre programação.

Exercícios propostos

Mas como não pode faltar isso, aqui vai uma lista de exercícios. Alguns exercícios irão precisar utilizar matrizes, mas esses ficam como desafio para vocês pensarem sobre como vetores podem ser utilizados para criar uma matriz. Lembrando também que qualquer dúvida relacionada aos posts ou aos problemas propostos, podem nos contactar através do email, telegram ou discord do BRUTE.

Obrigado a todos os que leram até aqui, se cuidem a até algum dia.

João Vitor Fröhlich

Membro | Participou de uma Summer School | Buscando ser roxo no codeforces | Prefere fazer exames finais a trabalhos durante o semestre