ALGORITMOS
Oficinas de Desenvolvimento de Software
Prof. Norton
www.norton.net.br
 [email protected]

Programação








Inicio as 19:00
Conceitos e definição de algoritmos
Vetores e matrizes
Recursão
Intervalo 20:40
Retorno 21:00
Pesquisa
Ordenação
O que é algoritmo ?



Um algoritmo é uma sequência ordenada de instruções para
resolver um problema.
Um algoritmo deve possuir as seguintes propriedades: garantia de
término, exatidão e efetividade.
“Algoritmo é uma sequência de passos que visa atingir um objetivo bem
definido” (FORBELLONE, 1999)

“Algoritmo é a descrição de uma sequência de passos que deve ser
seguida para a realização de uma tarefa” (ASCENCIO, 1999)
O que é algoritmo ?

Um algoritmo e composto por:
 Problematização
 Instruções
unitarias
 Sequencia Logica

Um algoritmo pode ser representado por:
 Uma
descrição narrativa
 Um Fluxograma
 Um Programa
Variáveis



Variável e um espaço alocado na memoria
para o armazenamento de um dado, durante
a execução de um programa.
Este valor pode ser modificado durante o
processamento do algoritmo
Exemplo:
int quantidade = 8;
float temperatura = 21.5;
Estruturas de Dados
Os tipos primitivos (inteiro, real, caracter e
lógico) não são suficientes para representar
todos os tipos de informação.
 Particularmente quando temos mais de uma
informação relacionada. Ex: Lista dos nomes
dos alunos de uma sala, endereço de alguém
etc.
 Utilizaremos os tipos primitivos para construir
outras estruturas de dados mais complexas.

Vetores

Também denominados:



Estruturas compostas homogêneas unidimensionais
Permitem a manipulação de um conjunto de informações de
um mesmo tipo primitivo
Exemplo:
float valores [40];
Onde:
 40: Quantidade total de elementos do vetor
 float: Tipo primitivo base do vetor
 valores: nome que representa o vetor no programa
 O índice do vetor inicia-se em 0 (zero) indo até 39 (n – 1)
Vetores
 Manipulação:
int A = 5;
valores [ 6 ] = 6.5;
valores [ 1 ] = 7.8;
valores [ 3 ] = 5.3;
valores [ A ] = 9.8;
valores [ A-1 ] = 9.1;
leia ( valores [ A+3 ] ); // supondo que foi informado 4.7
valores
7.8
0
1
5.3
2
3
9.1
4
9.8
5
6.5
6
4.7
7
8
37
38
39
Vetores - Notas acima da média usando vetor
float notas [10];
int NotaAcima;
float Soma, Media;
Soma = 0;
NotaAcima = 0;
for(int X =0; X < 10; X++){
cin >> notas[X];
Soma=Soma + notas[X];
}
Media = Soma / 10;
for(int X=0; X<10; X++){
if(notas[X] > Média ){
NotaAcima=NotaAcima + 1;
}
}
cout << NotaAcima;
Matrizes

Também denominadas:



Estruturas compostas homogêneas multidimensionais
Permitem a manipulação de um conjunto de informações de
um mesmo tipo primitivo.
Exemplo:
int SALA[4][4];
Onde:
 SALA: Nome da matriz
 4: Capacidade da primeira e da segunda dimensão
 int: Tipo primitivo base da matriz
Matrizes
 Manipulação:
int A, B;
SALA [1][2] = 5;
SALA [2][1]= 6;
SALA [0][1] = 7;
A = 3;
B = 2;
SALA [A][B]= 8;
SALA [A][B-2]= 9;
SALA [A-2][B-2]= 10;
SALA [B][A] =11;
SALA [B-2][A] =12;
SALA
0
0
1
7
1 10
2
3 9
2
3
12
5
6
11
8
Matrizes – Temperatura Semanal
float temperatura [7][3];
float minima, maxima, media;
minima = 99;
maxima = -99;
media = 0;
for(int J =0 ; J<7; J++){
cin >> temperatura[J][0] ; //Temperatura minima do dia
cin >> temperatura[J][1] ; //Temperatura maxima do dia
temperatura[J][2] = (temperatura[J][0] + temperatura[J][1]) /2;
if(temperatura[J][0] <= minima) minima = temperatura[J][0];
if(temperatura[J][1] >= maxima) maxima = temperatura[J][1];
media += temperatura[J][2];
}
media = media / 7;
cout << minima << maxima << media;
Recursão


Recursividade é o mecanismo de programação no
qual uma definição de função ou de outro objeto
refere-se ao próprio objeto sendo definido.
São sinônimos: recursividade, recursão, recorrência.
Recursão



Funções Recursivas
Recursividade Mutua
Recursividade de cauda
Recursão – Funções Recursivas

Estratégia para a definição recursiva de uma função:
dividir o problema em problemas menores do mesmo tipo
 resolver os problemas menores (dividindo-os em problemas
ainda menores, se necessário)
 combinar as soluções dos problemas menores para formar a
solução final


Ao dividir o problema sucessivamente em problemas
menores eventualmente os casos simples são
alcançados:
não podem ser mais divididos
 suas soluções são definidas explicitamente

Recursão – Funções Recursivas

Em todas as funções recursivas existe:
 Um
caso base, ou condição de parada, cujo resultado
é imediatamente conhecido.
 Um passo recursivo em que se tenta resolver um sub
problema do problema inicial.

Assim função recursiva é uma função que é definida
em termos de si mesma.
Recursão – Fatorial
int fatorial(int n){
if(n == 1) return n;
return fatorial(n-1) * n;
}
Recursão – Potencia de 2
int pot(int base, int exp){
if(exp == 0) return 1;
return (base * pot(base, exp-1));
}
Recursão – Fibonacci
int fibonacci(int n){
if(n==1 || n==2) return 1;
else
return fibonacci(n-1)+fibonacci(n-2);
}
Recursão – Recursividade Mutua



Recursividade mútua ocorre quando duas ou mais
funções são definidas em termos uma da outra.
Na Recursividade mútua , as subrotinas são
conectadas através de uma cadeia de chamadas
sucessivas que acaba retornando à primeira que
desencadeou.
Para exemplificar a recursividade indireta vamos
utilizar um código que verifica se um número é par
ou ímpar:
Recursão – Par e Impar
int par(int n){
if(n==0) return 1;
return impar(n-1);
}
int impar(int n){
if(n==0) return 0;
return par(n-1);
}
Recursividade de Cauda



Uma função recursiva apresenta recursividade de
cauda se o resultado final da chamada recursiva é o
resultado final da própria função.
Se o resultado da chamada recursiva deve ser
processado de alguma maneira para produzir o
resultado final, então a função não apresenta
recursividade de cauda.
A recursão de cauda é uma técnica de recursão que
faz menos uso de memória durante o processo de
empilhamento, o que a torna mais rápida que a
recursão comum.
Recursividade de Cauda
int fatorial_aux(int n, int parcial){
if(n==1) return parcial;
return fatorial_aux((n-1), parcial*n));
}
int fatorial_cauda(int n){
return fatorial_aux(n, 1);
}
Recursividade de Cauda



O que acontece é uma transcrição direta de um cálculo iterativo:
 passa-se inicialmente o valor parcial 1 para a função fatorial_aux()
e ela “atualiza” este valor a cada chamada recursiva, multiplicando
o cálculo parcial do fatorial por n, n – 1, n – 2, …, até o “caso
base”.
 Neste ponto, o valor do fatorial já foi calculado e é apenas
retornado.
Esta recursão de cauda poderia gastar menos memória ainda se
utilizasse passagem por referência dos parâmetros.
Desta forma, cada função recursiva empilhada não criaria um espaço
de memória para os parâmetros n e parcial, mas apenas atualizaria
estas duas variáveis sem ficar fazendo cópias delas.
Recursão versus Iteração
Recursão
Iteração
Estruturas de seleção if, if-else ou switch.
Estruturas de repetição for, while ou dowhile
Repetição por chamadas de funções
repetidas.
Repetição explícita.
Termina quando um caso base é
reconhecido.
Termina quando teste do laço falha.
Pode ocorrer infinitamente
Pode ocorrer infinitamente.
Lento
Rápido.
Soluções simples e de fácil manutenção
Soluções complicadas e de difícil
manutenção.
Recursão versus Iteração



Mesmo diminuindo-se os gastos de memória da
recursão através de uma implementação que usa
recursão de cauda e passagem de parâmetros por
referência, o cálculo iterativo será comumente mais
rápido por não fazer repetidas chamadas de funções.
No entanto, a recursão de cauda é importante
principalmente em linguagens de programação
funcionais, onde não existem estruturas de repetição.
Neste caso, a recursão é a única abordagem disponível
e o desempenho pode ser fator crítico, exigindo
implementações de recursão de cauda.
Pesquisa



Algoritmos de pesquisa tem o objetivo de encontrar
valores em uma estrutura de dados.
Para vetores ou matrizes não ordenadas utilizamos
a pesquisa linear.
Para vetores ou matrizes ordenadas podemos
utilizar a pesquisa binaria.
Pesquisa Linear



Busca linear ou sequencial e um tipo de pesquisa
em vetores ou listas de modo sequencial, elemento
por elemento, de modo que a função do tempo em
relação ao número de elementos é linear, ou seja,
cresce proporcionalmente.
No melhor caso, o elemento a ser buscado é
encontrado logo na primeira tentativa da busca.
No pior caso, o elemento a ser buscado encontra-se
na última posição e são feitas N comparações,
sendo N o número total de elementos.
Pesquisa Linear - Iterativo
int linearI(int v[], int tamanho, int busca){
for(int i=0; i<tamanho; i++){
if(v[i] == busca){
return i;
}
}
return -1;
}
Pesquisa Binaria





A pesquisa ou busca binária é um algoritmo de busca em
vetores que segue o paradigma de divisão e conquista.
Ela parte do pressuposto de que o vetor está ordenado e
realiza sucessivas divisões do espaço de busca comparando
o elemento buscado (chave) com o elemento no meio do
vetor.
Se o elemento do meio do vetor for a chave, a busca
termina com sucesso.
Caso contrário, se o elemento do meio vier antes do
elemento buscado, então a busca continua na metade
posterior do vetor.
E finalmente, se o elemento do meio vier depois da chave, a
busca continua na metade anterior do vetor.
Pesquisa Binaria - Iterativo
int binariaI(int v[], int chave, int N){
int inf = 0; //limite inferior
int sup = N-1; //limite superior
int meio;
while(inf <= sup){
meio = inf + (sup-inf)/2;
if(chave == v[meio]){
return meio;
} else {
if(chave < v[meio])
sup = meio – 1;
else
inf = meio + 1;
}
return -1; //não encontrado
}
Ordenação



Ordenação é o ato de se colocar os elementos de
uma sequência de informações, ou dados, em uma
ordem predefinida.
Os algoritmos que ordenam um conjunto,
geralmente representados em um vetor, são
chamados de algoritmos de ordenação.
Os algoritmos de ordenação auxiliam os algoritmos
de busca.
Ordenação

Métodos Simples
 Selection
sort – Ordenação por seleção
 Insertion sort - Ordenação por inserção
 Bubble sort - Ordenação por flutuação

Métodos Sofisticados
 Quicksort
– Ordenação Eficiente
Ordenação por Seleção


Algoritmo de ordenação baseado em se passar
sempre o menor valor do vetor para a primeira
posição (ou o maior dependendo da ordem
requerida),
Depois o de segundo menor valor para a segunda
posição, e assim é feito sucessivamente com os (n-1)
elementos restantes, até os últimos dois elementos.
Ordenação por Seleção
Ordenação por Seleção
void selection_sort(int v[], int tam){
int min,aux;
for(int i=0; i < (tam-1); i++) {
min = i;
for(int j = (i+1); j<tam; j++){
if(v[j] < num[min]){
min = j;
}
}
if(i != min){
aux = num[i];
num[i] = num[min];
num[min] = aux;
}
}
}
Ordenação por Seleção





5 3 1 4 2 4 comparações (5 e 3; 3 e 1; 1 e 4; 1 e 2)
1 3 5 4 2 3 comparações (3 e 5; 3 e 4; 3 e 2)
1 2 5 4 3 2 comparações (5 e 4; 4 e 3)
1 2 3 4 5 1 comparação (4 e 5)
1 2 3 4 5 n – 1 iterações realizadas: vetor ordenado
Ordenação por Inserção

Semelhante ao processo de ordenação de cartas
usado por jogadores de baralho.
 Olhar
a sequência de cartas da esquerda para a
direita e ver se alguma está fora da ordem.
 Ao encontrar uma fora da ordem, procura sua posição
correta nas cartas já olhadas que estão em ordem.
 Eficiente quando aplicado a um pequeno número de
elementos.
 Em termos gerais, ele percorre um vetor de elementos
da esquerda para a direita e à medida que avança
vai deixando os elementos mais à esquerda ordenados
Ordenação por Inserção
Ordenação por Inserção
void insertSort(int v[], int tam){
int eleito, j;
for(int i=1; i < tam; i++) {
eleito = v[i];
j = i-1;
while((j>=0) && (eleito < v[j])){
v[j+1] = números[j];
j--;
}
v[j+1] = eleito;
}
}
Ordenação por Inserção





5 4 3 2 1 1 comparação (5 e 4)
4 5 3 2 1 2 comparações (3 e 5; 3 e 4)
3 4 5 2 1 3 comparações (2 e 5; 2 e 4; 2 e 3)
2 3 4 5 1 4 comparações (1 e 5; 1 e 4; 1 e 3; 1 e 2)
1 2 3 4 5 N vazio e O igual ao tamanho do vetor: vetor
ordenado
Ordenação por Bolha

Dado um vetor de N elementos, inicia a iteração
comparando o primeiro elemento com o segundo:
 se
não estiverem em ordem (primeiro maior que o
segundo), eles são trocados;
 caso contrário, nada acontece.
 Em seguida, faz-se o mesmo para o segundo e terceiro
elementos.
 O processo se repete até que, ao final de n – 1
iterações, o maior elemento do vetor será deslocado
de sua posição inicial para a última.
Ordenação por bolha
Ordenação por bolha
void bubbleSort(int v[], int tam){
int aux;
for(int i=tam-1; i >=1; i--) {
for(int j=0; j < i; j++) {
if(v[j]>v[j+1]){
aux = v[j];
v[j] = v[j+1];
}
}
}
}
Ordenação por Bolha





5 4 3 2 1 4 comparações (5 e 4; 5 e 3; 5 e 2; 5 e 1)
4 3 2 1 5 3 comparações (4 e 3; 4 e 2; 4 e 1)
3 2 1 4 5 2 comparações (3 e 2; 3 e 1)
2 1 3 4 5 1 comparação (2 e 1)
1 2 3 4 5 n – 1 iterações realizadas: vetor ordenado
Ordenação Eficiente - QuickSort



O Quicksort adota a estratégia de divisão e
conquista.
A estratégia consiste em rearranjar as chaves de
modo que as chaves "menores" precedam as chaves
"maiores".
Em seguida o Quicksort ordena as duas sublistas de
chaves menores e maiores recursivamente até que a
lista completa se encontre ordenada.
Ordenação Eficiente - QuickSort

Os passos são:
1.
2.
3.
Escolha um elemento da lista, denominado pivô;
Rearranje a lista de forma que todos os elementos
anteriores ao pivô sejam menores que ele, e todos os
elementos posteriores ao pivô sejam maiores que ele.
Ao fim do processo o pivô estará em sua posição
final e haverá duas sublistas não ordenadas. Essa
operação é denominada partição;
Recursivamente ordene a sublista dos elementos
menores e a sublista dos elementos maiores;
Ordenação Eficiente - QuickSort

A base da recursão são
as listas de tamanho
zero ou um, que estão
sempre ordenadas. O
processo é finito, pois a
cada iteração pelo
menos um elemento é
posto em sua posição
final e não será mais
manipulado na iteração
seguinte
Ordenação Eficiente - QuickSort
Ordenação Eficiente - QuickSort
void quickSort(int v[], int esquerda, int direita){
int i, j, x, y;
i = esquerda;
j = direita;
x = v[(esquerda + direita) / 2];
while(i<=j) {
while(valor[i] < x && i < direita) {
i++;
}
while(valor[j] > x && j > esquerda){
j--;
}
if(i <=j){
y = valor[i];
valor[i] = valor[j];
valor[j] = y;
i++;
j--;
}
}
if(j > esquerda) quickSort(v, esquerda, j);
if(i < direita) quickSort(v, i, direita);