Title | 04-algoritmos - Resumo Programação I |
---|---|
Author | Miguel Pereira |
Course | Programação I |
Institution | Universidade da Beira Interior |
Pages | 31 |
File Size | 2.4 MB |
File Type | |
Total Downloads | 37 |
Total Views | 146 |
Resumos aula teorica...
Programação 13205 : Engenharia Informática 6619 : Tecnologias e Sistemas de Informação
Cap. 4 — Algoritmos e Programação Estruturada
Algoritmos e Programação Estruturada
Algoritmos e Programação Estruturada
Objectivos: •
Aprender o conceito de algoritmo e suas caracte ísticas fundamentais
•
Como resolve problemas através de algoritmos
•
Como desenha algoritmos e programas
•
Distinguir as diferentes representa õe de algoritmos
•
Como usar fluxogramas em programação visual
•
Como utilizar o método cartesiano de divid par conquistar em programação estruturada
•
Aprender a utilizar estruturas de controlo de fluxo: sequência, selecção e repetição
•
Aprender a utilizar programação estruturada
Algoritmos e Programação Estruturada
Problemas e Algoritmos •
Para resolver um problema atra és dum computador é necessário encontrar em primeiro lugar uma maneira de descre lo de uma forma clara e precisa.
•
É tam ém preciso que encontremos uma sequência de passo que conduzam à sua resoluçã . Esta sequência de passos é designada po algoritm .
•
A noção de algoritmo é central a toda a informátic .
•
A constru ão de algoritmos para resolver os problemas é uma das maiores dificuldades, mas tam ém um dos maiores desafios para quem programa computadores.
Algoritmos e Programação Estruturada
Noção de Problema Exemplo: como fazer um bolo?
Farinha de Trigo Ovos Fermento
Açúcar Leite
receita
Manteiga
Uma receita é uma descrição dum conjunto de passos ou acções que fazem a combinação dum conjunto de ingredientes com vista a obter um produto gastronómico particular.
Algoritmos e Programação Estruturada
Noção de Algoritmo •
Entradas ingredientes
•
S ídas bolo
•
Algoritmo receita
Farinha de Trigo Ovos Açúcar Fermento Leite
algoritmo
Manteiga
–
Um algoritmo opera sobre um conjunto de entrada (farinha ovos, fermento, etc. no caso do bolo) de modo a gerar um saíd que seja útil (ou agradável) para o utilizador (o bolo pronto).
–
Assim, o passo ou ac ões dum algoritmo para confeccionar um bolo são os seguintes: 1.
Bater duas claras em castelo;
2.
Adicionar duas gemas;
3.
Adicionar um xícara de açúcar;
4.
Adicionar duas colheres de manteiga;
5.
Adicionar uma xícara de leite de coco;
6.
Adicionar farinha e fermento;
7.
Colocar numa forma e levar ao forno em lume brando.
Algoritmos e Programação Estruturada
Desenho ou Concepção de Algoritmos para a Resolução de Problemas
PROBLEMA
ALGORITMO
PROGRAMA
•
Um algoritmo é uma descrição, pass passo, de uma metodologia que conduz à resolução de um problema ou à execução de uma tarefa.
•
A programação consiste na codifica ão precisa desse algoritmo, segundo uma linguagem de programa ão específica.
•
Há, pois, que ter em consideração que existem três fases distintas na elaboração de programas: –
a análise do problema (especificação do problema, análise de requisitos, pressupostos, etc.)
–
a concepção do algoritmo
–
a tradução desse algoritmo na linguagem de programação
Algoritmos e Programação Estruturada
Passos na Concepção e Construção de Algoritmos •
Compreender o problema
•
Identificar os dados de entrada
•
Identificar os dados de saída
•
•
Construir o algoritmo
•
Testar (manualmente) o algoritmo
•
Executar o algoritmo
Algoritmos e Programação Estruturada
Método Cartesiano de Dividir-para-Conquistar •
Também é conhecido po método descendente (to down method ou método de refinamento pass passo
•
Este método consiste em dividi um problema em parte menore ou su problema ) de modo a que seja mai fáci a sua resoluçã . -
•
Pass -
Exempl
Fazer sumo de laranja?
•
Lavar laranja;
•
Partir laranja ao meio;
•
Espremer laranja;
•
Filtrar o sumo;
•
Servir o sumo.
pass , significa que cada passo é completado antes que o próximo comece. Exempl : é impossíve ver telejorn ” antes de executar por inteiro o passo anterior de ligar a T ”
Algoritmos e Programação Estruturada
Características Fundamentais dum Algoritmo • • • • •
Finitud um algoritmo deve sempre terminar após um número finito de passos. Definiçã cada passo de um algoritmo deve ser precisamente definido. A acçõe devem ser definidas rigorosamente e sem ambiguidades. Entrada um algoritmo deve ter zero ou mais entradas, isto é quantidades que lhe são fornecidas antes do algoritmo iniciar. Saída : um algoritmo deve te zero ou mais saídas, isto é quantidades que tem uma relação específica com as entradas. Eficiênci : um algoritmo deve ser eficiente. Isto significa que todas as operações devem ser suficientemente básicas de modo que possam ser em princípio executadas com precisão em um tempo finito por um ser humano usando papel e lápis.
Pode haver mais do que um algoritmo para resolver um problema. Por exemplo, para ir de casa até o trabalho, podemos escolher diversos meios de transportes em função do preço, conforto, rapidez, etc..
Algoritmos e Programação Estruturada
Representações de Algoritmos •
Linguagem Natural -
•
Fluxograma (ou Diagrama de Flux ) -
•
Os algoritmos são expressos directamente em linguagem natural (e.g. o português como no exemplo do bolo).
Esta é um representação gráfica que emprega formas geométricas padronizadas para indicar as diversas acções e decisões que devem ser executadas para resolver o problema.
Pseud -
linguagem
Emprega uma linguagem intermediária entre a linguagem natural e uma linguagem de programação para descrever os algoritmos.
Não existe consenso entre os especialistas sobre qual é a melhor maneira de representar um algoritmo. Actualmente a maneira mais comum de representar algoritmos é através de uma pseudo-linguagem ou pseudocódigo. Esta forma de representação tem a vantagem de o algoritmo seja escrito de uma forma que está próxima de uma linguagem de programação de computadores.
Algoritmos e Programação Estruturada
Codificação em Linguagem Natural (1) •
Problem : –
•
Entradas: –
•
dois valores reais, X e Y
S ídas: –
•
Cáculo da média aritmética de dois valores reais?
a média M=(X+Y)/2
Algoritm : 1. 2. 3. 4. 5.
Início Ler X, Y Calcular a média M de X e Y Escrever M Fim
Algoritmos e Programação Estruturada
Codificação em Fluxograma (2) •
Problem : –
•
dois valores reais, X e Y
S ídas: –
•
Início
Entradas: –
•
Cáculo da média aritmética de dois valores reais?
Ler X
Ler Y
a média M=(X+Y)/2
Algoritm :
M=(X+Y)/2
Fim
Algoritmos e Programação Estruturada
Codificação em Pseudo-código (3) •
Problem : –
•
Entradas: –
•
dois valores reais, X e Y
S ídas: –
•
Cáculo da média aritmética de dois valores reais?
a média M=(X+Y)/2
Algoritm : 1. 2. 3. 4. 5.
Início Ler X, Y Calcular a média M=(X+Y)/2 Escrever M Fim
Algoritmos e Programação Estruturada
Codificação em C (4) •
Problem : –
•
Entradas: –
•
dois valores reais, X e Y
S ídas: –
•
Cáculo da média aritmética de dois valores reais?
a média M=(X+Y)/2
Program :
#include main(){ float X, Y, M; printf(Introduza o valor de X:\n”); scanf("%f", &X); printf(Introduza o valor de Y:\n”); scanf("%f", &Y); M=(X+Y)/2; printf(”A media M = %f\n”,M); }
Algoritmos e Programação Estruturada
Programação Visual com Fluxogramas •
Um fluxograma é uma representação gráfica de um algoritmo.
•
Programação visual: é a utilização de diagramas na programação.
•
Descrevem o fluxo dum algoritmo através de um conjunto de figuras geométrica padronizadas ligadas por setas de fluxo.
início e fim de fluxograma
entrada e saída de dados
teste e decisão
outras acções/instruções
conector na mesma página inicialização teste e actualização conector para outra página
Algoritmos e Programação Estruturada
Estruturas Lógicas de Programação (estruturas de controlo) •
Uma estrutura (de controlo) é a unidade básica da lógica de programação.
•
Em meados da década de 60, alguns matemáticos provaram que qualquer programa podia ser construído através da combinação de 3 estruturas básicas: sequência, selecção e repetição.
entrance
entrance
entrance
exit
exit exit SEQUÊNCIA
SELECÇÃO
REPETIÇÃO
Algoritmos e Programação Estruturada {…}
Sequência •
Numa sequência é processado um conjunto de instruções (ou acções) em série.
•
Não há qualquer possibilidade de alterar a ordem de processamento das instruções, i.e. após processar a 1ª instru ão process se a 2ª, depois da 2ª process se a 3ª, e assim por diante até processar a última acção.
•
Em C, uma sequência é um bloco de instruções que começa com e termina com }
entrance
exit
Algoritmos e Programação Estruturada if-else
Selecção de 2-vias •
Uma estrutura de selecção é também designada por estrutura de decisão.
•
Neste caso, o fluxo de processamento segue por 1 das 2 vias, dependendo do valor lógico (verdadeiro ou falso) da expressão avaliada no início da estrutura.
•
Se o fluxo de processamento só passa por 1 via, então só uma das acções é realizada ou processada.
•
Em C, uma estrutura de selecção com 2 vias é a instrução if-else.
false
?
true
Algoritmos e Programação Estruturada
Exemplo em C: if-else •
Problem : –
•
Calcular o maior de dois inteiros?
Entradas: –
xey
#include {
•
S ídas: –
•
int x, y, M; printf(”Introduza x e y: \n”); scanf("%d%d", &x, &y);
M
if (x > y) M = x; else M = y;
Program :
printf("O valor maior = %d\n", M); return 0; }
Algoritmos e Programação Estruturada if
Selecção de 1-via •
Neste caso, se a expressão lógica tiver resultado false, nenhuma acção é processada dentro da estrutura de selecção.
•
Só é processada uma acção dentro da estrutura de selecção se a expressão lógica for true; daí, o nome de selecção com 1 via.
•
Em C, uma estrutura de selecção com 1 via é a instrução if.
false
?
true
Algoritmos e Programação Estruturada
Exemplo em C: if •
Problem : –
•
Calcular o maior de dois inteiros?
Entradas: –
x, y #include
•
S ídas: –
•
{ int x, y, M; printf(”Introduza x e y: \n”); scanf("%d%d", &x, &y);
M
Program :
M = x; if (y > M) M = y; printf("O valor maior = %d\n", M); return 0; }
Algoritmos e Programação Estruturada switch
Selecção de n-vias •
Neste caso, a decisão não é feita com base numa expressão lógica porque há mais do que 2 resultados possíveis.
•
Também só são processadas a acção ou as acções encontradas numa via.
•
Em C, uma estrutura de selecção com n vias é a instrução switch com break. No entanto, se não usarmos o break, há a possibilidade de executar as acções de várias vias.
...
Algoritmos e Programação Estruturada
Exemplo em C: switch #include
•
Problem : –
•
Calculadora aritmética com as operações básicas?
printf(”Introduza x operador y: \n”); scanf("%d %c %d", &x, &operacao, &y); switch (operacao) { case ‘+’ : resultado break; case ‘-’ : resultado break; case ‘*’ : resultado break; case ‘/’ : resultado }
x, operacao, y
S ídas: –
•
int x, y, resultado; char operacao;
Entradas: –
•
{
resultado
Program :
= x + y; = x - y; = x * y; = x / y;
printf("O resultado = %d\n", resultado); return 0; }
Algoritmos e Programação Estruturada
Repetição com Teste à Cabeça •
Neste caso, também há a necessidade de tomar uma decisão com base no valor lógico duma expressão.
•
No entanto, a mesma acção será executada repetidamente enquanto o resultado da expressão lógica se mantiver verdadeiro (true).
•
O teste (da expressão lógica) precede a acção. Diz-se, por isso, que o teste é à cabeça.
•
O teste é importante porque funciona como uma condição de paragem (a false) dos ciclos or repetições.
•
Em C, uma estrutura de repetição deste tipo é a instrução while.
?
false
true
Algoritmos e Programação Estruturada
Exemplo em C: while •
Problem : –
•
Entradas: –
•
N/A
S ídas: –
•
Calcular a soma dos inteiros no intervalo [1,100]?
soma
#include { int soma, n=1;
Program :
soma = 0; while (n...