Apostila_AED_I - OK

•
NEWTON PAIVA

Nayara Santos
02/07/2020
E aí, curtiu este material?
Ajude a incentivar outros estudantes a melhorar o conteúdo
Gostou desse material? Compartilhe! 🧡
Algoritimos C++

421 Materiais compartilhados
Baixe o app para aproveitar ainda mais
Leia os materiais offline, sem usar a internet. Além de vários outros recursos!
Prévia do material em texto
l ó g i c a d e p r o g r a m a ç ã o m a t h g r a p h
Algoritmos e Estruturas de Dados
Introdução
Prof. Sinaide Nunes Bezerra <contato@mathgraph.com.br>
V́ıdeoaulas, exemplos e exerćıcios em linguagem C, acesse
www.mathgraph.com.br
25 de fevereiro de 2016
l ó g i c a d e p r o g r a m a ç ã o m a t h g r a p h
Sumário
1 Introdução
2 Estrutura Sequencial
3 Estrutura Condicional
se... então
se ... senão ...
4 Estruturas de Repetição
enquanto... faça
para... até... faça
repita... até...
5 Estruturas Homogêneas de Dados
Vetor
Matriz
Prof. Sinaide Nunes Bezerra <contato@mathgraph.com.br> — AED — 25 de fevereiro de 2016
2/37
l ó g i c a d e p r o g r a m a ç ã o m a t h g r a p h
Algoritmos computacionais
Definição
Segundo Cormem (2001) um algoritmo computacional pode ser
entendido como “... qualquer procedimento computacional bem
definido que toma algum valor ou conjunto de valores como
entrada e produz algum valor ou conjunto de valores como sáıda.
Portanto, um algoritmo é uma sequência de passos computacionais
que transformam a entrada na sáıda”.
Prof. Sinaide Nunes Bezerra <contato@mathgraph.com.br> — AED — 25 de fevereiro de 2016
3/37
l ó g i c a d e p r o g r a m a ç ã o m a t h g r a p h
Algoritmos computacionais
Outras definições
• ”Algoritmo é uma sequência de passos que visa atingir um
objetivo bem definido” (FORBELLONE, 1999)
• “Algoritmo é a descrição de uma seqüência de passos que
dever ser seguida para a realização de uma tarefa”
(ASCENCIO, 2007)
• “Algoritmo é uma sequência finita de instruções ou operações
cuja execução, em tempo finito, resolve um problema
computacional, qualquer que seja sua instância” (SALVETTI,
1999)
Prof. Sinaide Nunes Bezerra <contato@mathgraph.com.br> — AED — 25 de fevereiro de 2016
4/37
l ó g i c a d e p r o g r a m a ç ã o m a t h g r a p h
Algoritmos computacionais
Outras definições
• “Algoritmo são regras formais para a obtenção de um
resultado ou da solução de um problema, englobando
fórmulas de expressões aritméticas” (MANZANO, 1997)
• “Ação é um acontecimento que, a partir de um estado inicial,
após um peŕıodo de tempo finito, produz um estado final
previśıvel e bem-definido. Portanto, um algoritmo é a
descrição de um conjunto de comandos que, obedecidos,
resultam numa sucessão finita de ações” (FARRER, 1999)
Prof. Sinaide Nunes Bezerra <contato@mathgraph.com.br> — AED — 25 de fevereiro de 2016
5/37
l ó g i c a d e p r o g r a m a ç ã o m a t h g r a p h
Algoritmos computacionais
Continuação
Um algoritmo é como uma “receita de bolo” para o computador,
onde estão definidos todos os comandos que ele deve executar p
ara se chegar a um resultado. Dáı, temos que, o algoritmo é uma
sequência de instruções, onde cada instrução representa uma
AÇÃO que deve ser entendida e realizada. Em algoritmos
computacionais, o computador possui um conjunto limitado de
instruções e o algoritmo deve ser expresso nos termos destas
instruções. O computador utiliza dois conceitos básicos para
construir e interpretar algoritmos, são eles:
• Estruturas de Dados → para manipulação das informações
• Estruturas de Controle → para manipulação das ações
Prof. Sinaide Nunes Bezerra <contato@mathgraph.com.br> — AED — 25 de fevereiro de 2016
6/37
l ó g i c a d e p r o g r a m a ç ã o m a t h g r a p h
Tipos de Algoritmos
Descrição Narrativa
A descrição narrativa consiste em analisar o enunciado do
problema e escrever, utilizando um linguagem natural (por
exemplo, a ĺıngua portuguesa), os passos a serem seguidos para
resolução do problema (semelhante a escrever uma receita).
• Vantagem: Não é necessário aprender nenhum conceito novo,
pois uma ĺıngua natural já é bem conhecida.
• Desvantagem: A linguagem natural (não padronizada e
informal) abre espaço para várias interpretações. Será mais
dif́ıcil estruturá-la e transcrever este algoritmo para uma
linguagem de programação.
Prof. Sinaide Nunes Bezerra <contato@mathgraph.com.br> — AED — 25 de fevereiro de 2016
7/37
l ó g i c a d e p r o g r a m a ç ã o m a t h g r a p h
Tipos de Algoritmos
Fluxograma
Analisar o enunciado do problema e escrever, utilizando śımbolos
gráficos pré-definidos, os passos a serem seguidos para a resolução
do problema.
• Vantagem: Visão geral do fluxo de processamento.
• Desvantagem: É necessário aprender a simbologia dos
fluxogramas e, além disso o algoritmo resultante não
apresenta muitos detalhes, dificultando sua transcrição para
uma linguagem de programação.
Prof. Sinaide Nunes Bezerra <contato@mathgraph.com.br> — AED — 25 de fevereiro de 2016
8/37
l ó g i c a d e p r o g r a m a ç ã o m a t h g r a p h
Tipos de Algoritmos
Fluxograma
Os śımbolos utilizados para representar o uso em fluxograma
podem variar dependendo do autor. A seguir é apresentada a lista
de śımbolos a ser utilizada nas aulas deste curso.
Prof. Sinaide Nunes Bezerra <contato@mathgraph.com.br> — AED — 25 de fevereiro de 2016
9/37
l ó g i c a d e p r o g r a m a ç ã o m a t h g r a p h
Tipos de Algoritmos
Pseudocódigo
Consiste em analisar o enunciado do problema e escrever, por meio
de regras predefinidas, os passos a serem seguidos para a resolução
do problema.
• Vantagem: A passagem (transcrição) do algoritmo para uma
linguagem de programação é quase imediata, bastando
conhecer as regras e palavras reservadas da linguagem que
será utilizada.
• Desvantagem: É necessário aprender as regras para se
escrever um algoritmo corretamente.
Prof. Sinaide Nunes Bezerra <contato@mathgraph.com.br> — AED — 25 de fevereiro de 2016
10/37
l ó g i c a d e p r o g r a m a ç ã o m a t h g r a p h
Estruturas de Dados
Definição
Uma estrutura de dados é um meio para armazenar e organizar
dados com o objetivo de facilitar o acesso e as modificações.
Nenhuma estrutura de dados única funciona bem para todos os
propósitos, e assim é importante conhecer os pontos fortes e as
limitações de várias delas (CORMEN, 2001)
As estruturas de dados representam as informações do problema a
ser resolvido. Tais estruturas estão organizadas em tipos distintos
de informações. Dentro do escopo das estruturas de dados,
define-se os seguintes termos:
Constante, Variável e Identificador.
Prof. Sinaide Nunes Bezerra <contato@mathgraph.com.br> — AED — 25 de fevereiro de 2016
11/37
l ó g i c a d e p r o g r a m a ç ã o m a t h g r a p h
Estruturas de Dados
Constantes
Representam valores constantes, ou seja, que não variam no
decorrer do algoritmo.
Exemplo 1:
Seja x = 2, efetuando as seguintes operações:
y = x → y = 2
A = 3x + 5x → A = 3*(2) + 5 * 2 → A = 16
Exemplo 2:
Seja PI = 3,14, efetuando as seguintes operações:
A = PI .*1 → A = 3,14
A = PI * 2 → A = 6,28
A = PI * 3 → A = 9,42
Nos exemplos 1 e 2, tanto o valor de x quanto PI não variam a
medida que as operações são executadas.
Prof. Sinaide Nunes Bezerra <contato@mathgraph.com.br> — AED — 25 de fevereiro de 2016
12/37
l ó g i c a d e p r o g r a m a ç ã o m a t h g r a p h
Estruturas de Dados
Variáveis
Representam informações cujos valores são modificados ao longo
do tempo.
Exemplo 1:
Deseja-se saber o salário de um funcionário considerando que ele
recebe R$ 1.000, 00 por mês, supondo que teve um aumento de
20% e deve-se descontar 8% de INSS do novo salário, qual será o
salário ĺıquido?
Resposta:
salario = 1.000
reajuste = salario * 0,2
salario = salario + reajuste
imposto = salario * 0,08
salario = salario - imposto
Prof. Sinaide Nunes Bezerra <contato@mathgraph.com.br> — AED — 25 de fevereiro de 2016
13/37
l ó g i c a d e p r o g r a m a ç ã o m a t h g r a p h
Estruturas de Dados
Variáveis
Matematicamente, variável é a representação simbólica dos
elementos de um certo conjunto. Computacionalmente, pode-se
definir variável como um local reservado na memória do
computador usado para armazenar dados.Uma variável possui nome (identificador) e tipo, possui apenas um
valor em um determinado instante, mas seu conteúdo pode variar
ao longo do tempo.
O conceito de variável, em computação, corresponde a posições de
memória RAM (Random Access Memory) onde são
armazenados os dados manipulados pelo programa quando este for
executado.
Prof. Sinaide Nunes Bezerra <contato@mathgraph.com.br> — AED — 25 de fevereiro de 2016
14/37
l ó g i c a d e p r o g r a m a ç ã o m a t h g r a p h
Estruturas de Dados
Identificador
Nome de um local onde se pode colocar qualquer valor do
conjunto de valores posśıveis de um tipo básico associado. Usado
para manipular os dados necessários no algoritmo.
O identificador é também usado para rotular valores constantes,
assim como o nome PI, utilizado no exemplo 2, em constantes (o
identificador PI foi utilizado para representar o valor constante
3,14).
Prof. Sinaide Nunes Bezerra <contato@mathgraph.com.br> — AED — 25 de fevereiro de 2016
15/37
l ó g i c a d e p r o g r a m a ç ã o m a t h g r a p h
Estruturas de Dados
Regras para formação de identificadores
1 Começar sempre o nome com uma letra ou o caractere
sublinhado “ ”;
2 Não usar espaços em branco, pontuação, acentos nem
caracteres especiais (@, #, ?, $, etc);
3 Não usar palavras reservadas, ou seja, palavras que pertençam
a linguagem de programação que estiver sendo usada (ex: if,
for, case, int, etc).
Importante: Um identificador deve representar o melhor posśıvel
o papel da variável no algoritmo
Prof. Sinaide Nunes Bezerra <contato@mathgraph.com.br> — AED — 25 de fevereiro de 2016
16/37
l ó g i c a d e p r o g r a m a ç ã o m a t h g r a p h
Estruturas de Dados
Identificadores válidos
1 nota, nota1, nota 1, operador, salario, nome, x, y,
enderecoResidencial,
2 aluno01, preco produto, Area, Tensao A, tensao B, media,
soma, S.
Identificadores inválidos
1 1K, nota 1, salário, nome, x@1, y%2, aluno 01, preco produto.
Prof. Sinaide Nunes Bezerra <contato@mathgraph.com.br> — AED — 25 de fevereiro de 2016
17/37
l ó g i c a d e p r o g r a m a ç ã o m a t h g r a p h
Tipos Primitivos de Dados
Numéricos
1 Inteiros. Ex: ...-100... -2, -1, 0, 1, 2, ..., 100, ...
2 Reais. Ex: ... -100, ..., -50.2, ..., -2, ..., -1.5, ..., 0, ..., 1, ...,
2, ..., 25.12,
Literal
Caractere ou alfanuméricos. Ex: “ESCOLA”, “livro”, “18”,
“R$ 55,36”, ...
Lógicos ou booleanos
Assume um estado: verdadeiro (V) ou falso (F)
Prof. Sinaide Nunes Bezerra <contato@mathgraph.com.br> — AED — 25 de fevereiro de 2016
18/37
l ó g i c a d e p r o g r a m a ç ã o m a t h g r a p h
Tipos Primitivos de Dados
Declaração
É a criação (ou definição) do identificador da variável (ou
constante) que será utilizado no algoritmo. Esta variável será
utilizada para a manipulação de um determinado tipo de dado.
Formato
tipo do dados: identificador;
tipo do dado: identificador1, identificador2, . . . , identificadorn
1 Todas as variáveis utilizadas em algoritmos serão definidas no ińıcio
do mesmo, por meio de um comando de uma das formas seguintes:
2 Em uma mesma linha podem ser denidas uma ou mais variáveis do
mesmo tipo, separando-se os nomes das mesmas por v́ırgulas.
3 Variáveis de tipos diferentes devem ser declaradas em linhas
diferentes.
Prof. Sinaide Nunes Bezerra <contato@mathgraph.com.br> — AED — 25 de fevereiro de 2016
19/37
l ó g i c a d e p r o g r a m a ç ã o m a t h g r a p h
Tipos Primitivos de Dados
Exemplos
inteiro: idade;
real: salario;
caracter: nome;
lógico: temFilhos;
No exemplo, foram declaradas quatro variáveis, sendo elas:
• Variável nome: capaz de armazenar dados literais;
• Variável idade: capaz de armazenar um número inteiro;
• Variável salario: capaz de armazenar um número real;
• Variável temFilhos: capaz de armazenar um valor lógico,
verdadeiro (V) ou falso (F).
Prof. Sinaide Nunes Bezerra <contato@mathgraph.com.br> — AED — 25 de fevereiro de 2016
20/37
l ó g i c a d e p r o g r a m a ç ã o m a t h g r a p h
Comandos básico
Tabela: Comandos em pseudocódigo
Comando Função Exemplo
← atribui um valor a uma variável x ← 2
leia
obter um valor informado externo
e atribuir a uma variável
leia x;
escreva
mostrar algo, que pode ser uma
variável, texto ou ambos
escreva x;
escreva ”mensagem de teste”;
Prof. Sinaide Nunes Bezerra <contato@mathgraph.com.br> — AED — 25 de fevereiro de 2016
21/37
l ó g i c a d e p r o g r a m a ç ã o m a t h g r a p h
Estrutura Sequencial
Sobre a estrutura
Na estrutura sequencial os comandos são executados numa
sequência pré-estabelecida. Cada comando é executado somente
após o término do comando anterior.
Em pseudocódigos, a estrutura sequencial caracteriza-se por um
conjunto de comandos dispostos ordenadamente.
Formato
ińıcio
tipo: variável1, variável2, . . . ; //declaração das variávieis
leia variável1, variável2; //dados de entrada
comandos/ações; //ações a serem executadas
escreva “Mensagem pré-determinada”, variável; //dados de sáıda
fim.
Prof. Sinaide Nunes Bezerra <contato@mathgraph.com.br> — AED — 25 de fevereiro de 2016
22/37
l ó g i c a d e p r o g r a m a ç ã o m a t h g r a p h
Estruturas Condicional
Finalidade
Utilizada quando o problema apresenta alguma ou algumas
condições. Em problemas que apresentam classificação,
comparação, verificação, restrição, e outras situações que existam
condições a serem observadas.
Classificação:
1 Simples
2 Composta
Prof. Sinaide Nunes Bezerra <contato@mathgraph.com.br> — AED — 25 de fevereiro de 2016
23/37
l ó g i c a d e p r o g r a m a ç ã o m a t h g r a p h
Condicional Simples
Pseudocódigo
se (condição) então
comandos/ações;
fimse;
Caracteŕısticas:
• A ação será executada apenas se a condição for verdadeira.
• A ação ou ações a serem executadas são escritas depois da
palavra então e antes de fimse.
Prof. Sinaide Nunes Bezerra <contato@mathgraph.com.br> — AED — 25 de fevereiro de 2016
24/37
l ó g i c a d e p r o g r a m a ç ã o m a t h g r a p h
Condicional Composta
Pseudocódigo
se (condição) então
comando1;
senão
comando2;
fimse;
Funcionamento:
Se a condição for verdadeira, será executado o comando1; caso
contrário, se a condição for falsa, será executado o comando2.
Prof. Sinaide Nunes Bezerra <contato@mathgraph.com.br> — AED — 25 de fevereiro de 2016
25/37
l ó g i c a d e p r o g r a m a ç ã o m a t h g r a p h
Seleção de Múltipla Escolha
Finalidade
Utilizada para simplificar a escrita de seleções encadeadas
se-senão-se.
Pseudocódigo
escolha X
V1: C1;
V2: C2;
. . .
Vn: Cn;
fimescolha;
Prof. Sinaide Nunes Bezerra <contato@mathgraph.com.br> — AED — 25 de fevereiro de 2016
26/37
l ó g i c a d e p r o g r a m a ç ã o m a t h g r a p h
Estruturas de Repetição
Finalidade
Permitem executar mais de uma vez (repetir) um determinado
trecho do algoritmo
• O trecho do algoritmo em repetição é também chamado de
laço (ou “loop”)
• As repetições devem ser sempre finitas
Quanto a quantidade de repetições, os laços podem ser
1 Pré-determinados: Sabe-se antes a quantidade de execuções
2 Indeterminados: Não se conhece a quantidade de execuções
Quanto ao critério de parada, os laços podem utilizar
1 Variável de controle
2 Teste no ińıcio
3 Teste no final
Prof. Sinaide Nunes Bezerra <contato@mathgraph.com.br> — AED — 25 de fevereiro de 2016
27/37
l ó g i c a d e p r o g r a m a ç ã o m a t h g r a p h
Estruturas de Repetição
enquanto... faça
• Laço que verifica antes de cada execução, se é “permitido”
executar o trecho do algoritmo
• O laço acontece enquanto uma dada condição permanecer
verdadeira
Pseudocódigo
enquanto(condição) faça
comandos/ações;
fimenquanto;
Prof. Sinaide Nunes Bezerra <contato@mathgraph.com.br> — AED — 25 de fevereiro de 2016
28/37
l ó g i c a d e p r o g r a m a ç ã o m a t h g r a p h
Estruturasde Repetição
Exemplo: Faça um algoritmo que leia a nota de cada aluno de uma
turma com 50 alunos, em seguida apresente a média da turma.
ińıcio
real: mediaTurma, somaNotas, nota;
inteiro: i; //contador
i ← 0; //inicialização do contador
somaNotas ← 0; //inicializaodoacumulador
enquanto (i < 50) faça // teste da condição de parada
leia nota;
//soma em somaNotas os valores lidos em nota
somaNotas ← somaNotas + nota ;
i ← i + 1; //incremento do contador
fimenquanto;
mediaTurma ← somaNotas / 50; // cálculo da média da turma
escreva “média da turma = “, mediaTurma;
fim.
Prof. Sinaide Nunes Bezerra <contato@mathgraph.com.br> — AED — 25 de fevereiro de 2016
29/37
l ó g i c a d e p r o g r a m a ç ã o m a t h g r a p h
Estruturas de Repetição
para... até... faça
• Utilizada somente em casos nos quais a quantidade de
repetições previamente conhecida.
• Incorpora internamente o funcionamento de um contador para
controlar a quantidade de laços
Pseudocódigo
para v de vi até vf passo p faça
comandos/ações;
fimpara;
• v : variável de controle
• vi : valor inicial de v
• vf : valor final de v
• p: variação de v
Prof. Sinaide Nunes Bezerra <contato@mathgraph.com.br> — AED — 25 de fevereiro de 2016
30/37
l ó g i c a d e p r o g r a m a ç ã o m a t h g r a p h
Estruturas de Repetição
repita... até...
• A verificação se é permitido repetir a ação ocorre no final da
estrutura
• Trata-se de um laço que se mantém repetindo até que uma
dada condição se torne verdadeira
Pseudocódigo
repita
comandos/ações;
até (condição);
Prof. Sinaide Nunes Bezerra <contato@mathgraph.com.br> — AED — 25 de fevereiro de 2016
31/37
l ó g i c a d e p r o g r a m a ç ã o m a t h g r a p h
Estruturas de Repetição
Comparação
É importante perceber que existem laços mais adequados ou
convenientes para cada situação
Tabela: Comparação entre Estruturas de Repetição
Estrutura Condição Qtd. de Execuções
Condição de
Existência
enquanto ... ińıcio zero ou muitas verdadeira
para ... ińıcio valor final - valor inicial verdadeira
repita ... final ḿınimo uma falsa
Prof. Sinaide Nunes Bezerra <contato@mathgraph.com.br> — AED — 25 de fevereiro de 2016
32/37
l ó g i c a d e p r o g r a m a ç ã o m a t h g r a p h
Estrutura Homogênea de Dados
Definição
• Estruturas homogêneas de dados possibilitam o
armazenamento de grupos de valores em uma única variável
que será armazenada na memória do computador.
• São ditas homogêneas porque os valores a serem armazenados
devem ser do mesmo tipo.
• Entre outros nomes que estas estruturas recebem, iremos
chamá-las de vetores e matrizes.
Prof. Sinaide Nunes Bezerra <contato@mathgraph.com.br> — AED — 25 de fevereiro de 2016
33/37
l ó g i c a d e p r o g r a m a ç ã o m a t h g r a p h
Vetor
Vetor - Arranjo Unidimensional
• Um vetores é uma variável composta (arranjo) com múltiplas
posições.
• Podem ser vistos como lista de elementos do mesmo tipo.
• São estruturas lineares e estáticas, ou seja, são compostas por
um número finito e pré-determinado de valores
Representação:
Exemplo: Vetor de notas de uma turma com 10 alunos:
Notas = 6,1 3,4 9,2 8,5 4,6 8,3 7,4 6,5 10 9,6
Posição 1 2 3 4 5 6 7 8 9 10
Prof. Sinaide Nunes Bezerra <contato@mathgraph.com.br> — AED — 25 de fevereiro de 2016
34/37
l ó g i c a d e p r o g r a m a ç ã o m a t h g r a p h
Vetor
Pseudocódigo - Declaração
tipo: identificador[qtd. de elementos];
Exemplo: Faça um algoritmo que leia as notas de uma turma com
50 alunos e mostre o vetor resultante.
inicio
inteiro: i, notas[50];
para i de 1 até 50 passo 1 faça
escrever ”Entre com um valor: ”;
ler notas[i];
fimpara;
para i de 1 até 50 passo 1 faça
escrever notas[i];
fimpara;
fim.
Prof. Sinaide Nunes Bezerra <contato@mathgraph.com.br> — AED — 25 de fevereiro de 2016
35/37
l ó g i c a d e p r o g r a m a ç ã o m a t h g r a p h
Matriz
Matriz - Array Bidimensional
Uma matriz é uma variável composta homogênea bidimensional
formada por elementos do mesmo tipo, alocados sequencialmente
na memória, organizada em linhas e colunas.
Representação:
Aluno
6,1 3,4 9,2 8,5 4,6 8,3 7,4 6,5 10 9,6 1
Turma 5,6 3,1 8 4,5 7 6 7,3 9,8 6,7 8 2
8,6 9 5,5 8,4 3,5 7,3 8,9 8,1 5,7 7 3
1 2 3 4 5 6 7 8 9 10
Prof. Sinaide Nunes Bezerra <contato@mathgraph.com.br> — AED — 25 de fevereiro de 2016
36/37
l ó g i c a d e p r o g r a m a ç ã o m a t h g r a p h
Matriz
Pseudocódigo - Declaração
tipo: identificador[qtd. linha][qtd. coluna];
Exemplo: Faça um algoritmo que leia as notas de 5 turmas, cada turma com 50
alunos, e mostre a matriz resultante.
inicio
inteiro i, j;
real notas[5][50];
para i de 1 até 5 passo 1 faça
para j de 1 até 50 passo 1 faça
escreva ”Entre com um valor: ”;
leia notas[i][j];
fimpara;
fimpara;
para i de 1 até 5 passo 1 faça
para j de 1 até 50 passo 1 faça
escreva notas[i][j];
fimpara;
fimpara;
fim.
Prof. Sinaide Nunes Bezerra <contato@mathgraph.com.br> — AED — 25 de fevereiro de 2016
37/37
	Introdução
	Estrutura Sequencial
	Estrutura Condicional
	se... então
	se ... senão ...
	Estruturas de Repetição
	enquanto... faça
	para... até... faça
	repita... até...
	Estruturas Homogêneas de Dados
	Vetor
	Matriz