C1105 - Introdução à Programação em C
1º Trabalho de Laboratório
Algoritmos, Fluxogramas e Pseudo-Código Objectivo O objectivo deste trabalho é introduzir a noção de algoritmo, bem como duas formas alternativas que podem ser utilizadas para a sua representação.
O que é um Algoritmo? Um algoritmo é um conjunto de passos (ou instruções) bem definido que devem ser executados sequencialmente para levar a cabo uma determinada tarefa. 1. Possui um ponto de entrada (passo inicial) e um ponto de saída (passo final). 2. É composto de passos individuais. 3. Cada passo está bem definido, pode ser executado, e o seu resultado é previsível. 4. Existe um sentido lógico para a execução dos passos (sequência). Depois de executado um determinado passo, a execução prossegue no passo seguinte. 5. Tem de existir um número finito de passos. 6. Quando executado com um conjunto de dados válido um algoritmo termina garantidamente produzindo o resultado esperado.
)Do ponto de vista da forma como decorre o fluxo de execução num algoritmo (qual a
sequência de execução dos passos), pode ser demostrado que qualquer algoritmo de computador pode ser construído com recurso a apenas três tipos de construções: 1. Sequência – Salvo outra indicação, os passos são executados um a seguir ao outro, de cima para baixo. 2. Decisão - Uma forma de decidir entre a execução de duas instruções ou dois conjuntos de instruções. 3. Repetição - Uma forma de repetir a execução de uma dada instrução ou conjunto de instruções. Isto é, qualquer método de representação de algoritmos que permita representar as três noções acima descritas é suficiente para representar qualquer tipo de algoritmo.
)Para além das construções relacionadas com o controlo da execução, para que seja possível
representar qualquer algoritmo num computador, o método de representação tem ainda de ser capaz de: 1. Ler e escrever valores. 2. Realizar as 4 operações aritméticas básicas 3. Fornecer uma forma de definir quantidades (variáveis) capazes de armazenar valores. 4. Permitir a atribuição de valores a variáveis. Como é evidente existem inúmeras maneiras de expressar estes conceitos numa quantidade de linguagens de programação diferentes. E, por outro lado, existem muitas outras coisas que são incluídas nessas linguagens para as tornar mais úteis.
LNo entanto, em termos de conceitos básicos, os acima indicados são tudo o que precisa saber! Aliás, qualquer que seja o método de representação que utilizemos para escrever um algoritmo, caso este se destine a ser implementado com um computador, temos de ter em atenção que o conjunto de operações elementares que este é capaz de realizar é bastante restrito e composto por pouco mais do que as operações acima descritas.
O que é um Fluxograma? Um fluxograma não é mais do que uma representação esquemática de um algoritmo. A figura seguinte ilustra um fluxograma que representa um algoritmo hipotético composto por três passos. O início e o fim do algoritmo são representados por ovais, e cada passo da sequência que constitui o algoritmo é representado por um rectângulo. A sequência pela qual os passos são executados é indicada por linhas e setas. 2º Semestre 2006/2007 1/4
C1105 - Introdução à Programação em C
1º Trabalho de Laboratório Início
Passo 1
Passo 2
Passo 3
Fim
O que é o Pseudocódigo? O pseudocódigo não é mais do que uma outra forma de expressar um algoritmo. Enquanto as linguagens de programação o fazem de um modo formal, o pseudocódigo permite fazê-lo de um modo mais informal, sem a preocupação de obedecer a um léxico e a uma gramática rígida. No entanto, apesar desta liberdade, dois programadores distintos devem ser capazes de estar de acordo quanto a um dado algoritmo escrito em pseudocódigo e ser capazes de escrever dois programas funcionalmente equivalentes, mesmo em linguagens de programação distintas. O pseudocódigo pode ser escrito em qualquer linguagem natural (humana) na forma de uma lista ordenada (ou numerada) de passos. O algoritmo acima descrito na forma de um fluxograma pode ser escrito em pseudocódigo como: Início Passo 1 Passo 2 Passo 3 Fim Onde se admite a convenção habitual nas linguagens naturais de ler de cima para baixo.
Controlo da Execução - Decisões Uma instrução de decisão, também designada por instrução condicional ou instrução de selecção, permite tomar uma decisão quanto ao fluxo de execução entre dois (ou mais) caminhos de execução distintos, dependendo da resposta a uma pergunta (condição) que é colocada. Em pseudocódigo pode ser representada da seguinte forma: Se (condição for verdadeira)
Caso Contrário < acção a executar se condição falsa> Fim Se Podemos, evidentemente fazer o mesmo com um fluxograma:
V Acção a executar se condição verdadeira
Condição?
F Acção a executar se condição falsa
Note que introduzimos uma nova forma, um losango, para representar o local onde se toma a decisão entre dois caminhos de execução. Note que uma instrução de decisão caracteriza-se por possuir apenas um caminho a entrar e dois a sair. Apenas uma das acções pode ser executada. 2º Semestre 2006/2007
2/4
C1105 - Introdução à Programação em C
1º Trabalho de Laboratório
Controlo da Execução - Repetições O ingrediente final necessário é a capacidade para realizar a repetição de uma ou várias instruções. A repetição pode ser por um determinado número de vezes ou enquanto uma determinada condição for verdadeira (p.e.: Enquanto houver degraus, subir.). Por uma questão de generalidade vamos considerar esta última. Em pseudocódigo pode ser representada da seguinte forma: Enquanto (condição verdadeira) Fim Enquanto Com recurso a um fluxograma teremos:
Condição?
F
V Acção a executar se condição verdadeira
Exercícios Exercício 1 O pseudocódigo seguinte permite calcular as soluções para uma equação de segundo grau com coeficientes reais A, B e C. Represente o mesmo algoritmo recorrendo a um fluxograma. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23.
INÍCIO Cálculo das raízes de uma equação de 2º grau SE (B2 − 4AC < 0) ESCREVER (Não há solução porque B2− 4AC < 0) CASO CONTRÀRIO (isto é, se B2 − 4AC ≥ 0) SE (A ≠ 0) SE (B2 − 4AC = 0) x = −B/(2A) ESCREVER (Uma solução: x, porque B2 − 4AC = 0) CASO CONTRÁRIO (isto é, se B2 − 4AC > 0) x1 = (−B + √B2 − 4AC)/(2A) x2 = (−B − √B2 − 4AC)/(2A) ESCREVER (Duas soluções: x1 e x2) FIM DO SE CASO CONTRÁRIO (isto é, se A = 0) SE (B ≠ 0) x = −C/B ESCREVER (Apenas uma solução x, porque A = 0) CASO CONTRÁRIO (isto é, se B = 0) ESCREVER (Não há soluções porque A = 0 e B = 0) FIM DO SE FIM DO SE FIM DO SE FIM DO ALGORITMO
LNote a importância da indentação como forma de indicar visualmente, por exemplo, que o passo
3, está dependente do “SE”, e que os passos do 5 ao 21 estão dependentes do “CASO CONTRÁRIO”.
Exercício 2 Vejamos com podemos resolver um problema simples como o seguinte: Enunciado: Calcule a soma dos inteiros positivos entre 1 e N. 2º Semestre 2006/2007
3/4
C1105 - Introdução à Programação em C Início
Ler N
S=1
S=2
··· S=N
Escrever N
Fim
1º Trabalho de Laboratório
Uma solução evidente poderia ser a indicada no fluxograma 1.
INÍCIO
O problema é que para cada valor de N, teríamos de escrever um algoritmo diferente (repare nas reticências!).
I = 1, S = 1
Para N = 5, o algoritmo tem um total de 9 passos, para N = 500, tem 504 passos e para N igual a 5000 tem 5004 passos! Gostaria de fazer esse fluxograma? Uma melhor solução é a representada no fluxograma 2.
NÃO
Escreva esse algoritmo em pseudocódigo. Como curiosidade, e para que perceba a importância da fase de concepção de um algoritmo, fique a saber que Karl Friedrich Gauss (1777–1855) descobriu que S pode ser obtido matematicamente recorrendo à seguinte equação: S = N × (N + 1) / 2. (Consegue descobrir porquê?)
SIM Escrever S FIM
Fluxograma 2
Fluxograma 1
Exercício 3 O pseudocódigo seguinte permite calcular P = Kn e deve-se ao matemático árabe Al-Kashi que o descobriu em 1414. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13.
INÍCIO Cálculo de P = Kn P = 1 ENQUANTO (N ≥ 1 ) SE (N é PAR) N = N/2 k = k × k CASO CONTRÁRIO (isto é se N é impar) N = N - 1 P = P × k FIM DO SE FIM ENQUANTO ESCREVER (P) FIM DO ALGORITMO
Seria este o “seu” algoritmo? Como é evidente pode escrever uma solução semelhante ao fluxograma 2 do exercício anterior, percorrendo todos os possíveis valores de N. Escreva o pseudocódigo e desenhe o fluxograma deste algoritmo. Compare-o com o algoritmo apresentado. Qual é mais eficiente? Isto é, qual é mais rápido (executa menos passos)?
Entrega do trabalho A entrega do trabalho deve ser feita até às 24:00 da véspera do dia da próxima aula prática. Os três exercícios deverão ser entregues num documento Word, chamado IPLAB1.doc, no qual é também colocado o fluxograma pedido. Note que pode fazer os fluxogramas com o programa Visio, mas depois deve fazer Copy&Paste para os colocar no documento Word. O documento deve ser depois anexado a uma mensagem cujo ASSUNTO deve ser IPLAB1 e enviada para o endereço de correio electrónico indicado pelo professor. O corpo da mensagem deve incluir os nomes, os elementos do grupo. Exemplo:
números, a turma o turno e o curso dos
Para: [email protected] Assunto: IPLAB1 João Manuel Silva, nº123456 - 1T1 Eng. Electrotécnica Francisco Costa Lino, nº 454332 - 1P1 Eng. Industrial Turno PL4
2º Semestre 2006/2007
4/4
