1+-+Algoritmos,+Fluxogramas+e+Pseudocódigo

C1105 - Introdução à Programação em C 1º Trabalho de Laboratório

2º Semestre 2006/2007 1/4

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.

No 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.


Início

Passo 1

Passo 2

Passo 3

2º Semestre 2006/2007 2/4

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) <acção a executar se condição verdadeira> Caso Contrário < acção a executar se condição falsa> Fim Se

Podemos, evidentemente fazer o mesmo com um fluxograma:

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.

Condição? V F

Acção a executar se condição falsa

Acção a executar se condição verdadeira


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) <acção se condição verdadeira> Fim Enquanto

Com recurso a um fluxograma teremos:

FCondição?

Acção a executar se condição verdadeira

V

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. INÍCIO Cálculo das raízes de uma equação de 2º grau 2. SE (B2 − 4AC < 0) 3. ESCREVER (Não há solução porque B2− 4AC < 0) 4. CASO CONTRÀRIO (isto é, se B2 − 4AC ≥ 0) 5. SE (A ≠ 0) 6. SE (B2 − 4AC = 0) 7. x = −B/(2A) 8. ESCREVER (Uma solução: x, porque B2 − 4AC = 0) 9. CASO CONTRÁRIO (isto é, se B2 − 4AC > 0) 10. x1 = (−B + √B2 − 4AC)/(2A) 11. x2 = (−B − √B2 − 4AC)/(2A) 12. ESCREVER (Duas soluções: x1 e x2) 13. FIM DO SE 14. CASO CONTRÁRIO (isto é, se A = 0) 15. SE (B ≠ 0) 16. x = −C/B 17. ESCREVER (Apenas uma solução x, porque A = 0) 18. CASO CONTRÁRIO (isto é, se B = 0) 19. ESCREVER (Não há soluções porque A = 0 e B = 0) 20. FIM DO SE 21. FIM DO SE 22. FIM DO SE 23. FIM DO ALGORITMO

Note 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


Uma solução evidente poderia ser a indicada no fluxograma 1.

2º Semestre 200

O problema é que para cada valor de N, teríamos de escrevealgoritmo diferente (repare nas reticências!).

r um

sos! Gostaria de fazer

representada no fluxograma 2.

importância da fase de ue Karl Friedrich Gauss

xercício 3 guinte permite calcular P = Kn e deve-se ao matemático árabe Al-Kashi que o .

é PAR)

(isto é se N é impar)

MO

mo? Como é evidente pode escrever uma solução semelhante ao or, percorrendo todos os possíveis valores de N. Escreva o

feita até às 24:00 da véspera do dia da próxima aula prática.

ual é grama

Início

Fim

S = 1

Escrever N

Ler N

S = 2

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 pasesse fluxograma? Uma melhor solução é a

Escreva esse algoritmo em pseudocódigo.

Como curiosidade, e para que perceba a concepção de um algoritmo, fique a saber q

S = N

(1777–1855) descobriu que S pode ser obtido matematicamente recorrendo à seguinte equação: S = N × (N + 1) / 2. (Consegue descobrir porquê?)

···

INÍCIO

I = 1, S = 1

Escrever S

FIM

F 1

SIM

NÃO

EO pseudocódigo sedescobriu em 1414

1. INÍCIO Cálculo de P = Kn

2. P = 1 3. ENQUANTO (N ≥ 1 ) 4. SE (N 5. N = N/2 6. k = k × k 7. CASO CONTRÁRIO8. N = N - 1 9. P = P × k 10. FIM DO SE 11. FIM ENQUANTO 12. ESCREVER (P) 13. FIM DO ALGORIT

Seria este o “seu” algoritfluxograma 2 do exercício anteripseudocó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

Os três exercícios deverão ser entregues num documento Word, chamado IPLAB1.doc, no qtambém colocado o fluxograma pedido. Note que pode fazer os fluxogramas com o proVisio, 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 números, a turma o turno e o curso dos elementos do grupo.

Exemplo:

Para: [email protected]: IPLAB1

, nº123456 - 1T1 Eng. Electrotécnica rancisco Costa Lino, nº 454332 - 1P1 Eng. Industrial

João Manuel SilvaF

Turno PL4

luxograma

6/2007

Fluxograma 2

4/4

Documents

1+-+Algoritmos,+Fluxogramas+e+Pseudocódigo