Olimpíada Brasileira de Informática - UNIFEI · Algoritmo Definimos Algoritmo como a sequência...

TreinamentoOlimpíada Brasileira de Olimpíada Brasileira de

InformáticaInformática

Universidade Federal de Itajubá

Prof. Roberto Affonso da Costa Junior

AULA 01AULA 01

– Introdução– Estrutura do programa

Prof. Roberto Affonso da Costa Junior

rcosta62br@gmail.com

http//www.facebook.com/rcosta62br

http://www.rcosta62br.unifei.edu.br

(35) 8879.8637

Instituto de Matemática e Computação

O cursoO curso

• Tipo de aulas– Apresentação de slides– Prática em laboratório

– Prática em casa

Olimpíada Brasileira de Olimpíada Brasileira de Informática - OBIInformática - OBI

• A OBI é uma competição organizada nos moldes das outras olimpíadas científicas brasileiras, como Matemática, Física e Astronomia. O objetivo da OBI é despertar nos alunos o interesse por uma ciência importante na formação básica hoje em dia (no caso, ciência da computação), através de uma atividade que envolve desafio, engenhosidade e uma saudável dose de competição. A organização da OBI está cargo do Instituto de Computação da UNICAMP.

Olimpíada Brasileira de Olimpíada Brasileira de Informática - OBIInformática - OBI

• A OBI está organizada em três modalidades:

– Modalidade Iniciação:

• Nível 1, para alunos até sétimo ano do Ensino Fundamental e

• Nível 2, para alunos até nono ano do Ensino Fundamental.

Olimpíada Brasileira de Olimpíada Brasileira de Informática - OBIInformática - OBI

– Modalidade Programação:• Nível Júnior, para alunos do ensino fundamental,

• Nível 1, para alunos até o segundo ano do ensino médio e

• Nível 2, para alunos até o terceiro ano do ensino médio.

– Modalidade Universitária:• Para alunos que estejam cursando, pela primeira

vez, o primeiro ano de um curso de graduação.

Olimpíada Brasileira de Olimpíada Brasileira de Informática - OBIInformática - OBI

• A Olimpíada Brasileira de Informática disponibiliza o curso "on-line" Introdução à Programação de Computadores. O curso é composto de aulas com vídeos explicativos e muitos exercícios, com o diferencial de que tudo é em português, desde a interface do ambiente até mensagens de erros de sintaxe do editor. Confira em:

http://olimpiada.ic.unicamp.br/saci

URIURI

• Site de treinamento e exercícios:

https://www.urionlinejudge.com.br/judge/login

• Outros:

http://acm.timus.ru/

http://ahmed-aly.com/

http://uva.onlinejudge.org/

https://icpcarchive.ecs.baylor.edu/

http://br.spoj.com/

http://olimpiada.ic.unicamp.br/

http://maratona.ime.usp.br/

A UNIFEI na Maratona de Programação

- A UNIFEI participa da Maratona desde 2006

- A seguir, alguns resultados obtidos ao longo dos anos:

2012

1º Lugar - regional 26º Lugar - Final Brasileira

2013

2º Lugar - Maratona Mineira 1º Lugar - regional

2013

22º Lugar - Final Brasileira

2014

2º Lugar - Maratona Mineira 2º Lugar - Regional

2014

1º Lugar - regional 19º Lugar - Final Brasileira

2015

1º Lugar – Maratona Mineira de Programação

2015

1º Lugar - regional

11º Lugar - Final Brasileira

2016

1º Lugar – Maratona Mineira de Programação

2016

1º Lugar - regional

5º Lugar - Final Brasileira

AlgoritmoAlgoritmo

➢ Definimos Algoritmo como a sequência de passos que visam atingir um objetivo bem definido.

➢ Os algoritmos são utilizados no dia-a-dia para a solução dos mais diversos problemas.

AlgoritmoAlgoritmo➢ Alguns exemplos genéricos de algoritmos usados no nosso cotidiano são: uma coreografia, um manual de instruções, uma receita de bolo, a solução de uma equação do 2º grau, uma pesquisa na lista telefônica, etc.

➢ O que todas essas coisas tem em comum?

Elas podem ser vistas como uma serie finita e Elas podem ser vistas como uma serie finita e bem definida de passos ou regras que, quando bem definida de passos ou regras que, quando realizadas, atingem um objetivo previamente realizadas, atingem um objetivo previamente definido. definido.

AlgoritmoAlgoritmo➢Assim, outra definição para algoritmos poderia ser:

Algoritmo é a descrição de um conjunto de ações que, obedecidas,

resultam numa sucessão finita depassos, atingindo um

objetivo esperado.

AlgoritmoAlgoritmoExemplo

Considere o seguinte problema:

Temos três hastes. Uma das hastes serve de suporte para três discos de tamanhos diferentes. Os discos menores são sempre colocados sobre os discos maiores. A figura a seguir mostra uma possível situação inicial das hastes e discos.

Desejamos mover todos discos para outra haste, porém só podemos movimentar um disco de cada vez e um disco maior nunca pode ser colocado sobre um disco de menor tamanho.

24

AlgoritmoAlgoritmo

25

Solução: Em forma narrativa Nomeamos as hastes como 1, 2 e 3 e os discos como p, m e g. Considera-se que inicialmente os discos estão na haste 1. Os passos são:

1. move o disco p para a haste 3. 2. move o disco m para a haste 2. 3. move o disco p para a haste 2. 4. move o disco g para a haste 3. 5. move o disco p para a haste 1. 6. move o disco m para a haste 3. 7. move o disco p para a haste 3.

Podemos também representar a solução em forma gráfica, desenhando as hastes e a posição dos discos a cada momento (ou passo).

AlgoritmoAlgoritmo

O que é programar?O que é programar?

O que é programar?O que é programar?

O ato de, através de códigos, comandar as ações de um computador para alcançar objetivos definidos.

Estrutura BásicaEstrutura Básica

• Todos os códigos que faremos nas nossas aulas terão uma estrutura igual:

- Includes: são bibliotecas que guardam as funções dos códigos que você irá utilizar em seus programas!- Essa biblioteca é usada pelos alunos da UNIFEI e ela abrange todas as outras.

Estrutura BásicaEstrutura Básica

- int main(): Representa onde seu programa começa, mostrando para o compilador onde deve começar a executar.

- return 0;: Esta função é responsável por mostrar se o programa foi executado corretamente, mostrando 0 se sim, e outro número qualquer se não.

VariáveisVariáveis

• Definição

É o nome do local físico da memória onde a informação é armazenada no computador.

• Denominação

A denominação ou nome de uma variável é dada pelo programador e deve sempre lembrar a função da informação que está sendo armazenada.

VariáveisVariáveis

• Exemplos

idade → corresponde ao nome de uma variável cujo objetivo é armazenar a idade de uma pessoa;

nomeAluno → corresponde ao nome de uma variável cujo objetivo é armazenar o nome de um aluno.

VariáveisVariáveis

• Definição dos Tipos

Ao se definir uma variável, deve-se definir também o tipo da informação que esta variável vai armazenar.

Recomenda-se que esta tarefa seja realizada no inicio do programa para que haja melhor documentação do programa;

VariáveisVariáveis

• Exemplos

inteiro idade → corresponde ao nome de uma variável cujo objetivo é armazenar a idade de uma pessoa e é do tipo inteiro;

palavra nomeAluno → corresponde ao nome de uma variável cujo objetivo é armazenar o nome de um aluno e é do tipo caracter.

VariáveisVariáveis

• Na linguagem de programação C/C++ temos os seguintes tipos:

– int ou long long int para variáveis do tipo numérico inteiro.

– float ou double para variáveis do tipo numérico real.

– char ou char [] para variáveis do tipo alfabético ou caracter.

Tipos de Variáveis em Tipos de Variáveis em linguagem C/C++linguagem C/C++

Tipo inteiroTipo inteiro

#include <bits/stdc++.h>

using namespace std;

int main (){ int x, soma; return 0;}

Tipo inteiroTipo inteiro

#include <bits/stdc++.h>

using namespace std;

int main (){ long long int x, soma; return 0;}

Tipo RealTipo Real

#include <bits/stdc++.h>

using namespace std;

int main (){ float a, valor_soma, media; return 0;}

Tipo RealTipo Real

#include <bits/stdc++.h>

using namespace std;

int main (){ double pi, valor_soma, media; return 0;}

Tipo CaracterTipo Caracter

#include <bits/stdc++.h>

using namespace std;

int main (){ char ch, vogal, letra; return 0;}

Tipo CaracterTipo Caracter

#include <bits/stdc++.h>

using namespace std;

int main (){ char nome[50], cidade[30], endereco[60]; return 0;}

Atribuição de valores à variáveisAtribuição de valores à variáveis

● Linguagem C++

variavel = valor (e/ou operador valor);

Exemplo inteiroExemplo inteiro#include <bits/stdc++.h>

using namespace std;

int main (){ int soma; soma = 569; return 0;}

Exemplo RealExemplo Real

#include <bits/stdc++.h>

using namespace std;

int main (){ float media; media = 42 / 7; return 0;}

Exemplo caracterExemplo caracter

#include <bits/stdc++.h>

using namespace std;

int main (){ char vogal; vogal = 'a'; return 0;}

Exemplo palavraExemplo palavra

● Diferentemente dos outros tipos, o tipo palavra não pode ter atribuição direta;

● Esta atribuição somente poderá ser realizada através de funções da biblioteca da linguagem C/C++;

● Todas as vezes que esta biblioteca é usada, a seguinte declaração é necessária:

#include <string.h>

Com a nossa include não vai precisar colocar essa.

Funções de palavrasFunções de palavras

● A seguir algumas das funções que poderão ser usadas com o tipo cadeia:

– strcpy ( a, b )

copia a cadeia b na cadeia a

– strcmp ( a, b )

compara a cadeia a com a cadeia b ( se forem iguais o

resultado é igual a zero )

– strcat ( a, b ) concatena a cadeia b com a cadeia a guardando o resultado na

cadeia a

Exemplo 1Exemplo 1#include <bits/stdc++.h>

int main ( void ){ char x[10], y[5], t[20];

strcpy ( x, “Maria” );strcpy ( y, “sol” );strcpy ( t, x );strcat ( x, y );

return 0;}